142 lines
No EOL
4.1 KiB
C
142 lines
No EOL
4.1 KiB
C
/*----------------------------------------------------------
|
|
* HTBLA-Leonding / Class: 2IHIF
|
|
* ---------------------------------------------------------
|
|
* Exercise Number: 09
|
|
* Title: Tower of Hanoi Disk ADT implementation
|
|
* Author: Marc Tismonar
|
|
* ----------------------------------------------------------
|
|
* Description:
|
|
* Implementation of toh_board.h.
|
|
* ----------------------------------------------------------
|
|
*/
|
|
|
|
/* Includes, definitions and instanciations */
|
|
#include "toh_board.h"
|
|
#include "config.h"
|
|
#include "toh_disk.h"
|
|
#include "toh_board.h"
|
|
#include "toh_visualizer.h"
|
|
|
|
/* ========================================================= */
|
|
/* Private functions */
|
|
|
|
static int moveCount = 0;
|
|
|
|
/**
|
|
* Moves a single disk from the top of the 'source' rod to the 'target' rod.
|
|
* The move shall only be performed if it is allowed.
|
|
*
|
|
* @param source The rod from which the disk shall be moved.
|
|
* @param target The rod to which the disk shall be moved.
|
|
* @return True if the move was successful and according to the rules, false otherwise.
|
|
*/
|
|
static bool ts_move_disk(RodName source, RodName target) {
|
|
TohBoard board = tb_get_board();
|
|
if (!tb_is_valid(board)) {
|
|
return false;
|
|
}
|
|
|
|
Disk disk = tb_pop_disk(board, source);
|
|
|
|
if (!td_is_valid(disk)) {
|
|
return false;
|
|
}
|
|
bool success = tb_push_disk(tb_get_board(), target, disk);
|
|
|
|
if (success) {
|
|
moveCount++;
|
|
toh_visualize(tb_get_board(), moveCount);
|
|
}
|
|
|
|
return success;
|
|
}
|
|
|
|
/**
|
|
* Moves a stack of disks of the given size form the 'source' rod to the 'target' rod
|
|
* using the 'intermediate' rod as intermediate disk buffer.
|
|
* The move shall only be performed if it is valid. The move is valid, if each
|
|
* move of affected disks is allowed.
|
|
*
|
|
* @param size The size of the disk stack to move.
|
|
* @param source The rod from which the disks shall be moved.
|
|
* @param intermediate The rod that serves as intermediate buffer for the disks.
|
|
* @param target The rod to which the disks shall be moved.
|
|
* @return True if the move was successful and according to the rules, false otherwise.
|
|
*/
|
|
static bool ts_move_stack(unsigned short size, RodName source, RodName intermediate, RodName target) {
|
|
if (size == 1) {
|
|
return ts_move_disk(source, target);
|
|
}
|
|
|
|
if (!ts_move_stack(size - 1, source, target, intermediate)) {
|
|
return false;
|
|
}
|
|
|
|
if (!ts_move_disk(source, target)) {
|
|
return false;
|
|
}
|
|
|
|
return ts_move_stack(size - 1, intermediate, source, target);
|
|
}
|
|
|
|
static unsigned short ts_get_used_disks(RodName rod) {
|
|
TohBoard board = tb_get_board();
|
|
if (!tb_is_valid(board)) {
|
|
return 0;
|
|
}
|
|
|
|
unsigned short count = 0;
|
|
for (unsigned short i = 0; i < MAX_DISKS; i++) {
|
|
Disk disk = tb_get_disk(board, rod, i);
|
|
if (td_is_valid(disk)) {
|
|
count++;
|
|
}
|
|
}
|
|
|
|
return count;
|
|
}
|
|
|
|
/* ========================================================= */
|
|
/* Public functions */
|
|
|
|
/**
|
|
* Initials a 'Tower of Hanoi' board with the given number of disks.
|
|
* To initialize the board, all reqired disks are placed on the left rod
|
|
* in ascending order of their size, the smallest disk at the top.
|
|
* The middle and right rod are empty.
|
|
*
|
|
* All disks are initialized accordingly.
|
|
*
|
|
* @param disk_count The number of disks to use. Must be less than 'MAX_DISKS'.
|
|
*/
|
|
void ts_init(unsigned short disk_count) {
|
|
if(disk_count < 1 || disk_count > MAX_DISKS) {
|
|
return;
|
|
}
|
|
|
|
TohBoard board = tb_get_board();
|
|
tb_clear_board(board);
|
|
|
|
for (unsigned short i = disk_count; i > 0; i--) {
|
|
Disk disk = td_get_disk(i);
|
|
tb_push_disk(board, LEFT, disk);
|
|
}
|
|
|
|
moveCount = 0;
|
|
toh_init_visualizer(disk_count);
|
|
}
|
|
|
|
/**
|
|
* Solves the puzzle by moving all disks from the left rod to the right rod.
|
|
* In fact, this is the only function needed to 'play' the game after the
|
|
* board was initialized.
|
|
*
|
|
*/
|
|
void ts_solve() {
|
|
TohBoard board = tb_get_board();
|
|
if (!tb_is_valid(board)) {
|
|
return;
|
|
}
|
|
|
|
ts_move_stack(ts_get_used_disks(LEFT), LEFT, MIDDLE, RIGHT);
|
|
} |