# Advent of Code 2021

Published November 30, 2021

Is it Advent of Code time again? Well, here goes nothing. Let's see wha we can cook up.

I'm planning on completing most (all) of this year's challenges in Python, same as last year.

## Day 1 - Sonar Sweep

#### Part 1

I feel like it's Advent of Code tradition for me to read in the input from file (as strings) and try to do comparisons on it like ints, forgetting to cast them to intergers. Which means I was comparing textually, instead of numerically, so my answer was off by two. Absurd.

You really could do today's challenge entirely in one line, but I think it's slightly more readable broken up as I've done. Here's the complete code:

Day1/Part1.py

 ``````1 2 3 4 5 6 `````` ``````with open("input.txt", "r") as infile: data = [int(t) for t in infile.read().split('\n')] numDecreases = len([pair for pair in zip(data[:-1], data[1:]) if pair < pair]) print(f"{numDecreases=}")``````

The offending line, where I remembered to cast the input to ints.

#### Part 2

Part 2 could also probably be inlined, but the list-comprehension-within-list-comprehension is, again, not the most readable thing, I think. Breaking out the three key steps (creating triples of the data, finding their sums, and finding where adjacent sums are decreasing) into 3 lines of code I think makes the solution more parsable.

Day1/Part2.py

 ``````1 2 3 4 5 6 7 8 9 `````` ``````with open("input.txt", "r") as infile: data = [int(t) for t in infile.read().split('\n')] triples = zip(data[:-2], data[1:-1], data[2:]) windowSums = [sum(list(t)) for t in triples] numDecreases = len([t for t in zip(windowSums[:-1], windowSums[1:]) if t < t]) print(f"{numDecreases=}")``````

## Day 2 - Dive!

#### Part 1

The first part of today's challenge has us dealing with a list of things that happen sequentially (tracking the horizontal and vertical movements of our submarine), but the answer only has to do with summing them in some specific ways. This smells strongly of a 'gotcha' coming in part 2 - if we can the easy, just-sum-it-up route for part 1, we won't be able to reuse any code for part 2 when the order actually matters. But that's alright, I guess, we'll take the easy route on this one.

There's a fair amount of repetition in my list comprehensions here, but for a 7-line program I don't terribly feel like factoring it out.

Day2/Part1.py

 ``````1 2 3 4 5 6 7 `````` ``````with open("input.txt", 'r') as infile: # data is a list of tuples; each tuple is of form ('instruction', int) where 'instruction' is forward, down, up data = [(line.split(' '), int(line.split(' '))) for line in infile.read().split('\n')] horizontal = sum([step for step in data if step == 'forward']) depth = sum([step for step in data if step == 'down']) - sum([step for step in data if step == 'up']) print(f"Solution product is {horizontal * depth =}")``````

#### Part 2

As expected, we're paying the (small) price for not doing the first part iteratively. That's alright, we can implement it now.

This does give me a chance to play with a new feature of Python 3.10: structural pattern matching. It's like a switch-case structure on steroids. To make sure I'm running this code in Python 3.10 specifically, I'll use pipenv to lock the version to 3.10.0 by running `pipenv install --python 3.10` on the command line.

Our code is ultimately fairly simple; thankfully, I encountered no "unmatched instruction" errors, which means I parsed the input correctly.

Day2/Part2.py

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 `````` ``````with open("input.txt", 'r') as infile: # data is a list of tuples; each tuple is of form ('instruction', int) where 'instruction' is forward, down, up data = [(line.split(' '), int(line.split(' '))) for line in infile.read().split('\n')] horizontal, depth, aim = 0,0,0 for d in data: match d: case ('down', num): aim += num case ('up', num): aim -= num case ('forward', num): horizontal += num depth += aim * num case _: raise ValueError(f"Unmatched instruction {d}") print(f"Solution is {horizontal*depth= }")``````

## Day 3 - Binary Diagnostic

#### Part 1

Ah, day 3 of Advent of Code, where we traditionally get into nested-processing, working with binary, and parsing numbers based on their digits. I don't know that this literally happens on day 3 every year, but it seems a familiar progression in the early days of an Advent of Code challenge. My first thought is - let's make sure we iterate through the entire input as few times as possible, something made easier by the fact that epsilon and gamma are, in some sense, complements of each other.

This one's not too hard - using a `defaultdict` from the `collections` module makes the process of adding up the number of "1"'s in all the input numbers a little cleaner.

Day3/Part1.py

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 `````` ``````from collections import defaultdict with open("input.txt", 'r') as infile: data = infile.read().split('\n') numInputs = len(data) onesCount = defaultdict(lambda: 0) #Count the number of "1"'s at each digit position in all of the input numbers for num in data: for i, digit in enumerate(num): onesCount[i] += int(digit) #Calculate gamma, epison as lists of strings ("1" and "0") gamma = [("1" if onesCount[i] > (numInputs / 2) else "0") for i in range(len(onesCount))] epsilon = [("1" if gamma[i] == "0" else "0") for i in range(len(onesCount))] #Concatenate lists, as 0b to represent binary, cast to int result = int('0b' + ''.join(gamma), 2) * int('0b' + ''.join(epsilon), 2) print(f"{gamma= } {epsilon= } {result= }")``````

#### Part 2

Now we're moving into the realm of processing some input data with multiple passes, while restricting which data is in each pass based on our processing of previous steps. My initial solution was a little cumbersome, but I think gets the intention accross pretty well.

Day2/Part2.py (Version 1)

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 `````` ``````with open("input.txt", 'r') as infile: inputdata = infile.read().split('\n') def mostCommonDigitInPosition(data, position): return "1" if sum([int(num[position]) for num in data]) >= len(data)/2 else "0" oxyData = [d for d in inputdata] co2Data = [d for d in inputdata] #find Oxygen Rating for i in range(len(inputdata)): if len(oxyData) <= 1: break MCD_o2 = mostCommonDigitInPosition(oxyData, i) oxyData = [t for t in oxyData if t[i] == MCD_o2] #find CO2 Rating for i in range(len(inputdata)): if len(co2Data) <= 1: break MCD_co2 = mostCommonDigitInPosition(co2Data, i) co2Data = [t for t in co2Data if t[i] != MCD_co2] if len(oxyData) == 1: oxygenRating = int(oxyData, 2) else: raise ValueError(f"Oxygen Data should only have one element, instead was {oxyData}") if len(co2Data) == 1: co2Rating = int(co2Data, 2) else: raise ValueError(f"CO2 Data should only have one element, instead was {co2Data}") print(f"Product: {oxygenRating} * {co2Rating} = {oxygenRating * co2Rating= }")``````

We can refactor this a bit, so that the logic of reducing the list of input values is done in a function called `calculateRating`, which takes a list of data as well as a function. The function tells us, for a given digit position, what value at that position should be used to keep values in our data for our next round of culling.

While we could also get a little fancy and combine `mostCommonDigitInPosition` and `leastCommonDigitInPosition`, I think we'd actually be in danger of making things too concise. The difference between `>=` and `>` in each case is critical, and I think factoring that out might be too reductive.

Day3/Part2.py (Version 2)

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 `````` ``````with open("input.txt", 'r') as infile: inputdata = infile.read().split('\n') def mostCommonDigitInPosition(data, position): return "1" if sum([int(num[position]) for num in data]) >= len(data)/2 else "0" def leastCommonDigitInPosition(data, position): return "0" if sum([int(num[position]) for num in data]) >= len(data)/2 else "1" def calculateRating(data, digitFunc): for i in range(len(data)): if len(data) <= 1: break digitToMatch = digitFunc(data, i) data = [t for t in data if t[i] == digitToMatch] if len(data) == 1: return int(data, 2) else: raise ValueError(f"Function calculateRating should termiante with one element, instead was {data}") oxygenRating = calculateRating(inputdata, mostCommonDigitInPosition) co2Rating = calculateRating(inputdata, leastCommonDigitInPosition) print(f"Product: {oxygenRating} * {co2Rating} = {oxygenRating * co2Rating= }")``````

