I have some code rotting somewhere in a repository where I was doing several moves to organise some stuff.
Ages after I wrote I realised it was basically this problem and a standard algorithm could apply.
Adding a cache is the elegant solution here.
A child of five would understand this. Fetch me a child of five.
—Groucho Marx
Caxhe poisoned. By the time next child of 5 is brought, child turns 65 years old
Actually one of my most favorite memories because the simplicity of the solution using recursion blew my little mind. It was like discovering a magic spell.
To me it was an example that there are some problems only solved by recursion but that they also overblown in their relevancy
I remember learning recursion twice: once for Fibonacci and once for Hanoi. It did take a while to click but it unlocked recursion schemes and dynamic programming.
The Tower of Hanoi is just a game for children?
I don’t think most people would manage the optimal solution first go (1023 moves for a 10-piece game).
Most people? 100% not. Me who has probably autism and has internalised the algorithm, I can.
I love and hate my brain.
Do you hear yourself?
Yes. Why?
I thought I was clever, it took me 300 moves with only 8 disks.
Literally just easier to pick up the entire pile and move it over, or rotate the entire game and say Tower #1 is Tower #3 now.
The thing is… not doing it at all, is better than doing those 300 moves. What made you do this? Also a bit spicy?
I was sliding it back and forth as fast as I could, because I didn’t understand the puzzle at first, but then I saw there’s an sorting optimization puzzle and thought that I was clever only to find out it’s tedium.
Halfway through (or so I thought at move 80), I was just curious to see how ridiculously long the puzzle could be, shifting pieces back and forth
So the answer was: I thought the puzzle was easy, and I was humbled, and stubborn.
I solved it and wasted time, and used that time to warn others to not bother with the puzzle
I can respect that. Focused, determined, protective!
I thought it was fun…
Once you have it figured out, just mechanically doing it all correctly for 1023 steps is also annoying.
I did it up to the 511 moves for the 9-pice game on Android once, and according to the stats page that took me 6 min 18 seconds. The 10-piece version does not have a time, so I think I gave up :-)
Determining the correct algorithm is a game for children
Radix ftw!
Source tower has odd disks? Move top piece to destination tower. Otherwise, move it to the top of the off tower. Always move the largest disk you can that wasn’t placed in your previous move.
These instructions seem incomplete.
Consider a tower of three, moving from the left to right:
321 / - / -
32 / - / 1
3 / 2 / 1
Next, 1 should be moved to the center position on top of two for the optimal solution, but your ruleset has no indicator of which choice should be made.
You’re right, how can we simplify that into a usable insite?
Prioritize erecting “neat” towers then moving the largest disk not placed in the previous step?
For each tower of size N, move tower (N - 1) to the non-target position, then move the base to the target position, then move the previously moved tower of size (N - 1) to the target position.