infi-aoc-2018

infi.py

"""Solution to the 2018 infi Christmas puzzle.

Usage: python infi.py mazepath
mazepath is the path to a text file containing the maze

Prints the solution to part1 followed by the solution to part 2, each on separate lines. There are no checks for
invalid input."""

import sys
from collections import defaultdict
import copy


class Maze(object):
    """A maze consisting of shiftable tiles, represented as a graph.

    Public attributes:
        shape: tuple (width, height)

        nodes: dict of all tiles in the Maze. Key: coordinates of tile as a tuple (x, y). Value: a _MazeNode. It allows
            lookup of the _MazeNode at at particular position. Conversely, looking up the position of a particular
            _MazeNode (after 1 or more shifts of the Maze) can be done using the pos attribute of _MazeNode.

        edges: dict of all connections between all tiles in the Maze. Key: coordinates of tile as 2 tuple (x, y).
            Value: set of all connected positions as a set of (x, y) tuples.

        previously_shifted_tiles: set containing each _MazeNode that shifted in the previous shift (see the shift_maze
            method for more info).

        shape, nodes, and edges are not intended to be modified by the user of this class, and neither are the values
        inside their respective tuples and dicts."""

    class _MazeNode(object):
        """A tile/node in a Maze

        Attributes:
            tile: Unicode character representing the kind of tile.
            pos: tuple (x, y) representing the position inside the Maze. x runs left-to-right and y runs top-to-bottom
            exits: Set of exits from {'u', 'd', 'l', 'r'}, indicating on which sides the tile can be connected to
                another tile.

        A named tuple would not suffice here, since we need to be able to update the position."""

        def __init__(self, tile, pos):
            self.tile = tile
            self.pos = pos

        @property
        def exits(self):
            if self.tile == '║':
                return {'u', 'd'}
            if self.tile == '╔':
                return {'r', 'd'}
            if self.tile == '╗':
                return {'l', 'd'}
            if self.tile == '╠':
                return {'u', 'd', 'r'}
            if self.tile == '╦':
                return {'r', 'l', 'd'}
            if self.tile == '╚':
                return {'u', 'r'}
            if self.tile == '╝':
                return {'u', 'l'}
            if self.tile == '╬':
                return {'u', 'd', 'l', 'r'}
            if self.tile == '╩':
                return {'r', 'l', 'u'}
            if self.tile == '═':
                return {'r', 'l'}
            if self.tile == '╣':
                return {'l', 'u', 'd'}

    def __init__(self, maze_txt):
        """Init Maze with maze_txt, where maze_txt is a Unicode string describing the maze."""
        self.nodes = dict()

        for y, line in enumerate(maze_txt.splitlines()):
            for x, tile in enumerate(line):
                pos = (x, y)
                self.nodes[pos] = self._MazeNode(tile, pos)

        height = max([y for x, y in self.nodes]) + 1
        width = max([x for x, y in self.nodes]) + 1
        self.shape = (width, height)

        # edges dict. Key: coordinates tuple. Value: Set of coordinate tuples of connected positions.
        self.edges = defaultdict(set)
        for node_pos in self.nodes:
            self._set_edges(node_pos)

        self._num_shifts = 0
        self.previously_shifted_nodes = set()

    def __repr__(self):  # Not required for solving the puzzle, but helps (manual) testing
        txt = []

        for y in range(self.shape[1]):
            for x in range(self.shape[0]):
                txt.append(self.nodes[(x, y)].tile)
            txt.append('\n')

        return ''.join(txt)

    def shift_maze(self):
        """Shift the tiles in the maze according to the next move in a fixed pattern.

        The moves in the pattern are as follows:
            1. rotate the first row to the right
            2. rotate the second column downwards
            3. rotate the third row to the right
            4. rotate the fourth column downward
        etc. After the final row/column it repeats from the first row/column (whichever's turn it is).

        Args: No arguments. Returns: None."""
        # rotate the correct strip at the correct index, updating nodes and edges
        axis, strip_index = self._select_next_rotation()
        self._rotate_strip(axis, strip_index)
        self._num_shifts += 1

    # private methods
    def _set_edges(self, node_pos):
        u"""(Re)set the edges of the node at position node_pos by comparing its tile with surrounding tiles.

        For example, a tile ╠ will be connected to a tile ╗ to its right, but not to a tile ╬ to its left.

        Args:
            node_pos: tuple (x, y)

        Returns: None"""
        x, y = node_pos
        exits = self.nodes[node_pos].exits
        self.edges[node_pos] = set()

        if 'u' in exits and (x, y-1) in self.nodes and 'd' in self.nodes[(x, y-1)].exits:
            self.edges[(x, y)].add((x, y - 1))
        if 'd' in exits and (x, y+1) in self.nodes and 'u' in self.nodes[(x, y + 1)].exits:
            self.edges[(x, y)].add((x, y + 1))
        if 'r' in exits and (x+1, y) in self.nodes and 'l' in self.nodes[(x + 1, y)].exits:
            self.edges[(x, y)].add((x + 1, y))
        if 'l' in exits and (x-1, y) in self.nodes and 'r' in self.nodes[(x - 1, y)].exits:
            self.edges[(x, y)].add((x - 1, y))

    def _select_next_rotation(self):
        # axis == 0: rows, axis == 1: columns

        axis = self._num_shifts % 2
        strip_index = self._num_shifts % (self.shape[axis])

        return axis, strip_index

    def _rotate_strip(self, axis, strip_index):
        self.previously_shifted_nodes = set()

        # shift all nodes
        strip = self._get_1d_strip(axis, strip_index)
        positions = [node.pos for node in strip]  # This copy is required because positions change during iteration
        for idx in range(len(strip)):
            pos = positions[idx]
            self.nodes[pos] = strip[(idx - 1) % self.shape[axis]]
            self.nodes[pos].pos = pos
            self.previously_shifted_nodes.add(self.nodes[pos])

        # Redetermine all edges in the shifted row/column, and in the rows/columns directly adjacent to it. Edges in
        # other rows/columns are still valid and don't need to be updated.
        for idx in range(max(strip_index - 1, 0), min(strip_index + 2, self.shape[axis])):
            self._set_edges_along_strip(axis, idx)

    def _get_1d_strip(self, axis, strip_index):
        strip = []
        if axis == 0:
            for idx in range(self.shape[axis]):
                strip.append(self.nodes[(idx, strip_index)])
        elif axis == 1:
            for idx in range(self.shape[axis]):
                strip.append(self.nodes[(strip_index, idx)])

        return strip

    def _set_edges_along_strip(self, axis, strip_index):
        for node in self._get_1d_strip(axis, strip_index):
            self._set_edges(node.pos)


