Advent of code 2022

That time of the year again! I’ve always wanted to do one of these to the end. I don’t guarantee I’ll finish it, but in the meantime, I’ll post here the solutions I come up with for each day, along with some commentaries on how I approached each puzzle.

Here’s the list of days I’ve completed so far, in case this page gets too long to comfortably navigate:

Currently I’m ~8 days behind. I’ll probably try to give a go to the rest of problems, but later this week.

Day 1

The input looks like:

The problem is doing a sum of the numbers, grouped by the new line separations (so, here, 100+200+300, 400, 500+600). Then comes the easy part: you have to get the highest number for part one, then the sum of the top three for part two of the puzzle.

First I thought I could do it in Python, picking all items per row and appending them to a new list until it reaches an empty line, so that you get something easy to sum. The result to sum would be something like:

[100,200,300]
[400]
[500,600]

But then I thought, what the hell, doing it in a Bash oneliner is much more entertaining. I didn’t want to write a full script for what felt like a menial task. My first thought was to divide the output in columns - maybe something like:

100,400,500
200,,600
300,,

This would be as easy as a sum of all the elements of each column in awk, but it was a bit of a pain to produce with paste or such. Then I realized I just had to transform the new lines into pluses (+), replace any consecutive pluses (++) with new lines (effectively grouping the input) and feed to a calculator (I have a sweet spot for bc). Essentially, I wanted to produce this:

100+200+300
400
500+600

My solution is as simple as tr+sed for some basic character substitutions. From there it’s a matter of sorting and extracting the first item (head) for the requirements of the first half of the puzzle:

tr '\n' '+' < input.txt | sed 's/++/\n/g' | bc | sort -rn | head -1

To get the sum of the top 3, I just modified head and added an awk column sum:

tr '\n' '+' < input.txt | sed 's/++/\n/g' | bc | sort -rn | head -3 | awk '{sum += $1} END {print sum}

And that’s it!

Day 2

The input: {A, B, C} is the opponent’s choice and {X, Y, Z} is yours in rock, paper and scissors games. It looks like:

A X
B Y
C Z

The problem is calculating a total winning score, where you are given points for the choice (column 2, where rock=X=1, paper=Y=2, scissors=Z=3) and for winning (6 points) or getting a draw (3 points).

At this point there are several approaches - rock, paper & scissors is a common beginner programmer project. I chose to transform both columns to ordinals, then map the difference between columns to win/lose conditions. I used a bit too much sed for my taste, and a 3x3 choice matrix solution would have been quicker, but I really wanted to make this in bash again (shame on me!). I also learned a couple dirty tricks of awk derivatives.

First, the ascii values: Since all are capital letters, an easy way to get alphabet ordinals would be to convert the first column to ASCII values (values 65 onwards for uppercase letters):

