• akash_rawal@lemmy.world
    link
    fedilink
    arrow-up
    19
    ·
    6 months ago

    Replacing “Programmers:” with “Program:” is more accurate.

    spoiler

    Tower of Hanoi is actually easy to write program for. Executing it on the other hand…

    • CanadaPlus@lemmy.sdf.org
      link
      fedilink
      arrow-up
      10
      ·
      6 months ago

      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
        link
        fedilink
        arrow-up
        7
        ·
        6 months ago

        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
          link
          fedilink
          arrow-up
          2
          arrow-down
          1
          ·
          edit-2
          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.