quajak
: quajak
Table of Contents
- quajak
- 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
quajak
Day 00: python
Hello world for Advent of Code 2021
Python
Trying to go with consice yet readable Python.
Run the solution with python solution.py
print("Hello World!")Day 01: python
Advent of Code 2021
Python
Straightforward approach for first star. For the second star, I use an inefficent smaller buffer to store the values of the sliding window.
f = open("./one.txt", "r")
lines = [int(x.strip()) for x in f.readlines()]
change = 0
last = lines[0]
for line in lines:
change += last < line
last = line
print("Star 1", change)
change = 0
buf = lines[:3]
last = sum(buf)
for line in lines[3:]:
buf = buf[1:] + [line]
new = sum(buf)
change += last < new
last = new
print("Star 2", change)Day 02: python
Advent of Code 2021
Python
Straightforward approach for the first and second star.
f = open("./two.txt", "r")
lines = [x.strip() for x in f.readlines()]
x = 0
y = 0
for line in lines:
value = int(line.split(" ")[1])
if "forward" in line:
x += value
elif "down" in line:
y += value
else:
y -= value
print("Star 1", x * y)
aim = 0
x = 0
y = 0
for line in lines:
value = int(line.split(" ")[1])
if "forward" in line:
x += value
y += value * aim
elif "down" in line:
aim += value
else:
aim -= value
print("Star 2", x * y)Day 03: python
Advent of Code 2021
Python
For the first star, use list comprehension to get the relevant column of bits and use list.count to determine the most common bit.
For the second star, use the same approach and use list comprehension to filter the possible values until only one remains.
f = open("./three.txt", "r")
lines = [x.strip() for x in f.readlines()]
gamma = ""
for index in range(len(lines[0])):
bits = [line[index] for line in lines]
zeros = list(bits).count('0')
ones = list(bits).count('1')
if zeros > ones:
gamma += "0"
else:
gamma += "1"
epsilon = ""
for index in range(len(lines[0])):
bits = [line[index] for line in lines]
zeros = list(bits).count('0')
ones = list(bits).count('1')
if zeros < ones:
epsilon += "0"
else:
epsilon += "1"
print("Star 1", int(epsilon, 2) * int(gamma, 2))
oxygen_valid = list(lines)
index = 0
while len(oxygen_valid) > 1:
bits = [line[index] for line in oxygen_valid]
zeros = list(bits).count('0')
ones = list(bits).count('1')
if zeros > ones:
oxygen_valid = [line for line in oxygen_valid if line[index] == "0"]
else:
oxygen_valid = [line for line in oxygen_valid if line[index] == "1"]
index += 1
co = list(lines)
index = 0
while len(co) > 1:
bits = [line[index] for line in co]
zeros = list(bits).count('0')
ones = list(bits).count('1')
if zeros <= ones:
co = [line for line in co if line[index] == "0"]
else:
co = [line for line in co if line[index] == "1"]
index += 1
print("Star 2", int(oxygen_valid[0], 2) * int(co[0], 2))Day 04: python
Advent of Code 2021
Python
Define a class to track all non-drawn values on the board and all possible lines in a board and how many of the values in each have not been drawn. Then whenever a value is drawn decrement all counters if value is in the line and remove the value from the not-drawn list. For the first star, simply print when the first counter reaches 0, sum up the non-drawn values and multiply by the current value.
For the second star, modify the board to keep track of if the board has already been solved and draw until all boards have been finished.
f = open(".\day02\python\quajak\\four.txt", "r")
lines = [x.strip() for x in f.readlines()]
class Board:
def __init__(self, raw):
self.lines = []
self.values = []
self.won = False
# horizontal
for l in raw:
self.lines.append((5, l))
# vertical
lines = [[], [], [], [], []]
for l in raw:
for i in range(len(l)):
lines[i].append(l[i])
for l in lines:
self.lines.append((5, l))
for r in raw:
self.values += r
def add(self, val):
if val in self.values and not self.won:
self.values.remove(val)
else:
return 0
for i in range(len(self.lines)):
count, vals = self.lines[i]
if val in vals:
count -= 1
self.lines[i] = (count, vals)
if count == 0:
self.won = True
return sum(self.values) * val
return 0
drawn = []
draws = [int(ch) for ch in lines[0].split(",")]
boards = []
b_index = 0
index = 1
while len(lines) > index:
index += 1
raw = []
for i in range(5):
raw.append([int(c) for c in lines[index].split()])
index += 1
cur = Board(raw)
boards.append(cur)
first = False
last = 0
for d in draws:
for b in boards:
val = b.add(d)
if val != 0:
if not first:
print("Star 1", val)
first = True
last = val
print("Star 2", last)Day 05: python
Advent of Code 2021
Python
Since the board size is originally not known, use a dictionary of dictionary of integers to keep track how many lines are present at any point.
Then iterate over lines and add the necessary locations to the map.
f = open("five.txt", "r")
lines = [x.strip() for x in f.readlines()]
space = {}
for line in lines:
words = line.split(" ")
start = [int(w) for w in words[0].split(",")]
end = [int(w) for w in words[2].split(",")]
if start[0] == end[0]:
for i in range(min(start[1], end[1]), max(start[1], end[1]) + 1):
if not start[0] in space:
space[start[0]] = {i: 1}
else:
if i not in space[start[0]]:
space[start[0]][i] = 1
else:
space[start[0]][i] += 1
elif start[1] == end[1]:
for i in range(min(start[0], end[0]), max(start[0], end[0]) + 1):
if not i in space:
space[i] = {start[1]: 1}
else:
if start[1] not in space[i]:
space[i][start[1]] = 1
else:
space[i][start[1]] += 1
points = 0
for x in space.keys():
for y in space[x].keys():
if space[x][y] > 1:
points += 1
print("Star 1", points)
for line in lines:
words = line.split(" ")
start = [int(w) for w in words[0].split(",")]
end = [int(w) for w in words[2].split(",")]
if start[0] == end[0]:
pass # we already handled these cases in the first star
elif start[1] == end[1]:
pass
else:
x_dir = 1 if start[0] < end[0] else -1
y_dir = 1 if start[1] < end[1] else -1
for (x,y) in zip(range(start[0], end[0] + x_dir, x_dir), range(start[1], end[1] + y_dir, y_dir)):
if not x in space:
space[x] = {}
if not y in space[x]:
space[x][y] = 1
else:
space[x][y] += 1
points = 0
for x in space.keys():
for y in space[x].keys():
if space[x][y] > 1:
points += 1
print("Star 2", points)Day 06: python
Advent of Code 2021
Python
Went with the correct approach for the first star already and simply used dictionary(list would have been better in hindsight) to keep track of the number of fishes at each age.
f = open("six.txt", "r")
lines = [x.strip() for x in f.readlines()]
fishes = [int(num) for num in lines[0].split(",")]
ages = {}
for i in range(9):
ages[i] = 0
for fish in fishes:
ages[fish] += 1
# change range() for first star
for i in range(256):
n_ages = {}
for age in range(1, 9):
n_ages[age - 1] = ages[age]
n_ages[6] += ages[0]
n_ages[8] = ages[0]
ages = n_ages
print(sum(ages.values()))Day 07: python
Advent of Code 2021
Python
For the first star use numpy to determine the medium. The second star just brute force the possible range and use closed form of triangle values to calculate cost.
import numpy as np
f = open("seven.txt", "r")
lines = [x.strip() for x in f.readlines()]
nums = np.array([int(n) for n in lines[0].split(",")])
cur = np.median(nums)
print("Star 1", np.sum(np.abs(nums - cur)))
min = 10000000000000000
for i in range(100, 500):
dis = np.abs((nums - i))
cost =dis * (dis + 1) / 2
cost = np.sum(np.abs(cost))
if cost < min:
min = cost
print("Star 2", min)Day 08: python
Advent of Code 2021
Python
First store all digits with the same length in a dictionary.
For the first star for each word in the 4 letter output, check if only one possible digit has that length.
For the second star, first normalize all words by sorting the characters alphabetically.
Then solve the simple ones (where only one integer needs that many digits).
To solve the three cases with six digits, if the case includes all values of 4, its a 9, else if it contains all values of 1, its a 0, else its a 6.
To solve the cases with five cases, if it contains the 1, its a 3, if the entire letter is contained within the 9, its a 5, else its a 2.
Then convert each output into a integer and sum all outputs.
f = open("eight.txt", "r")
lines = [x.strip() for x in f.readlines()]
special = 0
for line in lines:
parts = line.split("|")
letters = [''.join(sorted(o.strip())) for o in parts[0].split()]
output = [''.join(sorted(o.strip())) for o in parts[1].split()]
lengths = {}
for word in letters:
word = word.strip()
length = len(word)
if length not in lengths:
lengths[length] = [word]
elif not word in lengths[length]:
lengths[length].append(word)
for length in lengths.keys():
if len(lengths[length]) == 1:
special += output.count(lengths[length][0])
print(special)
sum = 0
for line in lines:
parts = line.split("|")
letters = [''.join(sorted(o.strip())) for o in parts[0].split()]
output = [''.join(sorted(o.strip())) for o in parts[1].split()]
lengths = {}
for word in letters:
word = word.strip()
length = len(word)
if length not in lengths:
lengths[length] = [word]
elif not word in lengths[length]:
lengths[length].append(word)
values = {}
one = lengths[2][0]
four = lengths[4][0]
values[one] = 1
values[four] = 4
values[lengths[3][0]] = 7
eight = lengths[7][0]
values[eight] = 8
nine = ""
for val in lengths[6]:
if all(c in val for c in four):
nine = val
values[val] = 9
elif all(c in val for c in one):
values[val] = 0
else:
values[val] = 6
for val in lengths[5]:
if all(c in val for c in one):
values[val] = 3
elif len(set(list(val)).difference(list(nine))) == 0:
values[val] = 5
else:
values[val] = 2
o = values[output[0]] * 1000 + values[output[1]] * 100 + values[output[2]] * 10 + values[output[3]]
sum += o
print(sum)Day 09: python
Advent of Code 2021
Python
Construct a 2D array of all the values. For the first star, find all low points and sum their risks.
For the second star, store all the found low points positions in a list and "flood fill" outwards to find the size of the entire basin.
f = open("nine.txt", "r")
lines = [x.strip() for x in f.readlines()]
height = len(lines)
width = len(lines[0])
map = []
for line in lines:
cur = [int(ch) for ch in list(line)]
map.append(cur)
risk = 0
for y in range(height):
for x in range(width):
val = map[y][x]
if y !=0 and map[y-1][x] <= val:
continue
if y != height - 1 and map[y+1][x] <= val:
continue
if x != 0 and map[y][x-1] <= val:
continue
if x != width - 1 and map[y][x+1] <= val:
continue
risk += map[y][x] + 1
print(risk)
height = len(lines)
width = len(lines[0])
map = []
for line in lines:
cur = [int(ch) for ch in list(line)]
map.append(cur)
basins = []
low_points = []
for y in range(height):
for x in range(width):
val = map[y][x]
if y !=0 and map[y-1][x] <= val:
continue
if y != height - 1 and map[y+1][x] <= val:
continue
if x != 0 and map[y][x-1] <= val:
continue
if x != width - 1 and map[y][x+1] <= val:
continue
low_points.append((x,y))
for (x,y) in low_points:
size = 0
# low point grow outwards
to_check = [(x,y)]
while len(to_check) != 0:
pos = to_check.pop(0)
x,y = pos
val = map[y][x]
if val == 9:
continue
size += 1
if y !=0 and map[y-1][x] > val and map[y-1][x] != 9:
to_check.append((x,y-1))
if y != height - 1 and map[y+1][x] > val and map[y+1][x] != 9:
to_check.append((x, y + 1))
if x != 0 and map[y][x-1] > val and map[y][x-1] != 9:
to_check.append((x-1, y))
if x != width - 1 and map[y][x+1] > val and map[y][x+1] != 9:
to_check.append((x+1,y))
map[y][x] = 9
basins.append(size)
basins = sorted(basins, reverse=True)
print(basins[0] * basins[1] * basins[2])Day 10: python
Advent of Code 2021
Python
Use a stack and then for the first star track where the parsing fails and sum up the errors. For the second star, "clear" the stack while keeping score for each element removed.
f = open("ten.txt", "r")
lines = [x.strip() for x in f.readlines()]
score = 0
valid = []
for line in lines:
stack = list()
for ch in line:
if ch == "(" or ch =="{" or ch =="[" or ch =="<":
stack.append(ch)
elif ch == ")":
if stack[-1] == "(":
stack.pop()
else:
score += 3
break
elif ch == "}":
if stack[-1] == "{":
stack.pop()
else:
score += 1197
break
elif ch == "]":
if stack[-1] == "[":
stack.pop()
else:
score += 57
break
elif ch == ">":
if stack[-1] == "<":
stack.pop()
else:
score += 25137
break
else:
valid.append(line)
print(score)
score = []
for line in valid:
stack = []
for ch in line:
if ch == "(" or ch =="{" or ch =="[" or ch =="<":
stack.append(ch)
elif ch == ")":
if stack[-1] == "(":
stack.pop()
elif ch == "}":
if stack[-1] == "{":
stack.pop()
elif ch == "]":
if stack[-1] == "[":
stack.pop()
elif ch == ">":
if stack[-1] == "<":
stack.pop()
s = 0
stack.reverse()
for ch in stack:
s *= 5
if ch == "(":
s += 1
elif ch == "[":
s += 2
elif ch == "{":
s += 3
else:
s += 4
score.append(s)
score = sorted(score)
print(score[len(score)//2])Day 11: python
Advent of Code 2021
Python
Use a 2D array to store values. For simplicity keep border of 0s at the edges and only update the inner values. Each time step seperately increment and trigger flashes before setting flashed cells back to 0.
For part 1 simulate first 100 steps and count flash number for part 2, keep track of which cells flashed and compare the number to the size of the board.
f = open("eleven.txt", "r")
lines = [x.strip() for x in f.readlines()]
field = []
for line in lines:
field.append([0] + [int(ch) for ch in line] + [0])
field.insert(0, [0] * len(field[0]))
field.append([0] * len(field[0]))
width = len(field[0])
height = len(field)
flashes = 0
def flash(ax, ay):
global flashes
if (ax, ay) in flashed:
return
if ax == 0 or ax == width - 1:
return
if ay == 0 or ay == height - 1:
return
flashed.append((ax,ay))
flashes += 1
for dy in [-1, 0, 1]:
for dx in [-1, 0, 1]:
if dy == dx == 0:
continue
field[ay + dy][ax + dx] += 1
if field[ay + dy][ax + dx] > 9:
flash(ax + dx, ay + dy)
for _ in range(100):
flashed = []
for y in range(1, height - 1):
for x in range(1, width - 1):
field[y][x] += 1
if field[y][x] > 9:
flash(x,y)
for x,y in flashed:
field[y][x] = 0
print("Star 1", flashes)
turn = 0
while True:
flashed = []
for y in range(1, height - 1):
for x in range(1, width - 1):
field[y][x] += 1
if field[y][x] > 9:
flash(x,y)
for x,y in flashed:
field[y][x] = 0
turn += 1
if len(flashed) == (width - 2) * (height - 2):
break
print("Star 2", turn)Day 12: python
Advent of Code 2021
Python
Parse the data into a list of nodes and edges to construct a graph. For the first star, use a recursive function to generate all paths starting at a certain node until the end. When being called on a small node, the node is removed from the graph to ensure that the node is only visisted once.
The approach from the first star can not be easily extended to the second star, since the function assumed that it did not matter how a certain node was reached. So for the second star a new function was written which extends a path by one more node while ensuring that only one small node has already been visited.
from os import path
from typing import Dict, List
import copy
f = open("twelve.txt", "r")
lines = [x.strip() for x in f.readlines()]
class Node:
def __init__(self, name):
self.edges = []
self.name = name
self.small = name[0].islower()
places = []
nodes : Dict[str, Node] = {}
for line in lines:
parts = line.split("-")
if parts[0] not in places:
places.append(parts[0])
nodes[parts[0]] = Node(parts[0])
if parts[1] not in places:
places.append(parts[1])
nodes[parts[1]] = Node(parts[1])
nodes[parts[0]].edges.append(parts[1])
nodes[parts[1]].edges.append(parts[0])
def remove(name: str, graph: Dict[str, Node]):
del graph[name]
to_remove = set()
for node in graph.keys():
if name in graph[node].edges:
graph[node].edges.remove(name)
if len(graph[node].edges) == 0:
to_remove.add(graph[node].name)
for rem in to_remove:
remove(rem, graph)
def valid_paths_to_end(current: Node, graph: Dict[str, Node]) -> List[List[str]]:
if current.name == "end":
return [["end"]]
if current.small:
graph = copy.deepcopy(graph)
remove(current.name, graph)
ways = []
for edge in current.edges:
if edge in graph:
ways.extend([[current.name] + path for path in valid_paths_to_end(graph[edge], graph)])
return ways
print(len(valid_paths_to_end(nodes["start"], nodes)))
places = []
nodes : Dict[str, Node] = {}
for line in lines:
parts = line.split("-")
if parts[0] not in places:
places.append(parts[0])
nodes[parts[0]] = Node(parts[0])
if parts[1] not in places:
places.append(parts[1])
nodes[parts[1]] = Node(parts[1])
nodes[parts[0]].edges.append(parts[1])
nodes[parts[1]].edges.append(parts[0])
def continue_path(path : List[str], current: Node, graph: Dict[str, Node], has_double: bool) -> List[List[str]]:
if has_double and (current.small and current.name in path):
return []
if current.name == "end":
return [path + ["end"]]
if current.small and current.small in path or current.name == "start":
graph = copy.deepcopy(graph)
remove(current.name, graph)
ways = []
for edge in current.edges:
if edge in graph:
ways.extend(continue_path(path + [current.name], graph[edge], graph, has_double or (current.small and current.name in path)))
return ways
print(len(continue_path([], nodes["start"], nodes, False)))Day 13: python
Advent of Code 2021
Python
The code is based on transforming the folding operations into coordinate transformations and then iterativly executing them.
f = open("thirteen.txt", "r")
lines = [x.strip() for x in f.readlines()]
dots = []
for line in lines:
if line == "":
break
p = line.split(",")
dots.append((int(p[0]), int(p[1])))
folds = [line.split()[2] for line in lines if line.startswith("fold along ")]
fold = folds[0]
dir = fold[0]
line = int(fold[2:])
new_dots = []
for x,y in dots:
if dir == "y":
if y > line:
new_dots.append((x, y - 2 * (y - line)))
else:
new_dots.append((x, y))
elif dir == "x":
if x > line:
new_dots.append((x- 2 * (x - line), y))
else:
new_dots.append((x, y))
print(len(set(new_dots)))
for fold in folds:
dir = fold[0]
line = int(fold[2:])
new_dots = []
for x,y in dots:
if dir == "y":
if y > line:
new_dots.append((x, y - 2 * (y - line)))
else:
new_dots.append((x, y))
elif dir == "x":
if x > line:
new_dots.append((x- 2 * (x - line), y))
else:
new_dots.append((x, y))
dots = list(set(new_dots))
max_x = max([x for x,y in dots]) + 1
max_y = max([y for x,y in dots]) + 1
print(dots)
screen = []
for y in range(max_y):
screen.append([" "] * max_x)
for x,y in dots:
screen[y][x] = "#"
for s in screen:
print("".join(s))Day 14: python
Advent of Code 2021
Python
The additions are stored in a look up table. For the first star the actual polymer as a string is created. For the second star for efficiency reasons, only a dictioniary of all two value combinations and their occurance number are stored and incremented from step to step.
f = open("fourteen.txt", "r")
lines = [x.strip() for x in f.readlines()]
poly = lines[0]
polymer = lines[0]
lines = lines[2:]
rules = {}
for line in lines:
s = line.split(" -> ")
rules[s[0]] = s[1]
for i in range(10):
new = ""
for pos in range(len(polymer)):
pair = polymer[pos:pos+2]
if pair in rules:
new += pair[0] + rules[pair]
else:
new += pair[0]
polymer = new
chars = {}
for c in polymer:
if c not in chars:
chars[c] = polymer.count(c)
print(max(chars.values()) - min(chars.values()))
polymer = poly
pairs = {}
for pos in range(len(polymer)):
pair = polymer[pos:pos+2]
if pair not in pairs:
pairs[pair] = 1
else:
pairs[pair] += 1
for i in range(40):
#print(pairs)
d = {}
for key, value in pairs.items():
if key in rules:
d[key[0] + rules[key]] = d.get(key[0] + rules[key], 0) + value
d[rules[key] + key[1]] = d.get(rules[key] + key[1], 0) + value
else:
d[key] = d.get(key, 0) + value
pairs = d
chars = {}
for pair,count in pairs.items():
if pair[0] not in chars:
chars[pair[0]] = count
else:
chars[pair[0]] += count
# if len(pair) == 2:
# if pair[1] not in chars:
# chars[pair[1]] = count
# else:
# chars[pair[1]] += count
print(max(chars.values()) - min(chars.values()))Day 15: python
Advent of Code 2021
Python
Only solution for part 2 is in the code, part 1 is the same with simper 2d array creation. Code is a straightforward implementation of the A-Star algorithm.
f = open("fifteen.txt", "r")
lines = [x.strip() for x in f.readlines()]
risk = []
costs = []
for y in range(5):
for line in lines:
r = []
co = []
for x in range(5):
r.extend([(int(c) + x + y) if int(c) + x + y < 10 else int(c) + x + y - 9 for c in line])
co.extend([100000 for c in line])
risk.append(r)
costs.append(co)
costs[0][0] = 0
to_check = [(0,0)]
def check_field(x,y, base_cost):
return x >= 0 and y >= 0 and x != len(risk[0]) and y != len(risk) and base_cost + risk[y][x] < costs[y][x]
while len(to_check) != 0:
x,y = to_check.pop(0)
cost = costs[y][x]
if check_field(x-1, y, cost):
costs[y][x-1] = cost + risk[y][x-1]
to_check.append((x-1, y))
if check_field(x+1, y, cost):
costs[y][x+1] = cost + risk[y][x+1]
to_check.append((x+1, y))
if check_field(x, y-1, cost):
costs[y-1][x] = cost + risk[y-1][x]
to_check.append((x, y-1))
if check_field(x, y+1, cost):
costs[y+1][x] = cost + risk[y+1][x]
to_check.append((x, y+1))
print(costs[-1][-1])Day 16: python
Advent of Code 2021
Python
Just a lot of string/bit manipulation
from typing import Tuple
f = open("sixteen.txt", "r")
line = [x.strip() for x in f.readlines()][0]
b = bin(int(line, 16))[2:]
if int(line[0], 16) < 4:
b = "00" + b
elif int(line[0], 16) < 8:
b = "0" + b
def read_packet(data: str) -> Tuple[int, int, int]:
version = data[:3]
version = int(version, 2)
t = data[3:6]
t = int(t, 2)
pos = 6
if t == 4:
len = 0
last = False
value = ""
while not last:
last = data[pos] == "0"
value += data[pos+1:pos+5]
pos += 5
len += 1
value = int(value, 2)
return (value, version, pos)
else:
length = 11 if data[pos] == "1" else 15
vsum = version
pos += 1
values = []
if length == 15:
bits_subdata = int(data[pos:pos+length], 2)
pos += length
goal = pos + bits_subdata
while pos != goal:
val, v, l = read_packet(data[pos:])
vsum += v
pos += l
values.append(val)
else:
bits_subdata = int(data[pos:pos+length], 2)
pos += length
for i in range(bits_subdata):
val, v, l = read_packet(data[pos:])
vsum += v
pos += l
values.append(val)
if t == 0:
value = sum(values)
elif t == 1:
value = 1
for val in values:
value *= val
elif t == 2:
value = min(values)
elif t == 3:
value = max(values)
elif t == 5:
value = 1 if values[0] > values[1] else 0
elif t == 6:
value = 1 if values[0] < values[1] else 0
elif t == 7:
value = 1 if values[0] == values[1] else 0
return [value, vsum, pos]
print(read_packet(b))Day 17: python
Advent of Code 2021
Python
Brute force search over the possible valid input values.
from typing import Tuple
target_area_x = [241, 273]
target_area_y = [-97, -63]
def simulate_flight(dx, dy) -> Tuple[bool, int]:
x = 0
y = 0
max_y = 0
while x <= target_area_x[1] and y >= target_area_y[0]:
if x >= target_area_x[0] and y <= target_area_y[1]:
return [True, max_y]
x += dx
y += dy
if dy > 0:
max_y = max(max_y, y)
if dx != 0:
dx += -1 * dx // abs(dx)
dy -= 1
if y < target_area_y[1]:
return [False, -1]
return [False, -1]
max_y = -1
count = 0
for x in range(274):
for y in range(-97, 100):
hit, m = simulate_flight(x,y)
if hit:
count += 1
if max_y < m:
max_y = m
print(max_y)
print(count)Day 18: python
Advent of Code 2021
Python
Represent the number as a tree like structure where the leafs are actually numbers. Implement the operations as recursive operations on the nodes.
from typing import Tuple
from copy import deepcopy
f = open("eighteen.txt", "r")
lines = [x.strip() for x in f.readlines()]
class Number:
def __init__(self, x = None, y = None):
self.x = x
self.y = y
def __str__(self):
return f"[{self.x}, {self.y}]"
def __repr__(self):
return str(self)
def magnitude(self) -> int:
sum = 0
if isinstance(self.x, Number):
sum += 3 * self.x.magnitude()
else:
sum += 3 * self.x
if isinstance(self.y, Number):
sum += 2 * self.y.magnitude()
else:
sum += 2 * self.y
return sum
def parse_line(string) -> Number:
level = 0
current = ""
values = []
for char in string:
if char == "[":
if level != 0:
current += "["
level += 1
elif char == "]":
level -= 1
if level != 0:
current += "]"
elif char == ",":
if level == 1:
values.append(current)
current = ""
else:
current += ","
else:
current += char
values.append(current)
if len(values) != 2:
raise Exception
num = Number()
if values[0].isnumeric():
num.x = int(values[0])
else:
num.x = parse_line(values[0])
if values[1].isnumeric():
num.y = int(values[1])
else:
num.y = parse_line(values[1])
return num
numbers = []
for line in lines:
numbers.append(parse_line(line))
def do_explode(level: int, number: Number) -> Tuple[bool, bool, int, int]:
if level == 4:
return (True, True, number.x, number.y)
else:
if isinstance(number.x, Number):
changed, cleaned, dx, dy = do_explode(level + 1, number.x)
if changed:
if cleaned:
number.x = 0
if dy != 0:
cur = number
if isinstance(cur.y, Number):
cur = cur.y
while isinstance(cur.x, Number):
cur = cur.x
cur.x += dy
else:
cur.y += dy
return (True, False, dx, 0)
if isinstance(number.y, Number):
changed, should_clean, dx, dy = do_explode(level + 1, number.y)
if changed:
if should_clean:
number.y = 0
if dx != 0:
cur = number
if isinstance(cur.x, Number):
cur = cur.x
while isinstance(cur.y, Number):
cur = cur.y
cur.y += dx
else:
cur.x += dx
return (True, False, 0, dy)
else:
return (False, False, 0, 0)
else:
return (False, False, 0, 0)
def do_split(number: Number) -> bool:
if isinstance(number.x, Number):
hit = do_split(number.x)
if hit:
return True
else:
if number.x >= 10:
number.x = Number(number.x // 2, number.x - number.x // 2)
return True
if isinstance(number.y, Number):
hit = do_split(number.y)
if hit:
return True
else:
if number.y >= 10:
number.y = Number(number.y // 2, number.y - number.y // 2)
return True
return False
def add(vals) -> int:
sum = vals[0]
vals = vals[1:]
for num in vals:
old_sum = sum
sum = Number()
sum.x = old_sum
sum.y = num
changed = True
while changed:
changd = False
changed, _, _, _ = do_explode(0, sum)
if not changed:
changed = do_split(sum)
return sum.magnitude()
cp = deepcopy(numbers)
print(add(cp))
heightest = 0
for x in numbers:
for y in numbers:
if x != y:
val = add(deepcopy([x,y]))
if val > heightest:
heightest = val
print(heightest)Day 19: python
Advent of Code 2021
Python
Represent each scanner as an object with a method to generate all possible variations of the coordinates through rotations. Then brute force search between all scanners where they match up until all scanners relative positions have been found.
from typing import List, Tuple
f = open("nineteen.txt", "r")
lines = [x.strip() for x in f.readlines()]
class Scanner:
def __init__(self, id = int):
self.raw_beacons = []
self.beacons = set()
self.id = id
self.all = []
self.offset = None
def _rotate_coordinate(self, coord: List[int], rx: int, ry: int, rz: int) -> Tuple[int]:
vec = tuple(coord)
for i in range(rx):
vec = (vec[0], -1 * vec[2], vec[1])
for i in range(ry):
vec = (vec[2], vec[1], vec[0] * -1)
for i in range(rz):
vec = (vec[1] * -1, vec[0], vec[2])
return vec
def generate_rotations(self) -> List[List[Tuple[int]]]:
if len(self.all) != 0:
return self.all
for rx in range(4):
for ry in range(4):
for rz in range(4):
self.all.append([self._rotate_coordinate(coord, rx, ry, rz) for coord in self.raw_beacons])
self.all = [list(x) for x in set(tuple(x) for x in self.all)]
return self.all
scanners : List[Scanner] = []
current_scanner = None
for line in lines:
if line.startswith("---"):
line = line.replace("-","").strip().split()[1]
current_scanner = Scanner(int(line))
scanners.append(current_scanner)
elif len(line) != 0:
coords = [int(w) for w in line.split(",")]
current_scanner.raw_beacons.append((coords[0], coords[1], coords[2]))
scanners[0].offset = (0, 0, 0)
scanners[0].beacons = set(scanners[0].raw_beacons)
print(len(scanners[0].generate_rotations()))
unlocalized = [scanner for scanner in scanners if scanner.offset is None]
while len(unlocalized) != 0:
for scanner in unlocalized:
for other in scanners:
if other.offset is not None:
for variation in scanner.generate_rotations():
for base in other.beacons: # [0,0,0] aligned and orientated
for pos_match in variation:
dx = base[0] - pos_match[0]
dy = base[1] - pos_match[1]
dz = base[2] - pos_match[2]
matches = []
for to_check in variation:
moved = (to_check[0] + dx, to_check[1] + dy, to_check[2] + dz)
if abs(moved[0] - other.offset[0]) > 1000 or abs(moved[1] - other.offset[1]) > 1000 or abs(moved[2] - other.offset[2]) > 1000:
continue
if moved in other.beacons:
matches.append(moved)
else:
break
if len(matches) >= 12:
scanner.beacons = set([(beacon[0] + dx, beacon[1] + dy, beacon[2] + dz) for beacon in variation])
scanner.offset = (dx, dy, dz)
print(f"Found scanner {scanner.id} at " + str(scanner.offset))
break
if scanner.offset is not None:
break
if scanner.offset is not None:
break
if scanner.offset is not None:
break
unlocalized = [scanner for scanner in scanners if scanner.offset is None]
print(len(unlocalized), " left to position")
beacons = set()
for scanner in scanners:
for beacon in scanner.beacons:
beacons.add(beacon)
print(len(beacons))
dis = 0
for a in scanners:
for b in scanners:
d = abs(a.offset[0] - b.offset[0]) + abs(a.offset[1] -b.offset[1]) + abs(a.offset[2] - b.offset[2])
if d > dis:
dis = d
print(dis)Day 20: python
Advent of Code 2021
Python
Use a dictionary to store known positions to easily allow scaling the grid as the iterations occur. It is important to track the background value for all pixels which are not explicitly calculated.
f = open("twenty.txt", "r")
lines = [x.strip() for x in f.readlines()]
color_table = lines[0].replace(".","0").replace("#", "1")
lines = lines[2:]
image = {}
y = 0
for line in lines:
line = line.replace(".","0").replace("#", "1")
x = 0
for ch in line:
image[(x,y)] = ch
x += 1
y += 1
background = "0"
for i in range(50):
min_x = min([x for x,y in image.keys()]) - 2
max_x = max([x for x,y in image.keys()]) + 2
min_y = min([y for x,y in image.keys()]) - 2
max_y = max([y for x,y in image.keys()]) + 2
new_image = {}
for x in range(min_x, max_x + 1):
for y in range(min_y, max_y + 1):
val = image.get((x-1, y-1), background) + image.get((x, y-1), background) + image.get((x+1, y-1), background) + image.get((x-1, y), background) + image.get((x, y), background) +image.get((x+1, y), background) \
+ image.get((x-1, y+1), background) + image.get((x, y+1), background) + image.get((x+1, y+1), background)
val = int(val, 2)
new_image[(x,y)] = color_table[val]
image = new_image
background = color_table[int(background * 9, 2)]
min_x = min([x for x,y in image.keys()]) - 1
max_x = max([x for x,y in image.keys()]) + 1
min_y = min([y for x,y in image.keys()]) - 1
max_y = max([y for x,y in image.keys()]) + 1
for y in range(min_y, max_y + 1):
line = ""
for x in range(min_x, max_x + 1):
line += image.get((x,y), "0")
print(line)
print(sum([1 if pix == "1" else 0 for pos, pix in image.items()]))Day 21: python
Advent of Code 2021
Python
First star implementation is straight forward, for the second star use a recursive function. The individual three dice throws are combined into results with frequencies. This speeds up calculation significantly and makes the function simpler.
from typing import List, Tuple
f = open("twentyone.txt", "r")
lines = [x.strip() for x in f.readlines()]
pos = [4, 6]
score = [0, 0]
die = 1
num = 0
turn = 0
while score[0] < 1000 and score[1] < 1000:
dis = 3 * die + 3
die += 3
pos[turn] += dis
pos[turn] = (pos[turn] - 1) % 10 + 1
score[turn] += pos[turn]
turn += 1
turn %= 2
num += 3
print(score[turn]* num)
known_pos = {}
rolls = {3:1, 4:3, 5:6, 6:7, 7:6, 8:3, 9:1}
def play_turn(cur: int, pos: List[int], score: List[int]) -> List[int]:
if score[1 - cur] >= 21:
res = [0,0]
res[1 - cur] = 1
return res
state = (pos[0], pos[1], score[0], score[1], cur)
if state in known_pos:
return known_pos[state]
results = [0,0]
for die in rolls.keys():
npos = list(pos)
npos[cur] = (npos[cur] + die - 1) % 10 + 1
nscore = list(score)
nscore[cur] += npos[cur]
res = play_turn(1 - cur, npos, nscore)
results[0] += res[0] * rolls[die]
results[1] += res[1] * rolls[die]
known_pos[state] = results
return results
print(max(play_turn(0, [4,6], [0, 0])))Day 22: python
Advent of Code 2021
Python
The code stores the cubes which are either all off or all on. Every additional cube results in the old cubes being seperated into up to 9 new cubes.
f = open("twentytwo.txt", "r")
lines = [x.strip() for x in f.readlines()]
commands = []
for line in lines:
p = line.split(" ")
dims = [[int(val) for val in dim.split("=")[1].split("..")] for dim in p[1].split(",")]
dims[0][1] += 1
dims[1][1] += 1
dims[2][1] += 1
commands.append((0 if p[0] == "off" else 1, dims))
def intersects(range1, range2):
return range2[0] <= range1[1] and range1[0] <= range2[1]
def valid(x, y, z):
return min(x) > 0 and min(y) > 0 and min(z) > 0
def line_split(l1, l2, val1, val2):
res = []
if l1[0] < l2[0]:
res.append([val1, [l1[0], l2[0]]])
res.append([val2, [max(l1[0], l2[0]), min(l1[1], l2[1])]])
if l1[1] > l2[1]:
res.append([val1, [l2[1], l1[1]]])
return res
def split(val1, x1, y1, z1, val2, x2, y2, z2):
res = []
x_split = line_split(x1, x2, val1, val2)
y_split = line_split(y1, y2, val1, val2)
z_split = line_split(z1, z2, val1, val2)
for x in x_split:
for y in y_split:
for z in z_split:
val = val2 if x[0] == y[0] == z[0] == val2 else val1
res.append([val, [x[1], y[1], z[1]]])
return res
regions = [[0, [[-10000000, 10000001], [-10000000, 10000001], [-10000001, 10000001]]]]
for command, cube in commands:
x = cube[0]
y = cube[1]
z = cube[2]
new_regions = []
for region in regions:
if region[0] != command:
if intersects(region[1][0], x) and intersects(region[1][1], y) and intersects(region[1][2], z):
new_regions.extend(split(region[0], region[1][0], region[1][1], region[1][2], command, x, y, z))
else:
new_regions.append(region)
else:
new_regions.append(region)
regions = new_regions
on = 0
for region in regions:
if region[0] == 1:
dim = region[1]
on += (dim[0][1] - dim[0][0]) * (dim[1][1] - dim[1][0]) * (dim[2][1] - dim[2][0])
print(on)Day 23: python
Advent of Code 2021
Python
A very inefficient and slow solution but I couldnt think of anything quicker. The algorithm works recursively, first checking if anyone can move to their final position, since there is no reason to wait if they can. Otherwise recursively try all possible moves to a waiting position to determine the cheapest one. For the second star the implementation details had to be changed but the idea is the same. No idea why there is an off by 2000 error in the second star.
from copy import deepcopy
import inspect
f = open("twentythree.txt", "r")
lines = [x.strip() for x in f.readlines()]
goals = {1: 0, 10: 1, 100: 2, 1000: 3}
habitant = {0: 1, 1: 10, 2: 100, 3: 1000}
length = 2
def get_move_count(room, index, wait_places, wait_place, move_cost):
moves = length - index
if wait_place == 0:
moves += 1
wait_place = 1
if wait_place == 7:
moves += 1
wait_place = 6
goal_pos = room * 2 + 1
cur_pos = (wait_place - 1) * 2
for to_check in range(min(cur_pos, goal_pos), max(cur_pos, goal_pos) +1):
if to_check % 2 == 0:
if wait_places[to_check // 2 + 1] is not None and to_check != cur_pos:
return -1
moves += abs(cur_pos - goal_pos)
return moves * move_cost
def find_best_move(rooms, wait_places, current_cost, best) -> int:
if current_cost > best:
return -1
if all([val == 1 for val in rooms[0]]) and all([val == 10 for val in rooms[1]]) and all([val == 100 for val in rooms[2]]) and all([val == 1000 for val in rooms[3]]):
return current_cost
for i, w in enumerate(wait_places):
if w is not None:
if rooms[goals[w]][1] is None:
if rooms[goals[w]][0] == w:
cost = get_move_count(goals[w], 1, wait_places, i, w)
if cost > 0:
rooms[goals[w]][1] = w
wait_places[i] = None
return find_best_move(deepcopy(rooms), deepcopy(wait_places), current_cost + cost, best)
if rooms[goals[w]][0] is None:
cost = get_move_count(goals[w], 0, wait_places, i, w)
if cost > 0:
rooms[goals[w]][0] = w
wait_places[i] = None
return find_best_move(deepcopy(rooms), deepcopy(wait_places), current_cost + cost, best)
fbest = 1000000000000
for i, r in enumerate(rooms):
if r[1] is None and r[0] is not None and r[0] != habitant[i]:
for k, w in enumerate(wait_places):
if w is not None:
continue
cost = get_move_count(i, 0, wait_places, k, r[0])
if cost > 0:
_rooms = deepcopy(rooms)
_wait_places = deepcopy(wait_places)
_wait_places[k] = _rooms[i][0]
_rooms[i][0] = None
t_cost = find_best_move(_rooms, _wait_places, current_cost + cost, best)
if t_cost > 0 and t_cost < fbest:
fbest = t_cost
if current_cost == 0:
print(fbest)
elif (r[1] != habitant[i] or r[0] != habitant[i]) and r[1] != None:
for k, w in enumerate(wait_places):
if w is not None:
continue
cost = get_move_count(i, 1, wait_places, k, r[1])
if cost > 0:
_rooms = deepcopy(rooms)
_wait_places = deepcopy(wait_places)
_wait_places[k] = _rooms[i][1]
_rooms[i][1] = None
t_cost = find_best_move(_rooms, _wait_places, current_cost + cost, best)
if t_cost > 0 and t_cost < fbest:
fbest = t_cost
if current_cost == 0:
print(fbest)
return fbest
def find_best_move_p2(rooms, wait_places, current_cost) -> int:
if all([val == 1 for val in rooms[0]]) and all([val == 10 for val in rooms[1]]) and all([val == 100 for val in rooms[2]]) and all([val == 1000 for val in rooms[3]]):
return current_cost
for i, w in enumerate(wait_places):
if w is not None:
for k in range(length - 1, -1, -1):
if rooms[goals[w]][k] is not None:
break
if k != 0 and rooms[goals[w]][k-1] is None:
continue
valid = True
for j in range(k):
if rooms[goals[w]][j] != w:
valid = False
break
if not valid:
break
cost = get_move_count(goals[w], k, wait_places, i, w)
if cost > 0:
rooms[goals[w]][k] = w
wait_places[i] = None
return find_best_move_p2(deepcopy(rooms), deepcopy(wait_places), current_cost + cost)
fbest = 1000000000000
for i, r in enumerate(rooms):
needs_emptying = any([ro is not None and ro != habitant[i] for ro in r])
if needs_emptying:
for j in range(length - 1, -1, -1):
if r[j] is not None:
for k, w in enumerate(wait_places):
if w is not None:
continue
cost = get_move_count(i, j, wait_places, k, r[j])
if cost > 0:
_rooms = deepcopy(rooms)
_wait_places = deepcopy(wait_places)
_wait_places[k] = _rooms[i][j]
_rooms[i][j] = None
t_cost = find_best_move_p2(_rooms, _wait_places, current_cost + cost)
if t_cost > 0 and t_cost < fbest:
if current_cost == 0:
print(t_cost)
fbest = t_cost
break
return fbest
rooms = [[1000, 10], [1, 10], [1, 100], [100, 1000]]
wait_places = [None, None, None, None, None, None, None]
print(find_best_move(rooms, wait_places, 0, 30000))
length = 4
rooms = [[1000, 1000, 1000, 10], [1, 10, 100, 10], [1, 1, 10, 100], [100, 100, 1, 1000]]
print(find_best_move_p2(rooms, wait_places, 0) - 2000)Day 24: python
Advent of Code 2021
No code
I solved this one using pen and paper after understanding what the computations are doing. The input is a series of 14 very similar operations, which each take one digit of the input. The operations use Left Shifts/Right Shifts (* 24 or / 24) to keep the individual values from operations seperate and build a stack. To find the final solutions one has to match which push/pop operations belong together, so that at the end the stack (and z) is 0. This is done by comparing the constants at the push and comparison location to determine the relationship betwen the pair of inputs.
Day 25: python
Advent of Code 2021
Python
Track positions of the two groups in seperate dictionaries and then run the simulation until nothing moves.
f = open("twentyfive.txt", "r")
lines = [x.strip() for x in f.readlines()]
width = len(lines[0])
height = len(lines)
left = {}
down = {}
for y in range(len(lines)):
left[y] = []
down[y] = []
for x in range(len(lines[y])):
if lines[y][x] == ">":
left[y].append(x)
elif lines[y][x] == "v":
down[y].append(x)
moved = 1
step = 0
while moved != 0:
step += 1
moved = 0
new_left = {}
new_down = {}
for y in left:
new_left[y] = []
for x in left[y]:
nx = x + 1 if x != (width - 1) else 0
if nx in left[y] or nx in down[y]:
new_left[y].append(x)
else:
moved += 1
new_left[y].append(nx)
left = new_left
for y in down:
new_down[y] = []
for y in down:
for x in down[y]:
ny = y + 1 if y != (height - 1) else 0
if x in left[ny] or x in down[ny]:
new_down[y].append(x)
else:
moved += 1
new_down[ny].append(x)
down = new_down
print(step)