## Day 4 - Giant Squid

#### Part 1

Today my biggest obstacle was, as is often the case, myself trying to be too clever and concise. Today's challenge invovled parsing a somewhat more involved text file of inputs, and then further processing that input to make it into a useful data structure. Rather than load each bingo card as a 2D array, I used the input data to create two separate arrays, one indexed by rows, the other by columns, with boards at the same position representing the same board. Determining whether a board is winning (given a list of called numbers) is a simple as asking whether any of the lines (rows or columns) in that board have all their members in the called numbers.

Had I simply constructed each type of input using `for` loops, this would have been fairly simply, but I wanted everything packaged up nice in a list comprehension... which took me a spell to troubleshoot and get right. Ah well.

Day4/part1.py

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 `````` `````` with open ("input.txt", 'r') as infile: inputChunks = infile.read().split('\n\n') #---Parse the Input to make it useful---- allCalledNumbers = [int(num) for num in inputChunks.split(',')] boards = [' '.join(chunk.split('\n')) for chunk in inputChunks[1:]] #get boards #Make board list of ints instead of long string by splitting every 3 characters intBoards = [[int(b[n:n+2]) for n in range(0, len(b), 3)] for b in boards] #boardrows is a list of boards, each of which are a list of rows in each board, #each of which is a list of ints boardRows = [[b[index:index+5] for index in range(0, 25, 5)] for b in intBoards] #boardcols is a list of boards, each of of which is a list of columns in each board, #each of which is a list of ints boardCols = [[[b[row][index] for row in range(5)] for index in range(5)] for b in boardRows] #---Define some functions to help us solve the problem as written--- #For a given board (by row or column), are any of its lines made up only of numbers in 'calledNums'? def isBoardAWin(board, calledNums): return any([all([num in calledNums for num in line]) for line in board]) #Score is (sum of uncalled numbers on board) * (last number called) def calcScore(board, calledNumbers): unusedNumbers = [num for line in board for num in line if num not in calledNumbers] return sum(unusedNumbers) * calledNumbers[-1] def doWin(board, calledNumbers): print(f"Score is {calcScore(b, calledSoFar)}") exit() #---Find solution--- for i in range(len(allCalledNumbers)): calledSoFar = allCalledNumbers[:i] print(f"Searching for wins with numbers {calledSoFar}") winner = False for b in boardRows: if isBoardAWin(b, calledSoFar): print(f"Winner board by row! \n {b}") doWin(b, calledSoFar) for b in boardCols: if isBoardAWin(b, calledSoFar): print(f"Winner board by column! \n {b}") doWin(b, calledSoFar) print(f"No winners after {i} numbers, calling next number") ``````

Scroll to see complete code

#### Part 2

Thankfully, the infrastructure I built for part 1 of this puzzle was very useful for part to. Basically, instead of iterating through increasingly long lists of called numbers until the first winning is found, keep going until only 1 board has not won, recall that it's the winner, then keep adding called numbers until it does win.

Since all of the setup and parsing steps are the same, I'll only include the solution finding part of the code, for brevity:

Day2/Part2.py (Partial)

 ``````35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 `````` ``````#---Find solution--- hasWon = [False for b in boards] for i in range(len(allCalledNumbers)): calledSoFar = allCalledNumbers[:i] for x, b in enumerate(boardRows): if isBoardAWin(b, calledSoFar): hasWon[x] = True for x, b in enumerate(boardCols): if isBoardAWin(b, calledSoFar): hasWon[x] = True print(f"After calling {i} numbers,", end = " ") if hasWon.count(False) == 1: winningIndex = hasWon.index(False) print(f"found last board to win at index: {winningIndex}") elif hasWon.count(False) == 0: print(f"This board wins after {i} numbers called,",) doWin(boardCols[winningIndex], calledSoFar) else: print(f"{hasWon.count(False)} boards have not won")``````

## Day 5 - Hydrothermal Venture

#### Part 1

One of the gotchas on this day is making incorrect assumptions about the ordering of points in a given line. For eaxmple, for a line with endpoints (3,5) and (3,0), doing something like: `for y in range(point1.y, point2.y)` will generate exactly one point `(3.5)`, because the ending y coordinate is less than the starting one. This can be fixed by either ranging over the values in a consistent direction (always from lesser to great, say) or by pre-sorting the line coordinates so that the first coordinate is always less than the second for the given axis. I chose to do the former.

Unrelatedly, I'm personally a fan of Regex101 for working out regexes. It makes the process of fleshing out a given pattern visual and intuitive, and the built-in reference guides and regex tips are invaluable.

Day5/Part1.py

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 `````` ``````import re from collections import namedtuple with open ("input.txt", 'r') as infile: data = infile.read().split("\n") Line = namedtuple('Line', ['p1x', 'p1y', 'p2x', 'p2y']) parsedData = [] for d in data: reg = re.search(r'(.+),(.+) -> (.+),(.+)', d) parsedData.append(Line(p1x = int(reg.group(1)), p1y = int(reg.group(2)), p2x = int(reg.group(3)), p2y = int(reg.group(4)))) horizontalLines = [l for l in parsedData if l.p1y == l.p2y] verticalLines = [l for l in parsedData if l.p1x == l.p2x] coveredOnce, coveredMany = set(), set() for l in horizontalLines: for xCoord in range(min(l.p1x, l.p2x), max(l.p1x, l.p2x)+1): point = (xCoord, l.p1y) #If the point is already covered by multiple lines, we don't need to do anything more with it, but if point not in coveredMany: #If we haven't see it at all, we should mark that we've now seen it once. if point not in coveredOnce: coveredOnce.add(point) #Otherwise, we should mark that we've now seen it in multiple lines else: coveredOnce.remove(point) coveredMany.add(point) for l in verticalLines: for yCoord in range(min(l.p1y, l.p2y), max(l.p1y, l.p2y)+1): point = (l.p1x, yCoord) #If the point is already covered by multiple lines, we don't need to do anything more with it, but if point not in coveredMany: #If we haven't see it at all, we should mark that we've now seen it once. if point not in coveredOnce: coveredOnce.add(point) #Otherwise, we should mark that we've now seen it in multiple lines else: coveredOnce.remove(point) coveredMany.add(point) print(f"Solution is: {len(coveredMany)}") ``````

Scroll to see complete code

#### Part 2

Having selected to iterate over the points in a line in a consistent way in the first half, I felt it might be easier to pre-process the diagonal lines in the second half. That is, I swapped the endpoints of each diagonal line as necessary to ensure the point with the lower X coordinate was first. Then, if the second y coordinate is great than the first, each time we increase the x coordinate by 1, we will by definition incrase the y coordinate by 1. If the second y coordinate is less than the first, y decreased by 1 for each increase of the x coordinate. Other than that, the processing of each point to see if it's been covered already is the same as in part one.

For brevity, I've only included the addititional processing necessary for part 2 of today's challenge.

