this post was submitted on 05 May 2024
823 points (99.0% liked)

Programmer Humor

19623 readers
4 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

founded 1 year ago
MODERATORS
Feyter@programming.dev
anzo@programming.dev
BurningTurtle@programming.dev
pylapp@programming.dev
823
That Nim Flashbacks (sh.itjust.works)
submitted 6 months ago by pastermil@sh.itjust.works to c/programmer_humor@programming.dev
56 comments fedilink hide all child comments
 
you are viewing a single comment's thread
view the rest of the comments
[–] CanadaPlus@lemmy.sdf.org 10 points 6 months ago (1 children)

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.

[–] akash_rawal@lemmy.world 7 points 6 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 6 months ago* (last edited 6 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.