`hanoi.raku`

Towers of Hanoi.

Towers of Hanoi, the canonical recursion demo: to move N disks, move the top N-1 aside, move the biggest disk, then move the N-1 back on top. It prints the full sequence of moves for a 4-disk stack and checks that the total matches the provably-minimal 2^N - 1.

The program

Edit it and press Run — it executes in your browser.

#!/usr/bin/env raku
# Towers of Hanoi: move a stack of N disks from one peg to another, never
# placing a larger disk on a smaller one. The recursive insight is tiny --
# to move N disks, move the top N-1 out of the way, move the biggest, then
# move the N-1 back on top. Shows recursion and a running move counter.

my $moves = 0;

sub hanoi($n, $from, $to, $via) {
    return if $n == 0;
    # Move the top n-1 disks off onto the spare peg.
    hanoi($n - 1, $from, $via, $to);
    # Move the largest remaining disk to its destination.
    $moves++;
    say "  move {$moves.fmt('%2d')}: disk $n   $from -> $to";
    # Bring the n-1 disks back on top.
    hanoi($n - 1, $via, $to, $from);
}

my $disks = 4;
say "Towers of Hanoi with $disks disks:";
say '';
hanoi($disks, 'A', 'C', 'B');

say '';
say "Solved in $moves moves.";
# A stack of N disks always takes exactly 2^N - 1 moves -- the minimum.
say "Minimum for $disks disks is 2^$disks - 1 = {2 ** $disks - 1}.";
say 'Optimal? ', $moves == 2 ** $disks - 1;

Open in the playground ↗ Source on GitHub ↗

Output

Towers of Hanoi with 4 disks:

  move  1: disk 1   A -> B
  move  2: disk 2   A -> C
  move  3: disk 1   B -> C
  move  4: disk 3   A -> B
  move  5: disk 1   C -> A
  move  6: disk 2   C -> B
  move  7: disk 1   A -> B
  move  8: disk 4   A -> C
  move  9: disk 1   B -> C
  move 10: disk 2   B -> A
  move 11: disk 1   C -> A
  move 12: disk 3   B -> C
  move 13: disk 1   A -> B
  move 14: disk 2   A -> C
  move 15: disk 1   B -> C

Solved in 15 moves.
Minimum for 4 disks is 2^4 - 1 = 15.
Optimal? True

Feature focus: recursion, formatted output.