Day5/Part2.py (Partial)

 ``````44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 `````` ``````diagonalLines = [l for l in parsedData if l not in verticalLines and l not in horizontalLines] for l in diagonalLines: #Make sure the first coordinate of each line is left of the second coordinte if l.p2x < l.p1x: l = Line(p1x = l.p2x, p1y = l.p2y, p2x = l.p1x, p2y = l.p1y) #Determine if y increases or descreases with increasing X yDir = 1 if l.p2y > l.p1y else -1 for yDelta, xCoord in enumerate(range(l.p1x, l.p2x+1)): point = (xCoord, l.p1y + (yDelta*yDir)) if point not in coveredMany: #If we haven't see it at all, we should mark that we've now seen it once. if point not in coveredOnce: coveredOnce.add(point) #Otherwise, we should mark that we've now seen it in multiple lines else: coveredOnce.remove(point) coveredMany.add(point) print(f"Solution is: {len(coveredMany)}")``````

## Day 6 - Lanternfish

#### Part 1

Part one of today's puzzle was deceptively simple. It asks the challenger to calculate the number of lanternfish present after a given number of steps of an iterative process. The way the puzzle's data is displayed in the examples presented, one might be tempted to keep the data as a long list of individual fish listed by the number of days till they next reproduce; then, for each step, iterate over the list and take the appropriate action. While this shold generate a solution, the list would quickly balloon out of the control. The key insight is that each fish that will, say, generate a new fish in 4 days, is identical to every other fish that will spawn a new fish in four days. So really, we don't need to track individual fish, just the total count of fish that will reproduce in a given number of days. For every day that passes, each of those counts of fish reduce their count by one, and we do some special accounting to the fish that are reproducing today, and iterate.

This quick and simple approach does make one worry that part 2 will require more convoluted reasoning though.

Day6/Part1.py

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 `````` ``````with open("input.txt", "r") as infile: inputdata = [int(num) for num in infile.read().split(',')] fishcounts = [inputdata.count(num) for num in range(0,8+1)] daysToRun = 80 for _ in range(daysToRun): newfishcounts = fishcounts[1:] + [fishcounts] newfishcounts += fishcounts fishcounts = newfishcounts print(f"After {daysToRun} days there are {sum(fishcounts)} lanternfish")``````

#### Part 2

Ah! We've gotten lucky here and avoided the 'gotcha' that the puzzle writer was thinking of. The second step asks to calculate the number of fish present after 256 steps; if one had taken the "process the whole list" technique in part one, one would be screwed in part two as the exponential growth of the fish population really takes off. But with a condensed, iterative process like we used in part 1, one only has to change the `daysToRun` value to 256, and our answer pops out in less than a quarter of a second! Excellent. I'm not even going to include the code a second time, since it is identical to part 1 except for the value of `daysToRun`.

Day6/Part2.py

``#See Day6/Part1.py, above``

## Day 7 - The Treachery of Whales

#### Part 1

