You arrive at the first floor of this new building to discover a much less welcoming environment than the shiny atrium of the last one. Instead, you are in a maze of twisty little cubicles, all alike.
Every location in this area is addressed by a pair of non-negative integers (x,y). Each such coordinate is either a wall or an open space. You can't move diagonally. The cube maze starts at 0,0 and seems to extend infinitely toward positive x and y; negative values are invalid, as they represent a location outside the building. You are in a small waiting area at 1,1.
While it seems chaotic, a nearby morale-boosting poster explains, the layout is actually quite logical. You can determine whether a given x,y coordinate will be a wall or an open space using a simple system:
x*x + 3*x + 2*x*y + y + y*y.bits that are 1.
- If the number of bits that are 1 is `even`, it's an _open_ space.
- If the number of bits that are 1 is `odd`, it's a _wall_.For example, if the office designer's favorite number were 10, drawing walls as # and open spaces as ., the corner of the building containing 0,0 would look like this:
0123456789
0 .#.####.##
1 ..#..#...#
2 #....##...
3 ###.#.###.
4 .##..#..#.
5 ..##....#.
6 #...##.###
Now, suppose you wanted to reach 7,4. The shortest route you could take is marked as O:
0123456789
0 .#.####.##
1 .O#..#...#
2 #OOO.##...
3 ###O#.###.
4 .##OO#OO#.
5 ..##OOO.#.
6 #...##.###
Thus, reaching 7,4 would take a minimum of 11 steps (starting from your current location, 1,1).
What is the fewest number of steps required for you to reach 31,39?
This is finding the shortest path between two points - or alternatively, shortest route algorithm. It is clear that we need to find all paths to the route from the current point by taking every turn, and then recusrively traversing along that direction, backtracking to follow other paths. As before, we need a backtracking algorithm.
Getting the designers favorite number
In [1]:
with open('../inputs/day13.txt', 'r') as f:
designers_favorite_number = int(f.readline())
print(designers_favorite_number)
Building the office structure
We store the office points in a namedtuple called Point with the properties x and y to hold the co-ordinates.
In [2]:
from collections import namedtuple
Point = namedtuple('Point', ('x', 'y'))
The office has walls and open spaces, where travel is only permitted in an open space. Therefore, using the given formula, we need to check if a move is valid by checking if the position it is trying to move to is in an open space.
wall_number(x,y) = x*x + 3*x + 2*x*y + y + y*y + designers_favorite_number
bits set = count '1' in binary(wall_number)
In [3]:
def is_wall(x, y):
wall_number = x * x + 3 * x + 2 * x * y + y + y * y +\
designers_favorite_number
if bin(wall_number).count('1') % 2 == 0:
return False
return True
def valid_point(point):
if point.x < 0 or point.y < 0:
return False
# check for walls
if is_wall(*point):
return False
return True
Directions
At any given moment, there are four possible directions - up, down, left, and right. As per the co-ordinate system, we can map them as:
d X Y
-------------
up 0, +1
down 0, -1
left -1, 0
right +1, 0
Thus the number of possible movements become any permutation of (-1, 0, 1) of length 2. We can get this via:
permutations of (-1, 0, 1) with length 2 if sum != 0
Out of these, we need to remove that might result in an out-of-bounds position. Given (xc, yc) as the current position, and (xd, yd) as the direction vector:
direction is valid if 0 <= xc + xd and 0 <= yc + yd
We do not need to check for an upper bound as the space extends infinitely.
In [4]:
from itertools import permutations
directions = tuple(
x for x in permutations((-1, 0, 1), 2)
if sum(x) != 0)
print(directions)
Branching
We need to store the paths and whether we have been there before, and if yes, then which route were we taking. A simple queue should suffice.
The approach we are going to use is that of breadth-first-search. In this approach, we identify all possible directions we can currently move in and put them in the queue. Then while the stack is not empty, we pop a move out, and repeat the directions it can take and so on until we reach the end-point, at which, we store the length of the path we took.
To store the length of the path, each move put on the stack must have an accompanying count of the steps it took to reach there. It is possible to apply heuristic by storing an index of paths sorted by the length and giving priority to pursuing paths with a shorter length first, or those that are nearer to the end-point.
One very important thing to note: we must not travel to the same point again - otherwise we'll keep chasing our own tails in recursive cycles (or an infinite while loop, take your pick). To prevent that, we have to maintain an index of points we have already traversed. We use a dictionary to hold this index, which stores the number of steps we took to traverse to this point. If there comes a move that reaches the same point in lesser number of steps, we know that it is a shorter route, and we continue traversing it. If the move has more number of steps to reach the same point, then it is not an optimum path, and do not need to continue along it.
In [5]:
queue = []
points_traversed = {}
Representing each State/Move
Each state/move is represented using a namedtuple with the properties steps and point to hold the number of steps taken to reach that move and the point it is at respectively.
In [6]:
Move = namedtuple('Move', ('steps', 'point'))
Start and End points
The start and end points allow us to initialise the data structures with the start state and to identify what will be the end point where the algorithm must stop.
(1, 1) and the end point as (31, 39).
In [7]:
start_point = Point(1, 1)
end_point = Point(31, 39)
initial_state = Move(0, start_point)
queue.append(initial_state)
points_traversed[start_point] = 0
Run
Running the algorithm as long as there are moves in the queue or we have not reached our end point, we follow the steps as:
In [8]:
while queue:
state = queue.pop(0)
if state.point == end_point:
break
for vector in directions:
direction = Point(*vector)
move = Point(
state.point.x + direction.x,
state.point.y + direction.y)
if not valid_point(move):
continue
cost = state.steps + 1
if move not in points_traversed or cost < points_traversed[move]:
queue.append(Move(state.steps + 1, move))
points_traversed[move] = cost
In [9]:
print('answer', state.steps)
At first glance, it was not clear to me whether I need to calculate the most distinct points that could be taken in any route in 50 steps, or ALL distinct points from all paths possible in 50 steps. A little clear headed thought said that the most steps possible in 50 moves is 50 + 1 = 51 including the starting step. So that could not be the answer. So it was the other option - to calculate all distinct points visited by all paths possible in 50 moves.
Storing distinct points
Whenever the word distinct occurs, always think of sets. The set starts with the start point as we are currently there, and have visited it.
In [10]:
visited = set()
visited.add(start_point)
Algorithm
Doing everything as before, except for a few changes.
Here, we prioritize the paths that have shorter steps to reach the same point, since shorter steps mean more points traversed (overall). Therefore, we only add the point to the set if we are on optimum paths. This allows us to spread as much as possible without overlapping points or moves.
In [11]:
queue = []
points_traversed = {}
queue.append(initial_state)
points_traversed[start_point] = 0
while queue:
state = queue.pop(0)
if state.steps == 50:
continue
for vector in directions:
direction = Point(*vector)
move = Point(
state.point.x + direction.x,
state.point.y + direction.y)
if not valid_point(move):
continue
cost = state.steps + 1
if move not in points_traversed or cost < points_traversed[move]:
queue.append(Move(state.steps + 1, move))
points_traversed[move] = cost
visited.add(move)
In [12]:
print('answer', len(visited))
== END ==