# AoC 2018 Day 6: Chronal Coordinates

### Ben Steadman γ»5 min read

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:

- Initialise a
`list`

to store the coordinates - 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

- Split the line on

```
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

- X, Y locations cannot be
- The desired coordinate must have a
**finite**area- i.e. the coordinate is enclosed on all sides by another coordinate

- Find the min/max X, Y limits of the coordinates
- Within these limits, generate all possible integer X, Y locations
- Calculate the Manhattan Distance from each coordinate to each location
- For each location, determine the closest coordinate
- For each coordinate, calculate the area by summing up the number of locations for which it is closest
- 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.