Skip to content

Instantly share code, notes, and snippets.

@diederikwp diederikwp/infi.py
Last active Feb 4, 2019

Embed
What would you like to do?
infi-aoc-2018
"""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))
╔╬╦╗╝╦╩═║╬╚╝╩╗╣╠╔╗╚╝
╦╬╬╗═╩╝╔╚╗╗║╠╚╠╔╠╔╩═
║╩╩║╦╚═╩╚╦╚═╩╦╔║═╔╩╦
╝║║╩╗═╗╦══╩╠╔╔╠╩╚╗╔╠
╠╣╗═╬╣╩║╚═╣╬╗╦╠╦║╝╩╗
╦╚╬╠╬╬║═╚║╬╦╠╗╬╦╠╩╚║
╣╗╔╝╬╩╗╗═╔═╠╗╠╠╗╗═╬╬
╠╚╣╗╠╗╔╚╩╝═╔╝║╠╣║╦╝═
║╔╔╠╣╝╦╝══╗╗╝╚═╗╩╬╠║
╩╝╚╠╣╗╩╠╩╔╔╔║╔╚╣╦╦═╝
╣═║╠╗╗╝╔╝╦╔╦═╔║╬╬║╬═
╬╣╔║║╚║╝╦═╩╠╦╬╗╗╚═╣═
╝╚╔╚╠═╗╦╝╩╗╦═╠╝╠╠║╣╔
╬╠╠╚╝╩║╦║╝══╔╩═╔╔╣╝╩
╦╚╣╚╠║╚╗╔╚╚═╣╝║╠╚╣╬═
╝╗╦╠║╩╔║╠═╚║╔║╗╣╠╦╚║
╔╣╔╗║╩╩╣╔╚╗╔═╠╔╬╣╣╬╩
╗║╚╬╣╝╩╣╗╠║╦╚╝╚═╗╩╠╔
╝╦╩╗║╩╦╝╩╔║╝╚╝╚╔╗╚╬╩
╣╣║╔╦═╚══╦═╩══╩╣╚═╩╣
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.