def shortest_path_bfs(maze, start_pos, end_pos):
    """Return the length of the shortest path in maze between start_pos and end_pos using breadth-first search.

    Arguments:
        maze: a Maze object
        start_pos: start position of the shortest path as an (x, y) tuple.
        end_pos: end position of the shortest path as an (x, y) tuple.

    Returns: Integer representing the minimum number of steps required to go from start_pos to end_pos"""
    if start_pos == end_pos:
        return 0

    visited = set()
    reachable = {start_pos}
    steps = 0
    while True:
        steps += 1
        prev_reachable = reachable
        reachable = set()

        for source in prev_reachable:
            for destination in maze.edges[source]:
                if destination in visited:
                    continue

                if destination == end_pos:
                    return steps

                reachable.add(destination)

        visited.update(prev_reachable)


def shortest_path_shifting_tiles(maze, start_pos, end_pos, shifting_tiles=True):
    """Return the length of the shortest path in maze between start_pos and end_pos, allowing the maze to shift.

    The algorithm is somewhat similar to breadth-first search, with the difference that it does not exclude visited
    nodes in the remainder of the search, causing every node to be (potentially) visited multiple times. This is
    required because due to the shifting tiles we can no longer rely on the property that the shortest path from A to B
    along C starts with the shortest path from A to C, which is the property allowing breadth-first search to exclude
    visited nodes. The reason this property no longer holds is that the next time a node is visited, it might have
    different edges (or its neighbours may have different edges or its neighbours neighbours, etc.).

    Arguments:
        maze: a Maze object
        start_pos: start position of the shortest path as an (x, y) tuple.
        end_pos: end position of the shortest path as an (x, y) tuple.
        shifting_tiles: Boolean indicating whether the maze shifts its tiles after every step. If False, this function
            returns the same result as shortest_path_bfs, but will be less efficient.

    Returns: Integer representing the minimum number of steps required to go from start_pos to end_pos"""
    if start_pos == end_pos:
        return 0

    maze = copy.deepcopy(maze)
    reachable = {maze.nodes[start_pos]}  # set of all nodes reachable in "steps" steps
    steps = 0

    while True:
        steps += 1
        prev_reachable = reachable
        reachable = set()
        for source in prev_reachable:
            for destination_pos in maze.edges[source.pos]:
                if destination_pos == end_pos:
                    return steps

                reachable.add(maze.nodes[destination_pos])

        if shifting_tiles:  # allows testing: without shifting tiles, result should be identical to bfs.
            maze.shift_maze()

            # Because Santa moves with the tiles, we need to check if any reachable tile shifted to the exit
            for node in maze.previously_shifted_nodes:
                if node in reachable and node.pos == end_pos:
                    return steps


