9
\$\begingroup\$

Here is my solution to the Tower of Hanoi problem using Python


def helper(number_rings: int, origin: int, target: int, spare: int, list_result=[])->list:
    """Helper function works out which ring to move"""
    if number_rings == 1:
        list_result.append([origin, target])
    else:
        #Move all but 1 ring from ORIGIN tower to SPARE tower
        helper(number_rings - 1, origin=origin, target=spare, spare=target)
        #MOVE the last ring from ORIGIN tower to TARGET tower
        helper(1, origin=origin, target=target, spare=spare)
        #MOVE the remaining rings from the SPARE tower to TARGET tower
        helper(number_rings - 1, origin=spare, target=target, spare=origin)
        return list_result


def move_rings(number_rings: int)->int:
    """Function prints the ring move required"""
    dict_rings = {0: "A", 1: "B", 2: "C"}
    if number_rings == 1:
        print("Move from A to C")
        return 1
    list_result = helper(number_rings, 0, 2, 1)
    for item in list_result:
        print("Move from", dict_rings[item[0]], "to", dict_rings[item[1]])
    return len(list_result)


if __name__ == "__main__":
    counter = move_rings(1)
    print(f"Solution possible in {counter} moves")

\$\endgroup\$
  • \$\begingroup\$ So.... what is the question ? \$\endgroup\$ – Gloweye Sep 11 at 12:00
  • \$\begingroup\$ @Jacco - the question is (as always), "How could I make this code better?" \$\endgroup\$ – Toby Speight Sep 16 at 14:07
3
\$\begingroup\$

Overall your implementation is fine, I would just suggest a few things:

  1. Naming - move_rings and helper are not very descriptive. Give them better names, and give them good docstrings (I like NumpyDoc, but personal preference is fine)
  2. move_rings shouldn't both do calculations and print to stdout. Instead, move_rings should return the information, and the caller should decide what to do with it
  3. move_rings doesn't need the number_rings == 1 special case; your API handles it just fine
  4. Instead of the hard-coded number approach, you can make a little Peg class that makes things a bit cleaner - subclassing namedtuple is a nice way to do this
  5. Using f-strings makes printing easier
  6. You can yield from instead of appending to the default argument list, which is easier to read and doesn't waste time reallocating space for the list
  7. I added a (honestly pretty bad) visualization function to see the movements as well.

This is what I came up with (didn't do all of the things I mentioned above)

from math import ceil
from collections import defaultdict, namedtuple
from typing import Iterable, Generator, List, Tuple


class Peg(namedtuple("Peg", "id name")):
    pass


SOURCE_PEG = Peg(0, "A")
TARGET_PEG = Peg(2, "C")
WORKER_PEG = Peg(1, "B")
PEGS = [SOURCE_PEG, TARGET_PEG, WORKER_PEG]


def helper(
    number_rings: int, origin: Peg, target: Peg, spare: Peg
) -> Generator[Tuple[Peg, Peg], None, None]:
    """
    Helper function for performing the recursive call when solving the tower puzzle.

    Parameters
    ----------
    number_rings : int
        Number of rings in the puzzle
    origin : Peg
        The peg that we're moving from
    target : Peg
        The peg that we want to move to
    spare : Peg
        The other peg, that we can use as a helper

    Yields
    ------
    move : tuple
        The movement(s) (from-Peg, to-Peg) we determined were ncessary
    """

    if number_rings == 1:
        yield (origin, target)
    else:
        # Move all but 1 ring from ORIGIN tower to SPARE tower
        yield from helper(
            number_rings - 1,
            origin=origin,
            target=spare,
            spare=target,
        )
        # MOVE the last ring from ORIGIN tower to TARGET tower
        yield from helper(
            1, origin=origin, target=target, spare=spare
        )
        # MOVE the remaining rings from the SPARE tower to TARGET tower
        yield from helper(
            number_rings - 1,
            origin=spare,
            target=target,
            spare=origin,
        )

def move_rings(
    number_rings: int
) -> Iterable[Tuple[Peg, Peg]]:
    """
    Finds the optimal number of moves when solving a Tower of Hanoi puzzle
    with `number_rings` rings, starting on the first ring.

    Parameters
    ----------
    number_rings : int
        The number of rings in the Tower of Hanoi puzzle

    Returns
    -------
    move_list : iterator
        An iterable of the Peg movements
    """

    return helper(
        number_rings, SOURCE_PEG, TARGET_PEG, WORKER_PEG
    )


def draw_tower_of_hanoi(ring_map: List[int]):
    """
    Pretty dumb drawing tool that visualizes current peg state.

    Parameters
    ----------
    ring_map : list
        List of rings and their pegs. Format for a 3-ring puzzle start would be
        [0, 0, 0]. The index represents ring size (size = i+1), and the value at
        that index represents the peg (0, 1, or 2).
    """

    largest_ring = len(ring_map)
    peg_to_ring = defaultdict(list)
    for ring, peg in enumerate(ring_map, 1):
        peg_to_ring[peg].append(ring)

    peg_to_ring = {
        peg: sorted(ring_list, reverse=True)
        for peg, ring_list in peg_to_ring.items()
    }
    height_per_ring = {
        peg: len(ring_list)
        for peg, ring_list in peg_to_ring.items()
    }

    total_width = largest_ring * 6 + 7
    total_height = len(ring_map) + 2

    peg_centers = [
        1 + largest_ring,
        3 + largest_ring * 3,
        5 + largest_ring * 5,
    ]

    # fill it out
    drawing = [
        [" " for _ in range(total_width)]
        for _ in range(total_height)
    ]

    # Draw the pegs
    for i, row in enumerate(drawing):
        for center in peg_centers:
            drawing[i][center] = "P"

    # Draw the base
    drawing[-1][:] = ["G"] * total_width

    # Draw the rings
    for peg in peg_to_ring:
        for i, ring in enumerate(peg_to_ring[peg], 2):
            index = -i
            center = peg_centers[peg]
            drawing[index][center - ring : center] = [
                "R"
            ] * ring
            drawing[index][
                center + 1 : center + ring + 1
            ] = ["R"] * ring

    print("\r\n".join(["".join(row) for row in drawing]))



def visualize_tower_movements(
    number_rings: int, moves: Iterable[Tuple[Peg, Peg]]
):
    """
    Visualization tool for drawing the movement of rings in a Tower of Hanoi puzzle.

    Parameters
    ----------
    number_rings : int
        The number of rings in the puzzle
    moves : iterable
        The set of moves performed while working on the puzzle
    """

    visualizer = [0] * number_rings
    draw_tower_of_hanoi(visualizer)
    for move_from, move_to in moves:
        # Get the smallest ring on the peg, as that is the only one that can move
        move_from_index = min(
            ring
            for ring, value in enumerate(visualizer)
            if value == move_from.id
        )
        visualizer[move_from_index] = move_to.id
        draw_tower_of_hanoi(visualizer)



if __name__ == "__main__":
    moves = list(move_rings(5))
    print(f"Took {len(moves)} moves")
    for move_from, move_to in moves:
        print(
            f"Move from {move_from.name} to {move_to.name}"
        )
    visualize_tower_movements(5, moves)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.