tower of hanoi (cs assignment stuff)

this isn't gonna be a normal editorial
my cs teacher assigned us to write a blog post
and in a pure coincendence, i've just been developing this blog site
so might as well write it here

so.
tower of hanoi.
too lazy to explain it, so here's the description copied right from the wikipedia page

The Tower of Hanoi [...] is a mathematical game or puzzle consisting of three rods and a number of disks of various diameters, which can slide onto any rod. The puzzle begins with the disks stacked on one rod in order of decreasing size, the smallest at the top, thus approximating a conical shape. The objective of the puzzle is to move the entire stack to the last rod, obeying the following rules:

1. Only one disk may be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
3. No disk may be placed on top of a disk that is smaller than it.

so yeah i just have to make a solver for this (in java bc it's ap cs)

it's a good thing my wonderful cs teacher mr. jan gave a really good hint
first, let's just define the disks as A, B, and C (with all the disks starting on A)
second, we just have a move be `X -> Y`, where we move a disk from X to Y
now let's list out some simple solutions for 1 disk to 4 disks

it's a bit hard to notice, but there are three key observations to make here:

1. for `n` disks, there's \(2^n-1\) moves ALWAYS.
2. the middle move is always `A -> C`
3. this is the big one: the top half & bottom half of each solution is a transformation of the previous solution

what do i mean by the third point? well, if you squint real hard, you can see that the top part of each solution (the part before the `A -> C`) is a sort of "mapping" of the previous solution

`A -> B` gets transformed to `A -> C`, `B -> C` gets transformed to `C -> B`, and there's a bunch of other rules that i could go over
similar rules apply for the bottom part, it's just mixed around a bit

this basically solves the problem!
we just have to recurse all the way to the problem with 1 disk, and then slowly transform our solutions and go from there!

and without further ado, here's the code

and without further ado, here's the code

```java import java.util.Scanner; public class Hanoi { public static void main(String[] args) { // get the # of disks, there's only gonna be 3 places to put them int diskNum = new Scanner(System.in).nextInt(); for (char[] step : hanoi(diskNum)) { System.out.print(step[0]); System.out.print(" -> "); System.out.println(step[1]); } } private static char[][] hanoi(int diskNum) { /* * https://en.wikipedia.org/wiki/Tower_of_Hanoi * the min # of moves to complete the tower is gonna be 2^diskNum - 1 */ char[][] sol = new char[(1 << diskNum) - 1][2]; // the middle move is always gonna be this sol[sol.length / 2] = new char[] {'A', 'C'}; if (diskNum == 1) { return sol; } char[][] prev = hanoi(diskNum - 1); for (int i = 0; i < prev.length; i++) { char[] prevStep = prev[i]; int ind2 = sol.length / 2 + i + 1; if (prevStep[0] == 'A') { sol[i] = new char[] {'A', ternary(prevStep[1] == 'B', 'C', 'B')}; sol[ind2] = new char[] {'B', ternary(prevStep[1] == 'C', 'C', 'A')}; } else if (prevStep[0] == 'B') { sol[i] = new char[] {'C', ternary(prevStep[1] == 'A', 'A', 'B')}; sol[ind2] = new char[] {'A', ternary(prevStep[1] == 'A', 'B', 'C')}; } else if (prevStep[0] == 'C') { sol[i] = new char[] {'B', ternary(prevStep[1] == 'B', 'C', 'A')}; sol[ind2] = new char[] {'C', ternary(prevStep[1] == 'A', 'B', 'A')}; } } return sol; } // i'd use the built-in ternary but we can't use anything we haven't learned private static char ternary(boolean cond, char yes, char no) { if (cond) { return yes; } return no; } } ```