Just to humblebrag a bit (well, really, to brag; but hey, it's my website), I solved part 1 of day's challenge in the shower. My reasoing went something like the following:

• We're looking to select a point that minimizes the function , as presented in problem setup.
• Taking the derivative of this sum is somewhat complicated, but there's actually a better way to reason about it.
• Looked at another way, we're looking to find a point such that moving that point will only cause the total crab-distance traveled to increase; a local minimum.
• Picture our point where our crabs our converging at a point on the number line, with crabs less than x and crabs great than • As we slide our alignment point along the number line in a continuous fashion, if it moves a small distance in, say the positive direction:
• We add units of additional crab travel, as we move further from the crabs at positions less than our alignment point, but
• We subtract as we move closer to the crabs greater than our alignment point
• And similarly, if is negative, we get closer to crabs and futher from crabs.
• So, if , increasing will cause the total crab distance to descrease. And if , decreasing with cause thte total crab distance to increase.
• But recall, what we want is to find a point where neither of those things is true; where is at a mimumum, so any movement of it causes the total crab distance to incerase. This is only true where neither of the above inequalities is statisfied, i.e. when .
• Moving some terms around, we find that the total crab distance travelled is at a mimimum when , in other words, when the number of crabs greater than and less than the alignment point are equal. This is true when is the median of the crab points.

All that thinking in a warm shower yeilded a very short (and working) bit of code.

Day7/Part1.py

 ``````1 2 3 4 5 6 7 8 9 `````` ``````from statistics import median with open("input.txt", "r") as infile: data = [int(num) for num in infile.read().split(',')] median = median(data) minFuel = sum([abs(d-median) for d in data]) print(f"{minFuel= }")``````

#### Part 2

Sadly, my brain failed me when trying to come up with a similarly clever solution for part 2, so I ended up implementing the crab-fuel-expenditure function as described in the problem statement and iteratively increasing and decreasing the alignment point value until a minimum was found. I had the code start at the median value of the list, somewhat arbitrarily, but the code still finishes in under a quarter of a second and yields the correct answer.

I skipped a couple of obvious optimizations.

• Incrementing the position that we're currently testing the crab-distance of by only 1 unit each time probably isn't optimal (for my inputs, I had to evaluate 140 positions before finding a minimum). Perhaps some variation on Newton's method could have been used to estimate a better delta for `testVal`?
• There might be a more ideal value to start the search at (the mean perhaps?).

Day7/Part2.py

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 `````` `````` from statistics import median with open("input.txt", "r") as infile: data = [int(num) for num in infile.read().split(',')] def fuelUsed(crabPositions, position): return sum([(abs(d - position)*(abs(d-position)+1)/2) for d in crabPositions]) class lazyDict(dict): def __init__ (self, factory): self.factory = factory def __missing__ (self, key): self[key] = self.factory(key) return self[key] fuelToReach = lazyDict(lambda x: fuelUsed(data, x)) med = median(data) fuelToReach[med] = fuelUsed(data, med) testVal = med while not ((fuelToReach[testVal] < fuelToReach[testVal+1]) and (fuelToReach[testVal] < fuelToReach[testVal-1])): if fuelToReach[testVal-1] < fuelToReach[testVal]: testVal -= 1 elif fuelToReach[testVal+1] < fuelToReach[testVal]: testVal += 1 else: raise ValueError(f"Something has gone wrong\n {fuelToReach= }") print(f"Minimum required fuel is reached at position {testVal} with {fuelToReach[testVal]} fuel used") print(f"Calculated {len(fuelToReach)} potential positions") ``````

Scroll to see full code

## Day 8 - Seven Segment Search

#### Part 1

Whenever the first part of an AoC challenge says `For now...` you know you're in for an expansion of that area of the challenge in part 2. Today's part one specifcally says to `For now, focus on the easy digits`, meaning the hard digits are coming right down the pipe.

Part 1 is indeed pretty easy - it breaks down to parsing the input, throwing away half of it, then counting the members of a list that have a length of 2, 3, 4, or 7 letters. I had a feeling we'd be parsing the actual digit information in part 2, so I fleshed out a bit of a dataclass to hold the input values, assuming I'd expand this in part 2.

Day8/Part1.py

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 `````` ``````from dataclasses import dataclass @dataclass class displayRun: hookups: list[str] outputs: list[str] with open("input.txt", "r", encoding="utf-8") as infile: runs = [displayRun(hookups = line.split('|').strip().split(" "), outputs = line.split('|').strip().split(" ")) for line in infile.read().split('\n')] totalUnique = sum([sum([(1 if len(segments) in [2,3,4,7] else 0) for segments in r.outputs]) for r in runs]) print(f"{totalUnique=}")``````

#### Part 2

Ah, here we go, let's parse some digits. We'll need to figure out which actual segments (from `'abcdefg'`) are represented by which letters in the input rows.

I'll start by organizing the "hookups" (sequences of letters describing the segments lit up for a given digit) ina dictionary by the number of letters in each. This will help us tease apart which segment is which by looking at which segments are in how members members of each of thes lists.

For example, as part 1 illustrates, there is only 1 hookup with 2 segments ("1") and 1 hookup with 2 segments ("7"). The segment connected to the `a` illuminator is present in the "7" hookup, but not in the "1" hookup, and that's their only difference, so it's easy to find what's wired to the "a" segment.

The remainder of the deductions are slightly more complicated. For example:

• In the 3 digits with 5 segments illuminated (2, 3, 5), there are three segments common to all three (segments, `a`, `d`, and `g`).
• We've already found what's hooked up to segment `a`, as above. So the remaining two common segments correspond to illuminators `d` and `g`, in some order.
• The segment corresponding to `d` will be present in the single hookup with 4 illuminated sigments (which corresponds to the digit "4"); the segment corresponding to `g` will not. So we have established which segments should be wired now to `d` and `g`.

Similar logic allows us to work out:

• Segments `e` and `b` (both are in a single digit with 5 illuminated segments, with `e` present in 2 hookups with 6 illuminated segments and `b` present in 3).
• Segments `c` and `f` (both are present in two digits with 5 illuminated segments, with `c` present in 2 hookups with 6 illuminated segments and `f` present in 3).

There may be a more concise way of working this out, but this method worked out for me.

Once we know the mappings from poorly-wired-segments to true segments, we can iterate over all our input rows, transform the messed-up wirings to true wirings using this mapping, map the true mappings to digits, then sum them up.

Day8/Part2.py

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 `````` ``````from dataclasses import dataclass @dataclass(kw_only=True) class displayRun: hookups: list[str] outputs: list[str] segmentAssigns : dict[str:str](default_factory=dict) with open("input.txt", "r", encoding="utf-8") as infile: runs = [displayRun(hookups = line.split('|').strip().split(" "), outputs = line.split('|').strip().split(" "), segmentAssigns = dict()) for line in infile.read().split('\n')] def numFromSegmentsOn(segmentsOn): sortedLetters = ''.join(sorted([letter for letter in segmentsOn])) if sortedLetters == 'abcefg' : return 0 if sortedLetters == 'cf' : return 1 if sortedLetters == 'acdeg' : return 2 if sortedLetters == 'acdfg' : return 3 if sortedLetters == 'bcdf' : return 4 if sortedLetters == 'abdfg' : return 5 if sortedLetters == 'abdefg' : return 6 if sortedLetters == 'acf' : return 7 if sortedLetters == 'abcdefg' : return 8 if sortedLetters == 'abcdfg' : return 9 raise ValueError(f"Sorted letters {sortedLetters} do not match any digit pattern") sum = 0 for r in runs: #Determine display: control wire mapping #{"actual illuminated output: wire that currently controls it"} hookupsWithLen = dict() for i in range(2, 7+1): hookupsWithLen[i] = [h for h in r.hookups if len(h) == i] r.segmentAssigns['a'] = [seg for seg in 'abcdefg' if (seg in hookupsWithLen and seg not in hookupsWithLen)] #know wiring of segment a] d_or_g = [seg for seg in 'abcdefg' if (len([h for h in hookupsWithLen if seg in h]) == 3 and seg != r.segmentAssigns['a'])] #based on hookups with 5 segments r.segmentAssigns['d'] = [seg for seg in 'abcdefg' if seg in d_or_g and seg in hookupsWithLen] #based on single length-4 hookup r.segmentAssigns['g'] = [seg for seg in 'abcdefg' if seg in d_or_g and seg != r.segmentAssigns['d']] b_or_e = [seg for seg in 'abcdefg' if len([h for h in hookupsWithLen if seg in h]) == 1] #based on hookups with 5 segments on r.segmentAssigns['e'] = [seg for seg in 'abcdefg' if seg in b_or_e and len([h for h in hookupsWithLen if seg in h]) == 2] #based on hookups with 5 segments and knowing 'b' already r.segmentAssigns['b'] = [seg for seg in 'abcdefg' if seg in b_or_e and seg != r.segmentAssigns['e']] c_or_f = [seg for seg in 'abcdefg' if len([h for h in hookupsWithLen if seg in h]) == 2] #based on hookups with 5 segments on r.segmentAssigns['c'] = [seg for seg in 'abcdefg' if seg in c_or_f and len([h for h in hookupsWithLen if seg in h]) == 2] r.segmentAssigns['f'] = [seg for seg in 'abcdefg' if seg in c_or_f and seg != r.segmentAssigns['c']] #convert miswired digits to real digits, then to numbers, and sum up rowSum = 0 for i, digit in enumerate(r.outputs): rewiredDigit = ''.join([seg for seg in 'abcdefg' if r.segmentAssigns[seg] in digit]) rewiredNum = numFromSegmentsOn(rewiredDigit) rowSum += rewiredNum * 10 ** (3-i) sum += rowSum print(f"Total of all rewired numbers: {sum}")``````

Scroll to see full code

## Day 9 - Smoke Basin

#### Part 1

Another classic evolution of the Advent of Code is working with adjacent items in a grid, with the biggest connundrum/gotcha being how to deal with the edges/corners. While the list comprehension I've put together here isn't necessarily the most readable at first glance, nor the most efficient (it generates 9 positions, of which 4 are usable), it gets the job done.

Day9/Part1.py

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 `````` ``````from collections import defaultdict data = defaultdict(lambda:100) with open("input.txt", "r", encoding="utf-8") as infile: raw = infile.read().split('\n') numRows = len(raw) numCols = len(raw) for r, row in enumerate(raw): for c, col in enumerate(row): data[(r, c)] = int(col) total = 0 for r in range(numRows): for c in range(numCols): #print([(r + deltar, c + deltac) for deltar in [-1, 0, 1] for deltac in [-1, 0, 1] if (deltar*deltac == 0 and deltar != deltac)]) if all([data[(r, c)] < data[(r + deltar, c + deltac)] for deltar in [-1, 0, 1] for deltac in [-1, 0, 1] if (deltar*deltac == 0 and deltar != deltac)]): total += data[(r, c)] + 1 print(f"{total= }")``````

#### Part 2

The second part of today's challenge is essentially a flood-fill algorithm starting from the points we identified in part 1, ending when we reach the edges of the input data or a '9' in the data itself. By appending new points of interest to the end of the list (and only adding them if we haven't included them in the basin points already), we don't run into the issue of constantly checking points from each other.

Again, the meat of this solution is contained in a really long list comprehension. Probably not the most readable, as its checking four separate conditions to see if it should add a new point. Two have to do with generating the neighboring points, one to check if the newly checked point is a '9', and one to check if we've already included this point in the basin we're looking at.

Once we've found the sizes of all the basins, we take the three largest sizes, multiply them together, and we have our answer.

Day9/Part2.py

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 `````` ``````from collections import defaultdict from math import prod data = defaultdict(lambda:9) with open("input.txt", "r", encoding="utf-8") as infile: raw = infile.read().split('\n') numRows = len(raw) numCols = len(raw) for r, row in enumerate(raw): for c, col in enumerate(row): data[(r, c)] = int(col) basins = list() #Find the low point for each bsain (as in part 1) for r in range(numRows): for c in range(numCols): if all([data[(r, c)] < data[(r + deltar, c + deltac)] for deltar in [-1, 0, 1] for deltac in [-1, 0, 1] if (deltar*deltac == 0 and deltar != deltac)]): basins.append([(r, c),]) #Flood fill each basin until it hits a wall basinLengths = [] for b in basins: for pos in b: b.extend([(pos + deltar, pos + deltac) for deltar in [-1, 0, 1] for deltac in [-1, 0, 1] if (deltar*deltac == 0 and deltar != deltac and data[(pos + deltar, pos + deltac)] != 9 and (pos + deltar, pos + deltac) not in b)]) basinLengths.append(len(b)) print(f"Solution: {prod(sorted(basinLengths, reverse=True)[:3])}")``````

