Advent of Code 2021

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[0] < pair[1]])

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[0] < t[1]])

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(' ')[0], int(line.split(' ')[1])) for line in infile.read().split('\n')]

horizontal = sum([step[1] for step in data if step[0] == 'forward'])
depth = sum([step[1] for step in data if step[0] == 'down']) - sum([step[1] for step in data if step[0] == '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(' ')[0], int(line.split(' ')[1])) 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[0])):
    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[0])):
    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[0], 2)
else: raise ValueError(f"Oxygen Data should only have one element, instead was {oxyData}")

if len(co2Data) == 1: co2Rating = int(co2Data[0], 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[0])):
        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[0], 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[0].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[0]]
    newfishcounts[6] += fishcounts[0]
    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('|')[0].strip().split(" "), outputs = line.split('|')[1].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('|')[0].strip().split(" "), outputs = line.split('|')[1].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[3][0] and seg not in hookupsWithLen[2][0])][0] #know wiring of segment a]

    d_or_g = [seg for seg in 'abcdefg' if (len([h for h in hookupsWithLen[5] 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[4][0]][0] #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']][0]


    b_or_e = [seg for seg in 'abcdefg' if len([h for h in hookupsWithLen[5] 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[6] if seg in h]) == 2][0] #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']][0]


    c_or_f = [seg for seg in 'abcdefg' if len([h for h in hookupsWithLen[5] 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[6] if seg in h]) == 2][0]
    r.segmentAssigns['f'] = [seg for seg in 'abcdefg' if seg in c_or_f and seg != r.segmentAssigns['c']][0]

    #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[0])
    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[0])
    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[0] + deltar, pos[1] + deltac) for deltar in [-1, 0, 1] for deltac in [-1, 0, 1] if (deltar*deltac == 0 and deltar != deltac and data[(pos[0] + deltar, pos[1] + deltac)] != 9 and (pos[0] + deltar, pos[1] + 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[0])

#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[0])

#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'})[0]) 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][0]
                #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[0]
    if s[0] == s[0].lower(): smalls = {'start':0, str(s[0]):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][0]

                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(",")[0]), int(line.split(",")[1])) for line in data[0].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[1].split('\n')]

def executeFold(points, f):
    if f[0] == 'x': return doXFold(points, f)
    elif f[0] == '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[0] < f[1] else (f[1] - (p[0] - f[1]), p[1]) for p in points])

def doYFold(points, f):
    retSet = set()
    for p in points:
        if p[1] < f[1]: retSet.add(p)
        else: retSet.add((p[0], f[1] - (p[1] - f[1])))
    return retSet

def printPoints(points):
    maxX = max([p[0] for p in points])
    maxY = max([p[1] 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[0]))= }")

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[0]
rules = dict()
for line in data[1].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[1])

minimum, maximum = lCount[0][1], lCount[-1][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[0][0]
lastLetter = data[0][-1]

template = dict()
for i in range(len(data[0])-1):
        letterPair = data[0][i:i+2]
        template[letterPair] = (template[letterPair] + 1 if letterPair in template else 1)

rules = dict()
for line in data[1].split('\n'):
    r = re.search(r'(..) -> (.)', line)
    rules[r.group(1)] = (r.group(1)[0] + r.group(2), r.group(2) + r.group(1)[1])

def doStep(template):
    newTemplate = dict()
    for pairOfLetters in template:
        nextPairOne = rules[pairOfLetters][0]
        newTemplate[nextPairOne] = (newTemplate[nextPairOne] + template[pairOfLetters]) if nextPairOne in newTemplate else template[pairOfLetters]

        nextPairTwo = rules[pairOfLetters][1]
        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[0]] = (template[pair] + letterCounts[pair[0]]) if pair[0] in letterCounts else template[pair]
        letterCounts[pair[1]] = (template[pair] + letterCounts[pair[1]]) if pair[1] 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[1])
minimum, maximum = lCount[0][1], lCount[-1][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[0])

@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[0]+delta[0], point[1] + delta[1])
        if (0 <= testPoint[0] < maxX) and (0 <= testPoint[1] < 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[0]
        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[1] = min(self.selection[1] + 1, maxY)
            self.redraw()
        elif c == 56 or c == 450: #numpad up
            self.selection[1] = max(self.selection[1]-1, 0)
            self.redraw()
        elif c == 52 or c == 452: #numpad left
            self.selection[0] = max(self.selection[0]-1, 0)
            self.redraw()
        elif c == 54 or c == 454: #numpad right
            self.selection[0] = min(self.selection[0]+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[0])

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

-->