Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- """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):
- """Data-only class representing 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
- 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
- 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._exits(self.nodes[node_pos].tile)
- self.edges[node_pos] = set()
- if 'u' in exits and (x, y-1) in self.nodes and 'd' in self._exits(self.nodes[(x, y - 1)].tile):
- self.edges[(x, y)].add((x, y - 1))
- if 'd' in exits and (x, y+1) in self.nodes and 'u' in self._exits(self.nodes[(x, y + 1)].tile):
- self.edges[(x, y)].add((x, y + 1))
- if 'r' in exits and (x+1, y) in self.nodes and 'l' in self._exits(self.nodes[(x + 1, y)].tile):
- self.edges[(x, y)].add((x + 1, y))
- if 'l' in exits and (x-1, y) in self.nodes and 'r' in self._exits(self.nodes[(x - 1, y)].tile):
- 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)
- @staticmethod
- def _exits(tile):
- if tile == '║':
- return {'u', 'd'}
- if tile == '╔':
- return {'r', 'd'}
- if tile == '╗':
- return {'l', 'd'}
- if tile == '╠':
- return {'u', 'd', 'r'}
- if tile == '╦':
- return {'r', 'l', 'd'}
- if tile == '╚':
- return {'u', 'r'}
- if tile == '╝':
- return {'u', 'l'}
- if tile == '╬':
- return {'u', 'd', 'l', 'r'}
- if tile == '╩':
- return {'r', 'l', 'u'}
- if tile == '═':
- return {'r', 'l'}
- if tile == '╣':
- return {'l', 'u', 'd'}
- 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.copy()
- 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.copy()
- 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))
Add Comment
Please, Sign In to add comment