#include <stdio.h>
#include <stdlib.h>

int count = 0;

void hanoi(int blocks[], int i, int goal) {
	int rest;
	if (i == 0){
		printf("%d: %d -> %d\n", i, blocks[i], goal);
		blocks[i] = goal;
		count++;
	}
	else if (blocks[i - 1] == blocks[i]){
		rest = 3 - blocks[i] - goal;
		hanoi(blocks, i - 1, rest);
		hanoi(blocks, i, goal);
		hanoi(blocks, i - 1, goal);
	}
	else{
		printf("%d: %d -> %d\n", i, blocks[i], goal);
		blocks[i] = goal;
		count++;
	}
}

void main() {
	int numBlocks=0, j;
	int *blocks = NULL;
	while (1){
		printf("Enter the number of blocks: ");
		if (scanf_s("%d", &numBlocks) == 0 || numBlocks < 3){
			fflush(stdin);
			puts("You must input an integer n >= 3");
			continue;
		}

		count = 0;
		if (blocks != NULL) free(blocks);
		blocks = (int*)malloc(sizeof(int) * numBlocks);
		for (j = 0; j < numBlocks; j++) blocks[j] = 0;
		hanoi(blocks, numBlocks - 1, 2);
		printf("move count: %d\n", count);
	}
}