legend-of-zelda-twilight-princess-puzzle-solver.py

"""
Solution finder for puzzle in Legend of Zelda: Twilight Princess to obtain the Master Sword.

The temple is guarded by a pair of golems. When the player approaches, the ground transforms into a grid of squares.
As the player moves around the board, the golems move in response. The player must maneuver the two golems onto
two specific squares in order to proceed.

This Python script finds a solution in 801 iterations on a breadth-first search of all possible movements.
For some reason, I've annotated how it all works.

If you're just looking for the solution, it's this:
    start -> left -> down -> up -> up -> up -> right -> right -> down -> down -> down -> left -> up
"""

from collections import deque
from typing import NamedTuple, Tuple, Iterable, Optional, Set

# Typedef of an (X, Y) coordinate
XY = Tuple[int, int]


class Movement(NamedTuple):  # I didn't know about @dataclass when I wrote this, so I used NamedTuple
    """
    A cardinal direction that the player can move in.
    """
    name: str
    vector: XY


movements = [
    Movement(name='left', vector=(-1, 0)),
    Movement(name='right', vector=(1, 0)),
    Movement(name='up', vector=(0, -1)),
    Movement(name='down', vector=(0, 1)),
]


class Entity(NamedTuple):
    """
    Uniform data structure for things that can move around the board
    """
    symbol: str
    name: str
    start_position: Tuple[int, int]
    vectorMult: Tuple[int, int] # When the player moves, which direction does this entity actually move? (One golem always faces opposite the player)


# In the first iteration, I put all the entities into a single list.
# But the player has different movement rules than the golems, so the movement code refers to specfic entities
# more often to handling them in a uniform list, so defining them separately makes more sense
player_entity = Entity(symbol='P', name='player', start_position=(2, 3), vectorMult=(1,1))
same_golem_entity = Entity(symbol='S', name='golem_same', start_position=(2, 5), vectorMult=(1,1))
opposite_golem_entity = Entity(symbol='O', name='golem_opposite', start_position=(2, 1), vectorMult=(-1,-1))


# Define the shape of the board using a Set of coordinates as a lookup table
# The board is shaped like a heart; I didn't arbitrarily decide to lay them out like that
valid_squares: Set[XY] = {
    (0,0), (1,0),        (3,0), (4,0),
    (0,1), (1,1), (2,1), (3,1), (4,1),
    (0,2), (1,2), (2,2), (3,2), (4,2),
           (1,3), (2,3), (3,3),
           (1,4), (2,4), (3,4),
                  (2,5),
}


class EntityPositions(NamedTuple):
    """
    Store the positions of each entity.

    The first draft of this program used a Dict instead, but there are very few entities and the movement code
    refers to them specifically, so there was no reason to store them uniformly.

    Basically I never do this sort of thing; this is the exception
    """
    player: XY
    same_golem: XY
    opposite_golem: XY

    def print(self):
        for y in range(6):
            for x in range(5):
                coord: XY = (x, y)
                symbol = ' '
                if coord in valid_squares:
                    symbol = '.'
                    if self.player == coord:
                        symbol = player_entity.symbol
                    elif self.same_golem == coord:
                        symbol = same_golem_entity.symbol
                    elif self.opposite_golem == coord:
                        symbol = opposite_golem_entity.symbol
                print(symbol, end='')
                print(' ', end='')
            print()


class BoardState(NamedTuple):
    """
    Connect the state of a board with the movements taken to get there
    """
    entity_positions: EntityPositions
    movement_seq: Tuple[Movement, ...]

    def print(self):
        print(' -> '.join(('start', *(movement.name for movement in self.movement_seq))))
        self.entity_positions.print()

    def print_full(self):
        print('Full sequence:')
        print('--------------')
        print('Start')
        this_step_positions = start_board.entity_positions
        for i, movement in enumerate(self.movement_seq, start=1):
            this_step_positions.print()
            print(f'Step {i}: {movement.name}')
            this_step_positions = get_new_state_after_movement(this_step_positions, movement)
        print('Final')
        this_step_positions.print()


# Set up the initial state of the simulation
start_board = BoardState(
    entity_positions=EntityPositions(
        player=player_entity.start_position,
        same_golem=same_golem_entity.start_position,
        opposite_golem=opposite_golem_entity.start_position,
    ),
    movement_seq=(),
)

goal_coord_1: XY = (1,1)
goal_coord_2: XY = (3,1)
goal_coords = ((1, 1), (3, 1))


def is_victory(positions: EntityPositions) -> bool:
    """
    Define the goal of the puzzle
    """
    return (
        (positions.opposite_golem == goal_coord_1 and positions.same_golem == goal_coord_2) or
        (positions.same_golem == goal_coord_1 and positions.opposite_golem == goal_coord_2)
    )


