jamhocken
: jamhocken
Table of Contents
- jamhocken
- About me
- Day 00: python
- Day 01: python
- Day 02: python
- Day 03: python
- Day 04: python
- Day 05: python
- Day 06: python
- Day 07: python
- Day 08: python
- Day 09: python
- Day 10: python
- Day 11: python
- Day 12: python
- Day 13: python
- Day 14: python
- Day 15: python
- Day 16: python
- Day 17: python
- Day 18: python
- Day 19: python
- Day 20: python
- Day 21: python
- Day 22: python
- Day 23: python
- Day 24: python
- Day 25: python
jamhocken
Day 00: python
Day 0 of year 2021
Python
I have no time whatsoever and will finish late for sure. But it was so much fun last year that I have to repeat.
Day 01: python
Day 1 of year 2021 https://adventofcode.com/2021/day/1
What I learned
-
I forgot that Python also can do string comparisons. Now, I remember.
Approach
-
For star 1, I just go through the whole list comparing the values pair-wise.
-
For star 2, I created a list with the 3 value window. And then compared that list pair-wise.
Run script
Run the solution with python solution.py
def process_input(file_contents):
lines_stripped = [int(line.strip()) for line in file_contents]
return lines_stripped
def main():
with open("input.txt",'r') as depths_file:
file_lines = depths_file.readlines()
depths = process_input(file_lines)
count = 0
for i in range(len(depths)-1):
if depths[i+1]>depths[i]:
count += 1
print(count)
window = []
for i in range(len(depths)-2):
window.append(depths[i]+depths[i+1]+depths[i+2])
count = 0
for i in range(len(window)-1):
if window[i+1]>window[i]:
count += 1
print(count)
main()Day 02: python
Day 2 of year 2021 https://adventofcode.com/2021/day/2
What I learned
-
Straightforward. :-)
Approach
-
I parse the file and put the command as a string and the value as an int in a list of tuples.
-
For both stars, you go through the list and do what the instructions say to do.
-
Star 2 is then not any more complicated than star 1, just different instructions.
Run script
Run the solution with python solution.py
def process_input(file_contents):
lines_stripped = [line.strip() for line in file_contents]
lines_split = []
for lines in lines_stripped:
line = lines.split()
lines_split.append((line[0], int(line[1])))
return lines_split
def main():
with open("input.txt",'r') as course_file:
course_lines = course_file.readlines()
course = process_input(course_lines)
horizontal = 0
depth = 0
for directions in course:
if directions[0] == 'forward':
horizontal += directions[1]
elif directions[0] == 'up':
depth -= directions[1]
else:
depth += directions[1]
print(horizontal, depth, depth*horizontal)
horizontal = 0
aim = 0
depth = 0
for directions in course:
if directions[0] == 'forward':
horizontal += directions[1]
depth += aim*directions[1]
elif directions[0] == 'up':
aim -= directions[1]
else:
aim += directions[1]
print(horizontal, depth, depth*horizontal)
main()Day 03: python
Day 3 of year 2021 https://adventofcode.com/2021/day/3
What I learned
-
Somehow I don’t understand slices with lists in Python, but at least I do understand it for matrices with Numpy.
-
The whole thing isn’t very elegant, I’m afraid.
Approach
-
I parse the file and put all of the codes into a list of lists.
-
For star 1
-
I take that list of lists and turned it into a Numpy matrix. I then sum each digit over all codes and compare that sum to half of the number of codes to find the majority digit for Gamma.
-
I then used some modula arithmetic to find the inverse Epsilon.
-
Converted to strings, joined it and converted to integers.
-
-
For star 2
-
I go through each digit and cull out the codes that don’t belong to the majority / minority.
-
I recalculate the majority / minority evey run through the loop with a Numpy matrix again.
-
Run script
Run the solution with python solution.py
import numpy as np
def process_input(file_contents):
lines_stripped = [line.strip() for line in file_contents]
bin_digits = [[int(j) for j in list(code)] for code in lines_stripped]
return bin_digits
def main():
with open("input.txt",'r') as diagnostic_file:
diagnostic_lines = diagnostic_file.readlines()
diagnostics = process_input(diagnostic_lines)
diag_matrix = np.matrix(diagnostics)
matrix_size = diag_matrix.shape
no_codes = matrix_size[0]
sum_diag = diag_matrix.sum(0)
sum_diag = sum_diag.tolist()[0]
gamma = int(''.join([str(int(j // (no_codes/2))) for j in sum_diag]),2)
epsilon = int(''.join([str(int(j // (no_codes/2)+1)%2) for j in sum_diag]),2)
print(gamma, epsilon, gamma*epsilon)
if gamma<2**(matrix_size[1]-1):
majority_oxy = 0
majority_co2 = 1
else:
majority_oxy = 1
majority_co2 = 0
candidates_oxy = diagnostics.copy()
candidates_co2 = diagnostics.copy()
i = 0
while len(candidates_oxy)!=1 or len(candidates_co2)!=1:
oxy_temp = candidates_oxy.copy()
co2_temp = candidates_co2.copy()
if len(candidates_oxy) != 1:
for code in oxy_temp:
if code[i]!=majority_oxy:
candidates_oxy.remove(code)
if len(candidates_co2) != 1:
for code in co2_temp:
if code[i]!=majority_co2:
candidates_co2.remove(code)
if i != matrix_size[1]-1:
i += 1
oxy_matrix = np.matrix(candidates_oxy)
sum_oxy = oxy_matrix.sum(0)
sum_oxy = sum_oxy.tolist()[0]
co2_matrix = np.matrix(candidates_co2)
sum_co2 = co2_matrix.sum(0)
sum_co2 = sum_co2.tolist()[0]
if sum_oxy[i] >= len(candidates_oxy)/2:
majority_oxy = 1
else:
majority_oxy = 0
if sum_co2[i] < len(candidates_co2)/2:
majority_co2 = 1
else:
majority_co2 = 0
c_oxy = int(''.join([str(i) for i in candidates_oxy[0]]),2)
c_co2 = int(''.join([str(i) for i in candidates_co2[0]]),2)
print(c_oxy, c_co2, c_oxy*c_co2)
main()Day 04: python
Day 4 of year 2021 https://adventofcode.com/2021/day/4
What I learned
-
I tried out some new functions in Numpy
Approach
-
I parse the file and
-
Create a list of the numbers called
-
Create a list of all of the bingo cards as well as a "marker" card for each of the bingo cards
-
The marker cards are initialized to have the value 1 everywhere.
-
-
For star 1
-
I go through the numbers called and for each bingo card that has that number, I put a zero on the appropriate spot on the marker card.
-
I then check if any of the columns or rows of that marker card are now filled with zeros.
-
If it is the first card to get bingo, I set the "bingo" flag and print out the value for Star 1.
-
-
For star 2
-
I only had to slightly modify the code.
-
I added a set of all of the cards that haven’t won yet. If a card wins, I remove it from the set.
-
I iterate through until the last card has won. And then exit the loop and do the calculation for the answer.
-
Run script
Run the solution with python solution.py
import numpy as np
def process_input(file_contents):
lines_stripped = [line.strip() for line in file_contents]
numbers_called = [int(x) for x in lines_stripped[0].split(",")]
cards = []
i = 2
while i < len(lines_stripped):
bingo_card = []
marker_card = []
for j in range(5):
bingo_card.append([int(x) for x in lines_stripped[i+j].split()])
marker_card.append([1]*5)
cards.append([bingo_card,marker_card])
i += 6
return numbers_called, cards
def main():
with open("input.txt",'r') as bingo_file:
bingo_lines = bingo_file.readlines()
(numbers_called, cards) = process_input(bingo_lines)
card_arrays = [[np.array(bingo_card),np.array(marker_card)] for bingo_card, marker_card in cards]
bingo = 0
j = -1
non_winners = set(range(len(card_arrays)))
nw_temp = non_winners.copy()
while len(non_winners)>0:
j += 1
for i in non_winners:
card_arrays[i][1] = np.where(card_arrays[i][0]==numbers_called[j],0,card_arrays[i][1])
if (~card_arrays[i][1].any(axis=0)).any() or (~card_arrays[i][1].any(axis=1)).any():
if bingo == 0:
bingo = 1
winning_card = i
print(np.sum(np.multiply(card_arrays[winning_card][0],card_arrays[winning_card][1]))*numbers_called[j])
if len(non_winners)==1:
losing_card = i
nw_temp.remove(i)
non_winners = nw_temp.copy()
print(np.sum(np.multiply(card_arrays[losing_card][0],card_arrays[losing_card][1]))*numbers_called[j])
main()Day 05: python
Day 5 of year 2021 https://adventofcode.com/2021/day/5
What I learned
-
I refreshed regex for myself (again).
Approach
-
I parse the file with a regex and create a list of all of the vectors.
-
For star 1
-
I check if the line is vertical and iterate the value in a dictionary for each coordinate on the line.
-
I then check if it is horizontal and do the same.
-
I then check the dictionary for any values more than 1 and sum over the number of those entries.
-
-
For star 2
-
I still do the horizontal and vertical checks.
-
And then do the diagonal lines.
-
I think this could be simplified / shortened, but I didn’t bother.
-
Run script
Run the solution with python solution.py
import re
def process_input(file_contents):
lines_stripped = [line.strip() for line in file_contents]
regex_vectorline = re.compile('(\d+),(\d+)\s\S+\s(\d+),(\d+)')
vectors = sum([[[int(i) for i in j] for j in re.findall(regex_vectorline,lines)] for lines in lines_stripped],[])
return vectors
def star1(vectors):
vents = {}
for vector in vectors:
if vector[0] == vector[2]:
if vector[1]>vector[3]:
y_coordinates = range(vector[3],vector[1]+1)
else:
y_coordinates = range(vector[1],vector[3]+1)
for y in y_coordinates:
if (vector[0],y) in vents:
vents[(vector[0],y)] += 1
else:
vents[(vector[0],y)] = 1
elif vector[1] == vector[3]:
if vector[0]>vector[2]:
x_coordinates = range(vector[2],vector[0]+1)
else:
x_coordinates = range(vector[0],vector[2]+1)
for x in x_coordinates:
if (x,vector[1]) in vents:
vents[x,(vector[1])] += 1
else:
vents[x,(vector[1])] = 1
return vents
def star2(vectors):
vents = {}
for vector in vectors:
if vector[0] == vector[2]:
if vector[1]>vector[3]:
y_coordinates = range(vector[3],vector[1]+1)
else:
y_coordinates = range(vector[1],vector[3]+1)
for y in y_coordinates:
if (vector[0],y) in vents:
vents[(vector[0],y)] += 1
else:
vents[(vector[0],y)] = 1
elif vector[1] == vector[3]:
if vector[0]>vector[2]:
x_coordinates = range(vector[2],vector[0]+1)
else:
x_coordinates = range(vector[0],vector[2]+1)
for x in x_coordinates:
if (x,vector[1]) in vents:
vents[x,(vector[1])] += 1
else:
vents[x,(vector[1])] = 1
else:
if vector[0]>vector[2]:
x_coordinates = range(vector[2],vector[0]+1)
else:
x_coordinates = range(vector[2],vector[0]-1,-1)
if vector[1]>vector[3]:
y_coordinates = range(vector[3],vector[1]+1)
else:
y_coordinates = range(vector[3],vector[1]-1,-1)
for i in range(len(x_coordinates)):
if (x_coordinates[i],y_coordinates[i]) in vents:
vents[x_coordinates[i],y_coordinates[i]] += 1
else:
vents[x_coordinates[i],y_coordinates[i]] = 1
return vents
def main():
with open("input.txt",'r') as vector_file:
vector_lines = vector_file.readlines()
vectors = process_input(vector_lines)
vents = star1(vectors)
critical = sum([1 if value>1 else 0 for value in vents.values()])
print(critical)
vents = star2(vectors)
critical = sum([1 if value>1 else 0 for value in vents.values()])
print(critical)
main()Day 06: python
Day 6 of year 2021 https://adventofcode.com/2021/day/6
What I learned
-
It is straightforward as soon as you see that you only have to count the fish.
Approach
-
I parse the line and convert to integers.
-
Then I count how many fish are in each of the possible fish states (9 of them).
-
For both stars, you just create a loop with the right number of days.
-
You write the number in state 0 into state 8.
-
You add the number from state 7 to the number from state 0 and put it into state 6.
-
All others follow the rule state n is written to state n-1.
-
Run script
Run the solution with python solution.py
def process_input(file_contents):
lines_stripped = [line.strip() for line in file_contents]
fish = [int(i) for i in lines_stripped[0].split(",")]
fish_states = [0]*9
for lf in fish:
fish_states[lf] += 1
return fish_states
def main():
with open("input.txt",'r') as fish_file:
fish_lines = fish_file.readlines()
fish_states = process_input(fish_lines)
for day in range(256):
fish_states_temp = fish_states.copy()
for states in range(len(fish_states)):
if states == 0:
fish_states_temp[8] = fish_states[0]
fish_states_temp[6] = fish_states[0]
elif states == 7:
fish_states_temp[6] += fish_states[7]
else:
fish_states_temp[states-1] = fish_states[states]
fish_states = fish_states_temp
if day == 79:
print(sum(fish_states))
print(sum(fish_states))
main()Day 07: python
Day 7 of year 2021 https://adventofcode.com/2021/day/7
What I learned
-
Straightforward.
Approach
-
I parse the line and convert to integers.
-
For star 1, it’s just statistics.
-
The optimal spot is the median.
-
-
For star 2
-
If you start going through all possible values, it might take a while.
-
So, I used the median as my starting point and looked if the fuel consumption is improved by increasing or decreasing from there.
-
Then, I just iterate through until I come to the other side of the global optimum and take the value before that.
-
-
It’s probably not optimized, but it only takes a few seconds to run.
Run script
Run the solution with python solution.py
import statistics
def process_input(file_contents):
lines_stripped = [line.strip() for line in file_contents]
crabs = [int(i) for i in lines_stripped[0].split(",")]
return crabs
def main():
with open("input.txt",'r') as crab_file:
crab_lines = crab_file.readlines()
crabs = process_input(crab_lines)
# The optimal position is the median for star 1
center = int(statistics.median(crabs))
fuel = 0
for crab in crabs:
fuel += abs(crab-center)
print(fuel)
# The median is a good starting point for star 2
fuel = 0
for crab in crabs:
for i in range(abs(crab-center)):
fuel += i+1
# Is the optimal answer more or less than the median?
fuel_old = fuel
fuel = 0
center_temp = center - 1
for crab in crabs:
for i in range(abs(crab-center_temp)):
fuel += i+1
if fuel < fuel_old:
iterator = -1
else:
iterator = 1
# Iterate until the values start to increase
fuel = fuel_old
while fuel<=fuel_old:
fuel_old = fuel
fuel = 0
center = center + iterator
for crab in crabs:
for i in range(abs(crab-center)):
fuel += i+1
print(fuel_old)
main()Day 08: python
Day 8 of year 2021 https://adventofcode.com/2021/day/8
What I learned
-
Frozen sets and some basic set manipulation in Python.
Approach
-
I parse the line and create 2 lists with the input and output strings
-
For star 1, i just flatten the output list and count all entries with 2,3,4 or 7 letters.
-
For star 2
-
I turned the input and output entries (strings) into frozen sets to avoid messing with ordering.
-
I also sorted the input strings for every entry according to their lengths to minimize searching later.
-
For each input line, I immediately map 1, 7, 4 and 8 since these are only length dependent (I used a dict to hold the mapping).
-
You can logically derive the other ones by using length + looking at which other known numbers are subsets.
-
Then, you just use the dictionary to find the output digits, concatenate them and sum over all lines
-
Run script
Run the solution with python solution.py
def process_input(file_contents):
lines_stripped = [line.strip() for line in file_contents]
inputs = [lines.split("|")[0].split() for lines in lines_stripped]
outputs = [lines.split("|")[1].split() for lines in lines_stripped]
return inputs, outputs
def main():
with open("input.txt",'r') as segment_file:
segment_lines = segment_file.readlines()
inputs,outputs = process_input(segment_lines)
#star 1
uniques = 0
flat_list = [item for sublist in outputs for item in sublist]
for item in flat_list:
if len(item) in [2,3,4,7]:
uniques += 1
print(uniques)
#star 2
inputs = [sorted([frozenset(segment) for segment in i],key=len) for i in inputs]
outputs = [[frozenset(segment) for segment in i] for i in outputs]
sum_digits = 0
for j in range(len(inputs)):
mapping = {inputs[j][0]:1,inputs[j][1]:7,inputs[j][2]:4,inputs[j][9]:8}
for i in [3,4,5]:
if inputs[j][1].issubset(inputs[j][i]):
mapping[inputs[j][i]] = 3
elif (inputs[j][2]- inputs[j][0]).issubset(inputs[j][i]):
mapping[inputs[j][i]] = 5
else:
mapping[inputs[j][i]] = 2
for i in [6,7,8]:
if inputs[j][2].issubset(inputs[j][i]):
mapping[inputs[j][i]] = 9
elif inputs[j][0].issubset(inputs[j][i]):
mapping[inputs[j][i]] = 0
else:
mapping[inputs[j][i]] = 6
digits = int("".join([str(mapping[item]) for item in outputs[j]]))
sum_digits += digits
print(sum_digits)
main()Day 09: python
Day 9 of year 2021 https://adventofcode.com/2021/day/9
What I learned
-
I got the recursion right the first time. (Nothing that I learned, but it’s probably the first time ever for me.)
Approach
-
I parse the file and create a list of lists with all of the integers (e.g. a matrix)
-
Star 1
-
I take each integer from the matrix and check if its 4 neighbors are all bigger than it.
-
If yes, it’s a lowest point and its location gets added to a list as a tuple.
-
And I go ahead and sum up the risk within this loop as well.
-
The messy part is taking care that you aren’t in the first or last column or first or last row.
-
In those cases, you only check 3 neighbors (or 2 if its one of the 4 corners)
-
-
Star 2
-
It seemed to be a clear case for a recursive function.
-
I take each of the lowest points and create a "basin" set with the lowest point in it.
-
Then I call a function that checks all 4 directions from that point out. If the value found is not 9 and the point is not yet in the set, add it to the set and recursively call the function with that point.
-
Again, the messy part is making sure that you are not at any of the edges.
-
Run script
Run the solution with python solution.py
def process_input(file_contents):
lines_stripped = [line.strip() for line in file_contents]
floor_plan = [[int(i) for i in list(line)] for line in lines_stripped]
return floor_plan
def extend_basin(point,map_floor,basin):
if point[0] != 0:
if map_floor[point[0]-1][point[1]] != 9:
if (point[0]-1,point[1]) not in basin:
basin.add((point[0]-1,point[1]))
basin = extend_basin((point[0]-1,point[1]),map_floor,basin)
if point[0] != len(map_floor)-1:
if map_floor[point[0]+1][point[1]] != 9:
if (point[0]+1,point[1]) not in basin:
basin.add((point[0]+1,point[1]))
basin = extend_basin((point[0]+1,point[1]),map_floor,basin)
if point[1] != 0:
if map_floor[point[0]][point[1]-1] != 9:
if (point[0],point[1]-1) not in basin:
basin.add((point[0],point[1]-1))
basin = extend_basin((point[0],point[1]-1),map_floor,basin)
if point[1] != len(map_floor[0])-1:
if map_floor[point[0]][point[1]+1] != 9:
if (point[0],point[1]+1) not in basin:
basin.add((point[0],point[1]+1))
basin = extend_basin((point[0],point[1]+1),map_floor,basin)
return basin
def main():
with open("input.txt",'r') as floor_file:
floor_lines = floor_file.readlines()
map_floor = process_input(floor_lines)
#star 1
low_points = []
sum_risk = 0
for i in range(len(map_floor)):
for j in range(len(map_floor[i])):
if i == 0:
if j == 0:
if map_floor[i][j]<map_floor[i][j+1] and map_floor[i][j]<map_floor[i+1][j]:
sum_risk += 1+map_floor[i][j]
low_points.append((i,j))
elif j == len(map_floor[i])-1:
if map_floor[i][j]<map_floor[i][j-1] and map_floor[i][j]<map_floor[i+1][j]:
sum_risk += 1+map_floor[i][j]
low_points.append((i,j))
elif map_floor[i][j]<map_floor[i][j+1] and map_floor[i][j]<map_floor[i+1][j] and map_floor[i][j]<map_floor[i][j-1]:
sum_risk += 1+map_floor[i][j]
low_points.append((i,j))
elif i == len(map_floor)-1:
if j == 0:
if map_floor[i][j]<map_floor[i][j+1] and map_floor[i][j]<map_floor[i-1][j]:
sum_risk += 1+map_floor[i][j]
low_points.append((i,j))
elif j == len(map_floor[i])-1:
if map_floor[i][j]<map_floor[i][j-1] and map_floor[i][j]<map_floor[i-1][j]:
sum_risk += 1+map_floor[i][j]
low_points.append((i,j))
elif map_floor[i][j]<map_floor[i][j+1] and map_floor[i][j]<map_floor[i-1][j] and map_floor[i][j]<map_floor[i][j-1]:
sum_risk += 1+map_floor[i][j]
low_points.append((i,j))
elif j == 0:
if map_floor[i][j]<map_floor[i][j+1] and map_floor[i][j]<map_floor[i+1][j] and map_floor[i][j]<map_floor[i-1][j]:
sum_risk += 1+map_floor[i][j]
low_points.append((i,j))
elif j == len(map_floor[i])-1:
if map_floor[i][j]<map_floor[i][j-1] and map_floor[i][j]<map_floor[i-1][j] and map_floor[i][j]<map_floor[i+1][j]:
sum_risk += 1+map_floor[i][j]
low_points.append((i,j))
elif map_floor[i][j]<map_floor[i][j+1] and map_floor[i][j]<map_floor[i+1][j] and map_floor[i][j]<map_floor[i-1][j] and map_floor[i][j]<map_floor[i][j-1]:
sum_risk += 1+map_floor[i][j]
low_points.append((i,j))
print(sum_risk)
#star 2
size_basin = []
for i in low_points:
basin = set()
basin.add(i)
basin = extend_basin(i,map_floor,basin)
size_basin.append(len(basin))
size_basin.sort(reverse=True)
print(size_basin[0]*size_basin[1]*size_basin[2])
main()Day 10: python
Day 10 of year 2021 https://adventofcode.com/2021/day/10
What I learned
-
Another day of recursion with only minor mishaps.
Approach
-
I parse the file and strip the carriage returns from the lines. I leave the lines as strings.
-
Star 1
-
I created 2 functions. One to check the status of the line in total and one to check if 2 characters match.
-
For each of the lines, I call the check line function.
-
It checks the first 2 digits in the line against each other.
-
The matcher function checks if they "match" (one closes the other) or if they are both "openers" or if they are a mismatch.
-
In the case of a mismatch, we have a corruption and done.
-
If we have 2 openers, we check the second opener against the rest of the string with a recursive call of the line checker function.
-
If we have a match, we remove the match and continue / return.
-
When that’s all done, you add up the error value according to the formula for the corrupted entries.
-
-
Star 2
-
I only needed minor additions / modifications.
-
You now keep a stack of the openers and for the incomplete lines, you know what has to be closed at the end.
-
Then you just reverse the order, use the formula, sort and find the middle value.
-
After doing star 2, I think I could simplify the whole thing since the whole recursion is just pushing and popping stuff from a stack…
-
Run script
Run the solution with python solution.py
def process_input(file_contents):
lines_stripped = [line.strip() for line in file_contents]
return lines_stripped
def check_line(navicode,opener,stack):
status = ""
corruptor = ""
while len(navicode) > 1 and len(status)==0:
navicode = navicode[1:]
status = check_match(opener,navicode[0])
if status == "corrupt":
return navicode, "corrupt", navicode[0],stack
elif status == "match":
if len(stack[:-1])>0:
return navicode, "", "", stack[:-1]
else:
stack = stack[:-1]
status = ""
else:
stack += status
(navicode,status,corruptor,stack) = check_line(navicode,navicode[0],stack)
return navicode, status, corruptor, stack
def check_match(opener,candidate):
if candidate in ["(","[","<","{"]:
status = candidate
else:
if opener == "(":
if candidate == ")":
status = "match"
else:
status = "corrupt"
elif opener == "[":
if candidate == "]":
status = "match"
else:
status = "corrupt"
elif opener == "{":
if candidate == "}":
status = "match"
else:
status = "corrupt"
else:
if candidate == ">":
status = "match"
else:
status = "corrupt"
return status
def main():
with open("input.txt",'r') as navi_file:
navi_lines = navi_file.readlines()
navigation = process_input(navi_lines)
#star 1
syntax_error = 0
incompletes = []
for navi in navigation:
(navicode,status,corruptor,stack) = check_line(navi,navi[0],navi[0])
if status == "corrupt":
if corruptor == ")":
syntax_error += 3
elif corruptor == "]":
syntax_error += 57
elif corruptor == "}":
syntax_error += 1197
else:
syntax_error += 25137
else:
incompletes.append(stack)
print(syntax_error)
#star 2
scores = []
for incomplete in incompletes:
score = 0
for closer in incomplete[::-1]:
score *= 5
if closer == "(":
score += 1
elif closer == "[":
score += 2
elif closer == "{":
score += 3
else:
score += 4
scores.append(score)
scores.sort()
print(scores[(len(scores)-1)//2])
main()Day 11: python
Day 11 of year 2021 https://adventofcode.com/2021/day/11
What I learned
-
Brushed up on modula arithmetic.
Approach
-
I parse the file and strip the carriage returns from the lines.
-
I put everything into a single flat list of integers.
-
I created a function to do one step and used it for both stars.
-
Basically, I just use a set for the indexes of octopuses that flash.
-
I add one to the octopuses and see if anything flashes.
-
If so, I add those indexes to the set.
-
I then start a loop.
-
And then I add one to their neighbors (lots of code to check the edges) and check if any of them are more than 9 and not already flashed.
-
Repeat until no new flashes occur. Return the new state and the number of flashes that occured.
-
-
Star 1
-
Do 100 steps and add up the flashes.
-
-
Star 2
-
Loop until all Octopuses are 0.
-
Run script
Run the solution with python solution.py
def process_input(file_contents):
lines_stripped = [line.strip() for line in file_contents]
octos = [int(i) for lines in lines_stripped for i in lines]
return octos
def iterate_octos(flashes,octos):
flashed = set()
flashed_temp = flashed.copy()
octos = [octo + 1 for octo in octos]
if any([octo == 10 for octo in octos]):
flash_locations = [i for i, e in enumerate(octos) if e >9]
flashed_temp.update(flash_locations)
while flashed != flashed_temp:
for octo in flashed_temp-flashed:
if octo > 9:
octos[octo-10] += 1
if octo % 10 != 0:
octos[octo-11] += 1
if (octo+1) % 10 != 0:
octos[octo-9] += 1
if octo < 90:
octos[octo+10] += 1
if octo % 10 != 0:
octos[octo+9] += 1
if (octo+1) % 10 != 0:
octos[octo+11] += 1
if octo % 10 != 0:
octos[octo-1] +=1
if (octo+1) % 10 != 0:
octos[octo+1] += 1
flashed = flashed_temp.copy()
if any([octo > 9 for octo in octos]):
flash_locations = [i for i, e in enumerate(octos) if e >9]
flashed_temp.update(flash_locations)
flashes += sum([1 if octo>9 else 0 for octo in octos])
octos = [octo if octo <10 else 0 for octo in octos]
return flashes,octos
def main():
with open("input.txt",'r') as octo_file:
octo_lines = octo_file.readlines()
octos = process_input(octo_lines)
octos_temp = octos.copy()
flashes = 0
#star 1
for i in range(100):
flashes,octos = iterate_octos(flashes,octos)
print(flashes)
#star 2
count = 0
octos = octos_temp
while octos != [0]*100:
flashes,octos = iterate_octos(flashes,octos)
count += 1
print(count)
main()Day 12: python
Day 12 of year 2021 https://adventofcode.com/2021/day/12
What I learned
-
I read up on first depth search.
-
I also understood better what happens when you pass a list to a function in Python.
-
Overall, this was the first day this year that gave me bigger headaches, but I think the solution is pretty ok. :-)
Approach
-
I parse the file and create a dictionary with the vertices as keys. The values are sets containing all adjacent vertices.
-
Star 1
-
I do a modified first depth search. I implemented it recursively.
-
The difference to a more standard first depth search is that I don’t note the nodes I’ve visited but rather only keep track of any lower case vertex that I’ve visited.
-
I tried with first breadth search, but somehow I got my head around first depth search easier.
-
-
Star 2
-
You just have to modify the way you handle "doubles".
-
You note "start" and "end" as soon you reach them.
-
You note any lower case vertex if your list of doubles already has at least 3 elements.
-
You note any lower case vertex if it already occurred in the path.
-
-
You need some extra logic in the loop for the child vertices to avoid visiting more than one lower case vertex twice.
-
Run script
Run the solution with python solution.py
def process_input(file_contents):
lines_stripped = [line.strip() for line in file_contents]
paths_dict = {}
for line in lines_stripped:
vertices = line.split("-")
if vertices[0] in paths_dict:
temp = paths_dict[vertices[0]]
temp.add(vertices[1])
paths_dict[vertices[0]] = temp
else:
paths_dict[vertices[0]] = {vertices[1]}
if vertices[1] in paths_dict:
temp = paths_dict[vertices[1]]
temp.add(vertices[0])
paths_dict[vertices[1]] = temp
else:
paths_dict[vertices[1]] = {vertices[0]}
return paths_dict
def traverse_graph_star1(paths,start,end,path,doubles,found_paths):
path.append(start)
if start[0]>"Z":
doubles.add(start)
if start == end:
found_paths.append(path.copy())
else:
for child in paths[start].difference(doubles):
traverse_graph_star1(paths,child,end,path,doubles,found_paths)
path.pop()
if start[0]>"Z":
doubles.remove(start)
return
def traverse_graph_star2(paths,start,end,path,doubles,found_paths):
flag = 0
if start=="end" or start=="start":
doubles.add(start)
flag = 1
elif start[0]>"Z" and len(doubles)>2:
doubles.add(start)
flag = 1
elif start[0]>"Z" and start in path:
doubles.add(start)
flag = 1
path.append(start)
if start == end:
found_paths.append(path.copy())
else:
for child in paths[start].difference(doubles):
if len(doubles)<2 or child[0]<"a" or child not in path:
traverse_graph_star2(paths,child,end,path,doubles,found_paths)
path.pop()
if flag == 1:
doubles.remove(start)
return
def main():
with open("input.txt",'r') as paths_file:
path_lines = paths_file.readlines()
paths = process_input(path_lines)
#star 1
start = "start"
end = "end"
path = []
doubles = set()
found_paths = []
traverse_graph_star1(paths,start,end,path,doubles,found_paths)
print(len(found_paths))
#star 2
path = []
doubles = set()
found_paths = []
traverse_graph_star2(paths,start,end,path,doubles,found_paths)
print(len(found_paths))
main()Day 13: python
Day 13 of year 2021 https://adventofcode.com/2021/day/13
What I learned
-
This one was actually straightforward
Approach
-
I parse the file and create a list with all instrucions and a set with all coordinates.
-
Both Stars
-
I look at each coordinate and compare it to the cutting line.
-
If it’s above or to the left of the line (depending on vertical or horizontal cutting line), I put the coordinate into the new set.
-
If it’s not, I mirror it to the right spot and put it into the set.
-
-
Star 1
-
Do the first instruction and find the length of the resulting set.
-
-
Star 2
-
Do all of the instructions.
-
Print the coordinates in a grid. (# for present, . for absent). Read the letters in the ASCII graphic.
-
I didn’t right a parser to read the 8 letters, but did it manually. :-)
-
Run script
Run the solution with python solution.py
def process_input(file_contents):
lines_stripped = [line.strip() for line in file_contents]
i = 0
coordinates = set()
instructions = []
while lines_stripped[i]:
coord = lines_stripped[i].split(",")
coordinates.add((int(coord[0]),int(coord[1])))
i += 1
i += 1
while i < len(lines_stripped):
parts = lines_stripped[i].split()
instructions.append((parts[2][0],int(parts[2][2:])))
i += 1
return (coordinates,instructions)
def main():
with open("input.txt",'r') as paper_file:
paper_lines = paper_file.readlines()
(coordinates,instructions) = process_input(paper_lines)
# star 1
folded_coordinates = set()
for coord in coordinates:
if instructions[0][0] == 'y':
if coord[1]<instructions[0][1]:
folded_coordinates.add(coord)
else:
folded_coordinates.add((coord[0],2*instructions[0][1]-coord[1]))
else:
if coord[0]<instructions[0][1]:
folded_coordinates.add(coord)
else:
folded_coordinates.add((2*instructions[0][1]-coord[0],coord[1]))
print(len(folded_coordinates))
# star 2
for inst in instructions:
folded_coordinates = set()
for coord in coordinates:
if inst[0] == 'y':
if coord[1]<inst[1]:
folded_coordinates.add(coord)
else:
folded_coordinates.add((coord[0],2*inst[1]-coord[1]))
else:
if coord[0]<inst[1]:
folded_coordinates.add(coord)
else:
folded_coordinates.add((2*inst[1]-coord[0],coord[1]))
coordinates = folded_coordinates
max_x = max(set([coordinate[0] for coordinate in coordinates]))
max_y = max(set([coordinate[1] for coordinate in coordinates]))
for y in range(max_y+1):
for x in range(max_x+1):
if (x,y) in coordinates:
print("#",end='')
else:
print(".",end='')
print()
main()Day 14: python
Day 14 of year 2021 https://adventofcode.com/2021/day/14
What I learned
-
I practiced with linked lists, but you can’t see that here since it only works for star 1.
Approach
-
I parse the file and create
-
A list containing the initial pairs of letters.
-
A dictionary with the letter pairs as key and the values are the two new letter pairs created by the letter insertion.
-
A set containing all of the valid letter pairs.
-
-
Both Stars
-
I initially solved star 1 with a linked list and brute force. That works fine for up to about 20 iterations, but then you get into major trouble.
-
So, after some thought, I noticed that there are a finite number of letter pairs that can occur. Each of these letter pairs breeds exactly two pairs of letters in the next step. So, you just have to keep track of how many of each pairs you have and you know how many of each pair you have in the next step.
-
Then, you just have to do some math to turn the number of pairs in the final line into the number of corresponding letters.
-
Run script
Run the solution with python solution.py
def process_input(file_contents):
lines_stripped = [line.strip() for line in file_contents]
all_combos = set()
breed = {}
for i in range(2,len(lines_stripped)):
(key,value) = lines_stripped[i].split(" -> ")
breed[key] = (key[0]+value,value+key[1])
all_combos.update(breed[key])
initial_seed = []
for i in range(len(lines_stripped[0])-1):
initial_seed.append(lines_stripped[0][i]+lines_stripped[0][i+1])
all_combos.add(lines_stripped[0][i]+lines_stripped[0][i+1])
all_combos = list(all_combos)
return initial_seed, breed, all_combos
def main():
with open("input.txt",'r') as poly_file:
poly_lines = poly_file.readlines()
(initial_seed, breed, all_combos) = process_input(poly_lines)
all_letters = list(set([item for sublist in all_combos for item in sublist]))
count_pairs = [0]*len(all_combos)
for seed in initial_seed:
count_pairs[all_combos.index(seed)] += 1
for j in range(40): # replace with 10 for star 1
count_pairs_temp = [0]*len(all_combos)
for i,pair in enumerate(all_combos):
new_pairs = breed[pair]
count_pairs_temp[all_combos.index(new_pairs[0])] += count_pairs[i]
count_pairs_temp[all_combos.index(new_pairs[1])] += count_pairs[i]
count_pairs = count_pairs_temp
count_letters = [0]*len(all_letters)
for i,letter in enumerate(all_letters):
for j,combo in enumerate(all_combos):
for letter1 in combo:
if letter == letter1:
count_letters[i] += count_pairs[j]
count_fix = []
for i,count in enumerate(count_letters):
if all_letters[i] == initial_seed[0][0] or all_letters[i] == initial_seed[-1][1]:
count_fix.append((count+1)//2)
else:
count_fix.append(count//2)
print(max(count_fix)-min(count_fix))
main()Day 15: python
Day 15 of year 2021 https://adventofcode.com/2021/day/15
What I learned
-
I understood Dijsktra’s algorithm.
Approach
-
I parse the file and create a list containing each node of the graph.
-
For each node, I hold it’s index, risk, distance to start, neighbors and parent.
-
Initially, the distance is "Inf" and the parent is 0 (as a placeholder).
-
It turns out that I didn’t need the parent, but you never know what Star2 might bring…
-
Star 1
-
I implemented Dijkstra’s algorithm to find the shortest path.
-
The distance is already computed, so the answer is then readily available.
-
-
Star 2
-
I decided to re-read the data in and create the bigger grid from scratch.
-
The distance calculation is principally the same. My first implementation was not efficient enough. After 20 minutes without an answer, I decided to improve it.
-
The key seems to be that I now have 2 sets. One for the visited nodes and one for the nodes with a non-Inf value that are not visited yet. It seems to have massively speeded up the search for the next node. (Finding min distance and the corresponding node is much faster this way).
-
Run script
Run the solution with python solution.py
def return_first(elem):
return elem[0]
def process_input_star1(file_contents):
lines_stripped = [line.strip() for line in file_contents]
nodes = list()
line_length = len(lines_stripped[0])
for i,line in enumerate(lines_stripped):
for j,risk in enumerate(line):
adjacent = set()
index = i*line_length+j
if i != 0:
adjacent.add(index-line_length)
if i != line_length-1:
adjacent.add(index+line_length)
if index % line_length != 0:
adjacent.add(index-1)
if (index+1) % (line_length) != 0:
adjacent.add(index+1)
if index == 0:
distance = 0
else:
distance = float('Inf')
nodes.append([index,int(risk),distance,adjacent,0])
return nodes
def process_input_star2(file_contents):
lines_stripped = [line.strip() for line in file_contents]
nodes = list()
line_length = len(lines_stripped[0])
for k in range(5):
for i,line in enumerate(lines_stripped):
for m in range(5):
for j,risk in enumerate(line):
adjacent = set()
index = (i+m*line_length)*line_length*5+j+k*line_length
risk = int(risk)+m+k
if risk > 9:
risk = risk - 9
if index > line_length*5-1:
adjacent.add(index-line_length*5)
if index < line_length*5*line_length*5-line_length*5:
adjacent.add(index+line_length*5)
if index % (5*line_length) != 0:
adjacent.add(index-1)
if (index+1) % (5*line_length) != 0:
adjacent.add(index+1)
if index == 0:
distance = 0
else:
distance = float('Inf')
nodes.append([index,risk,distance,adjacent,0])
nodes.sort(key=return_first)
return nodes
def find_shortest_path(nodes):
visited = set()
current_node = 0
valued = {current_node}
while current_node != len(nodes)-1:
neighbors = nodes[current_node][3]
valued.update(neighbors-visited)
for neighbor in neighbors:
if neighbor not in visited:
if nodes[neighbor][2] > nodes[current_node][2]+nodes[neighbor][1]:
nodes[neighbor][2] = nodes[current_node][2]+nodes[neighbor][1]
nodes[neighbor][4] = current_node
visited.add(current_node)
valued.remove(current_node)
min_distance = min([nodes[node][2] for node in valued])
for node in valued:
if nodes[node][2] == min_distance:
current_node = node
risk = nodes[current_node][2]
return risk
def main():
with open("input.txt",'r') as chiton_file:
chiton_lines = chiton_file.readlines()
#star 1
nodes = process_input_star1(chiton_lines)
risk = find_shortest_path(nodes)
print(risk)
#star 2
nodes = process_input_star2(chiton_lines)
risk = find_shortest_path(nodes)
print(risk)
main()Day 16: python
Day 16 of year 2021 https://adventofcode.com/2021/day/16
What I learned
-
Hex and Bin manipulation in Python
Approach
-
I take the line from the file and turn it in to a binary string.
-
To decode the transmission and find the sums and the versions, you basically just follow the instructions.
-
Honestly, it’s mostly just reading the requirements closely and not creating any unnecessary bugs in the code.
Run script
Run the solution with python solution.py
def hex_to_binary(hex_num, num_digits):
return str(bin(int(hex_num, 16)))[2:].zfill(num_digits)
def process_input(file_contents):
lines_stripped = [line.strip() for line in file_contents]
return hex_to_binary(lines_stripped[0],len(lines_stripped[0])*4)
def do_type_code(type_code,value,v,flag):
if type_code == 0:
value += v
elif type_code == 1:
if flag == 0:
value = v
flag = 1
else:
value *= v
elif type_code == 2:
if flag == 0:
value = v
flag = 1
else:
value = min(value,v)
elif type_code == 3:
if flag == 0:
value = v
flag = 1
else:
value = max(value,v)
elif type_code == 5:
if flag == 0:
value = v
flag = 1
elif value > v:
value = 1
else:
value = 0
elif type_code == 6:
if flag == 0:
value = v
flag = 1
elif value < v:
value = 1
else:
value = 0
elif type_code == 7:
if flag == 0:
value = v
flag = 1
elif value == v:
value = 1
else:
value = 0
return value,flag
def decode_transmission(code,versions):
value = 0
versions.append(int(code[0:3],2))
type_code = int(code[3:6],2)
length = 6
if type_code == 4:
bits = ""
while int(code[length])!=0:
bits += code[length+1:length+5]
length += 5
bits += code[length+1:length+5]
length += 5
value = int(bits,2)
else:
flag = 0
if int(code[length])==0:
length += 1
subpacket_length = int(code[length:length+15],2)
length += 15
length_temp = length + subpacket_length
while length < length_temp:
(x,v) = decode_transmission(code[length:],versions)
length += x
value,flag = do_type_code(type_code,value,v,flag)
else:
length += 1
no_subpackets = int(code[length:length+11],2)
length += 11
for i in range(no_subpackets):
(x,v) = decode_transmission(code[length:], versions)
length += x
value,flag = do_type_code(type_code,value,v,flag)
return length, value
def main():
with open("input.txt",'r') as hex_file:
hex_lines = hex_file.readlines()
bin_num = process_input(hex_lines)
versions = list()
length, value = decode_transmission(bin_num,versions)
print(sum(versions))
print(value)
main()Day 17: python
Day 17 of year 2021 https://adventofcode.com/2021/day/17
What I learned
-
Some basic math. :-)
Approach
-
I take the line from the file and use a regex to extract the 4 numbers and put them into a list.
-
Star 1
-
This is just math. If the probe goes up with a certain velocity, it is guaranteed to come back down through and exactly hit zero.
-
The velocity when it hits zero will be negative and its magnitude is the initial velocity + 1.
-
So, the max velocity is the absolute value of the bottom edge of the target area minus 1. And the maximum height is then also clear.
-
-
Star 2
-
Maybe there is a cool math solution, but I didn’t find it, so I just brute force this by trying all theoretically possible initial velocity combinations and playing it through for each.
-
Run script
Run the solution with python solution.py
import regex as re
def process_input(file_contents):
input_regex = re.compile('(-?\d+)')
area = re.findall(input_regex,file_contents[0])
area = [int(i) for i in area]
return area
def landed(x,y,area):
pos1 = 0
pos2 = 0
hit = 0
while pos1 < area[1]+1 and pos2 > area[2]-1:
pos1 += x
pos2 += y
if pos1 in list(range(area[0],area[1]+1)) and pos2 in list(range(area[2],area[3]+1)):
hit=1
if x != 0:
x -= abs(x)//x
y -= 1
return hit
def main():
with open("input.txt",'r') as trajectory_file:
trajectory_lines = trajectory_file.readlines()
area = process_input(trajectory_lines)
# star 1
print(max(-1*area[2],-1*area[3])*(max(-1*area[2],-1*area[3])-1)//2)
hits = 0
for x in range(1,area[1]+1):
for y in range(area[2],-1*area[2]-1+1):
hits += landed(x,y,area)
print(hits)
main()Day 18: python
Day 18 of year 2021 https://adventofcode.com/2021/day/18
What I learned
-
Working with match objects from regex
Approach
-
I just read in the lines and strip them and put them into a list.
-
Star 1
-
After some thought, I didn’t have any better idea than to leave everything as a string and parse it.
-
I setup a loop that stops if neither condition is met.
-
For explode …I regex to find the pairs that could explode. And then count up the [ to the left (subtracting closers if any).
-
If more than 4, then it explodes. I scan through to see if there are any numbers to the left or right and do the addition and substition.
-
-
For split
-
It’s actually easy. I just check for any double digits and do the substition.
-
-
-
Star 2
-
I use the same code as before and just run 2 nested loops and keep the max magnitude while running through.
-
Run script
Run the solution with python solution.py
import regex as re
import math
def process_input(file_contents):
lines_stripped = [line.strip() for line in file_contents]
return lines_stripped
def explode(snail):
for m in re.finditer("(\d+),(\d+)", snail):
parenths = 0
for character in snail[:m.start()]:
if character == "[":
parenths += 1
elif character == "]":
parenths -= 1
if parenths > 4:
cl = ""
cr = ""
for i, character in enumerate(snail[0:m.start()]):
if character.isnumeric():
cl = character
il = i
if snail[i-1].isnumeric():
cl = snail[i-1]+cl
for i, character in enumerate(snail[m.end():]):
if character.isnumeric():
cr = character
ir = i
if snail[m.end()+i+1].isnumeric():
cr = cr + snail[m.end()+i+1]
break
if bool(cr):
snail = snail[:m.end()+ir]+str(int(cr)+int(m.group(2)))+snail[m.end()+ir+len(cr):]
snail = snail[:m.start()-1]+"0"+snail[m.end()+1:]
if bool(cl):
snail = snail[:il-len(cl)+1]+str(int(cl)+int(m.group(1)))+snail[il+1:]
break
return snail
def split(snail):
pattern = re.compile("\d\d")
m = pattern.search(snail)
if m:
num_to_split = int(m.group(0))
left = math.floor(int(num_to_split)/2)
right = math.ceil(int(num_to_split)/2)
snail = snail[:m.start()]+"["+str(left)+","+str(right)+"]"+snail[m.end():]
return snail
def main():
with open("input.txt",'r') as snail_file:
snail_lines = snail_file.readlines()
snails = process_input(snail_lines)
# star 1
snail = snails[0]
for snail_temp in snails[1:]:
snail = "["+snail+","+snail_temp+"]"
snail_temp = ""
while snail_temp != snail:
snail_temp = snail
snail = explode(snail)
if snail == snail_temp:
snail = split(snail)
pattern = re.compile("\[(\d+),(\d+)\]")
while not snail.isnumeric():
m = pattern.search(snail)
snail = snail[:m.start()]+str(int(m.group(1))*3+int(m.group(2))*2)+snail[m.end():]
print(snail)
# star 2
max_mag = 0
for snail1 in snails:
for snail2 in snails:
snail = "["+snail1+","+snail2+"]"
snail_temp = ""
while snail_temp != snail:
snail_temp = snail
snail = explode(snail)
if snail == snail_temp:
snail = split(snail)
pattern = re.compile("\[(\d+),(\d+)\]")
while not snail.isnumeric():
m = pattern.search(snail)
snail = snail[:m.start()]+str(int(m.group(1))*3+int(m.group(2))*2)+snail[m.end():]
max_mag = max(max_mag,int(snail))
print(max_mag)
main()Day 19: python
Day 19 of year 2021 https://adventofcode.com/2021/day/19
What I learned
-
I am not fond of puzzles with multiple geometric transformations.
Approach
-
I use regex to fish out the integers and create a scanners dictionary with the scanner as the key and a list of beacons as value.
-
I then calculate a vector of the distances between pairs of beacons of each scanner.
-
Star 1
-
I make a set containing scanner 0. And another set with all of the other scanners.
-
I loop through until the second set is empty.
-
For each member of the second set, I check it against scanners that are already mapped.
-
To find possible overlapping beacons between scanners, I use the distance vectors. If 12 beacons of one scanner have the same relative vectors as the another scanners, these are probably common beacons.
-
In that case, I first sort out the x, y and z coordinates to match the order of the already mapped scanner.
-
Then, I see if the axis has been inverted (e.g. -x) and correct that.
-
Then, I figure out the distance between the 2 scanners and shift the second scanner.
-
-
In the end, I take the now shifted lists of beacons, put them into a set to eliminate duplicates and check how many items the set has.
-
-
Star 2
-
You reuse everythin from Star 1.
-
And you just have to keep track of those distances between the scanners on the way.
-
And you calculate the distance between all scanners and take the max.
-
-
I am pretty sure that this can be done much or elegantly. But, I have trouble with geometry sometimes and was able to work it out best with "divide and conquer".
-
The data structures were also kind of messy and suboptimal, but after I got it working, I didn’t want to mess with them.
Run script
Run the solution with python solution.py
import regex as re
import collections
def process_input(file_contents):
lines_stripped = [line.strip() for line in file_contents]
scanners = dict()
scanner_pattern = re.compile("(\d+)")
beacon_pattern = re.compile("(-?\d+),(-?\d+),(-?\d+)")
for line in lines_stripped:
if len(line)>0 and line[1] == "-":
scanner_match = re.search(scanner_pattern,line)
scanner = int(scanner_match.group(0))
beacons = list()
elif len(line)>0:
beacon_match = re.match(beacon_pattern,line)
beacon = [int(beacon_match.group(i)) for i in [1,2,3]]
beacons.append(beacon)
else:
scanners[scanner] = beacons
scanners[scanner] = beacons
return scanners
def find_distance(scanners):
distance_dict = dict()
for key,value in scanners.items():
distances = dict()
for i in range(len(value)):
for j in range(i+1,len(value)):
distances[(i,j)] = [abs(value[i][k]-value[j][k]) for k in [0,1,2]]
distance_dict[key] = distances
return distance_dict
def find_matches(mapped,unmapped,distances,scanners,scan_translation):
new_unmapped = unmapped.copy()
new_mapped = mapped.copy()
for key_unmapped in unmapped:
# find all distances between beacons that match for both scanners
for key_mapped in mapped:
matches = list()
beacon_unmapped = set()
beacon_mapped = set()
for pair_mapped,distance_mapped in distances[key_mapped].items():
for pair_unmapped,distance_unmapped in distances[key_unmapped].items():
if set(distance_mapped) == set(distance_unmapped):
matches.append([pair_mapped,pair_unmapped])
beacon_unmapped.update(pair_unmapped)
beacon_mapped.update(pair_mapped)
#find the matching pairs of beacons
beacon_mapping = dict()
for beacon in beacon_mapped:
other_beacon = set()
for match in matches:
if beacon in match[0]:
if not other_beacon:
other_beacon = set(match[1])
else:
other_beacon = other_beacon.intersection(match[1])
beacon_mapping[beacon] = other_beacon.pop()
# If there are at least 12 beacon matches
if len(beacon_mapping)>11:
#First we sort out the x,y,z coordinates so that both scanners have the same definition
flagx = sum([1 if distances[key_mapped][matches[j][0]][0] == distances[key_unmapped][matches[j][1]][0] else 0 for j in range(len(matches))])
flagy = sum([1 if distances[key_mapped][matches[j][0]][0] == distances[key_unmapped][matches[j][1]][1] else 0 for j in range(len(matches))])
flagz = sum([1 if distances[key_mapped][matches[j][0]][0] == distances[key_unmapped][matches[j][1]][2] else 0 for j in range(len(matches))])
if flagy >= flagx and flagy >= flagz:
distances[key_unmapped] = {key:[value[1],value[0],value[2]] for key,value in distances[key_unmapped].items()}
scanners[key_unmapped] = [[value[1],value[0],value[2]] for value in scanners[key_unmapped]]
elif flagz >= flagx and flagz >= flagy:
distances[key_unmapped] = {key:[value[2],value[1],value[0]] for key,value in distances[key_unmapped].items()}
scanners[key_unmapped] = [[value[2],value[1],value[0]] for value in scanners[key_unmapped]]
flagy = sum([1 if distances[key_mapped][match[0]][1] == distances[key_unmapped][match[1]][1] else 0 for match in matches])
flagz = sum([1 if distances[key_mapped][match[0]][1] == distances[key_unmapped][match[1]][2] else 0 for match in matches])
if flagz >= flagy:
distances[key_unmapped] = {key:[value[0],value[2],value[1]] for key,value in distances[key_unmapped].items()}
scanners[key_unmapped] = [[value[0],value[2],value[1]] for value in scanners[key_unmapped]]
# Then we see if any x,y,z is inverted
# First though we have to reorder our matching list to keep beacon pairs consistent
temp_matches = list()
for match in matches:
if match[1][0] != beacon_mapping[match[0][0]]:
temp_matches.append([match[0],(match[1][1],match[1][0])])
else:
temp_matches.append(match)
matches = temp_matches
invertx = sum([1 if scanners[key_mapped][match[0][0]][0] - scanners[key_mapped][match[0][1]][0] == scanners[key_unmapped][match[1][0]][0] - scanners[key_unmapped][match[1][1]][0] else -1 for match in matches])
inverty = sum([1 if scanners[key_mapped][match[0][0]][1] - scanners[key_mapped][match[0][1]][1] == scanners[key_unmapped][match[1][0]][1] - scanners[key_unmapped][match[1][1]][1] else -1 for match in matches])
invertz = sum([1 if scanners[key_mapped][match[0][0]][2] - scanners[key_mapped][match[0][1]][2] == scanners[key_unmapped][match[1][0]][2] - scanners[key_unmapped][match[1][1]][2] else -1 for match in matches])
if invertx < 0:
scanners[key_unmapped] = [[-1*value[0],value[1],value[2]] for value in scanners[key_unmapped]]
if inverty < 0:
scanners[key_unmapped] = [[value[0],-1*value[1],value[2]] for value in scanners[key_unmapped]]
if invertz < 0:
scanners[key_unmapped] = [[value[0],value[1],-1*value[2]] for value in scanners[key_unmapped]]
# And finally we shift the scanner to overlap with the other one
translation = [(scanners[key_mapped][match[0][0]][0] - scanners[key_unmapped][match[1][0]][0],scanners[key_mapped][match[0][0]][1] - scanners[key_unmapped][match[1][0]][1],scanners[key_mapped][match[0][0]][2] - scanners[key_unmapped][match[1][0]][2]) for match in matches]
translation = collections.Counter(translation).most_common(1)[0][0]
scanners[key_unmapped] = [[value[0]+translation[0],value[1]+translation[1],value[2]+translation[2]] for value in scanners[key_unmapped]]
if key_unmapped in new_unmapped:
new_unmapped.remove(key_unmapped)
new_mapped.add(key_unmapped)
scan_translation.append(translation)
return new_mapped, new_unmapped
def main():
with open("input.txt",'r') as beacon_file:
beacon_lines = beacon_file.readlines()
scanners = process_input(beacon_lines)
distances = find_distance(scanners)
keys = list(scanners.keys())
mapped = {keys[0]}
unmapped = set(keys[1:])
translation = list()
while unmapped:
(new_mapped, new_unmapped) = find_matches(mapped,unmapped,distances,scanners,translation)
mapped = new_mapped
unmapped = new_unmapped
# Star 1
beacons = set()
for key,value in scanners.items():
for beacon in value:
beacons.add(tuple(beacon))
print(len(beacons))
# Star 2
max_distance = 0
for i in range(len(translation)):
for j in range(i+1,len(translation)):
max_distance = max(max_distance,sum([abs(translation[i][k]-translation[j][k]) for k in [0,1,2]]))
print(max_distance)
main()Day 20: python
Day 20 of year 2021 https://adventofcode.com/2021/day/20
What I learned
-
How to do the equivalent of elif in a list comprehension.
Approach
-
I read in the enhancer and just leave it as a string.
-
I put the trench values into a dictionary with the x,y coordinates in a tuple as the key
-
Both Stars
-
I create a loop.
-
First, I add a frame of entries to my dictionary around the current grid of the current dictionary.
-
Since the parts outside of the grid could be "" (the zero value in my enhancer was ""), you have to be careful here.
-
Then you just find the values for all of the neighbors, join it to be a binary string and use the decimal conversion as an index into the enhancer string.
-
At the end, you just add up the lit squares.
-
It’s not super efficient, but it still runs in a few seconds.
-
Run script
Run the solution with python solution.py
def process_input(file_contents):
lines_stripped = [line.strip() for line in file_contents]
enhancer = lines_stripped[0]
trench = dict()
for j,line in enumerate(lines_stripped[2:]):
for i,character in enumerate(line):
trench[(i,j)] = character
return enhancer, trench
def main():
with open("input.txt",'r') as trench_file:
trench_lines = trench_file.readlines()
(enhancer, trench) = process_input(trench_lines)
size_trench = max(trench.keys())[0]+1
neighbors = [(-1,-1),(0,-1),(1,-1),(-1,0),(0,0),(1,0),(-1,1),(0,1),(1,1)]
for i in range(50):
for j in range(-1-i,size_trench+i):
if i%2 == 0:
trench[(j,-1-i)] = "."
trench[(j,size_trench+i)] = "."
trench[(-1-i,j)] = "."
trench[(size_trench+i,j)] = "."
trench[(size_trench+i,size_trench+i)] = "."
else:
trench[(j,-1-i)] = enhancer[0]
trench[(j,size_trench+i)] = enhancer[0]
trench[(-1-i,j)] = enhancer[0]
trench[(size_trench+i,j)] = enhancer[0]
trench[(size_trench+i,size_trench+i)] = enhancer[0]
trench_temp = trench.copy()
for key,value in trench.items():
grid = [tuple(map(sum,zip(key,neighbor))) for neighbor in neighbors]
code = ''.join([trench[grid_item] if grid_item in trench else '.' if i%2 == 0 else enhancer[0] for grid_item in grid])
code = ''.join(["1" if character == "#" else "0" for character in code])
trench_temp[key] = enhancer[int(code,2)]
trench = trench_temp
if i == 1:
print(sum([1 if i == "#" else 0 for key,i in trench.items()]))
print(sum([1 if i == "#" else 0 for key,i in trench.items()]))
main()Day 21: python
Day 21 of year 2021 https://adventofcode.com/2021/day/21
What I learned
-
Used a deque
Approach
-
I read in the 2 positions and put them into a list.
-
Star 1
-
I used a deque to represent the die.
-
You just iterate through until one of the players reaches the score.
-
-
Star 2
-
I realized that there are 27 different die roles for 3 dice. But, there are of course not 27 different sums of the three.
-
I created a dictionary with the keys being the possible sums and the values being how often they occur. e.g. 3 happens only once. 6 happens 7 times.
-
I created a dictionary with the score and position of both players as the key. And how often that combo occurs as the value.
-
Then, it’s pretty straightforward. It just loops through figuring out all combos on each turn. If one of the player wins, we add the universes to its win sum value.
-
Run script
Run the solution with python solution.py
import collections
def process_input(file_contents):
lines_stripped = [line.strip() for line in file_contents]
position = list()
position.append(int(lines_stripped[0][-1]))
position.append(int(lines_stripped[1][-1]))
return position
def main():
with open("input.txt",'r') as player_file:
player_lines = player_file.readlines()
position = process_input(player_lines)
# star 1
score = [0,0]
die = collections.deque([i for i in range(1,101)])
i = 0
j = 0
while max(score)<1000:
player = 0
for k in range(3):
player += die[0]
die.rotate(-1)
position[i] = (position[i]+player-1)%10+1
score[i] += position[i]
i = (i+1)%2
j += 3
print(j*min(score))
position = process_input(player_lines)
# star 2
adder_dict = dict()
for i in range(1,4):
for j in range(1,4):
for k in range(1,4):
if i+j+k in adder_dict:
adder_dict[i+j+k] += 1
else:
adder_dict[i+j+k] = 1
sp1_sp2_dict = dict()
for key1, value1 in adder_dict.items():
for key2, value2 in adder_dict.items():
score1 = (position[0]+key1-1)%10+1
score2 = (position[1]+key2-1)%10+1
sp1_sp2_dict[(score1,score1,score2,score2)] = value1*value2
player1_wins = 0
player2_wins = 0
while sp1_sp2_dict:
sp1_sp2_dict_temp = dict()
for key,value in sp1_sp2_dict.items():
for key1,value1 in adder_dict.items():
position1 = (key[1]+key1-1)%10+1
score1 = key[0]+position1
if score1>=21:
player1_wins += value*value1
else:
for key2,value2 in adder_dict.items():
position2 = (key[3]+key2-1)%10+1
score2 = key[2]+position2
if score2 >= 21:
player2_wins += value*value1*value2
elif (score1,position1,score2,position2) in sp1_sp2_dict_temp:
sp1_sp2_dict_temp[(score1,position1,score2,position2)] = sp1_sp2_dict_temp[(score1,position1,score2,position2)] + value*value1*value2
else:
sp1_sp2_dict_temp[(score1,position1,score2,position2)] = value*value1*value2
sp1_sp2_dict = sp1_sp2_dict_temp
print(max(player1_wins,player2_wins))
main()Day 22: python
Day 22 of year 2021 https://adventofcode.com/2021/day/22
What I learned
-
To make sure that you know if your representation of the geometry is correct before anything else.
-
I also created some tests this time since it was hard to easily verify otherwise which parts were working.
Approach
-
I read in each line and use a simple regex to fish out the numbers.
-
I put the "on" or "off" and the numbers into a tuple for each line and put the whole thing into a list.
-
Important: I added one to the right number for each axis. Otherwise, the math doesn’t work out later.
-
Star 1
-
I brute forced this one initially, but that really doesn’t scale. So, I just added an if statement to star 2 to only add up the cubes in the right region.
-
-
Star 2
-
I take each reboot step. If it is "off", I ignore it.
-
If it is "on", I take it and "subtract" each of the following instructions from it. That avoids double counting.
-
I add any cubes still remaining after this to the total count.
-
My subtraction is just transposing the 2 cubes and if they overlap, creating up to 6 new boxes that cover the original box minus each of the further boxes in the list.
-
My implementation creates a lot of boxes that are all the same. So, I turn them into a set and back into a list in the loop. Without this, I quckly ran out of memory.
-
Run script
Run the solution with python solution.py
import regex as re
def process_input(file_contents):
lines_stripped = [line.strip() for line in file_contents]
cube = list()
pattern = re.compile("(-?\d+)")
for line in lines_stripped:
numbers = re.findall(pattern,line)
cube.append((line[0:2],int(numbers[0]),int(numbers[1])+1,int(numbers[2]),int(numbers[3])+1,int(numbers[4]),int(numbers[5])+1))
return cube
def cut_cube(cube_in, cube_cut):
cubes = list()
cubes.append((min(cube_in[1],cube_cut[1]),cube_in[1],cube_in[2],cube_in[3],cube_in[4],cube_in[5]))
cubes.append((cube_in[0],max(cube_cut[0],cube_in[0]),cube_in[2],cube_in[3],cube_in[4],cube_in[5]))
cubes.append((max(cube_in[0],cube_cut[0]),min(cube_in[1],cube_cut[1]),min(cube_in[3],cube_cut[3]),cube_in[3],cube_in[4],cube_in[5]))
cubes.append((max(cube_in[0],cube_cut[0]),min(cube_in[1],cube_cut[1]),cube_in[2],max(cube_in[2],cube_cut[2]),cube_in[4],cube_in[5]))
cubes.append((max(cube_in[0],cube_cut[0]),min(cube_in[1],cube_cut[1]),max(cube_in[2],cube_cut[2]),min(cube_in[3],cube_cut[3]),min(cube_in[5],cube_cut[5]),cube_in[5]))
cubes.append((max(cube_in[0],cube_cut[0]),min(cube_in[1],cube_cut[1]),max(cube_in[2],cube_cut[2]),min(cube_in[3],cube_cut[3]),cube_in[4],max(cube_cut[4],cube_in[4])))
return cubes
def main():
with open("input.txt",'r') as player_file:
player_lines = player_file.readlines()
insts = process_input(player_lines)
cubes = 0
cubes_star1 = 0
for i,inst in enumerate(insts):
if inst[0] != "of":
space = [inst[1:]]
for inst1 in insts[i+1:]:
space_temp = list()
for cube in space:
if inst1[2] >= cube[0] and inst1[4]>= cube[2] and inst1[6] >= cube[4] and inst1[1] <= cube[1] and inst1[3] <= cube[3] and inst1[5]<=cube[5]:
if inst1[1]<=cube[0] and inst1[2]>=cube[1] and inst1[3]<=cube[2] and inst1[4]>=cube[3] and inst1[5]<=cube[4] and inst1[6]>=cube[5]:
pass
else:
[space_temp.append(i) for i in cut_cube(cube,inst1[1:])]
else:
space_temp.append(cube)
space = list(set(space_temp))
cubes += sum([(spa[1]-spa[0])*(spa[3]-spa[2])*(spa[5]-spa[4]) for spa in space])
if inst[2] >= -50 and inst[4]>= -50 and inst[6] >= -50 and inst[1] <= 50 and inst[3] <= 50 and inst[5]<=50:
cubes_star1 += sum([(spa[1]-spa[0])*(spa[3]-spa[2])*(spa[5]-spa[4]) for spa in space])
print(cubes_star1)
print(cubes)
main()Day 23: python
Day 23 of year 2021 https://adventofcode.com/2021/day/23
What I learned
-
Some data representations are better (easier to read and debug) then others
Approach
This one was kind of a mess. Initially, I actually just solved star 1 by hand and then created code. I am pretty sure my data represenation is not so optimal and the code takes a while to solve it, but it works. Both stars are essentially the same approach.
-
I create a tuple with the relevant locations. Those are of course the rooms. And some of the hallway spots. The space in the hallway right in front of a room is never used to park since it would block the room.
-
I created a dictionary with the final destinations of each letter as a set.
-
I also created 2 further dictionaries with the spaces on the path between any two relevant pairs of locations. And the distance between those 2 locations.
-
I then run it through Dijkstra’s algorithm to find the solution.
I am sure there are much better ways to find the "neighbors" and my representation made it hard to fill the paths and distance dictionaries.
Run script
Run the solution with python solution.py
def process_input(file_contents):
grid = [0]*7
for i in[3,5,7,9]:
for j in [2,3]:
grid.append(file_contents[j][i])
return tuple(grid)
def find_neighbors_star1(current_node,goals,paths,distance):
neighbors = list()
neighbor_dict = dict()
multiplier = {'A':1, 'B':10, 'C':100, 'D':1000}
for i, position in enumerate(current_node):
if position != 0 and i != goals[position][1] and not (i == goals[position][0] and current_node[goals[position][1]]==position):
if i<7:
if current_node[goals[position][0]] == 0:
if current_node[goals[position][1]] == position:
if not sum([1 if current_node[k] != 0 else 0 for k in paths[(i,goals[position][0])]]):
neighbor = list(current_node)
neighbor[goals[position][0]] = position
neighbor[i] = 0
neighbors.append(tuple(neighbor))
neighbor_dict[tuple(neighbor)] = distance[(i,goals[position][0])]*multiplier[position]
break
elif current_node[goals[position][1]] == 0:
if not sum([1 if current_node[k] != 0 else 0 for k in paths[(i,goals[position][1])]]):
neighbor = list(current_node)
neighbor[goals[position][1]] = position
neighbor[i] = 0
neighbors.append(tuple(neighbor))
neighbor_dict[tuple(neighbor)] = distance[(i,goals[position][1])]*multiplier[position]
break
else:
for j in range(7):
if current_node[j] == 0:
if not sum([1 if current_node[k] != 0 else 0 for k in paths[(j,i)]]):
neighbor = list(current_node)
neighbor[j] = position
neighbor[i] = 0
neighbors.append(tuple(neighbor))
neighbor_dict[tuple(neighbor)] = distance[(j,i)]*multiplier[position]
neighbors = set(neighbors)
return neighbors, neighbor_dict
def find_neighbors_star2(current_node,goals,paths,distance):
neighbors = list()
neighbor_dict = dict()
multiplier = {'A':1, 'B':10, 'C':100, 'D':1000}
for i, position in enumerate(current_node):
if position != 0 and i != goals[position][3] and not (i == goals[position][2] and current_node[goals[position][3]]==position) and not (i == goals[position][1] and current_node[goals[position][2]]==position and current_node[goals[position][3]]==position) and not (i == goals[position][0] and current_node[goals[position][1]]==position and current_node[goals[position][2]]==position and current_node[goals[position][3]]==position):
if i<7:
if current_node[goals[position][0]] == 0:
if not sum([1 if current_node[goals[position][k]] != position else 0 for k in [1,2,3]]):
if not sum([1 if current_node[k] != 0 else 0 for k in paths[(i,goals[position][0])]]):
neighbor = list(current_node)
neighbor[goals[position][0]] = position
neighbor[i] = 0
neighbors.append(tuple(neighbor))
neighbor_dict[tuple(neighbor)] = distance[(i,goals[position][0])]*multiplier[position]
break
elif current_node[goals[position][1]] == 0:
if not sum([1 if current_node[goals[position][k]] != position else 0 for k in [2,3]]):
if not sum([1 if current_node[k] != 0 else 0 for k in paths[(i,goals[position][1])]]):
neighbor = list(current_node)
neighbor[goals[position][1]] = position
neighbor[i] = 0
neighbors.append(tuple(neighbor))
neighbor_dict[tuple(neighbor)] = distance[(i,goals[position][1])]*multiplier[position]
break
elif current_node[goals[position][2]] == 0:
if not sum([1 if current_node[goals[position][k]] != position else 0 for k in [3]]):
if not sum([1 if current_node[k] != 0 else 0 for k in paths[(i,goals[position][2])]]):
neighbor = list(current_node)
neighbor[goals[position][2]] = position
neighbor[i] = 0
neighbors.append(tuple(neighbor))
neighbor_dict[tuple(neighbor)] = distance[(i,goals[position][2])]*multiplier[position]
break
elif current_node[goals[position][3]] == 0:
if not sum([1 if current_node[k] != 0 else 0 for k in paths[(i,goals[position][3])]]):
neighbor = list(current_node)
neighbor[goals[position][3]] = position
neighbor[i] = 0
neighbors.append(tuple(neighbor))
neighbor_dict[tuple(neighbor)] = distance[(i,goals[position][3])]*multiplier[position]
break
else:
for j in range(7):
if current_node[j] == 0:
if not sum([1 if current_node[k] != 0 else 0 for k in paths[(j,i)]]):
neighbor = list(current_node)
neighbor[j] = position
neighbor[i] = 0
neighbors.append(tuple(neighbor))
neighbor_dict[tuple(neighbor)] = distance[(j,i)]*multiplier[position]
neighbors = set(neighbors)
return neighbors, neighbor_dict
def find_shortest_path(nodes,goals,paths,distance,star):
if star == 1:
end_node = (0,0,0,0,0,0,0,'A','A','B','B','C','C','D','D')
else:
end_node = (0,0,0,0,0,0,0,'A','A','A','A','B','B','B','B','C','C','C','C','D','D','D','D')
visited = set()
current_node = nodes
energy_dict = {current_node:0}
valued = {current_node}
while current_node != end_node:
if star == 1:
(neighbors, neighbor_dict) = find_neighbors_star1(current_node,goals,paths,distance)
else:
(neighbors, neighbor_dict) = find_neighbors_star2(current_node,goals,paths,distance)
valued.update(neighbors-visited)
for neighbor in neighbors:
if neighbor not in visited:
if neighbor not in energy_dict.keys():
energy_dict[neighbor] = energy_dict[current_node] + neighbor_dict[neighbor]
else:
energy_dict[neighbor] = min(energy_dict[neighbor],energy_dict[current_node]+neighbor_dict[neighbor])
visited.add(current_node)
valued.remove(current_node)
energy_dict.pop(current_node)
min_distance = min([energy_dict[key] for key in valued])
for node in valued:
if energy_dict[node] == min_distance:
current_node = node
break
energy = min_distance
return energy
def main():
with open("input.txt",'r') as amph_file:
amph_lines = amph_file.readlines()
grid = process_input(amph_lines)
goals = {"A":(7,8),"B":(9,10),"C":(11,12),"D":(13,14)}
paths = {(0,7):{1},(0,8):{1,7},(0,9):{1,2},(0,10):{1,2,9},(0,11):{1,2,3},(0,12):{1,2,3,11},(0,13):{1,2,3,4},(0,14):{1,2,3,4,13}}
paths.update({(1,7):{},(1,8):{7},(1,9):{2},(1,10):{2,9},(1,11):{2,3},(1,12):{2,3,11},(1,13):{2,3,4},(1,14):{2,3,4,13}})
paths.update({(2,7):{},(2,8):{7},(2,9):{},(2,10):{9},(2,11):{3},(2,12):{3,11},(2,13):{3,4},(2,14):{3,4,13}})
paths.update({(3,7):{2},(3,8):{2,7},(3,9):{},(3,10):{9},(3,11):{},(3,12):{11},(3,13):{4},(3,14):{4,13}})
paths.update({(4,7):{2,3},(4,8):{2,3,7},(4,9):{3},(4,10):{3,9},(4,11):{},(4,12):{11},(4,13):{},(4,14):{13}})
paths.update({(5,7):{2,3,4},(5,8):{2,3,4,7},(5,9):{3,4},(5,10):{3,4,9},(5,11):{4},(5,12):{4,11},(5,13):{},(5,14):{13}})
paths.update({(6,7):{2,3,4,5},(6,8):{2,3,4,5,7},(6,9):{3,4,5},(6,10):{3,4,5,9},(6,11):{4,5},(6,12):{4,5,11},(6,13):{5},(6,14):{5,13}})
distance = {(0,7):3,(0,8):4,(0,9):5,(0,10):6,(0,11):7,(0,12):8,(0,13):9,(0,14):10}
distance.update({(1,7):2,(1,8):3,(1,9):4,(1,10):5,(1,11):6,(1,12):7,(1,13):8,(1,14):9})
distance.update({(2,7):2,(2,8):3,(2,9):2,(2,10):3,(2,11):4,(2,12):5,(2,13):6,(2,14):7})
distance.update({(3,7):4,(3,8):5,(3,9):2,(3,10):3,(3,11):2,(3,12):3,(3,13):4,(3,14):5})
distance.update({(4,7):6,(4,8):7,(4,9):4,(4,10):5,(4,11):2,(4,12):3,(4,13):2,(4,14):3})
distance.update({(5,7):8,(5,8):9,(5,9):6,(5,10):7,(5,11):4,(5,12):5,(5,13):2,(5,14):3})
distance.update({(6,7):9,(6,8):10,(6,9):7,(6,10):8,(6,11):5,(6,12):6,(6,13):3,(6,14):4})
energy = find_shortest_path(grid,goals,paths,distance,1)
print(energy)
grid_temp = [0]*23
for i in range(8):
grid_temp[i] = grid[i]
grid_temp[8] = "D"
grid_temp[9] = "D"
grid_temp[10] = grid[8]
grid_temp[11] = grid[9]
grid_temp[12] = "C"
grid_temp[13] = "B"
grid_temp[14] = grid[10]
grid_temp[15] = grid[11]
grid_temp[16] = "B"
grid_temp[17] = "A"
grid_temp[18] = grid[12]
grid_temp[19] = grid[13]
grid_temp[20] = "A"
grid_temp[21] = "C"
grid_temp[22] = grid[14]
grid = tuple(grid_temp)
goals = {"A":(7,8,9,10),"B":(11,12,13,14),"C":(15,16,17,18),"D":(19,20,21,22)}
paths = {(0,7):{1},(0,8):{1,7},(0,9):{1,7,8},(0,10):{1,7,8,9},(0,11):{1,2},(0,12):{1,2,11},(0,13):{1,2,11,12},(0,14):{1,2,11,12,13},(0,15):{1,2,3},(0,16):{1,2,3,15},(0,17):{1,2,3,15,16},(0,18):{1,2,3,15,16,17},(0,19):{1,2,3,4},(0,20):{1,2,3,4,19},(0,21):{1,2,3,4,19,20},(0,22):{1,2,3,4,19,20,21}}
distance = {(0,7):3,(0,8):4,(0,9):5,(0,10):6,(0,11):5,(0,12):6,(0,13):7,(0,14):8,(0,15):7,(0,16):8,(0,17):9,(0,18):10,(0,19):9,(0,20):10,(0,21):11,(0,22):12}
for k in range(7,23):
paths[(1,k)] = paths[(0,k)] - {1}
distance[(1,k)] = distance[(0,k)] - 1
for k in range(7,11):
paths[(2,k)] = paths[(1,k)]
paths[(3,k)] = paths[(2,k)] | {2}
paths[(4,k)] = paths[(3,k)] | {3}
paths[(5,k)] = paths[(4,k)] | {4}
paths[(6,k)] = paths[(5,k)] | {5}
distance[(2,k)] = distance[(1,k)]
distance[(3,k)] = distance[(2,k)] + 2
distance[(4,k)] = distance[(3,k)] + 2
distance[(5,k)] = distance[(4,k)] + 2
distance[(6,k)] = distance[(5,k)] + 1
for k in range(11,15):
paths[(2,k)] = paths[(1,k)] - {2}
paths[(3,k)] = paths[(2,k)]
paths[(4,k)] = paths[(3,k)] | {3}
paths[(5,k)] = paths[(4,k)] | {4}
paths[(6,k)] = paths[(5,k)] | {5}
distance[(2,k)] = distance[(1,k)] - 2
distance[(3,k)] = distance[(2,k)]
distance[(4,k)] = distance[(3,k)] + 2
distance[(5,k)] = distance[(4,k)] + 2
distance[(6,k)] = distance[(5,k)] + 1
for k in range(15,19):
paths[(2,k)] = paths[(1,k)] - {2}
paths[(3,k)] = paths[(2,k)] - {3}
paths[(4,k)] = paths[(3,k)]
paths[(5,k)] = paths[(4,k)] | {4}
paths[(6,k)] = paths[(5,k)] | {5}
distance[(2,k)] = distance[(1,k)] - 2
distance[(3,k)] = distance[(2,k)] - 2
distance[(4,k)] = distance[(3,k)]
distance[(5,k)] = distance[(4,k)] + 2
distance[(6,k)] = distance[(5,k)] + 1
for k in range(19,23):
paths[(2,k)] = paths[(1,k)] - {2}
paths[(3,k)] = paths[(2,k)] - {3}
paths[(4,k)] = paths[(3,k)] - {4}
paths[(5,k)] = paths[(4,k)]
paths[(6,k)] = paths[(5,k)] | {5}
distance[(2,k)] = distance[(1,k)] - 2
distance[(3,k)] = distance[(2,k)] - 2
distance[(4,k)] = distance[(3,k)] - 2
distance[(5,k)] = distance[(4,k)]
distance[(6,k)] = distance[(5,k)] + 1
energy = find_shortest_path(grid,goals,paths,distance,2)
print(energy)
main()Day 24: python
Day 24 of year 2021 https://adventofcode.com/2021/day/24
What I learned
-
Sometimes you are faster by hand…
Approach
I let it run brute force for a bit to see how long it would take. I am guessing days to weeks.
So, I stepped back and went through my input to see what it is doing and if there is a pattern. And in fact there was a pattern. There are 14 blocks of equal length. There are 2 kinds of blocks. . The previous value of z is multipled by 26 and the new character from the input is added to it with an offset. . The current character with an offset is compared to the z mod 26. Essentially, the multiplying and modula with 26 is creating a stack and the comparison will give you a relationship between exactly 2 of the input characters. So, you have at the end 7 pairs with an offset. If all 7 are satisfied, then z = 0.
I did write some code to double check the answers that I did on paper. I guess you could write code to parse the input and derive the answer, but it would take much more time than just doing it by hand. And, this problem was strange somehow since I can’t see a way to get to an answer without using human intelligence to analyze the input and notice the pattern in the first place.
Run script
Run the solution with python solution.py
def process_input(file_contents):
commands = list()
for line in file_contents:
line = line.strip()
command = line[0:3]
var1 = line[4]
if command != "inp":
var2 = line[6:len(line)]
if var2[0] not in ["w","x","y","z"]:
var2 = int(var2)
commands.append((command,var1,var2))
else:
commands.append((command,var1))
return commands
def main():
with open("input.txt",'r') as alu_file:
alu_lines = alu_file.readlines()
commands = process_input(alu_lines)
for x_str in ["97919997299495","51619131181131"]:
i = 0
variables = {"w":0,"x":0,"y":0,"z":0}
for command in commands:
if command[0] == "inp":
variables[command[1]] = int(x_str[i])
i += 1
elif command[0] == "add":
if isinstance(command[2], int):
variables[command[1]] = variables[command[1]] + command[2]
else:
variables[command[1]] = variables[command[1]] + variables[command[2]]
elif command[0] == "mul":
if isinstance(command[2], int):
variables[command[1]] = variables[command[1]] * command[2]
else:
variables[command[1]] = variables[command[1]] * variables[command[2]]
elif command[0] == "div":
if isinstance(command[2], int):
variables[command[1]] = variables[command[1]] // command[2]
else:
variables[command[1]] = variables[command[1]] // variables[command[2]]
elif command[0] == "mod":
if isinstance(command[2], int):
variables[command[1]] = variables[command[1]] % command[2]
else:
variables[command[1]] = variables[command[1]] % variables[command[2]]
else:
if isinstance(command[2], int):
if variables[command[1]] == command[2]:
variables[command[1]] = 1
else:
variables[command[1]] = 0
else:
if variables[command[1]] == variables[command[2]]:
variables[command[1]] = 1
else:
variables[command[1]] = 0
print(variables["z"])
main()Day 25: python
Day 25 of year 2021 https://adventofcode.com/2021/day/25
What I learned
-
Deepcopy on lists of lists. (Although I already knew this theoretically)
Approach
It’s actually straightforward. I put the input into a list of lists. I iterate over the lists of lists and check for ">"'s and move them to the right if possible and wrap if necessary. I do the same then for the "v"'s. I set a flag if anything moves in a round. And leave the while loop as soon as nothing has moved in the round. I count the rounds on the way. That’s it.
Run script
Run the solution with python solution.py
import copy
def process_input(file_contents):
lines_stripped = [line.strip() for line in file_contents]
seafloor = [list(line) for line in lines_stripped]
return seafloor
def main():
with open("input.txt",'r') as cuc_file:
cuc_lines = cuc_file.readlines()
seafloor = process_input(cuc_lines)
flag = 1
rounds = 0
while flag != 0:
flag = 0
new_floor = copy.deepcopy(seafloor)
for i,row in enumerate(seafloor):
for j,position in enumerate(row):
if position == ">":
if j < len(row)-1:
if row[j+1] == ".":
new_floor[i][j] = "."
new_floor[i][j+1] = ">"
flag = 1
else:
if row[0] == ".":
new_floor[i][j] = "."
new_floor[i][0] = ">"
flag = 1
seafloor = copy.deepcopy(new_floor)
for i,row in enumerate(seafloor):
for j,position in enumerate(row):
if position == "v":
if i < len(seafloor)-1:
if seafloor[i+1][j] == ".":
new_floor[i][j] = "."
new_floor[i+1][j] = "v"
flag = 1
else:
if seafloor[0][j] == ".":
new_floor[i][j] = "."
new_floor[0][j] = "v"
flag = 1
seafloor = copy.deepcopy(new_floor)
rounds += 1
print(rounds)
main()