Scroll to see complete code

## Day 10 - Syntax Scoring

#### Part 1

Today's part 1 is not too hard if you understand the concept of a stack - a list from which things are only added or removed from the end. Our latest character can always be an opening bracket of some kind (starting a new chunk) or a closing bracket. For a closing bracket, if it matches the last opening bracket in our stack, pop the last opening bracket off the stack and throw both of them away. If it doesn't match, we've found our first illegal character and can stop and score.

Day10/Part1.py

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 `````` ``````with open ("input.txt", "r", encoding='utf-8') as infile: data = infile.read().split("\n") lefts = [ '(', '[', '{', '<' ] rights = [ ')', ']', '}', '>' ] points = [ 3, 57, 1197, 25137] totalScore = 0 for line in data: stack = list() for char in line: if char in lefts: stack.append(char) elif char in rights: lastLeft = stack.pop() if lefts.index(lastLeft) != rights.index(char): totalScore += points[rights.index(char)] break else: raise ValueError(f"Unkown character {char}") else: continue print(f"{totalScore= }")``````

Scroll to see complete code

#### Part 2

For part 2, we'll score our incomplete lines if and only if there are no corrupt characters in the line; that is, if we reach the end of iterating through the line without hitting a corrupt character. This is what the `for...else` syntax achieves. We hand off these incomplete lines to the `autocompleteScore` method for scoring, append those scores to the list, and find the middle (median) element at the end.

Day10/Part2.py

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 `````` ``````from statistics import median with open ("input.txt", "r", encoding='utf-8') as infile: data = infile.read().split("\n") lefts = [ '(', '[', '{', '<' ] rights = [ ')', ']', '}', '>' ] points = [ 1, 2, 3, 4 ] scores = list() def autocompleteScore(stack): score = 0 for item in stack[::-1]: score = (score * 5) + points[lefts.index(item)] return score for line in data: stack = list() for char in line: if char in lefts: stack.append(char) elif char in rights: lastLeft = stack.pop() if lefts.index(lastLeft) != rights.index(char): break else: raise ValueError(f"Unkown character {char}") else: scores.append(autocompleteScore(stack)) print(f"{median(scores)= }")``````

Scroll to see complete code

## Day 11 - Dumbo Octopus

#### Part 1

We're getting deeper and deeper into coding ideas now; today's part 1 introduces a challenge which requires is to iterate over a data set, performing a unique operation as many times as we're able until we're unable to any longer.

Once again I'm making sure of a dataclass to hold the state of each octopus, as well as lazy dictionary which allows us to treat the grid points outside of our area of interest as infinite sinks of energy.

Day11/Part1.py

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 `````` ``````from dataclasses import dataclass @dataclass class OctoData: intensity: int flashedThisStep: bool class lazyDict(dict): def __missing__ (self, key): self[key] = OctoData(intensity=0, flashedThisStep = False) return self[key] grid = lazyDict() with open("input.txt", "r", encoding="utf-8") as infile: data = infile.read().split('\n') numRows = len(data) numCols = len(data) #Load data into dict for r in range(numRows): for c in range (numCols): grid[(r, c)] = OctoData(intensity = int(data[r][c]), flashedThisStep = False) def printGrid(printFlashes = False ): for r in range(numRows): for c in range(numCols): val = grid[(r,c)].intensity if val <= 9: print(val, end = "") else: print("-", end = "") print("") numSteps = 100 numFlashes = 0 for step in range(numSteps): #Increment by 1 for r in range(numRows): for c in range(numCols): grid[(r,c)].intensity += 1 while True: anyFlashesThisRound = False #Flash as necesasry for r in range(numRows): for c in range(numCols): if grid[(r,c)].intensity > 9 and grid[(r,c)].flashedThisStep == False: grid[(r,c)].flashedThisStep = True numFlashes += 1 anyFlashesThisRound = True for deltar in [-1,0,1]: for deltac in [-1,0,1]: if not(deltar == 0 and deltac == 0): grid[(r + deltar, c + deltac)].intensity += 1 fts = [grid[(r,c)].flashedThisStep for r in range(numRows) for c in range(numCols)] if not anyFlashesThisRound: break for r in range(numRows): for c in range(numCols): if grid[(r,c)].flashedThisStep: grid[(r,c)].intensity = 0 grid[(r,c)].flashedThisStep = False print("--") print("final:") printGrid() print(f"Number of Flashes: {numFlashes}")``````

Scroll to see full code

#### Part 2

Part 2 is very similar to part 1, except instead of tracking the total number of octopus flashes, we want to know on what step all the octopuses flash at once. The code is quite similar; I've highlighted the key changes in the following code

Day11/Part2.py

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 `````` ``````from dataclasses import dataclass @dataclass class OctoData: intensity: int flashedThisStep: bool class lazyDict(dict): def __missing__ (self, key): self[key] = OctoData(intensity=0, flashedThisStep = False) return self[key] grid = lazyDict() with open("input.txt", "r", encoding="utf-8") as infile: data = infile.read().split('\n') numRows = len(data) numCols = len(data) #Load data into dict for r in range(numRows): for c in range (numCols): grid[(r, c)] = OctoData(intensity = int(data[r][c]), flashedThisStep = False) def printGrid(printFlashes = False ): for r in range(numRows): for c in range(numCols): val = grid[(r,c)].intensity if val <= 9: print(val, end = "") else: print("-", end = "") print("") stepNumber = 0 printGrid() print("--") while True: stepNumber += 1 #Increment by 1 for r in range(numRows): for c in range(numCols): grid[(r,c)].intensity += 1 while True: anyFlashesThisRound = False #Flash as necesasry for r in range(numRows): for c in range(numCols): if grid[(r,c)].intensity > 9 and grid[(r,c)].flashedThisStep == False: grid[(r,c)].flashedThisStep = True anyFlashesThisRound = True for deltar in [-1,0,1]: for deltac in [-1,0,1]: if not(deltar == 0 and deltac == 0): grid[(r + deltar, c + deltac)].intensity += 1 fts = [grid[(r,c)].flashedThisStep for r in range(numRows) for c in range(numCols)] if not anyFlashesThisRound: break for r in range(numRows): for c in range(numCols): if grid[(r,c)].flashedThisStep: grid[(r,c)].intensity = 0 grid[(r,c)].flashedThisStep = False if sum([grid[(r,c)].intensity for r in range(numRows) for c in range(numCols)]) == 0: break print("--") print("final:") printGrid() print(f"All flashed on step {stepNumber}")``````

Scroll to see full code

## Day 12 - Passage Pathing

#### Part 1

I'm not 100% proud of my solution to today's problems, though it definitely works. Mostly, the way I'm generating the possible-next routes from the currently-arrived-at-room for any given path is just a little hacky. I'm getting a list of all paths (pairs of connected caves) that include the current cave, then finding the element in that path that isn't the current cave. I have to loop through the full list of cave connections every time I want to do this, rather than generating a list of possible connections for each cave out the outset. The efficiency hit here is significant, but for the data size in the problem, it turns out to be fine.

