Programmer Humor

19817 readers

44 users here now

Welcome to Programmer Humor!

This is a place where you can post jokes, memes, humor, etc. related to programming!

For sharing awful code theres also Programming Horror.

Rules

Keep content in english
No advertisements
Posts must be related to programming or programmer topics

founded 2 years ago

MODERATORS

[email protected]

823

That Nim Flashbacks (sh.itjust.works)

submitted 7 months ago by [email protected] to c/[email protected]

56 comments fedilink hide all child comments

you are viewing a single comment's thread
view the rest of the comments

[–] [email protected] 7 points 7 months ago (1 children)

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.

[–] [email protected] 1 points 7 months ago* (last edited 7 months ago)

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.