def get_entity_position_after_movement(entity: Entity, position: XY, movement: Movement) -> XY:
    """
    Figure out where an entity will try to go in response to a movement
    """
    return (
        position[0] + movement.vector[0] * entity.vectorMult[0],
        position[1] + movement.vector[1] * entity.vectorMult[1]
    )


def get_new_state_after_movement(old_entity_positions: EntityPositions, movement: Movement) -> Optional[EntityPositions]:
    """
    Given the state of the board and a movement, figure out what the new board state will be and whether it's even valid.
    If a movement is invalid, this returns None instead.

    This is the most complicated part of the program because of the weird rules around movement.
    """

    old_player_position = old_entity_positions.player
    old_same_golem_position = old_entity_positions.same_golem
    old_opposite_golem_position = old_entity_positions.opposite_golem

    # The player always moves first
    player_position = get_entity_position_after_movement(player_entity, old_player_position, movement)

    # Player cannot jump off the board or onto an occupied square
    if player_position == old_same_golem_position or player_position == old_opposite_golem_position or player_position not in valid_squares:
        return None

    # Then the golems attempt to move to a new square
    same_golem_position = get_entity_position_after_movement(same_golem_entity, old_same_golem_position, movement)
    opposite_golem_position = get_entity_position_after_movement(opposite_golem_entity, old_opposite_golem_position, movement)

    # If a Golem jumps onto the player's square, the puzzle resets
    if same_golem_position == player_position or opposite_golem_position == player_position:
        return None

    # Golems cannot leave the board; they stay on the same square
    if same_golem_position not in valid_squares:
        same_golem_position = old_same_golem_position
    if opposite_golem_position not in valid_squares:
        opposite_golem_position = old_opposite_golem_position

    # Golems on adjacent tiles that jump into each other return to their original squares
    if same_golem_position == old_opposite_golem_position and opposite_golem_entity == old_same_golem_position:
        same_golem_position = old_same_golem_position
        opposite_golem_position = old_opposite_golem_position

    # Golems attempting to jump onto the same tile return to their original squares
    if same_golem_position == opposite_golem_position:
        same_golem_position = old_same_golem_position
        opposite_golem_position = old_opposite_golem_position

    # At this point, the new positions have been determined
    return EntityPositions(
        player=player_position,
        same_golem=same_golem_position,
        opposite_golem=opposite_golem_position,
    )


def find_solution(iteration_limit: int, log_interval: int = 100) -> Optional[BoardState]:
    """
    Exhaustively search for a solution to the puzzle
    """

    # We're going to use a breadth-first search.
    # Breadth-first searches differ from depth-first searches by storing steps using a Queue instead of a Stack.
    # This allows us to examine all the 1-step solutions, then all the 2-step solutions, and so on.
    boards = deque([start_board])

    # Since we're also going to use an exhaustive search, we want to prune down the search as much as possible.
    # When we examine a board, we don't want to examine it again if we can help it. If the player moves left and then
    # right, the board might be back to the same state it was in 2 iterations prior -- which is totally useless.
    # Since our entity positions are implemented with tiny immutable tuples, we can just use a Set to record every
    # board we've seen.
    seen_positions: Set[EntityPositions] = set(board.entity_positions for board in boards)

    # We're going to keep track of some counters manually here.
    i = 0
    total_added = 1

    # Limit how many iterations we're going to process.
    # Now I know exactly how many iterations it's going to take,
    # but when I was working on this the script would hang so having a hard cutoff was useful
    while i < iteration_limit:
        current_board = boards.popleft()

        # Log a message intermittently so we can monitor its progress.
        if i % log_interval == 0:
            print(f'deriving from board {i + 1} of {total_added}. Depth = {len(current_board.movement_seq)}')
        i += 1

        # Look at every possible player input
        for movement in movements:
            next_entity_positions = get_new_state_after_movement(current_board.entity_positions, movement)

            # Eliminate invalid boards early if we can
            if next_entity_positions is None:
                continue  # movement is invalid
            if next_entity_positions in seen_positions:
                continue  # we've already processed this one

            # In a depth-first search, we'd recursively call the same function again to examine any possible move
            # from THIS board. But this is a breadth-first search. Stick it in the back of the queue so we can prioritize
            # the shorter-iteration states first
            next_board = BoardState(entity_positions=next_entity_positions, movement_seq=(*current_board.movement_seq, movement))
            boards.append(next_board)
            seen_positions.add(next_entity_positions)

            # However, if we DID just find the solution, it makes more sense to check for it now than to process the queue first!
            if is_victory(next_entity_positions):
                return next_board


if __name__ == '__main__':
    iteration_limit = 10000
    solution = find_solution(iteration_limit=iteration_limit)
    if solution:
        print('Found solution!')
        solution.print_full()
    else:
        print(f'No solution found after checking {iteration_limit} boards')