Day12/Part1.py

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 `````` ``````from dataclasses import dataclass with open("input.txt", "r", encoding="utf-8") as infile: data = [line.split('-') for line in infile.read().split('\n')] @dataclass class Route(): pathSoFar: list currentCave: str smallCavesVisited: list startingPaths = [path for path in data if 'start' in path] routesInProgress = [Route(pathSoFar=[s], smallCavesVisited= ['start'] if not(all([item == item.lower() for item in s])) else s, currentCave = list(set(s) - {'start'})) for s in startingPaths] completeRoutes = list() while(len(routesInProgress) > 0): nextRoutes = list() for r in routesInProgress: if r.currentCave == 'end': completeRoutes.append(r) else: #Get all path segments including hte current room nextPaths = [path for path in data if r.currentCave in path] for p in nextPaths: #Get the room this path segment would lead to (it's the room that's not our current room) nextCave = [item for item in p if item != r.currentCave] #Can't go to a little room twice if nextCave not in r.smallCavesVisited: newPath = r.pathSoFar + [p] if nextCave == nextCave.lower(): #If we're now going to be in a little room, add it to the list of little rooms we've visited newSmallCaves = r.smallCavesVisited + [nextCave] else: #Otherwise, the list of little rooms visited doens't change newSmallCaves = r.smallCavesVisited nextRoutes.append(Route(pathSoFar = newPath, smallCavesVisited = newSmallCaves, currentCave = nextCave)) else: pass routesInProgress = nextRoutes print(f"Total routes: {len(completeRoutes)}")``````

Scroll to see fulll code

#### Part 2

For part 2, we'll need to track not only which small caves we've visited, but how many times we've visited them. So we'll need the Route object to have, not just a list of small caves, but a `dict` with keys as small caves and values of how many times we've been there. Then, we'll change the criteria for whether we can visit a small cave next to include the possibility of visited a small cave twice if we've yet to visit any small cave twice.

Day12/Part2.py

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 `````` ``````from dataclasses import dataclass with open("input.txt", "r", encoding="utf-8") as infile: data = [line.split('-') for line in infile.read().split('\n')] @dataclass class Route(): pathSoFar: list currentCave: str smallCavesVisited: dict #['a', numberOfTimesVisited]. This is the key change startingPaths = [path for path in data if 'start' in path] routesInProgress = list() for p in startingPaths: route = p.copy() s = p.copy() s.remove('start') current = s if s == s.lower(): smalls = {'start':0, str(s):1} else: smalls = {'start':0} routesInProgress.append(Route(pathSoFar=','.join(route), smallCavesVisited = smalls, currentCave = current)) completeRoutes = list() while(len(routesInProgress) > 0): nextRoutes = list() for r in routesInProgress: if r.currentCave == 'end': completeRoutes.append(r) else: nextPaths = [path for path in data if r.currentCave in path and 'start' not in path] for p in nextPaths: nextCave = [item for item in p if item != r.currentCave] if nextCave not in r.smallCavesVisited or (r.smallCavesVisited[nextCave] == 1 and not any([(v >= 2) for v in r.smallCavesVisited.values()])): newPath = r.pathSoFar +',' + nextCave newSmallCaves = r.smallCavesVisited.copy() if nextCave == nextCave.lower(): if nextCave in r.smallCavesVisited: newSmallCaves[nextCave] += 1 else: newSmallCaves[nextCave] = 1 nextRoutes.append(Route(pathSoFar = newPath, smallCavesVisited = newSmallCaves, currentCave = nextCave)) routesInProgress = nextRoutes print(f"Total routes: {len(completeRoutes)}")``````

Scroll to see fulll code

## Day 13 - Transparent Origami

#### Part 1

A surprisingly easy challenge for day 13, I thought. Basically, for a list of points, which have (x or y as appropriate) coodinates greater than a given number, then reflect that point over a given line. So we do a little data parsing, and we use Python `sets` to eliminate duplicates.

Day13/Part1.py

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 `````` ``````import re with open("input.txt", "r", encoding="utf-8") as infile: data = infile.read().split('\n\n') points = set([(int(line.split(",")), int(line.split(","))) for line in data.split('\n')]) foldPattern = r'fold along (.)=(\d+)' folds = [(re.search(foldPattern, line).group(1),int(re.search(foldPattern, line).group(2))) for line in data.split('\n')] def executeFold(points, f): if f == 'x': return doXFold(points, f) elif f == 'y': return doYFold(points, f) else: raise ValueError(f"Expected fold in x or y, got fold {f}") def doXFold(points, f): return set([p if p < f else (f - (p - f), p) for p in points]) def doYFold(points, f): retSet = set() for p in points: if p < f: retSet.add(p) else: retSet.add((p, f - (p - f))) return retSet def printPoints(points): maxX = max([p for p in points]) maxY = max([p for p in points]) for y in range(maxY+1): for x in range(maxX+1): if (x, y) in points: print("X", end = "") else: print(".", end = "") print("") if __name__ == "__main__": print(f"{len(executeFold(points, folds))= }")``````

Scroll to see fulll code

#### Part 2

And, since the first part sets up the general mechanics of the problem, all we need to do for part 2 is execute all the folds, then print out the formatted output.

For brevity, here's the only change required for part 2:

Day13/Part2.py (Partial)

 ``````35 36 37 38 `````` ``````if __name__ == "__main__": for f in folds: points = executeFold(points, f) printPoints(points)``````

## Day 14 - Extended Polymerization

#### Part 1

There were lots of jokes on /r/adventofcode today about this being a return to the lanternfish we saw on day 6. Indeed, it has a similar flavor, with an expotentially-increasing processing space that you can brute-force your way through in part 1, if you want, but that will hose you for part 2.

The brute-forcing is easy though! For each pair of letters in the current step, we add a new letter in between them based on the rules given in our input. This means our list of letters doubles in length every step, but at only 10 steps, we should be fine, right?

Day14/Part1.py

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 `````` ``````import re from collections import Counter with open("input.txt", "r", encoding="utf-8") as infile: data = infile.read().split("\n\n") template = data rules = dict() for line in data.split('\n'): r = re.search(r'(..) -> (.)', line) rules[r.group(1)] = r.group(2) def doStep(template): additions = [" "] * len(template) for i in range(len(template[:-1])): letterPair = template[i:i+2] if letterPair in rules: additions[i] = rules[letterPair] return ''.join([val for pair in zip(template, additions) for val in pair] + [template[-1]]) for i in range(10): template = doStep(template) counts = Counter(template) lCount = sorted(counts.items(), key=lambda x: x) minimum, maximum = lCount, lCount[-1] print(f"Result is {maximum - minimum= }")``````

Scroll to see fulll code

#### Part 2

...oh, now it's 40 steps. Dang.

Thankfully, just like with those dang lanternfish, we don't actually have the store the whole list of letters between each round. The key observation is that each pair of letters geneates a unique pair of pairs of letters for the next step. E.g., for the example input, the pair `NN` combined with the rule `NN -> C` means that if there is a one pair NN at the beginning of a step, there will be one `NC` and one `CN` after that step. Or at least, one of each contributed by the `NN`, as there could be more `CN`'s and `NC`'s generated by other rules.

But, we can store the possible letter combinations in a dictionary which tracks their count, and then apply these rules at each step to get our answer. We do have to be a little clever about counting up letters at the end - if we total up the counts from each pair a given letter is in, we'll get double our answer... except for the first and last characters of our string, which will be counted exactly 1 less time. Thankfully, the first and laster letters never change under any rule, so we can note those right at the beginning of our code and account for them later.

