I didn’t have to program this, thankfully. The code was used as an example of recursion but the explanation was lacking so I ended up writing out each frame by end until I understood it. Took a few pages and a couple of hours.
I am grateful that I learned what I did going through it but I’d rather not do it again.
Fuck all programming puzzles. I refuse them.
True hommies hate them too.
Nah Hanoi was easy stuff, first year. Definitely more traumatizing practice problems.
Hanoi […] practice problems.
Like you come to the exam and there’s a 64 piece Tower of Hanoi you need to solve manually to pass the exam
Assuming 1 second per swap, a 64 disk tower of hanoi would take 585 billion years to solve - it has 2^64 -1 swaps.
And that makes It good enough for an exam
God I can’t remember how to do this something about moving tower a to spare pin recursively.
I like recursive functions tho
Yet I have not met a CS grad without a trauma.
I have a production bug… it only happens on Saturdays ever our ops folks have no idea - this can be replicated on a test server that gets no traffic.
Saturday why!
If we reject the theory that it could be someone’s elaborate revenge, Saturday may be the first day of the week that may become workday or non-workday because of incorrect assumption about the first day of the week. If everywhere but one place in your software the day numeration is correct it would be a hard bug to spot.
Also, if it is in Java, I vaguely remember there being a lot of ways to express weekday, so a lot of ways to shoot off your foot (solely on Saturday)
For bonus points, this failure is in a cron job that sends out recently queued messages. It runs once every ten minutes - last weekend we had 12 failures: four were in a cluster on their own, one was in a run of two, and six were in a single continuous run.
Please note that this server is unused by our business so no messages ever get naturally queued. Every day we sync the live production server to this server at about 9 PM - assuming an employee was queuing up a message before the snapshot is taken there might be a number of unsent messages in the snapshot - those messages will all be sent by the first cron job after the sync.
It is a wonderfully awful problem that has me wanting to pull out my luscious locks.
I wish you luck. Also, maybe you could get someone else to get a fresh view of an issue
I’ve always hated recursion. It’s always seemed like a cutesy programming trick that’s not reliable in all conditions.
You could blow the stack in an edge case that you didn’t think of. So it should never be a standard pattern. It’s only good if you need to rewrite something for optimization and recursion is appropriate. But in many cases recursion is slower.
“Look at what I can do in 5 lines of code!” is for programming contests, not for anything important.
Is this a hard problem to solve? I’ve not attempted it yet myself.
I seem to remember this was a problem in Advent of Code one year?
I’m imagining there are plenty of algorithms to solve this already, right? With varying numbers of towers and plates? A general solution for solvable amounts of each? Maybe?
Towers of Hanoi? I don’t think so.
Lettme introduce you to ackermann’s function:
int ack(int m, int n) { if (m == 0) { return n+1; } else if((m > 0) && (n == 0)){ return ack(m-1, 1); } else if((m > 0) && (n > 0)) { return ack(m-1, ack(m, n-1)); } }You won’t run out of stackoverflows any time soon.
Replacing “Programmers:” with “Program:” is more accurate.
spoiler
Tower of Hanoi is actually easy to write program for. Executing it on the other hand…
It’d be a trick if you didn’t already know the answer. Or at least, it would be for me. It’s also hard to actually visualise.
I didn’t know the answer either, but usually you can compose solution from solutions of smaller problems.
solution(0): There are no disks. Nothing to do. solution(n): Let’s see if I can use solution(n-1) here. I’ll use solution(n-1) to move all but last disk A->B, just need to rename the pins. Then move the largest disk A->C. Then use solution(n-1) to move disks B->C by renaming the pins. There we go, we have a stack based solution running in exponential time.
It’s one of the easiest problem in algorithm design, but running the solution by hand would give you a PTSD.
Good for you. I think I’d figure it out eventually, but it would certainly take me a while.
I’d probably be trying a number of approaches, including the recursive one. Renaming pegs is a critical piece that you’d have to realise you can do, and you can’t be sure you have a correct inductive solution unless you actually walk through the first few solutions from the base instance.