if __name__ == '__main__':
    with open(sys.argv[1]) as f:
        maze = Maze(f.read())

    start_pos = (0, 0)
    end_pos = (maze.shape[0] - 1, maze.shape[1] - 1)

    # Part 1 using breadth-first search
    print(shortest_path_bfs(maze, start_pos, end_pos))

    # Part 2 using a similar algorithm that works for shifting mazes
    print(shortest_path_shifting_tiles(maze, start_pos, end_pos, shifting_tiles=True))

maze

╔╬╦╗╝╦╩═║╬╚╝╩╗╣╠╔╗╚╝
╦╬╬╗═╩╝╔╚╗╗║╠╚╠╔╠╔╩═
║╩╩║╦╚═╩╚╦╚═╩╦╔║═╔╩╦
╝║║╩╗═╗╦══╩╠╔╔╠╩╚╗╔╠
╠╣╗═╬╣╩║╚═╣╬╗╦╠╦║╝╩╗
╦╚╬╠╬╬║═╚║╬╦╠╗╬╦╠╩╚║
╣╗╔╝╬╩╗╗═╔═╠╗╠╠╗╗═╬╬
╠╚╣╗╠╗╔╚╩╝═╔╝║╠╣║╦╝═
║╔╔╠╣╝╦╝══╗╗╝╚═╗╩╬╠║
╩╝╚╠╣╗╩╠╩╔╔╔║╔╚╣╦╦═╝
╣═║╠╗╗╝╔╝╦╔╦═╔║╬╬║╬═
╬╣╔║║╚║╝╦═╩╠╦╬╗╗╚═╣═
╝╚╔╚╠═╗╦╝╩╗╦═╠╝╠╠║╣╔
╬╠╠╚╝╩║╦║╝══╔╩═╔╔╣╝╩
╦╚╣╚╠║╚╗╔╚╚═╣╝║╠╚╣╬═
╝╗╦╠║╩╔║╠═╚║╔║╗╣╠╦╚║
╔╣╔╗║╩╩╣╔╚╗╔═╠╔╬╣╣╬╩
╗║╚╬╣╝╩╣╗╠║╦╚╝╚═╗╩╠╔
╝╦╩╗║╩╦╝╩╔║╝╚╝╚╔╗╚╬╩
╣╣║╔╦═╚══╦═╩══╩╣╚═╩╣