Day14/Part2.py

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 `````` ``````import re with open("input.txt", "r", encoding="utf-8") as infile: data = infile.read().split("\n\n") firstLetter = data lastLetter = data[-1] template = dict() for i in range(len(data)-1): letterPair = data[i:i+2] template[letterPair] = (template[letterPair] + 1 if letterPair in template else 1) rules = dict() for line in data.split('\n'): r = re.search(r'(..) -> (.)', line) rules[r.group(1)] = (r.group(1) + r.group(2), r.group(2) + r.group(1)) def doStep(template): newTemplate = dict() for pairOfLetters in template: nextPairOne = rules[pairOfLetters] newTemplate[nextPairOne] = (newTemplate[nextPairOne] + template[pairOfLetters]) if nextPairOne in newTemplate else template[pairOfLetters] nextPairTwo = rules[pairOfLetters] newTemplate[nextPairTwo] = (newTemplate[nextPairTwo] + template[pairOfLetters]) if nextPairTwo in newTemplate else template[pairOfLetters] return newTemplate def getLetterCounts(template): letterCounts = dict() for pair in template: letterCounts[pair] = (template[pair] + letterCounts[pair]) if pair in letterCounts else template[pair] letterCounts[pair] = (template[pair] + letterCounts[pair]) if pair in letterCounts else template[pair] letterCounts[firstLetter] += 1 letterCounts[lastLetter] += 1 return {key: val/2 for key, val in letterCounts.items()} for _ in range(40): template = doStep(template) lCount = sorted(getLetterCounts(template).items(), key = lambda x: x) minimum, maximum = lCount, lCount[-1] print(f"Result is {maximum - minimum= }")``````

Scroll to see fulll code

## Day 15 - Chiton

#### Part 1

Dolor velit incididunt cillum incididunt sint amet reprehenderit commodo magna Lorem proident duis do.

Day14/Part1.py

 ``````1 `````` ``#some code here``

Scroll to see fulll code

#### Part 2

Pariatur incididunt veniam tempor eiusmod sunt id labore occaecat nostrud fugiat.

At this point, I thought it might be useful to try to optimize my algorithm a little bit by tweaking my heuristic distance function.

Day14/Part2.py

 ``````1 `````` ``#some code here``

Scroll to see fulll code

## Day 15 - Chiton

#### Part 1

A pathfinding day! We'll use a modified A* pathfinding algorithm to start this one, but where the H-value of each space (the heurtistic that's usually based on cartesian distance to the endpoint) is zero.

As part of the development and debugging process, I took the opportunity to explore some terminal-based display methods, using the curses library. (Well, on windows, the windows-curses port of the same). The map-utils file and the mapDisplay class allow for single-stepping the map pathfinding while exploring the value at each space.

Day15/Part1.py

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 `````` ``````from dataclasses import dataclass from typing import Any from termcolor import colored, cprint from maputils import mapDisplay from astarutils import calc_h_cost showMaps = False with open("input.txt", "r", encoding="utf-8") as infile: data = infile.read().split('\n') risk = dict() for y, line in enumerate(data): for x, val in enumerate(line): risk[(x, y)] = int(val) maxY = len(data) maxX = len(data) @dataclass class PointData(): f_cost: int parent: Any def getNeighbors(point): nList = list() for delta in [(-1,0),(0,1),(1,0),(0,-1)]: testPoint = (point+delta, point + delta) if (0 <= testPoint < maxX) and (0 <= testPoint < maxY): nList.append(testPoint) return nList def printMap(openPoints, closedPoints, activePoint): for y in range(maxY): for x in range(maxX): val = risk[(x,y)] if (x,y) == activePoint: cprint(val, 'grey', 'on_green', end="") elif (x,y) in closedPoints: cprint(val, 'red', end="") elif (x,y) in openPoints: cprint(val, 'green', end="") else:cprint(val, 'white', end="") print("") def findPath(start, end): locationScores = {start: PointData(f_cost = 0, parent=None)} openPoints = {start} closedPoints = set() oldSelection = [0,0] while True: if showMaps: m = mapDisplay(maxX, maxY, risk, locationScores=locationScores, openPoints=openPoints, closedPoints=closedPoints, oldSelection = oldSelection) if m.retCode['exitcode'] == 1: exit() else: oldSelection = m.retCode['selection'] costList = sorted([p for p in openPoints], key= lambda p:locationScores[p].f_cost) if len(costList) > 0: lowestCostPoint = costList else: break #??? #printMap(openPoints, closedPoints, lowestCostPoint) #print(f"Cheapest next point is {lowestCostPoint}:{locationScores[lowestCostPoint]}") if lowestCostPoint == end: break closedPoints.add(lowestCostPoint) openPoints.remove(lowestCostPoint) for newPoint in getNeighbors(lowestCostPoint): if newPoint not in closedPoints: #print(f"Exploring neighbor {newPoint} of {lowestCostPoint}") if newPoint not in openPoints: # or (risk[newPoint] + cost(lowestCostPoint, closedPoints[lowestCostPoint])) < 100000000: #TODO or new path to neighbor is cheaper newFCost = locationScores[lowestCostPoint].f_cost + calc_h_cost(newPoint, end) + risk[newPoint] locationScores[newPoint] = PointData(f_cost=newFCost, parent = lowestCostPoint) if newPoint not in openPoints: openPoints.add(newPoint) else: pass scoringPoint = lowestCostPoint totalRisk = 0 pathPoints = [scoringPoint] #print("Calculating Path Score:") while locationScores[scoringPoint].parent != None: if showMaps: m = mapDisplay(maxX, maxY, risk, locationScores=locationScores, openPoints=openPoints, closedPoints=closedPoints, pathPoints=pathPoints, oldSelection = oldSelection, pathLength=totalRisk) if m.retCode['exitcode'] == 1: exit() else: oldSelection = m.retCode['selection'] totalRisk += risk[scoringPoint] scoringPoint = locationScores[scoringPoint].parent pathPoints.append(scoringPoint) #totalRisk -= risk[(0,0)] print(f"{totalRisk= }") if __name__ == '__main__': findPath((0,0), (maxX-1, maxY-1))``````

Scroll to see full code

