Advent of Code 2018 Day 6: Chronal Coordinates

This post originally appeared on steadbytes.com

Complete solution can be found on GitHub

Part One

We are asked to find the largest finite area surrounding area of a coordinate from the list of coordinates in the puzzle input.

Parsing Input

Each line of the input contains a pair of X,Y coordinates separated by ,:

1, 1
1, 6
8, 3
3, 4
5, 5
8, 9

To obtain a list of integer coordinates:

1. Initialise a list to store the coordinates
2. For each line of input:
   • Split the line on ,
   • Cast each split item to an int
   • Append a tuple of integer coordinates to a list

with open("input.txt") as f:
    coords = []
    for line in f.readlines():
        x, y = line.split(", ")
        coords.append((int(x), int(y)))

This works fine, but can be cleaned up and made more Pythonic using a list comprehension:

with open("input.txt") as f:
    coords = [tuple(int(s) for s in line.split(", ")) for line in f.readlines()]

Calculating Coordinate Area

From here on, the term coordinate will refer to one of the X, Y positions extracted from the puzzle input and location will refer to any X, Y position in the search grid.

The puzzle includes some important constraints:

• Calculations must use the Manhattan Distance
• The area around a coordinate is the number of integer X, Y locations that are closest to it
  • X, Y locations cannot be equal distance with another coordinate
• The desired coordinate must have a finite area
  • i.e. the coordinate is enclosed on all sides by another coordinate

1. Find the min/max X, Y limits of the coordinates
2. Within these limits, generate all possible integer X, Y locations
3. Calculate the Manhattan Distance from each coordinate to each location
4. For each location, determine the closest coordinate
5. For each coordinate, calculate the area by summing up the number of locations for which it is closest
6. Return the largest area

Finding the limits of the coordinates is a case of finding the minimum and maximum values for the X, Y components of the puzzle input:

def coords_limits(coords):
    min_x = min(coords, key=lambda c: c[0])[0]
    max_x = max(coords, key=lambda c: c[0])[0]
    min_y = min(coords, key=lambda c: c[1])[1]
    max_y = max(coords, key=lambda c: c[1])[1]

    return ((min_x, max_x), (min_y, max_y))

coords_limits(
    [(1, 1), (1, 6), (8, 3), (3, 4), (5, 5), (8, 9)]
)
# ((1, 8), (1, 9))

Now a nested loop between each set of limits can be used to enumerate all the possible locations:

def gen_locations(x_lims, y_lims):
    for x in range(x_lims[0], x_lims[1] + 1):
        for y in range(y_lims[0], y_lims[1] + 1):
            yield (x, y)

Note that I'm using a generator here for lazy evaluation. This means that each location will be calculated on demand as it is required, instead of building up the entire list at once. The benefit of this will become clear in the next steps.

To calculate the distance between the coordinates and locations, I will first generate a tuple of (<location>, <coord>) for each combination:

def gen_locations_coords(coords):
    x_lims, y_lims = coords_limits(coords)
    for x, y in gen_locations(x_lims, y_lims):
        for cx, cy in coords:
            yield ((x, y), (cx, cy))

Then calculate the Manhattan Distance for each of these, generating tuples of ((<location>, <cood>), <distance>):

def manhattan_distance(x1, y1, x2, y2):
    return abs(x1 - x2) + abs(y1 - y2)

def gen_locations_coords_dists(coords):
    for (x, y), (cx, cy) in gen_locations_coords(coords):
        d = manhattan_distance(cx, cy, x, y)
        yield ((x, y), (cx, cy), d)

Using generators here is incredibly powerful, allowing a 'chain' of iteration logic to be split up over multiple functions without building and passing around large data structures (in this case a list of locations).

To determine the closest coordinate to each location, I iterate over the combinations of locations, coordinate and distances produced by gen_locations_coords_dists updating a mapping between the pairing with the shortest distance:

# location: closest coordinate
closest_coord_map = {}
# location: shortest distance
closest_coord_dists = defaultdict(lambda: float("inf"))
for (x, y), (cx, cy), d in gen_locations_coords_dists(coords):
    # shortest distance seen so far
    closest = closest_coord_dists[(x, y)]
    if d < closest:
        # current pairing is shorter
        closest_coord_map[(x, y)] = (cx, cy)
        closest_coord_dists[(x, y)] = d
    elif d == closest and closest_coord_map[(x, y)] != (cx, cy):
        # same distance, not the same X,Y values
        # locations with multiple equal distance coords don't count towards area
        closest_coord_map[(x, y)] = None

Using this closest_coord_map, the area for each coordinate can be calculated, by counting the number of locations where each coordinate is closest:

x_lims, y_lims = coords_limits(coords)
coords_areas = defaultdict(int)
for xy, coord in closest_coord_map.items():
    if coord is None:
        # location was equal distance to coordinates
        continue
    if xy[0] in x_lims or xy[1] in y_lims:
        # location at edge of coordinate limits
        # must have an infinite area
        coords_areas[coord] = float("-inf")
    coords_areas[coord] += 1
largest_area = max(coords_areas.values())

These last two steps can be wrapped up into a function for Part 1:

def part_1(coords):
    closest_coord_map = {}
    closest_coord_dists = defaultdict(lambda: float("inf"))
    for (x, y), (cx, cy), d in gen_locations_coords_dists(coords):
        closest = closest_coord_dists[(x, y)]
        if d < closest:
            closest_coord_map[(x, y)] = (cx, cy)
            closest_coord_dists[(x, y)] = d
        elif d == closest and closest_coord_map[(x, y)] != (cx, cy):
            closest_coord_map[(x, y)] = None

    x_lims, y_lims = coords_limits(coords)
    coords_areas = defaultdict(int)
    for xy, coord in closest_coord_map.items():
        if coord is None:
            continue
        if xy[0] in x_lims or xy[1] in y_lims:
            coords_areas[coord] = float("-inf")
        coords_areas[coord] += 1
    return max(coords_areas.values())

For my puzzle input, the result is 3358.

Part Two

We are now asked to find the **size of the region containing all locations which have a total distance to all given coordinates of less than 10000`. The puzzle actually provides us an algorithm for finding the desired region (using a smaller size of 32):

For each location, add up the distances to all of the given coordinates; if the total of those distances is less than 32, that location is within the desired region.

All of the hard work has been done in part one, we can already generate the distances between all locations and all coordinates. The final step is to sum up the distances for each location to find the total distance to all coordinates in the region, filter these to where the total distance is less than 10000 and count them up!

python
def part_2(coords):
total_dists_to_coords = defaultdict(int)
for (x, y), (cx, cy), d in gen_locations_coords_dists(coords):
# calculate region size for each location
total_dists_to_coords[(x, y)] += d
# filter and count
return len([l for l, d in total_dists_to_coords.items() if d < 10000])


For my puzzle input, the result is 45909

A note on Lazy Evaluation

This puzzle was a great fit for generators and lazy evaluation. It provides a very interesting programming paradigm which can be extremely useful for large datasets (and fun of course). I would highly encourage reading Structure and Interpretation of Computer Programs chapter 3.5 on Streams for an excellent introduction to the topic.

Resources

• Manhattan Distance
• Generators
• defaultdict
• Structure and Interpretation of Computer Programs chapter 3.5 on Streams.