We had game night tonight, more HeroQuest (yay!), so I didn’t have a lot of time to work on this.

Basically, you’re digging out a lagoon into which lava will flow. Part 1 could easily be calculated using a basic flood fill algorithm, so I did it that way, got the first star for the day, and went to work. I’d already seen that, as expected, part 2 would resist something that easy.

I started working on algorithms during meetings. There was a lot of talk about the “shoelace” algorithm back in the Metal Maze puzzle. I solved it a weird way that worked for me. When I was reading hints that the shoelace algorithm was the answer for this one, I typed up the sample data into Excel, plugged the data into the formula and it just didn’t work. The missing element had something to do with the perimeter – the puzzle makes that clear. Jabbing at it in various ways didn’t help. Turns out I was really close. I’d already summed up the total lengths of all the segments. Turns out, because of their non-zero width, they had to be considered to be half a unit closer. So, half of the sum of the steps, plus one unit to honor Santa, whose lagoon this is.

Since the only difference between parts 1 and 2 was in the details on how to read the input data, I broke the interpreting the input data into generators, and called the work procedure twice, once with each generator.

`import re

in part 1, UDLR are directions, in part 2, they are hex digits (0..3)

dir_map = {‘U’: (0, 1), ‘D’: (0, -1), ‘L’: (-1, 0), ‘R’: (1, 0), ‘3’: (0, 1), ‘1’: (0, -1), ‘2’: (-1, 0), ‘0’: (1, 0)}

split the input into tuples of (direction, steps, code)

def read_data(): pat = re.compile(r’(\w)\s(\d+)…([\w]{6})’) with open(‘puzzle18.dat’) as f: return map(lambda x: pat.match(x).groups(), f.read().splitlines())

shoelace formula for area of a polygon

def shoelace(vertices): shoelace = 0 for i in range(len(vertices) - 1): shoelace += vertices[i][0] * vertices[i + 1][1] -
vertices[i + 1][0] * vertices[i][1] return abs(shoelace) // 2

generators for part 1 and 2

def part1generator(): yield 0, 0, 0 for uplr, steps, _ in read_data(): yield (*dir_map[uplr], int(steps))

def part2generator(): yield 0, 0, 0 for _, _, code in read_data(): yield (*dir_map[code[-1]], int(code[:-1], 16))

create a list of vertices, sum the perimeter and shoelace area

def calcarea(part_num, pgen): vertices = [(0, 0)] perimeter = 0 for dx, dy, steps in pgen(): vertices.append((vertices[-1][0] + dx * steps, vertices[-1][1] + dy * steps)) perimeter += steps

print('Part {}: {}'.format(part_num, shoelace(vertices) + perimeter // 2 + 1))

run both generators

calcarea(‘1’, part1generator) calcarea(‘2’, part2generator)`

I was reading my code from AoC last year and found I not only didn’t remember the puzzles that well, I honestly had little idea how the code worked. Problem is, most of my actual programming job doesn’t need these algorithms…