# Trench Map

`2021-12-28`

Original Prompt ## Part 1

I was so confident. I read this prompt through and felt right away like I knew how to do it. All I needed was a `set`

to store the points where were illuminated. On each enhancement, I could iterate the list of illuminated pixels and calculate their new value. I’d also need to calculate any for any pixel that *neighbored* an illuminated pixel. If your 3x3 grid has no `#`

, then you can’t turn on, so it can be safely ignored. Coded it up, passed the sample input and… failed my puzzle input. That’s unusual. I stepped through the sample and it did exactly what it was supposed to. Out of frustration, I took to reddit and searched recent posts with `day 20`

, hoping for a hint (can usually find people asking for help rather than going straight to the solutions thread). I came across this post, which made me laugh and cry at the same time:

In the sample, the enhancement algorithm started with a `.`

, meaning 9 dots (out in infinite space somewhere) would always stay a `0`

. But, in my (and it turns out, everyone’s) puzzle input, the string started with `#`

. As a result, the infinite field turns on every other step. Luckily, the puzzle is asking about an odd step, so the field will be dark. But, that means pixels that border the infinite have to account for unknown pixels sometimes being `#`

instead of always being `.`

. Well played, puzzle creator.

Once I got the trick, the rest wasn’t too bad. We have to look at every pixel in the input (or that neighbors anything in the input) and calculate its value on each step. We can use a dict of `point -> bool`

to reduce the amount of data we have to store (since there’ll be a lot of it). We’ll also need a variable to track what the current default for the infinite space is (it alternates, but only if the enhancement string starts with a `#`

. Let’s code that up:

```
from typing import Tuple
# set of indexes that will result in an illuminated pixelenhancer = {x for x in range(len(self.input[0])) if self.input[0][x] == "#"}# the bounds are initialized as `.`, regardless of if we swapif_missing = False# don't really need this for the puzzle solution, but it allows the code to work# for both the sample and the puzzleshould_swap = self.input[0][0] == "#"
GridPoint = Tuple[int, int]Image = Dict[GridPoint, bool]
# read inputimage: Image = {}for y, line in enumerate(self.input[2:]): for x, c in enumerate(line): image[(x, y)] = c == "#"
```

Next is the pixel iteration. Because I’m using it so much, I finally wrote a `neighbors`

function into my base class:

```
from operator import itemgetter
# in my custom base fileGridPoint = Tuple[int, int]# sort the direction tuples so they go from top left to bottom rightDIRECTIONS = sorted(product((-1, 0, 1), repeat=2), key=itemgetter(1))
```

`operator`

(a package we saw before on day 16) supplies a function that returns a function. `itemgetter(N)`

creates a function that returns `item[N]`

for anything you pass it. It’s roughly you could write this as:

```
def itemgetter(N: int): def inner(obj): return obj[N] return inner
l = ['a', 'b', 'c']get_1 = itemgetter(1)print(get_1(l)) # => 'b'
```

This lets us sort our list of tuples by their second element (instead of by their first, the default). We could have also used `lambda x: x[1]`

as the `key`

, but `itemgetter`

is more of a standard and handles more complex cases, so it’s good to be familiar with it.

Past that, we loop through that list and `yield`

relevant neighbors like we’ve done before. The function includes some helpful parameters for handling different types of grid (such as those that don’t go negative) and will likely evolve further over time:

```
# also in my base filedef neighbors( center: GridPoint, num_directions=8, *, ignore_negatives: bool = False, max_size: int = 0,) -> Iterator[Tuple[int, int]]: """ given a point (2-tuple) it yields each neighboring point. Iterates from top left to bottom right, skipping any points as described below:
* `num_directions`: Can get cardinal directions (4), include diagonals (8), or include self (9) * `ignore_negatives`: skips points where either value is less than 0 * `max_size`: skips points where either value is greater than the max grid size. Currently assumes a square grid """ assert num_directions in [4, 8, 9]
for dx, dy in DIRECTIONS: if num_directions == 4 and dx and dy: # diagonal; skip continue
if num_directions == 8 and not (dx or dy): # skip self continue
rx = center[0] + dx ry = center[1] + dy
if ignore_negatives and (rx < 0 or ry < 0): continue
if max_size and (rx > max_size or ry > max_size): continue
yield (rx, ry)
```

Finally, we can do our actual enhancement like I described above:

```
# initial input is stored in `image`
for _ in range(2): new_image: Image = {} for pixel in image: for neighbor in neighbors(pixel, 9): # this line brings a 5x speed increase if neighbor in new_image: continue # get each digit result = [ # if_missing is the current state of the "infinite" part of the grid "1" if image.get(n, if_missing) else "0" for n in neighbors(neighbor, 9) ] # merge them as parse as binary; check if it's in our `Set[int]` # each neighbor is stored, so store points grows slowly over time new_image[neighbor] = int("".join(result), 2) in enhancer
image = new_image # again, this is just so the code works for both the sample and the puzzle if should_swap: if_missing = not if_missing
return len([x for x in image.values() if x])
```

That should all be fairly familiar. We count it up at the end and are all set!

## Part 2

AoC speed check! Can you do part 1, but many more times? Luckily, the answer is yes!

```
# input parsing, etc...
results = []for i in range(50): # same code ...
if i in [1, 49]: results.append(len([x for x in image.values() if x]))
return results
```

I know I keep saying “this is my slowest day yet”, but this time it’s really is. Everything so far has been under 1 second for both parts; today is north of 4.5s. The profiler points to calling `neighbors`

a *bunch*. Some things just take time.