Day15/maputils.py

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 `````` ``````import curses from time import sleep from astarutils import calc_h_cost class mapDisplay(): def __init__(self, maxX, maxY, risk, locationScores=[], openPoints=[], closedPoints=[], pathPoints = [], oldSelection=[0,0], end=None, pathLength = 0): self.maxX = maxX self.maxY = maxY self.risk = risk self.locationScores = locationScores self.openPoints = openPoints self.closedPoints = closedPoints self.selection = oldSelection self.pathPoints = pathPoints self.pathLength = pathLength self.retCode = {'exitcode':0, 'selection': self.selection } if end == None: self.end = (maxX-1, maxY-1) else: self.end = end screen = curses.initscr() screen.keypad(True) curses.start_color() #color pair 0 is white on black standard curses.init_pair(1, curses.COLOR_GREEN, curses.COLOR_BLACK) #1 - open points curses.init_pair(2, curses.COLOR_RED, curses.COLOR_BLACK) #2 - closed points curses.init_pair(3, curses.COLOR_YELLOW, curses.COLOR_BLACK) #3 - end point curses.init_pair(4, curses.COLOR_MAGENTA, curses.COLOR_BLACK) #4 - final path curses.init_pair(10, curses.COLOR_BLACK, curses.COLOR_WHITE) #11 - open points highlighted curses.init_pair(11, curses.COLOR_BLACK, curses.COLOR_GREEN) #11 - open points highlighted curses.init_pair(12, curses.COLOR_BLACK, curses.COLOR_RED) #12 - closed points highlighted curses.init_pair(13, curses.COLOR_BLACK, curses.COLOR_YELLOW) #13 - end point curses.init_pair(14, curses.COLOR_BLACK, curses.COLOR_MAGENTA) #14 - final path self.map_pad = curses.newpad(maxY+1,maxX+1) self.info_pad = curses.newpad(7, 40) self.info_pad.addstr(0,0,"Coords:") self.info_pad.addstr(1,0,"F_Cost:") self.info_pad.addstr(2,0,"G_Cost:") self.info_pad.addstr(3,0,"H_Cost:") self.instruction_pad = curses.newpad(5,40) self.instruction_pad.addstr(0,0,"Arrow keys to move") self.instruction_pad.addstr(1,0,"Enter to advance") self.instruction_pad.addstr(2,0,"Esc to hard quit") self.open_pad = curses.newpad(200,20) self.open_pad.addstr(0,0,"Open Points", curses.A_UNDERLINE) curses.noecho() self.redraw() while True: c = screen.getch() if c == 10: #Enter to continue self.retCode['exitcode'] = 0 break elif c == 27: #Escape to quit self.retCode['exitcode'] = 1 break elif c == 100: #d self.redraw() elif c == 50 or c == 456: #numpad down self.selection = min(self.selection + 1, maxY) self.redraw() elif c == 56 or c == 450: #numpad up self.selection = max(self.selection-1, 0) self.redraw() elif c == 52 or c == 452: #numpad left self.selection = max(self.selection-1, 0) self.redraw() elif c == 54 or c == 454: #numpad right self.selection = min(self.selection+1, maxX) self.redraw() def redraw(self): #pad, maxX, maxY, risk, locationScores=[], openPoints=[], closedPoints=[], selection=[0,0]): self.updateMapPad() self.update_info_pad() self.update_instruction_pad() self.update_open_pad() def updateMapPad(self): for x in range(self.maxX): for y in range (self.maxY): if [x, y] == self.selection: if (x,y) == self.end: color = curses.color_pair(13) elif (x,y) in self.pathPoints: color = curses.color_pair(14) elif (x,y) in self.openPoints: color = curses.color_pair(11) elif (x,y) in self.closedPoints: color = curses.color_pair(12) else: color = curses.color_pair(10) else: if (x,y) == self.end: color = curses.color_pair(3) elif (x,y) in self.pathPoints: color= curses.color_pair(4) elif (x,y) in self.openPoints: color = curses.color_pair(1) elif (x,y) in self.closedPoints: color = curses.color_pair(2) else: color = curses.color_pair(0) self.map_pad.addch(y, x, str(self.risk[(x,y)]), color) self.map_pad.refresh(0,0,0,0,curses.LINES-1,40) def update_info_pad(self): #Coordinates self.info_pad.addstr(0,10," ") self.info_pad.addstr(0,10,str(self.selection)) #F Cost self.info_pad.addstr(1,10," ") if tuple(self.selection) in self.locationScores: self.info_pad.addstr(1,10,str(self.locationScores[tuple(self.selection)].f_cost) + " ") self.info_pad.addstr(2,10,str(self.locationScores[tuple(self.selection)].g_cost) + " ") else: self.info_pad.addstr(1,10,"Unknown") self.info_pad.addstr(2,10,"Unknown") #H Cost self.info_pad.addstr(3,10," ") self.info_pad.addstr(3,10,str(calc_h_cost(self.selection, self.end))) if self.pathPoints != []: self.info_pad.addstr(4,0,"Path Length:") self.info_pad.addstr(5,0,str(self.pathLength)) else: self.info_pad.addstr(4,0,"Searching...") self.info_pad.refresh(0,0,0,40,5,80) def update_instruction_pad(self): self.instruction_pad.refresh(0,0,10,40,12,60) def update_open_pad(self): pointList = sorted(self.openPoints[:min(len(self.openPoints), 99)], key= lambda x:self.locationScores[x].f_cost) for i, p in enumerate(pointList): self.open_pad.addstr(i+1,0,f"{p} - {self.locationScores[p].f_cost}") self.open_pad.refresh(0,0,0,70,10,100)``````

Scroll to see full code

#### Part 2

Thankfully, the algorithm from part 1 is efficient enough to be used in the larger data size in part 2. For brevity, here's just the input-generating lines of part 2; the algorithm is the same.

Day15/Part2.py (partial)

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 `````` ``````with open("input.txt", "r", encoding="utf-8") as infile: data = infile.read().split('\n') originalRisk = dict() for y, line in enumerate(data): for x, val in enumerate(line): originalRisk[(x, y)] = int(val) original_maxY = len(data) original_maxX = len(data) risk = dict() for x_copy in range(5): for y_copy in range(5): for i in range(original_maxX): for j in range(original_maxY): risk[(x_copy*original_maxX + i, y_copy*original_maxY + j)] = (originalRisk[(i,j)] + x_copy + y_copy - 1) % 9 + 1 maxY = original_maxY * 5 maxX = original_maxX * 5 totalPoints = maxY * maxY``````

Scroll to see full code

## Day 17 - Trick Shot

-->

#### Part 1

Part one of today's challenge can be solved by logical deduction with a minimum of coding. With the movement described, a probe moving upward will always pass though y=0 on its way back down; the fastest speed it can reach at this point is when its next step just clips the bottom of the target area, ie. when its downward speed is equal to the lower y coordinate of our input. Because the y speed increases downward by 1 unit per timestep, the highest point on its trajectory is the sum of all speeds up to and including this one. That is, our solution will be the sum of all numbers up to and including our lower-y bound.

I solved this one using the Python REPL as a calculator using `sum(range(maxY))`, but as an actual script it might look like:

Day17/Part1.py

 ``````1 2 3 4 5 6 7 `````` ``````import re with open("input.txt", "r", encoding="utf-8") as infile: data = infile.read() maxY = int(re.search(r'y=(-?\d+)', data).group(1)) print(sum(range(abs(maxY))))``````

#### Part 2

There might be a similarly clever way to reason about part 2, but I elected to just find the solutions by iterating over the (fairly reasonable) possibilities for the starting velocity. I got a little fancy with a dataclass and NamedTuple for the current location and target area, but that's not strictly necessary.

Day17/Part2.py

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 `````` ``````import re from typing import NamedTuple from dataclasses import dataclass with open("input.txt", "r", encoding="utf-8") as infile: data = infile.read() reg = re.search(r'x=(\d+)\.\.(\d+), y=(-?\d+)\.\.(-?\d+)', data) class region(NamedTuple): minX: int maxX: int minY: int maxY: int def pointIn(self, x, y): return (self.minX <= x <= self.maxX) and (self.minY <= y <= self.maxY) @dataclass class point(): x: int y: int target = region(minX = int(reg.group(1)), maxX = int(reg.group(2)), minY = int(reg.group(3)), maxY = int(reg.group(4))) input(target) validInitialVelocities = set() #Highest Y initial speed is abs(maxY) as in part 1 #Lowest Y initial speed is minY #Highest X initial speed is abs(maxX) (or we'll definitely overshoot) #Lowest X initial speed is 1 for initialSpeed_X in range(1, target.maxX+1): for initialSpeed_Y in range(target.minY, abs(target.minY)): currentXSpeed = initialSpeed_X currentYSpeed = initialSpeed_Y #print(f"Examining intial speed {(initialSpeed_X, initialSpeed_Y)}") loc = point(x=0, y=0) while (loc.y > target.minY - 1 and loc.x < target.maxX+1): if target.pointIn(loc.x, loc.y): validInitialVelocities.add((initialSpeed_X, initialSpeed_Y)) #print(f"Found valid velocity {(initialSpeed_X, initialSpeed_Y)}") break loc.x += currentXSpeed loc.y += currentYSpeed currentXSpeed = max(currentXSpeed - 1, 0) currentYSpeed -= 1 print(f"{len(validInitialVelocities)= }")``````

Scroll to see full code

-->