Programmer Humor

19207 readers

982 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 1 year ago

MODERATORS

Feyter@programming.dev

anzo@programming.dev

BurningTurtle@programming.dev

814

That Nim Flashbacks (sh.itjust.works)

submitted 4 months ago by pastermil@sh.itjust.works to c/programmer_humor@programming.dev

50 comments fedilink hide all child comments

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

[–] akash_rawal@lemmy.world 7 points 4 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.

[–] CanadaPlus@lemmy.sdf.org 1 points 4 months ago* (last edited 4 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.