echo $(($(printf '%d' \'A ) -64))
> 1

Turns out regular awk doesn’t have a handy implementation for this… but gwak does as ord()! so you can do this:

gawk -l ordchr '{print $1" = "ord($1)-65, 
    $2 " = " ord($2)-88}' example_input.txt
> A = 0 X = 0
> B = 1 Y = 1
> C = 2 Z = 2

Now it’s a matter of checking the difference, and adjusting the resulting numbers to the win-lose choice matrix.

My final solution for part 1 of this day ended up like this:

choice_points=$(gawk -l ordchr '
    {s+=ord($2)-87} END 
    {print s}'  input.txt)

victory_points=$(gawk -l ordchr '{
    col1=ord($1)-64; 
    col2=ord($2)-88;
    print (col1-col2)}' input.txt |  
    sed 's/0/6/g ; s/3/6/g ; s/-1/0/g ; s/1/3/g ; s/2/0/g' |  
    awk '{sum += $1} END {print sum}')

echo $choice_points+$victory_points | bc

The second variable transforms the letters to ordinals (1-3 for the A-C, 0-2 for the X-Z in this case), so that wins(6 points)=[0|3], draws(3 points)=[1] and loses(0 points)=[-1|2] in the difference between both columns. For example, (elf) ROCK VS PAPER (you) would be here 1-1 = 0 = you win. Then, it’s a matter of summing columns and scores. Note that the order of the substitutions matters.

The second part of the puzzle reveals that {Y,X,Z} actually stood for the desired victory condition! Effectively, the same problem, but departing from the result rather than the choices of you and your opponent. Getting the victory points has few shenanigans:

victory_points=$(gawk -l ordchr '
    {col2=ord($2)-88; score=col2*3}
    {sum+=score} END {print sum}' input.txt)

However, guessing the combinations needed is where I’ll pay my dirty sed pipping above. After some fiddling I ended up dividing between more predictable draws (where you just have to filter the input for draws then pick the numeric value of column 1):

draw_choice_points=$(gawk -l ordchr '
    {col1=ord($1)-64; col2=ord($2)-87}
    {if (col2==2) print $1, col1}' input.txt |
    sort | uniq -c | 
    awk '{col1=$1*$3; sum+=col1} END {print sum}')

And the more lousy win and lose conditions. At this point I gave up with the ASCII approach and I just initialized an array detailing the conditions and applied it to the thing:

rest_choice_points=$(gawk -l ordchr 'BEGIN {
    arr["A X"] = 3 
    arr["B Z"] = 3
    arr["C X"] = 2
    arr["A Z"] = 2
    arr["B X"] = 1
    arr["C Z"] = 1
}{print arr[$0]}' input.txt | sed '/^[[:blank:]]*$/ d' | sort | uniq -c | awk '{res=$1*$2; sum+=res} END {print sum}')

Then the final sum (I told you I like bc!):

echo $victory_points+$draw_choice_points+$rest_choice_points | bc

And that’s it. By the second part it got a bit out of hand with awk (who would have thought that a language released 45 years ago feels awkward?) but it was fun!

Day 3

The input looks like this:

vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDw

The problem is dividing the string evenly, then searching for common characters, then doing a sum of points (1-26 for lowercase letters, 27-52 for uppercase).

This one was easy, I took awk and… nah, kidding, I used python, like a sane person would. Here’s my solution for part 1:

# read input, clean
with open("input.txt") as file:
    input = file.readlines()
input = [line.strip('\n') for line in input]

# divide in two sacks (ns1, ns2), find common characters, append to a list
common_chars = []
for i in input:
    ns1= i[0:len(i)//2]
    ns2= i[len(i)//2:len(i)]
    common = list(set(ns1)&set(ns2))
    common_chars.append(common[0])

# some ASCII conversion and some adjusting for uppercase
priorities = [ord(l.swapcase())-64 for l in common_chars]
priorities = [d-6 if d>26 else d for d in priorities]
print(sum(priorities))

(PS: I was playing around with ChatGPT’s open beta and fed it the for loop above to improve it, and after some gentle prompting it replied with the following working oneliner that doesn’t use sets:)

common_chars = [next((char for char in i[0:len(i)//2] if char in i[len(i)//2:len(i)]), "") for i in input]

Anyway: part two of the puzzle swaps the problem from row based to column-based (in groups of three). So:

# generates list of lists in chunks of 3
# then finds common characters between each of the 3 lists
grouped = [input[i:i+3] for i in range(0, len(input), 3)]
common_chars = []
for i in grouped:
    common_chars.append(list(set(i[0]) & set(i[1]) & set(i[2]))[0])

# same as before
priorities = [ord(l.swapcase())-64 for l in common_chars]
priorities = [d-6 if d>26 else d for d in priorities]
print(sum(priorities))

And that’s it!

Day 4

The input looks like this:

2-4,6-8
2-3,4-5
5-7,7-9
2-8,3-7
6-6,4-6
2-6,4-8

The problem is finding those ranges that fully contain others.

I really didn’t want to keep using awk, but in the end this was a problem too easy to solve with it. Took me about three minutes to solve part 1:

sed 's/-/,/g' example_input.txt      # changes - by , so that it can be treated as a column
    | awk  'BEGIN {FS=","}; 
    {if (($1<=$3 && $2>=$4) ||       
         ($1>=$3 && $2<=$4))
    print $1"-"$2,$3"-"$4}' | wc -l  
# if statement: controls if range 1 is covered by range 2 
# or viceversa
# then some unnecesary pretty printing, and counts output lines

The second part requires you get all ranges that overlap in any way. I found it quicker to calculate how many don’t overlap at all, then rest that number to the total number of lines:

# same as above, but conditions control ranges don't overlap
non_overlapping=$(sed 's/-/,/g' input.txt | 
    awk  ' BEGIN {FS=","}; 
        {if (($1<$3) && ($2<$3) || 
            ($1>$4) && ($2>$4)) 
        print $1"-"$2,$3"-"$4}' | wc -l)
all=$(wc -l < input.txt)
echo $all-$non_overlapping | bc

And that’s it!

Day 5

The input looks like:

    [D]    
[N] [C]    
[Z] [M] [P]
 1   2   3 

move 1 from 2 to 1
move 3 from 1 to 3
move 2 from 2 to 1
move 1 from 1 to 2

The problem is moving the [X] crates in column-based stacks according to the instructions below. A problem of stacks, basically.

First, we divide the input in two big lines: crates and instructions. Luckily, we can just divide at the empty line:

with open("ex_input.txt") as file:
    input = file.readlines()
input = [line.strip('\n') for line in input]

# separates by empty line in two lists: crates, and move instructions 
crates_instructions = [input[:input.index('')], input[input.index('')+1:]]

Getting the “columns” right for the crates input required a bit of tinkering, but ultimately it was simple. Basically I wanted this:

[['[]' '[D]' '[]']
 ['[N]' '[C]' '[]']
 ['[Z]' '[M]' '[P]']]

so that I could get this kind of input, where I could just use python’s pop() to follow the instructions:

[['[Z]', '[N]'], 
 ['[M]', '[C]', '[D]', 
 ['[P]']]

In order to do that I used the following code:

# Create empty crates ("[]")
crates = [re.sub("    ", " [] ", row).strip() for row in crates]

# split by spaces, remove the last line with the numbers as I don't really need it
crates = [crate.split() for crate in crates][:-1]
# to array, for convenience:
crate_array = np.array(crates)

# transpose coordinates, reverse items in each row, end with a list of lists of different lengths
crate_array = crate_array.T
crate_array = np.flip(crate_array, axis= 1)
crates = crate_array.tolist()

# remove empty crates 
# (I only needed them to flip the array comfortably)
for list_crates  in crates:
    list_crates[:] = [item for item in list_crates if item != "[]"]

Then I just need to follow instructions, remove the number of items required and append it to the required stack:

instructions = crates_instructions[1]
for instruction in instructions:
    # takes instruction lines and picks relevant numbers
    inst_list = instruction.split(" ")
    ncrates = int(inst_list[1])
    origin = int(inst_list[3])-1  # -1 because it'll be treated as an index
    destiny = int(inst_list[5])-1 # idem

    # for each required item to move
    for i in range(1,ncrates+1):
        # it pops it from the required stack 
        moving_crate = crates[origin].pop()
        # and appends it elsewhere:
        crates[destiny].append(moving_crate)

# the final output is just joining all the last items of each list in a string:
print(''.join([item[-1].strip('[]') for item in crates]))

Verbose, but not really hard once you figure out the input formatting.

Part two of the puzzle requires the same output, but keeping the order of the removed stack. I modified the instructions block slightly to adjust to this, working with list slices rather than pop():

for instruction in instructions:
    #same as above: 
    inst_list = instruction.split(" ")
    ncrates = int(inst_list[1])
    origin = int(inst_list[3])-1
    destiny = int(inst_list[5])-1
    
    moving_crates = crates[origin][-ncrates:]
    crates[origin] = crates[origin][:-ncrates]
    for single_crate in moving_crates:
        crates[destiny].append(single_crate)

Aaand that’s it!

Day 6

The input looks like:

mjqjpqmgbljsphdztnvjfqwrcgsmlb

The problem is identifying the index of the first group where four unique characters happen (actually, index+4, since m, mj, mjq in the example count towards the number).

My solution is simple: transform each group of four characters to sets (to get unique characters). Control for the length of that set, and move on if it’s less than 4 unique characters.

s,e = 0, 4
marker = set(input[0][s:e])

while len(marker) < 4:
    s+=1
    e+=1
    marker = set(input[0][s:e]) 
print(s+4)

You could make it more terse, probably.

The second part requires that the substring become 14 unique characters. Easy to modify - just change the 4s for 14’s:

s,e = 0, 14
marker = set(input[0][s:e])

while len(marker) < 14:
    s+=1
    e+=1
    marker = set(input[0][s:e])
print(s+14)

And that’s it!

Day 7

The input looks like this:

$ cd /
$ ls
dir a
14848514 b.txt
8504156 c.dat
dir d
$ cd a
$ ls
dir e
29116 f
2557 g
62596 h.lst
$ cd e
$ ls
584 i
$ cd ..
$ cd ..
$ cd d
$ ls
4060174 j
8033020 d.log
5626152 d.ext
7214296 k

The problem is parsing this file structure and doing a sum per directory of file sizes, then outputting… well, actually, the problem is, errr… implementing a tree filesystem. Ugh.

This one was a bit more complicated. My first instinct was that I needed something like this:

[{'/': ['a', 14848514, 8504156, 'd']}
{'a': ['e', 29116, 2557, 62596]}
{'e': [584]}
{'d': [4060174, 8033020, 5626152, 7214296]}]

Where I could apply the following process:

Sum all directories where all elements are integers (here, e and d)
Substitute the names of the directories elsewhere for the sum
Repeat untill all directories are a single integer

Not terrible, but what I actually needed what this:

[{'/': ['a', 14848514, 8504156, 'd'],
 'a': ['e', 29116, 2557, 62596]
 'e': [584],
 'd': [4060174, 8033020, 5626152, 7214296]}]

Mostly because working with lists withing dictionaries within lists was a road to madness. Working like this is way cleaner. Also!! The input example doesn’t match the actual input! That was a lot of fun. So rather, since the same name can appear in different places, you want:

[{'/': ['a', 14848514, 8504156, 'd'],
 '/a': ['e', 29116, 2557, 62596]
 '/a/e': [584],
 '/d': [4060174, 8033020, 5626152, 7214296]}]

After quite some effort I ended up doing this for part one (comments directly on the code):

import re
with open("input.txt") as file:
        input = file.readlines()
input = [line.strip('\n') for line in input]

tree = []
pwd = "/"
for line in input:
    if line.startswith("$ cd"):
        ls = []
        match = re.search("cd (.*)$", line)
        cd_dir = match.group(1)
        
        # store first ls
        if cd_dir == "/":
            # strip if dir
            dir = re.search(r"dir (.*)", line)
            file_size = re.search(r"\d+", line)
            if dir:
                ls.append(pwd+dir.group(1))
            if file_size:
                ls.append(int(file_size.group(0)))

            tree.append({"/" : ls})
        
        if cd_dir != "..":
            if cd_dir != "/":
                pwd = pwd+cd_dir+"/"
                tree.append({pwd : ls})
        if cd_dir == "..":
            pwd = pwd.split("/")
            pwd = [x for x in pwd if x != ""] 
            pwd = pwd[:-1]
            pwd = "/"+"/".join(pwd)+"/"
            pwd = pwd.replace("//","/")
            
    if "$" not in line:
        
        # get dir name if dir
        dir = re.search(r"dir (.*)", line)

        if dir:
            ls.append(pwd+dir.group(1)+"/")
        # get file sizes as int
        file_size = re.search(r"\d+", line)
        if file_size:
            ls.append(int(file_size.group(0)))


# transform list of dictionaries into a megadictionary 
# with all paths 
flat_tree = {}
for d in tree:
    flat_tree.update(d)

After getting the dictionary of dictionaries, it was a matter of replacing the values:

def sum_values(tree):
    for key, values in tree.items():
    # control for done sums
        if isinstance(values, int):
            continue
    
    # if its a list of digits, sum
        if all(isinstance(x, int) for x in values):
            total = sum(values)
            tree.update({key:total})
    return tree

def replace_values(tree):
    tree = sum_values(tree)
    keys = list(tree.keys())
    
    for key, values in tree.items():
        if isinstance(values, list):
            to_check = [x for x in values if isinstance(x, str)]
            for directory in to_check:
                if isinstance(tree[directory], int):
                    values[values.index(directory)] = tree[directory]
                    tree[key] = values

    # recursive call:
    all_values = list(tree.values())
    for i in all_values:
        if not isinstance(i, int):
            replace_values(tree)
            tree = sum_values(tree)
            return tree
        else: 
            return tree

# Run the above code, and filter
result_size = replace_values(flat_tree)
final = {k: v for k, v in result_size.items() if v < 100000}
print("Solution part 1:", sum(final.values()))

Part two requires that you calculate left space in the filesystem, get how much space you need for some update and pick the smallest folder that fulfills that criteria:

# part two
left_space = 70000000-result_size.get("/")
to_free = 30000000-left_space
final2 = {k: v for k, v in result_size.items() if v > to_free}
candidates = list(final2.values())
print("Solution part 2:min(candidates))

Way easier once you have implemented the filesystem! Pew! And that’s it!

Day 8

The input looks like this:

The problem is (succintely) seeing if numbers up, down, left and right of a given tree are smaller than the tree at a given position, and then marking that position and counting a total of marks.

My solution for part one was approaching this as boolean mask, where I just needed to transform the orientation of the input array to adjust to the orientation (from up, from down, from left and from right), then apply a single function that checks for each element if the elements that precede it in the row are smaller.

The input array and function to check it from a certain orientation looked like this:

import numpy as np
with open("input.txt") as file:
            input = file.readlines()
input = [line.strip('\n') for line in input]

digits_input = [list(x) for x in input]
input_array = np.array(digits_input, dtype=int)

def check_array(input_array):
    mask = []
    for row in input_array:
        row_mask = []
        for i in range(len(row)):
            if i == 0:
                row_mask.append(True)
            else:
                posterior = row[:i]
                if all(row[i] > x for x in posterior):
                    row_mask.append(True)
                else:
                    row_mask.append(False*(len(row)-i-1))
        mask.append(row_mask)
    
    mask = np.array(mask,dtype=bool)
    return mask

And the actual transformations for the array to be checked like this:

# set true condition for all elements in edges
edge_mask =  np.zeros_like(input_array, dtype=bool)
edge_mask[0] = True
edge_mask[-1] = True
edge_mask[:,0] = True
edge_mask[:,-1] = True

# left to right
lr_mask = check_array(input_array)

# right to left
rl_array = np.flip(input_array, axis = 1)
rl_mask = check_array(rl_array) 
rl_mask =  np.flip(rl_mask, axis = 1)

# up to down
ud_array = input_array.T
ud_mask = check_array(ud_array)
ud_mask = ud_mask.T

# down to up
du_array = np.flip(input_array.T, axis = 1)
du_mask = check_array(du_array)
du_mask = np.flip(du_mask.T, axis = 0)

# merge arrays:
mask = np.logical_or(lr_mask, edge_mask)
mask = np.logical_or(mask, rl_mask)
mask = np.logical_or(mask, lr_mask)
mask = np.logical_or(mask, ud_mask)
mask = np.logical_or(mask, du_mask)

print("solution 1:", mask.sum())

Not too hard, actually - took me an embarrasing amount of time to come up with this solution, as I was making a function for each orientation and it took a bit of rethinking to make it less complicated.

Part 2 requires that you calculate a scenic score by multiplying the number of numbers that are set to True in the mask: you have to get the highest score. After some fiddling, it ended up like this:

def check_conseqs(tree, list_input):
    """
    checks how many of the trees preceding, following, up or down 
    are bigger than a given tree
    """
    smaller_than_input = []
    # control for edge
    if len(list_input) == 0:
        return 1
    for adj_tree in list_input:
        if tree > adj_tree:
            smaller_than_input.append(tree)
        else:
            return len(smaller_than_input)+1
    return len(smaller_than_input)

def check_score(arr):
    """
    iterates over all trees and calculates the score
    """
    grid_score = []
    for row in range(len(arr)):
        row_score = []
        for tree in range(len(arr[row])):
            following = arr[row][tree:][1:]
            score = check_conseqs(arr[row][tree], following)
            row_score.append(score)

        grid_score.append(row_score)
    scores = np.array(grid_score)
    return scores

#looking right        
lr_scenery = check_score(input_array)

# looking left
rl_scenery = np.flip(check_score(rl_array), axis = 1)

# looking down
ud_scenery = check_score(ud_array)
ud_scenery = ud_scenery.T

# looking up 
du_scenery = check_score(du_array)
du_scenery = np.flip(du_scenery.T, axis = 0)

# sets edges at 0...
edge_mask =  np.ones(input_array.shape, dtype = np.int8)
edge_mask[0] = 0
edge_mask[-1] = 0
edge_mask[:,0] = 0
edge_mask[:,-1] = 0

final_scenery_score = du_scenery*rl_scenery*ud_scenery*lr_scenery*edge_mask
print("solution 2:", np.max(final_scenery_score))

Very similar approach (one function for all calculations, just rotating the input, iterating over rows to create a new array with given scores). I’m sure there was a more efficient way to do this, but well, I’m ok with the “naive” solution.

Day 9

The input looks like a set of instructions to move two elements (head and tail) around a board:

R 4
U 4
L 3
D 1
R 4
D 1
L 5
R 2

The problem is that two elements (head and tail) will be moving, one following instructions and the other tracking it closely.

My solution was to create two classes (one for each element) and just have them move according to the other. I’m refreshed some of my knowledge of classes in Python and feel the final solution is fairly elegant, for once in the last days!

import numpy as np
with open("input.txt") as file:
            input = file.readlines()
input = [line.strip('\n') for line in input]

class head:
    def __init__(self):
        self._v = 0
        self._h = 0

    def coords(self):
        return self._v, self._h

    def move(self, where):
        if where == "R":
            self._h +=1
        if where == "L":
            self._h -=1
        if where == "U":
            self._v +=1
        if where == "D":
            self._v -=1
        return head.coords()

class tail(head):
    def follow_head(self, head_coords, prev_position = None):
        diffv = head_coords[0]-self.coords()[0]
        diffh = head_coords[1]-self.coords()[1]
        
        # in case of diagonal moving needed
        if abs(diffh) == 2 and abs(diffv) == 1 or \
            abs(diffh) == 1 and abs(diffv) == 2:
            # match head previous position
            self._v = prev_position[0]
            self._h = prev_position[1]
            return self.coords()

        # regular moving:
        if diffh > 1:
            self.move("R")
        if diffh < -1:
            self.move("L")
        if diffv > 1:
            self.move("U")
        if diffv < -1:
            self.move("D")

        return self.coords()

head = head()
tail = tail()
record_steps = []

for inst in input:
    inst = inst.split(" ")
    for _ in range(int(inst[1])):
        prev_position = head.coords()
        head.move(inst[0])
        steps = tail.follow_head(head.coords(), prev_position)
        record_steps.append(steps)

# how many unique steps have been taken by tail?
print("Solution 1:",len(set(record_steps))

Part 2 involves adding 10 objects to the grid (sigh). I’m glad I approached this as a class problem, but I didn’t model diagonal movement properly. So much for elegance. What I did is retouch the follwing formula to include diagonal movement cases and track each previous knot’s position (since the cheat of just moving to the last head’s position wasn’t enough now):

import numpy as np
with open("input.txt") as file:
            input = file.readlines()
input = [line.strip('\n') for line in input]

class head:
    def __init__(self):
        self._v = 0
        self._h = 0

    def coords(self):
        return self._v, self._h

    def move(self, where, how=None):
        if where == "R":
            self._h +=1
        if where == "L":
            self._h -=1
        if where == "U":
            self._v +=1
        if where == "D":
            self._v -=1
        # diagonal:
        if where == "UR":
            self._h +=1
            self._v +=1
        if where == "DR":
            self._h +=1
            self._v -=1
        if where == "UL":
            self._h -=1
            self._v +=1
        if where == "DL":
            self._h -=1
            self._v -=1
        return self.coords()

class tail(head):
    def follow_head(self, headcoords, prev_position = None):
        diffv = headcoords[0]-self.coords()[0]
        diffh = headcoords[1]-self.coords()[1]
        #print(diffv, diffh)
        if diffh == 0 or diffv == 0:
                if diffh > 1:
                    self.move("R")
                if diffh < -1:
                    self.move("L")
                if diffv > 1:
                    self.move("U")
                if diffv < -1:
                    self.move("D")
        else:
            if (diffh == 2 and diffv == 1) or (diffh == 1 and diffv == 2): 
                self.move("UR")
            if (diffh == 2 and diffv == -1) or (diffh == 1 and diffv == -2):
                self.move("DR") 
            if (diffh == -2 and diffv == 1) or (diffh == -1 and diffv == 2): 
                self.move("UL")
            if (diffh == -2 and diffv == -1) or (diffh == -1 and diffv == -2): 
                self.move("DL")
            
            if diffh == 2 and diffv == 2:
                self.move("UR")
            if diffh == -2 and diffv == 2:
                self.move("UL")
            if diffh == 2 and diffv == -2:
                self.move("DR")
            if diffh == -2 and diffv == -2:
                self.move("DL")
        
        return self.coords()

part1_head = head()
part1_tail = tail()
record_steps = []

for inst in input:
    inst = inst.split(" ")
    for _ in range(int(inst[1])):
        prev_position = part1_head.coords()
        part1_head.move(inst[0])
        steps = part1_tail.follow_head(part1_head.coords(), prev_position)
        record_steps.append(steps)

print("Solution 1:",len(set(record_steps)))
print("")

part2_head = head()
tail1 = tail()
tail2 = tail()
tail3 = tail()
tail4 = tail()
tail5 = tail()
tail6 = tail()
tail7 = tail()
tail8 = tail()
tail9 = tail()

record_steps = []
for inst in input:
    inst = inst.split(" ")
    for _ in range(int(inst[1])):
        part2_head.move(inst[0])
        tail1.follow_head(part2_head.coords())
        tail2.follow_head(tail1.coords())
        tail3.follow_head(tail2.coords())
        tail4.follow_head(tail3.coords())
        tail5.follow_head(tail4.coords())
        tail6.follow_head(tail5.coords())
        tail7.follow_head(tail6.coords())
        tail8.follow_head(tail7.coords())
        steps = tail9.follow_head(tail8.coords())
        record_steps.append(steps)

print("Solution 2:",len(set(record_steps)))

Aaand that’s it! It’s getting harder! This one took me a bit more of thinking, and I wish I had the time to rewrite it from scratch knowing the second part - I probably would have approached this differently.

Day 10

The input looks like this:

noop
addx 3
addx -5

The problem is computing cycles according to instructions (1 per line, +1 for each addx) and checking a value (X) at certain cycles.

My solution to the first part was a bit trivial, and made me fear the worst for part 2:

import re
with open("input.txt") as file:
    input = file.readlines()

input = [line.strip('\n') for line in input]

X = 1
cycle = 1

cycles = [20, 60, 100, 140, 180, 220]
list_out = []
for line in input:
    if cycle in cycles:
        list_out.append(cycle*X) 

    if line != "noop":
        # match digit
        match = re.search(" (.*\d*)$", line)
        digit = int(match.group(0))
        cycle += 1
        if cycle in cycles:
            list_out.append(cycle*X)
        X += digit
    cycle += 1

print("Solution 1:", sum(list_out))

Part 2… well, it’s a bit complicated to explain. Basically, it requires you print some characters depending on the value of X before.

Here’s my solution:

X = 1
cycle = 1
pixel = 0
crt = []
list_X = []

def draw_crt(cycle, X, crt):
    pixel_position = divmod((cycle-1), 40)
    sprite_position = [X-1, X, X+1]
    if pixel_position[1] in sprite_position:
        crt.append("#")
    else:
        crt.append(".")
    if pixel_position[1] == 39:
        crt.append("\n")
    return crt

for line in input:
    crt = draw_crt(cycle, X, crt)

    if line != "noop":
        # match digit
        match = re.search(" (.*\d*)$", line)
        digit = int(match.group(0))
        cycle += 1 
        crt = draw_crt(cycle, X, crt)
        X += digit
    cycle += 1

crt = "".join(crt)
print("Solution 2:")
print(crt)

And that’s it! 10 out of 25! This one was easier than the latter ones - I think I spent more time trying to get the prompt of part two than actually writing it.

Day 11

The input looks like this:

Monkey 0:
  Starting items: 79, 98
  Operation: new = old * 19
  Test: divisible by 23
    If true: throw to monkey 2
    If false: throw to monkey 3

Monkey 1:
  Starting items: 54, 65, 75, 74
  Operation: new = old + 6
  Test: divisible by 19
    If true: throw to monkey 2
    If false: throw to monkey 0

Monkey 2:
  Starting items: 79, 60, 97
  Operation: new = old * old
  Test: divisible by 13
    If true: throw to monkey 1
    If false: throw to monkey 3

Monkey 3:
  Starting items: 74
  Operation: new = old + 3
  Test: divisible by 17
    If true: throw to monkey 0
    If false: throw to monkey 1

The problem is 1) parsing the notes, 2) creating a monkey class with that info and 3) making the inspect/throw functions.

My solution for this one felt way cleaner than the one I took for the similarly class problem Day 9:

import re
import math

with open("ex_input.txt") as file:
    input = file.read()

input = input.split("\n\n")

class monkey():
    def __init__(self, id, items, operation, test, passed, failed):
        self.id = id
        self.items = items
        self.operation = operation 
        self.test = int(test)
        self.passed = int(passed)
        self.failed = int(failed)
        self.inspected = 0
    
    def inspect(self):
        for item in self.items:
            self.inspected += 1
            worry = eval(self.operation.replace("old", str(item)))//3
            if worry%self.test == 0:
                monkey_list[self.passed].items.append(worry)
            else:
                monkey_list[self.failed].items.append(worry)  
        self.items = [] 

    def monkey_business(self):
        self.inspect()
    
def parse_notes(note):
    """
    parses monkey notes
    """
    monkey_id = re.search("Monkey (\d*)", note).group(1)
    # parse items
    items = re.search("items: ([\d ,]*)", note).group(1)
    items = items.split(", ")

    operation = re.search("new = (.*)", note).group(1)
    test = re.search("by (\d*)", note).group(1)
    true_cond = re.search("true: throw to monkey (\d*)", note).group(1)
    false_cond = re.search("false: throw to monkey (\d*)", note).group(1)
    return monkey_id, items, operation, test,true_cond, false_cond

# parse notes, asign to a list of monkeys
notes = []
for n_monkeys in range(len(input)):
    notes.append(parse_notes(input[n_monkeys]))
monkey_list = [monkey(*notes[x]) for x in range(len(notes))]

# 20 rounds
for _ in range(20):
    for monkey in monkey_list:
        monkey.inspect()

# get inspection metric
inspected = []
for monkey in monkey_list:
    inspected.append(monkey.inspected)
sorted_inspected = sorted(inspected)
print("Solution 1:", math.prod(sorted_inspected[-2:]))

The second part involves no longer dividing by 3 the worry metric, and increasing the rounds to 10000, resulting in slow computation times and big integer overflow.

I admit I had to check hints on this one because my maths game is very very weak. Anyway, in the end it turns out it’s a matter of computing the least common multiple to keep the validation of tests ok without feeding the operation monstruous integers. Makes sense. The implementation is quite trivial: modify the monkey function inspect() to divide by the LCM:

    def inspect(self, lcm):

        for item in self.items:
            self.inspected += 1
            worry = eval(self.operation.replace("old", str(item)))%lcm
            if worry%self.test == 0:
                monkey_list[self.passed].items.append(worry)
            else:
                monkey_list[self.failed].items.append(worry)
    self.items = []

and instead of the 20 rounds, compute the LCM of the tests of all monkeys, feed it into inspect, then increase rounds to 10000:

lcm = []
for monkey in monkey_list:
    lcm.append(monkey.test)
lcm = math.prod(lcm)

for _ in range(10000):
    for monkey in monkey_list:
        monkey.inspect(lcm)

The rest is the same.

I should have realized before, but well… First time I find a similar problem. A signal that I should go back to math principles.