For a fourth year I did some advent of code.
This year’s advent of code
Compared to last year, the problems was OKish but I didn’t really have fun except for a few problems.
Maybe I’m now too used to some types of problems (map exploration, interpreter…) so there is no sense of discovery any more, even when learning a new programming language.
Some exercices like the 8thor the 19th really felt tedious (but maybe it’s because I failed to find a better solution).
I even skipped exercices from the 24th because I didn’t have enough spoon to analyse the code to find the pattern that is probably here (so this day’s code is only generating a somehow optimized Python code).
Python
I wanted to learn some Python because I want to play with Blender’s Python API. As I’m experienced in Java and Ruby the Python syntax is not particulary alien to me, but I wanted some training before using it for a real project, to avoid dealing with too many unknown things at the same time.
As several of my coworkers are Python developers I’ll avoid to post publicly my opinion about Python 😬.
Disclaimers:
-
The bellow code is the first code I’ve written in Python, so it’s probably more an exemple of Python written by a Ruby dev who spent too much type coding in Java than an example of good Python code.
-
Code is provided as is, blablabla.
The code
Day 1
Part one
01/day_01_1.py
import sys
last_depth = None
deeper = 0
for line in open(sys.argv[1], 'r'):
current_depth = int(line)
if last_depth is not None:
if current_depth > last_depth:
deeper += 1
last_depth = current_depth
print(deeper)Part two
01/day_01_2.py
import sys
last_depth = None
deeper = 0
lines = list(map(int, open(sys.argv[1]).readlines()))
for line_index in range(2, len(lines)):
current_depth = lines[line_index - 2] + lines[line_index - 1] + lines[line_index]
if last_depth is not None:
if current_depth > last_depth:
deeper += 1
last_depth = current_depth
print(deeper)Day 2
Part one
02/day_02_1.py
import sys
import binascii
horizontal_position = 0
depth = 0
for line in open(sys.argv[1], 'r'):
splitted_line = line.split(' ')
value = int(splitted_line[1])
instruction = splitted_line[0]
match instruction:
case 'forward':
horizontal_position += value
case 'down':
depth += value
case 'up':
depth -= value
print(horizontal_position * depth)Part two
02/day_02_2.py
import sys
horizontal_position = 0
aim = 0
depth = 0
for line in open(sys.argv[1], 'r'):
splitted_line = line.split(' ')
value = int(splitted_line[1])
instruction = splitted_line[0]
match instruction:
case 'forward':
horizontal_position += value
depth += value * aim
case 'down':
aim += value
case 'up':
aim -= value
print(horizontal_position * depth)Day 3
Part one
03/day_03_1.py
import sys
number_of_lines = 0
one_bits_numbers = None
for line in open(sys.argv[1], 'r'):
number_of_lines += 1
if one_bits_numbers is None:
one_bits_numbers = [0] * (len(line) - 1)
for i in range(len(line)):
bit = line[i]
if bit == '1':
one_bits_numbers[i] += 1
gamma_rate = 0
gamma_rate = list(map(lambda b: '1' if (b > number_of_lines / 2) else '0', one_bits_numbers))
epsilon = list(map(lambda b: '1' if (b < number_of_lines / 2) else '0', one_bits_numbers))
print(one_bits_numbers)
gamma_rate_int = int(''.join(gamma_rate), 2)
print(gamma_rate_int)
epsilon_int = int(''.join(epsilon), 2)
print(epsilon_int)
print(gamma_rate_int * epsilon_int)Part two
03/day_03_2.py
import sys
lines = open(sys.argv[1]).readlines()
def finder(current_lines: [str], current_bit_index: int, comparator) -> str:
one_values = sum(map(lambda line: 1 if line[current_bit_index] == '1' else 0, current_lines))
value_to_find = '1' if comparator(one_values, (len(current_lines) / 2)) else '0'
new_lines = list(filter(lambda line: line[current_bit_index] == value_to_find, current_lines))
if len(new_lines) == 1:
return new_lines[0]
else:
return finder(new_lines, current_bit_index + 1, comparator)
oxygen = finder(lines, 0, lambda x, y: x >= y)
print(oxygen)
oxygen_int = int(''.join(oxygen), 2)
co2 = finder(lines, 0, lambda x, y: x < y)
print(co2)
co2_int = int(''.join(co2), 2)
print(oxygen_int * co2_int)Day 4
Part one
04/day_04_1.py
import sys
class Board:
def __init__(self, data: [str]):
self.data = []
self.checked_items = []
for line in data:
parsed_line = []
for index in range(0, 5):
value = line[index * 3:(index * 3 + 2)]
parsed_line.append(int(value))
self.data.append(parsed_line)
self.checked_items.append([False] * 5)
def draw_number(self, value: int) -> bool:
for line_index in range(0, 5):
line = self.data[line_index]
try:
column_index = line.index(value)
self.checked_items[line_index][column_index] = True
return True
except ValueError:
pass
return False
def win(self) -> bool:
for index in range(0, 5):
if self.win_line(index):
return True
if self.win_column(index):
return True
return False
def win_line(self, line_index: int) -> bool:
for i in range(0, 5):
if not self.checked_items[line_index][i]:
return False
return True
def win_column(self, column_index: int) -> bool:
for i in range(0, 5):
if not self.checked_items[i][column_index]:
return False
return True
def score(self) -> int:
result = 0
for index_line in range(0, 5):
for index_column in range(0, 5):
if not self.checked_items[index_line][index_column]:
result += self.data[index_line][index_column]
return result
lines = open(sys.argv[1]).readlines()
number_of_boards = int((len(lines) - 1) / 6)
boards = []
for board_index in range(0, number_of_boards):
boards.append(Board(lines[(2 + (board_index * 6)):(7 + (board_index * 6))]))
for move in map(int, lines[0].split(',')):
for board in boards:
board.draw_number(move)
if board.win():
print(board.score() * move)
exit(0)Part two
04/day_04_2.py
import sys
class Board:
def __init__(self, data: [str]):
self.data = []
self.checked_items = []
for line in data:
parsed_line = []
for index in range(0, 5):
value = line[index * 3:(index * 3 + 2)]
parsed_line.append(int(value))
self.data.append(parsed_line)
self.checked_items.append([False] * 5)
def draw_number(self, value: int) -> bool:
for line_index in range(0, 5):
line = self.data[line_index]
try:
column_index = line.index(value)
self.checked_items[line_index][column_index] = True
return True
except ValueError:
pass
return False
def win(self) -> bool:
for index in range(0, 5):
if self.win_line(index):
return True
if self.win_column(index):
return True
return False
def win_line(self, line_index: int) -> bool:
for i in range(0, 5):
if not self.checked_items[line_index][i]:
return False
return True
def win_column(self, column_index: int) -> bool:
for i in range(0, 5):
if not self.checked_items[i][column_index]:
return False
return True
def score(self) -> int:
result = 0
for index_line in range(0, 5):
for index_column in range(0, 5):
if not self.checked_items[index_line][index_column]:
result += self.data[index_line][index_column]
return result
lines = open(sys.argv[1]).readlines()
number_of_boards = int((len(lines) - 1) / 6)
current_boards = []
for board_index in range(0, number_of_boards):
current_boards.append(Board(lines[(2 + (board_index * 6)):(7 + (board_index * 6))]))
for move in map(int, lines[0].split(',')):
next_boards = []
for current_board in current_boards:
current_board.draw_number(move)
if current_board.win():
if len(current_boards) == 1:
print(current_board.score() * move)
exit(0)
else:
next_boards.append(current_board)
current_boards = next_boardsDay 5
Part one
05/day_05_1.py
import sys
import re
lines = open(sys.argv[1]).readlines()
line_regex = re.compile(r"^(?P<x1>\d+),(?P<y1>\d+) -> (?P<x2>\d+),(?P<y2>\d+)$")
checked_values = {}
def process_value(x: int, y: int, checked_values):
key = f"{x}-{y}"
if key in checked_values:
checked_values[key] += 1
else:
checked_values[key] = 1
for line in lines:
match = line_regex.search(line)
x1 = int(match.group('x1'))
y1 = int(match.group('y1'))
x2 = int(match.group('x2'))
y2 = int(match.group('y2'))
if x1 == x2:
r = range(y1, y2 + 1) if y2 > y1 else range(y2, y1 + 1)
for y in r:
process_value(x1, y, checked_values)
elif y1 == y2:
r = range(x1, x2 + 1) if x2 > x1 else range(x2, x1 + 1)
for x in r:
process_value(x, y1, checked_values)
print(len(list(filter(lambda x: x > 1, checked_values.values()))))Part two
05/day_05_2.py
import sys
import re
lines = open(sys.argv[1]).readlines()
line_regex = re.compile(r"^(?P<x1>\d+),(?P<y1>\d+) -> (?P<x2>\d+),(?P<y2>\d+)$")
checked_values = {}
def process_value(x: int, y: int, checked_values):
key = f"{x}-{y}"
if key in checked_values:
checked_values[key] += 1
else:
checked_values[key] = 1
for line in lines:
match = line_regex.search(line)
x1 = int(match.group('x1'))
y1 = int(match.group('y1'))
x2 = int(match.group('x2'))
y2 = int(match.group('y2'))
if x1 == x2:
r = range(y1, y2 + 1) if y2 > y1 else range(y2, y1 + 1)
for y in r:
process_value(x1, y, checked_values)
elif y1 == y2:
r = range(x1, x2 + 1) if x2 > x1 else range(x2, x1 + 1)
for x in r:
process_value(x, y1, checked_values)
else:
r_x = list(range(x1, x2 + 1) if x2 > x1 else range(x1, x2 - 1, -1))
r_y = list(range(y1, y2 + 1) if y2 > y1 else range(y1, y2 - 1, -1))
for index in range(0, len(r_x)):
process_value(r_x[index], r_y[index], checked_values)
print(len(list(filter(lambda x: x > 1, checked_values.values()))))Day 6
Part one
06/day_06_1.py
import sys
line = open(sys.argv[1]).readlines()[0]
current_fishes = [0] * 9
for starting_fish in line.split(','):
starting_fish_int = int(starting_fish)
current_fishes[starting_fish_int] += 1
print(current_fishes)
for day in range(0, 80):
next_fishes = [0] * 9
for index in range(1, 9):
next_fishes[index - 1] = current_fishes[index]
next_fishes[6] += current_fishes[0]
next_fishes[8] = current_fishes[0]
current_fishes = next_fishes
print(f"{day + 1} {current_fishes} {sum(current_fishes)}")Part two
06/day_06_2.py
import sys
line = open(sys.argv[1]).readlines()[0]
current_fishes = [0] * 9
for starting_fish in line.split(','):
starting_fish_int = int(starting_fish)
current_fishes[starting_fish_int] += 1
print(current_fishes)
for day in range(0, 256):
next_fishes = [0] * 9
for index in range(1, 9):
next_fishes[index - 1] = current_fishes[index]
next_fishes[6] += current_fishes[0]
next_fishes[8] = current_fishes[0]
current_fishes = next_fishes
print(f"{day + 1} {current_fishes} {sum(current_fishes)}")Day 7
Part one
07/day_07_1.py
import sys
positions_list = list(map(int, open(sys.argv[1]).readlines()[0].split(',')))
print(positions_list)
min_pos = min(positions_list)
max_pos = max(positions_list)
delta = max_pos - min_pos + 1
initial_positions = [0] * delta
for position in positions_list:
initial_positions[position - min_pos] += 1
def calculate_fuel(positions: [int], target_index: int) -> int:
result = 0
for index in range(0, len(positions)):
result += abs(target_index - index) * positions[index]
return result
print(initial_positions)
print(min(map(lambda i: calculate_fuel(initial_positions, i), range(0, len(initial_positions)))))Part two
07/day_07_2.py
import sys
positions_list = list(map(int, open(sys.argv[1]).readlines()[0].split(',')))
print(positions_list)
min_pos = min(positions_list)
max_pos = max(positions_list)
delta = max_pos - min_pos + 1
initial_positions = [0] * delta
for position in positions_list:
initial_positions[position - min_pos] += 1
def calculate_fuel(positions: [int], target_index: int) -> int:
result = 0
for index in range(0, len(positions)):
distance = abs(target_index - index)
result += int(distance * (distance + 1) * positions[index] / 2)
return result
print(initial_positions)
print(min(map(lambda i: calculate_fuel(initial_positions, i), range(0, len(initial_positions)))))Day 8
Part one
08/day_08_1.py
import sys
interesting_digits = [2, 3, 4, 7]
def process_line(line: str) -> int:
output_values = line.split('|')[1].strip().split(' ')
return len(list(filter(lambda v: len(v) in interesting_digits, output_values)))
print(sum(map(lambda l: process_line(l), open(sys.argv[1]).readlines())))Part two
08/day_08_2.py
import sys
uniques_number_of_segments_to_numbers = {
2: 1,
3: 7,
4: 4,
7: 8
}
def process_line(line: str) -> int:
splitted_lines = line.split('|')
signal_patterns = list(
map(lambda s: ''.join(sorted(s)), splitted_lines[0].strip().split(' ')))
output_values = list(
map(lambda s: ''.join(sorted(s)), splitted_lines[1].strip().split(' ')))
values = signal_patterns + output_values
length_to_values = {}
for i in range(0, 8):
length_to_values[i] = set()
for value in values:
length = len(value)
length_to_values[length].add(value)
for length in length_to_values.keys():
length_to_values[length] = list(length_to_values[length])
known_numbers = {}
# 1, 4, 7, 8: only one per segment length
for number, segments_to_numbers in uniques_number_of_segments_to_numbers.items():
if len(length_to_values[number]) == 1:
known_numbers[segments_to_numbers] = set(length_to_values[number][0])
length_to_values[number].remove(length_to_values[number][0])
# 6: 1 - 6 has one segment, 0 and 9 have two
if 1 in known_numbers:
for candidate in length_to_values[6]:
candidate_set = set(candidate)
if len(list(known_numbers[1] - candidate_set)) == 1:
known_numbers[6] = candidate_set
length_to_values[6].remove(candidate)
# 9 & 0: 9 - (merging 4 and 7) has one segment, 0 has two
if (4 in known_numbers) and (7 in known_numbers):
four_seven = known_numbers[4] | known_numbers[7]
for candidate in length_to_values[6]:
candidate_set = set(candidate)
if len(list(candidate_set - four_seven)) == 1:
known_numbers[9] = candidate_set
length_to_values[6].remove(candidate)
for candidate in length_to_values[6]:
candidate_set = set(candidate)
if len(list(candidate_set - four_seven)) == 2:
known_numbers[0] = candidate_set
length_to_values[6].remove(candidate)
# 3: 1 - 3 has zero segment, 2 and 5 have two
if 1 in known_numbers:
for candidate in length_to_values[5]:
candidate_set = set(candidate)
if len(list(known_numbers[1] - candidate_set)) == 0:
known_numbers[3] = candidate_set
length_to_values[5].remove(candidate)
# 2 & 5: 5 - 6 has zero segment, 2 - 6 has one
if 6 in known_numbers:
for candidate in length_to_values[5]:
candidate_set = set(candidate)
if len(list(candidate_set - known_numbers[6])) == 0:
known_numbers[5] = candidate_set
length_to_values[5].remove(candidate)
for candidate in length_to_values[5]:
candidate_set = set(candidate)
if len(list(candidate_set - known_numbers[6])) == 1:
known_numbers[2] = candidate_set
length_to_values[5].remove(candidate)
known_numbers_reverse = dict((''.join(sorted(v)), k) for k, v in known_numbers.items())
result = known_numbers_reverse[output_values[0]] * 1000 + \
known_numbers_reverse[output_values[1]] * 100 + \
known_numbers_reverse[output_values[2]] * 10 + \
known_numbers_reverse[output_values[3]]
return result
print(sum(map(lambda l: process_line(l), open(sys.argv[1]).readlines())))Day 9
Part one
09/day_09_1.py
import sys
def is_low_point(height_map: [[int]], map_height: int, map_width: int, line_index: int, column_index: int) -> bool:
point_value = height_map[line_index][column_index]
if (line_index > 0) and (height_map[line_index - 1][column_index] <= point_value):
return False
elif (column_index > 0) and (height_map[line_index][column_index - 1] <= point_value):
return False
if (line_index < (map_height - 1)) and (height_map[line_index + 1][column_index] <= point_value):
return False
elif (column_index < (map_width - 1)) and (height_map[line_index][column_index + 1] <= point_value):
return False
else:
return True
height_map = list(map(lambda line: list(map(int, line.strip())), open(sys.argv[1]).readlines()))
map_height = len(height_map)
map_width = len(height_map[0])
result = 0
for line_index in range(0, map_height):
for column_index in range(0, map_width):
if is_low_point(height_map, map_height, map_width, line_index, column_index):
point_value = height_map[line_index][column_index]
result += 1 + point_value
print(result)Part two
09/day_09_2.py
import sys
def is_low_point(height_map: [[int]], map_height: int, map_width: int, line_index: int, column_index: int) -> bool:
point_value = height_map[line_index][column_index]
if (line_index > 0) and (height_map[line_index - 1][column_index] <= point_value):
return False
elif (column_index > 0) and (height_map[line_index][column_index - 1] <= point_value):
return False
if (line_index < (map_height - 1)) and (height_map[line_index + 1][column_index] <= point_value):
return False
elif (column_index < (map_width - 1)) and (height_map[line_index][column_index + 1] <= point_value):
return False
else:
return True
def check_point(height_map, current_point_value, target_point, visited_points, next_points_to_visit) -> None:
target_value = height_map[target_point[0]][target_point[1]]
if (target_point not in visited_points) \
and (target_point not in next_points_to_visit) \
and (target_value < 9) \
and (target_value > current_point_value):
next_points_to_visit.append(target_point)
def calculate_bassin(height_map: [[int]], map_height: int, map_width: int, line_index: int, column_index: int) -> int:
visited_points = []
past_points_to_visit = [(line_index, column_index)]
while len(past_points_to_visit) != 0:
next_points_to_visit = []
for current_point in past_points_to_visit:
current_point_line_index, current_point_column_index = current_point
current_point_value = height_map[current_point_line_index][current_point_column_index]
if current_point_line_index > 0:
target_point = (current_point_line_index - 1, current_point_column_index)
check_point(height_map, current_point_value, target_point, visited_points, next_points_to_visit)
if current_point_column_index > 0:
target_point = (current_point_line_index, current_point_column_index - 1)
check_point(height_map, current_point_value, target_point, visited_points, next_points_to_visit)
if current_point_line_index < (map_height - 1):
target_point = (current_point_line_index + 1, current_point_column_index)
check_point(height_map, current_point_value, target_point, visited_points, next_points_to_visit)
if current_point_column_index < (map_width - 1):
target_point = (current_point_line_index, current_point_column_index + 1)
check_point(height_map, current_point_value, target_point, visited_points, next_points_to_visit)
visited_points.append(current_point)
past_points_to_visit = next_points_to_visit
return len(visited_points)
height_map = list(map(lambda line: list(map(int, line.strip())), open(sys.argv[1]).readlines()))
map_height = len(height_map)
map_width = len(height_map[0])
bassins = []
for line_index in range(0, map_height):
for column_index in range(0, map_width):
if is_low_point(height_map, map_height, map_width, line_index, column_index):
bassins.append(calculate_bassin(height_map, map_height, map_width, line_index, column_index))
bassins.sort()
print(bassins[-1] * bassins[-2] * bassins[-3])Day 10
Part one
10/day_10_1.py
import sys
matching_symbols = {
')': '(',
']': '[',
'}': '{',
'>': '<',
}
opening_symbols = list(matching_symbols.values())
closing_symbols = list(matching_symbols.keys())
def pop_valid(stack, char):
if stack[-1] == char:
stack.pop()
return True
else:
return False
def process_line(line: str):
stack = []
for char in line:
if char in opening_symbols:
stack.append(char)
elif char in closing_symbols:
if not pop_valid(stack, matching_symbols[char]):
return char
elif char == "\n":
return None
else:
raise Exception(char)
return None
symbol_to_value = {
')': 3,
']': 57,
'}': 1197,
'>': 25137,
}
result = 0
for line in open(sys.argv[1]).readlines():
line_result = process_line(line)
if line_result is not None:
result += symbol_to_value[line_result]
print(result)Part two
10/day_10_2.py
import sys
matching_symbols = {
')': '(',
']': '[',
'}': '{',
'>': '<',
}
opening_symbols = list(matching_symbols.values())
closing_symbols = list(matching_symbols.keys())
def pop_valid(stack, char):
if stack[-1] == char:
stack.pop()
return True
else:
return False
def process_line(line: str):
stack = []
for char in line:
if char in opening_symbols:
stack.append(char)
elif char in closing_symbols:
if not pop_valid(stack, matching_symbols[char]):
return None
elif char == "\n":
return stack
else:
raise Exception(char)
return stack
symbol_to_value = {
'(': 1,
'[': 2,
'{': 3,
'<': 4,
}
scores = []
for line in open(sys.argv[1]).readlines():
line_result = process_line(line)
if line_result is not None:
line_total = 0
for char in reversed(line_result):
line_total = (line_total * 5) + symbol_to_value[char]
scores.append(line_total)
scores.sort()
print(scores[int(len(scores) / 2)])Day 11
Part one
11/day_11_1.py
import sys
octopus_map = list(map(lambda line: list(map(int, line.strip())), open(sys.argv[1]).readlines()))
map_height = len(octopus_map)
map_width = len(octopus_map[0])
total_flashes = 0
def process_flashed(octopus_map: [[int]], flashed_line: int, flashed_column: int, new_flashes_to_process) -> None:
current_value = octopus_map[flashed_line][flashed_column]
octopus_map[flashed_line][flashed_column] += 1
if current_value == 9:
new_flashes_to_process.append((flashed_line, flashed_column))
def process_flash(octopus_map: [[int]], flash_line: int, flash_column: int, map_height: int, map_width: int,
new_flashes_to_process) -> None:
north_available = flash_line > 0
south_available = flash_line < (map_height - 1)
west_available = flash_column > 0
east_available = flash_column < (map_width - 1)
if north_available:
process_flashed(octopus_map, flash_line - 1, flash_column, new_flashes_to_process)
if south_available:
process_flashed(octopus_map, flash_line + 1, flash_column, new_flashes_to_process)
if west_available:
process_flashed(octopus_map, flash_line, flash_column - 1, new_flashes_to_process)
if east_available:
process_flashed(octopus_map, flash_line, flash_column + 1, new_flashes_to_process)
if north_available and west_available:
process_flashed(octopus_map, flash_line - 1, flash_column - 1, new_flashes_to_process)
if north_available and east_available:
process_flashed(octopus_map, flash_line - 1, flash_column + 1, new_flashes_to_process)
if south_available and west_available:
process_flashed(octopus_map, flash_line + 1, flash_column - 1, new_flashes_to_process)
if south_available and east_available:
process_flashed(octopus_map, flash_line + 1, flash_column + 1, new_flashes_to_process)
def process_step(octopus_map: [[int]], map_height: int, map_width: int) -> int:
flashes_to_process = []
for line_index in range(0, map_height):
for column_index in range(0, map_width):
octopus_map[line_index][column_index] += 1
if octopus_map[line_index][column_index] == 10:
flashes_to_process.append((line_index, column_index))
while len(flashes_to_process) > 0:
new_flashes_to_process = []
for flash_to_process in flashes_to_process:
process_flash(octopus_map, flash_to_process[0], flash_to_process[1], map_height, map_width,
new_flashes_to_process)
flashes_to_process = new_flashes_to_process
flashes_number = 0
for line_index in range(0, map_height):
for column_index in range(0, map_width):
if octopus_map[line_index][column_index] > 9:
flashes_number += 1
octopus_map[line_index][column_index] = 0
return flashes_number
for step in range(0, 100):
current_flashes = process_step(octopus_map, map_height, map_width)
total_flashes += current_flashes
print(total_flashes)Part two
11/day_11_2.py
import sys
octopus_map = list(map(lambda line: list(map(int, line.strip())), open(sys.argv[1]).readlines()))
map_height = len(octopus_map)
map_width = len(octopus_map[0])
total_flashes = 0
def process_flashed(octopus_map: [[int]], flashed_line: int, flashed_column: int, new_flashes_to_process) -> None:
current_value = octopus_map[flashed_line][flashed_column]
octopus_map[flashed_line][flashed_column] += 1
if current_value == 9:
new_flashes_to_process.append((flashed_line, flashed_column))
def process_flash(octopus_map: [[int]], flash_line: int, flash_column: int, map_height: int, map_width: int,
new_flashes_to_process) -> None:
north_available = flash_line > 0
south_available = flash_line < (map_height - 1)
west_available = flash_column > 0
east_available = flash_column < (map_width - 1)
if north_available:
process_flashed(octopus_map, flash_line - 1, flash_column, new_flashes_to_process)
if south_available:
process_flashed(octopus_map, flash_line + 1, flash_column, new_flashes_to_process)
if west_available:
process_flashed(octopus_map, flash_line, flash_column - 1, new_flashes_to_process)
if east_available:
process_flashed(octopus_map, flash_line, flash_column + 1, new_flashes_to_process)
if north_available and west_available:
process_flashed(octopus_map, flash_line - 1, flash_column - 1, new_flashes_to_process)
if north_available and east_available:
process_flashed(octopus_map, flash_line - 1, flash_column + 1, new_flashes_to_process)
if south_available and west_available:
process_flashed(octopus_map, flash_line + 1, flash_column - 1, new_flashes_to_process)
if south_available and east_available:
process_flashed(octopus_map, flash_line + 1, flash_column + 1, new_flashes_to_process)
def process_step(octopus_map: [[int]], map_height: int, map_width: int) -> int:
flashes_to_process = []
for line_index in range(0, map_height):
for column_index in range(0, map_width):
octopus_map[line_index][column_index] += 1
if octopus_map[line_index][column_index] == 10:
flashes_to_process.append((line_index, column_index))
while len(flashes_to_process) > 0:
new_flashes_to_process = []
for flash_to_process in flashes_to_process:
process_flash(octopus_map, flash_to_process[0], flash_to_process[1], map_height, map_width,
new_flashes_to_process)
flashes_to_process = new_flashes_to_process
flashes_number = 0
for line_index in range(0, map_height):
for column_index in range(0, map_width):
if octopus_map[line_index][column_index] > 9:
flashes_number += 1
octopus_map[line_index][column_index] = 0
return flashes_number == (map_height * map_width)
current_step = 1
while True:
if process_step(octopus_map, map_height, map_width):
print(current_step)
exit(0)
current_step+= 1Day 12
Part one
12/day_12_1.py
import sys
caves_map = {}
for path in open(sys.argv[1]).readlines():
caves = path.strip().split('-')
from_cave = caves[0]
to_cave = caves[1]
if from_cave in caves_map:
caves_map[from_cave].append(to_cave)
else:
caves_map[from_cave] = [to_cave]
if to_cave in caves_map:
caves_map[to_cave].append(from_cave)
else:
caves_map[to_cave] = [from_cave]
pathes_reaching_the_end = 0
pathes_to_visit = [['start']]
while len(pathes_to_visit) != 0:
next_pathes_to_visit = []
for current_path in pathes_to_visit:
for target in caves_map[current_path[-1]]:
if target == 'end':
pathes_reaching_the_end += 1
elif target.islower():
if target not in current_path:
next_pathes_to_visit.append(current_path + [target])
elif target.isupper():
next_pathes_to_visit.append(current_path + [target])
else:
raise Exception(target)
pathes_to_visit = next_pathes_to_visit
print(pathes_reaching_the_end)Part two
12/day_12_2.py
import sys
caves_map = {}
for path in open(sys.argv[1]).readlines():
caves = path.strip().split('-')
from_cave = caves[0]
to_cave = caves[1]
if from_cave in caves_map:
caves_map[from_cave].append(to_cave)
else:
caves_map[from_cave] = [to_cave]
if to_cave in caves_map:
caves_map[to_cave].append(from_cave)
else:
caves_map[to_cave] = [from_cave]
class Path:
def __init__(self, path: [str], small_cave_double_visit: str|None):
self.path = path
self.small_cave_double_visit = small_cave_double_visit
pathes_reaching_the_end = 0
pathes_to_visit = [Path(['start'], None)]
while len(pathes_to_visit) != 0:
next_pathes_to_visit = []
for current_path in pathes_to_visit:
for target in caves_map[current_path.path[-1]]:
if target == 'end':
pathes_reaching_the_end += 1
elif target == 'start':
pass
elif target.islower():
if target not in current_path.path:
next_pathes_to_visit.append(Path(current_path.path + [target], current_path.small_cave_double_visit))
elif current_path.small_cave_double_visit is not None:
pass
elif current_path.path.count(target) == 1:
next_pathes_to_visit.append(Path(current_path.path + [target], target))
elif target.isupper():
next_pathes_to_visit.append(Path(current_path.path + [target], current_path.small_cave_double_visit))
else:
raise Exception(target)
pathes_to_visit = next_pathes_to_visit
print(pathes_reaching_the_end)Day 13
Part one
13/day_13_1.py
import sys
import re
page = open(sys.argv[1]).readlines()
dots = set()
last_dot_line_index = 0
for dot_line in page:
last_dot_line_index += 1
if dot_line == "\n":
break
dot_coordinates = list(map(int, dot_line.split(',')))
dots.add((dot_coordinates[0], dot_coordinates[1]))
fold_regex = re.compile(r"^fold along (?P<axis>[xy])=(?P<value>\d+)$")
def fold_y(fold_value: int, dots):
result = set()
for dot in dots:
dot_column, dot_line = dot
if dot_line < fold_value:
result.add(dot)
elif dot_line > fold_value:
result.add((dot_column, (2 * fold_value) - dot_line))
return result
def fold_x(fold_value: int, dots):
result = set()
for dot in dots:
dot_column, dot_line = dot
if dot_column < fold_value:
result.add(dot)
elif dot_column > fold_value:
result.add(((2 * fold_value) - dot_column, dot_line))
return result
fold_line = page[last_dot_line_index]
match = fold_regex.search(fold_line)
fold_axis = match.group('axis')
fold_value = int(match.group('value'))
match fold_axis:
case 'x':
dots = fold_x(fold_value, dots)
case 'y':
dots = fold_y(fold_value, dots)
case _:
raise Exception(fold_axis)
print(len(list(dots)))Part two
13/day_13_2.py
import sys
import re
page = open(sys.argv[1]).readlines()
dots = set()
last_dot_line_index = 0
for dot_line in page:
last_dot_line_index += 1
if dot_line == "\n":
break
dot_coordinates = list(map(int, dot_line.split(',')))
dots.add((dot_coordinates[0], dot_coordinates[1]))
fold_regex = re.compile(r"^fold along (?P<axis>[xy])=(?P<value>\d+)$")
def fold_y(fold_value: int, dots):
result = set()
for dot in dots:
dot_column, dot_line = dot
if dot_line < fold_value:
result.add(dot)
elif dot_line > fold_value:
result.add((dot_column, (2 * fold_value) - dot_line))
return result
def fold_x(fold_value: int, dots):
result = set()
for dot in dots:
dot_column, dot_line = dot
if dot_column < fold_value:
result.add(dot)
elif dot_column > fold_value:
result.add(((2 * fold_value) - dot_column, dot_line))
return result
for fold_index in range(last_dot_line_index, len(page)):
fold_line = page[fold_index]
match = fold_regex.search(fold_line)
fold_axis = match.group('axis')
fold_value = int(match.group('value'))
match fold_axis:
case 'x':
dots = fold_x(fold_value, dots)
case 'y':
dots = fold_y(fold_value, dots)
case _:
raise Exception(fold_axis)
max_column = max(map(lambda dot: dot[0], dots))
max_line = max(map(lambda dot: dot[1], dots))
for line_index in range(0, max_line + 1):
for column_index in range(0, max_column + 1):
print('#' if (column_index, line_index) in dots else ' ', sep=' ', end='')
print()Day 14
Part one
14/day_14_1.py
import sys
import re
instructions = open(sys.argv[1]).readlines()
current_value = instructions[0].strip()
possible_elements = set(current_value)
rule_regex = re.compile(r"^(?P<from>[A-Z]{2}) -> (?P<to>[A-Z])$")
rules = {}
for rule in instructions[2:(len(instructions))]:
match = rule_regex.search(rule)
from_rule = match.group('from')
to_rule = match.group('to')
rules[from_rule] = to_rule
possible_elements.update(from_rule)
possible_elements.update(to_rule)
print(current_value)
for step in range(0,2):
next_value = []
for char_index in range(0, len(current_value) - 1):
current_pair = ''.join(current_value[char_index:char_index+2])
next_value.append(current_value[char_index])
applied_rule = rules[current_pair]
if applied_rule is not None:
next_value.append(applied_rule)
next_value.append(current_value[-1])
current_value = next_value
print(current_value)
cardinalities = list(map(lambda e: current_value.count(e), possible_elements))
print(max(cardinalities) - min(cardinalities))Part two
14/day_14_2.py
import sys
import re
instructions = open(sys.argv[1]).readlines()
initial_value = instructions[0].strip()
possible_elements = set(initial_value)
rule_regex = re.compile(r"^(?P<from>[A-Z]{2}) -> (?P<to>[A-Z])$")
rules = {}
for rule in instructions[2:(len(instructions))]:
match = rule_regex.search(rule)
from_rule = match.group('from')
to_rule = match.group('to')
rules[from_rule] = to_rule
possible_elements.update(from_rule)
possible_elements.update(to_rule)
def insert_value(value, number, pairs):
if value in pairs:
pairs[value] += number
else:
pairs[value] = number
current_pairs = {}
current_cardinalities = {}
for char_index in range(0, len(initial_value) - 1):
current_pair = initial_value[char_index:char_index + 2]
insert_value(current_pair, 1, current_pairs)
insert_value(initial_value[char_index], 1, current_cardinalities)
insert_value(initial_value[-1], 1, current_cardinalities)
def insert_value(value: str, number: int, pairs: dict) -> None:
if value in pairs:
pairs[value] += number
else:
pairs[value] = number
for step in range(0, 40):
next_pairs = {}
next_cardinalities = current_cardinalities.copy()
for value, number in current_pairs.items():
if value in rules:
rule_target = rules[value]
from_pair = f"{value[0]}{rule_target}"
to_pair = f"{rule_target}{value[1]}"
insert_value(rule_target, number, next_cardinalities)
insert_value(from_pair, number, next_pairs)
insert_value(to_pair, number, next_pairs)
else:
insert_value(value, number, next_pairs)
current_pairs = next_pairs
current_cardinalities = next_cardinalities
print(max(current_cardinalities.values()) - min(current_cardinalities.values()))Day 15
Part one
15/day_15_1.py
import sys
chiton_map = list(map(lambda line: list(map(int, line.strip())), open(sys.argv[1]).readlines()))
map_height = len(chiton_map)
map_width = len(chiton_map[0])
visited_positions = {(0, 0): 0}
current_positions = set()
current_positions.add((0, 0))
minimal_risk = 0
def check_position(current_risk, target_line, target_column, next_positions):
target_position = (target_line, target_column)
target_risk = current_risk + chiton_map[target_line][target_column]
if target_position in visited_positions:
if target_risk < visited_positions[target_position]:
visited_positions[target_position] = target_risk
next_positions.add(target_position)
else:
visited_positions[target_position] = target_risk
next_positions.add(target_position)
while len(current_positions) > 0:
next_positions = set()
for current_position in current_positions:
current_line, current_column = current_position
current_risk = visited_positions[current_position]
if current_line > 0:
check_position(current_risk, current_line - 1, current_column, next_positions)
if current_column > 0:
check_position(current_risk, current_line, current_column - 1, next_positions)
if current_line < (map_height - 1):
check_position(current_risk, current_line + 1, current_column, next_positions)
if current_column < (map_width - 1):
check_position(current_risk, current_line, current_column + 1, next_positions)
current_positions = next_positions
print(visited_positions[(map_height - 1, map_width - 1)])Part two
15/day_15_2.py
import sys
chiton_map = list(map(lambda line: list(map(int, line.strip())), open(sys.argv[1]).readlines()))
initial_map_height = len(chiton_map)
initial_map_width = len(chiton_map[0])
def process_risk(value: int) -> int:
return value if value < 10 else 1
for map_index in range(1, 5):
for current_line in chiton_map:
for tile_index in range(0, initial_map_width):
current_line.append(process_risk((current_line[tile_index + ((map_index - 1) * initial_map_width)] + 1)))
for map_index in range(1, 5):
for current_line_index in range(0, initial_map_height):
chiton_map.append(list(map(lambda c: process_risk(c + 1), chiton_map[current_line_index + ((map_index - 1) * initial_map_height)])))
map_height = initial_map_height * 5
map_width = initial_map_width * 5
visited_positions = {(0, 0): 0}
current_positions = set()
current_positions.add((0, 0))
minimal_risk = 0
def check_position(current_risk, target_line, target_column, next_positions):
target_position = (target_line, target_column)
target_risk = current_risk + chiton_map[target_line][target_column]
if target_position in visited_positions:
if target_risk < visited_positions[target_position]:
visited_positions[target_position] = target_risk
next_positions.add(target_position)
else:
visited_positions[target_position] = target_risk
next_positions.add(target_position)
while len(current_positions) > 0:
next_positions = set()
for current_position in current_positions:
current_line, current_column = current_position
current_risk = visited_positions[current_position]
if current_line > 0:
check_position(current_risk, current_line - 1, current_column, next_positions)
if current_column > 0:
check_position(current_risk, current_line, current_column - 1, next_positions)
if current_line < (map_height - 1):
check_position(current_risk, current_line + 1, current_column, next_positions)
if current_column < (map_width - 1):
check_position(current_risk, current_line, current_column + 1, next_positions)
current_positions = next_positions
print(visited_positions[(map_height - 1, map_width - 1)])Day 16
Part one
16/day_16_1.py
import sys
hex_sequence = open(sys.argv[1]).readlines()[0].strip()
sequence = bin(int(hex_sequence, 16))[2:].zfill(len(hex_sequence) * 4)
class Packet:
PACKET_VERSION_SIZE = 3
PACKET_TYPE_ID_SIZE = 3
PACKET_HEADER_SIZE = PACKET_VERSION_SIZE + PACKET_TYPE_ID_SIZE
PACKET_TYPE_LITERAL_VALUE = 4
def __init__(self, starting_position: int, version: int):
print(f"Starting to read a {self.__class__.__name__}")
self.starting_position = starting_position
self.version = version
@staticmethod
def read_binary(from_index: int, size: int) -> int:
read_content = sequence[from_index:(from_index + size)]
print(f"Reading {sequence[0:from_index]}[{read_content}]{sequence[from_index + size:]}")
return int(read_content, 2)
@staticmethod
def parse_packet(starting_position: int):
version = Packet.read_binary(starting_position, Packet.PACKET_VERSION_SIZE)
type_id = Packet.read_binary(starting_position + Packet.PACKET_VERSION_SIZE, Packet.PACKET_TYPE_ID_SIZE)
print(f"Starting to read a packet at {starting_position} with version {version} and type {type_id}")
match type_id:
case Packet.PACKET_TYPE_LITERAL_VALUE:
return LiteralValuePacket(starting_position, version)
case _:
return OperatorPacket(starting_position, version)
class LiteralValuePacket(Packet):
def __init__(self, starting_position: int, version: int):
Packet.__init__(self, starting_position, version)
self.last_position = starting_position + Packet.PACKET_HEADER_SIZE
value_bits = []
while sequence[self.last_position] == '1':
value_bits.extend(sequence[(self.last_position + 1):(self.last_position + 5)])
self.last_position += 5
value_bits.extend(sequence[(self.last_position + 1):(self.last_position + 5)])
self.value = int(''.join(value_bits), 2)
self.last_position += 5
print(f"\tValue is {self.value}")
print(f"Ending reading LiteralValuePacket, last position is {self.last_position}")
def total(self) -> int:
return self.version
class OperatorPacket(Packet):
SUB_PACKETS_LENGTH_TYPE_SIZE = 1
SUB_PACKETS_LENGTH_SIZE = 15
SUB_PACKETS_NUMBER_SIZE = 11
def __init__(self, starting_position: int, version: int):
Packet.__init__(self, starting_position, version)
length_type_id = Packet.read_binary(
starting_position + Packet.PACKET_HEADER_SIZE,
OperatorPacket.SUB_PACKETS_LENGTH_TYPE_SIZE)
print(f"\tLength type is {length_type_id}")
self.sub_packets = []
match length_type_id:
case 0:
sub_packets_size = Packet.read_binary(
starting_position + Packet.PACKET_HEADER_SIZE + OperatorPacket.SUB_PACKETS_LENGTH_TYPE_SIZE,
OperatorPacket.SUB_PACKETS_LENGTH_SIZE)
print(f"Sub-packets size is {sub_packets_size}")
current_sub_packet_position = starting_position + Packet.PACKET_HEADER_SIZE + OperatorPacket.SUB_PACKETS_LENGTH_TYPE_SIZE + OperatorPacket.SUB_PACKETS_LENGTH_SIZE
self.last_position = current_sub_packet_position + sub_packets_size
while current_sub_packet_position < self.last_position:
sub_packet = Packet.parse_packet(current_sub_packet_position)
self.sub_packets.append(sub_packet)
current_sub_packet_position = sub_packet.last_position
case 1:
sub_packets_number = Packet.read_binary(
starting_position + Packet.PACKET_HEADER_SIZE + OperatorPacket.SUB_PACKETS_LENGTH_TYPE_SIZE,
OperatorPacket.SUB_PACKETS_NUMBER_SIZE)
print(f"Sub-packets number is {sub_packets_number}")
current_sub_packet_position = starting_position + Packet.PACKET_HEADER_SIZE + OperatorPacket.SUB_PACKETS_LENGTH_TYPE_SIZE + OperatorPacket.SUB_PACKETS_NUMBER_SIZE
for packet_index in range(0, sub_packets_number):
sub_packet = Packet.parse_packet(current_sub_packet_position)
self.sub_packets.append(sub_packet)
current_sub_packet_position = sub_packet.last_position
self.last_position = self.sub_packets[-1].last_position
case _:
raise Exception(length_type_id)
print(f"Ending reading OperatorPacket, last position is {self.last_position}")
def total(self) -> int:
return self.version + sum(map(lambda p: p.total(), self.sub_packets))
main_packet = Packet.parse_packet(0)
print(main_packet.total())Part two
16/day_16_2.py
import sys
import functools
hex_sequence = sys.argv[1].strip()
sequence = bin(int(hex_sequence, 16))[2:].zfill(len(hex_sequence) * 4)
class Packet:
PACKET_VERSION_SIZE = 3
PACKET_TYPE_ID_SIZE = 3
PACKET_HEADER_SIZE = PACKET_VERSION_SIZE + PACKET_TYPE_ID_SIZE
PACKET_TYPES = {}
def __init__(self, starting_position: int, version: int):
self.starting_position = starting_position
self.version = version
@staticmethod
def read_binary(from_index: int, size: int) -> int:
read_content = sequence[from_index:(from_index + size)]
return int(read_content, 2)
@staticmethod
def parse_packet(starting_position: int):
version = Packet.read_binary(starting_position, Packet.PACKET_VERSION_SIZE)
type_id = Packet.read_binary(starting_position + Packet.PACKET_VERSION_SIZE, Packet.PACKET_TYPE_ID_SIZE)
if type_id in Packet.PACKET_TYPES:
return Packet.PACKET_TYPES[type_id](starting_position, version)
else:
raise Exception(type_id)
class LiteralValuePacket(Packet):
def __init__(self, starting_position: int, version: int):
Packet.__init__(self, starting_position, version)
self.last_position = starting_position + Packet.PACKET_HEADER_SIZE
value_bits = []
while sequence[self.last_position] == '1':
value_bits.extend(sequence[(self.last_position + 1):(self.last_position + 5)])
self.last_position += 5
value_bits.extend(sequence[(self.last_position + 1):(self.last_position + 5)])
self.value = int(''.join(value_bits), 2)
self.last_position += 5
print(self.total())
def total(self) -> int:
return self.value
class OperatorPacket(Packet):
SUB_PACKETS_LENGTH_TYPE_SIZE = 1
SUB_PACKETS_LENGTH_SIZE = 15
SUB_PACKETS_NUMBER_SIZE = 11
def __init__(self, starting_position: int, version: int):
Packet.__init__(self, starting_position, version)
length_type_id = Packet.read_binary(
starting_position + Packet.PACKET_HEADER_SIZE,
OperatorPacket.SUB_PACKETS_LENGTH_TYPE_SIZE)
self.sub_packets = []
match length_type_id:
case 0:
sub_packets_size = Packet.read_binary(
starting_position + Packet.PACKET_HEADER_SIZE + OperatorPacket.SUB_PACKETS_LENGTH_TYPE_SIZE,
OperatorPacket.SUB_PACKETS_LENGTH_SIZE)
current_sub_packet_position = starting_position + Packet.PACKET_HEADER_SIZE + OperatorPacket.SUB_PACKETS_LENGTH_TYPE_SIZE + OperatorPacket.SUB_PACKETS_LENGTH_SIZE
self.last_position = current_sub_packet_position + sub_packets_size
while current_sub_packet_position < self.last_position:
sub_packet = Packet.parse_packet(current_sub_packet_position)
self.sub_packets.append(sub_packet)
current_sub_packet_position = sub_packet.last_position
case 1:
sub_packets_number = Packet.read_binary(
starting_position + Packet.PACKET_HEADER_SIZE + OperatorPacket.SUB_PACKETS_LENGTH_TYPE_SIZE,
OperatorPacket.SUB_PACKETS_NUMBER_SIZE)
current_sub_packet_position = starting_position + Packet.PACKET_HEADER_SIZE + OperatorPacket.SUB_PACKETS_LENGTH_TYPE_SIZE + OperatorPacket.SUB_PACKETS_NUMBER_SIZE
for packet_index in range(0, sub_packets_number):
sub_packet = Packet.parse_packet(current_sub_packet_position)
self.sub_packets.append(sub_packet)
current_sub_packet_position = sub_packet.last_position
self.last_position = self.sub_packets[-1].last_position
case _:
raise Exception(length_type_id)
def total(self) -> int:
return self.version + sum(map(lambda p: p.total(), self.sub_packets))
def sub_packets_values(self) -> map:
return map(lambda p: p.total(), self.sub_packets)
class SumPacket(OperatorPacket):
def total(self) -> int:
return sum(self.sub_packets_values())
class ProductPacket(OperatorPacket):
def total(self) -> int:
return functools.reduce(lambda a, b: a * b, self.sub_packets_values())
class MinimumPacket(OperatorPacket):
def total(self) -> int:
return min(self.sub_packets_values())
class MaximumPacket(OperatorPacket):
def total(self) -> int:
return max(self.sub_packets_values())
class TestPacket(OperatorPacket):
def sub_packets_values(self):
if len(self.sub_packets) != 2:
raise Exception(self.sub_packets)
return self.sub_packets[0].total(), self.sub_packets[1].total()
class GreaterThanPacket(TestPacket):
def total(self) -> int:
sub_packet_1_value, sub_packet_2_value = self.sub_packets_values()
return 1 if sub_packet_1_value > sub_packet_2_value else 0
class LessThanPacket(TestPacket):
def total(self) -> int:
sub_packet_1_value, sub_packet_2_value = self.sub_packets_values()
return 1 if sub_packet_1_value < sub_packet_2_value else 0
class EqualToPacket(TestPacket):
def total(self) -> int:
sub_packet_1_value, sub_packet_2_value = self.sub_packets_values()
return 1 if sub_packet_1_value == sub_packet_2_value else 0
Packet.PACKET_TYPES[0] = SumPacket
Packet.PACKET_TYPES[1] = ProductPacket
Packet.PACKET_TYPES[2] = MinimumPacket
Packet.PACKET_TYPES[3] = MaximumPacket
Packet.PACKET_TYPES[4] = LiteralValuePacket
Packet.PACKET_TYPES[5] = GreaterThanPacket
Packet.PACKET_TYPES[6] = LessThanPacket
Packet.PACKET_TYPES[7] = EqualToPacket
main_packet = Packet.parse_packet(0)
print(main_packet.total())Day 17
Part one
17/day_17_1.py
import re
import sys
from enum import Enum, auto
input = open(sys.argv[1]).readlines()[0].strip()
line_regex = re.compile(r"^target area: x=(?P<x_min>-?\d+)..(?P<x_max>-?\d+), y=(?P<y_min>-?\d+)..(?P<y_max>-?\d+)$")
match = line_regex.search(input)
x_min = int(match.group('x_min'))
x_max = int(match.group('x_max'))
y_min = int(match.group('y_min'))
y_max = int(match.group('y_max'))
class Status(Enum):
IN_FLY = auto()
IN_TARGET_AREA = auto()
LOST = auto()
def calculate_trajectory(launch_x: int, launch_y: int):
current_x_velocity = launch_x
current_y_velocity = launch_y
current_x_position = 0
current_y_position = 0
max_y = 0
while True:
status = check_position(current_x_position, current_y_position)
if status != Status.IN_FLY:
return status, max_y
current_x_position += current_x_velocity
current_y_position += current_y_velocity
if current_x_velocity > 0:
current_x_velocity -= 1
elif current_x_velocity < 0:
current_x_velocity += 1
current_y_velocity -= 1
max_y = max(max_y, current_y_position)
def check_position(x: int, y: int) -> Status:
if y < y_min:
return Status.LOST
elif y > y_max:
return Status.IN_FLY
elif x_min <= x <= x_max:
return Status.IN_TARGET_AREA
else:
return Status.IN_FLY
def calculate_trajectories(x: int):
print(f"calculate_trajectories {x}")
max_y = 0
for y in range(-1000, 1000):
current_status, current_max_y = calculate_trajectory(x, y)
if current_status == Status.IN_TARGET_AREA:
max_y = max(max_y, current_max_y)
return max_y
max_y = 0
for x in range(1, x_max + 1):
max_y = max(max_y, calculate_trajectories(x))
print(max_y)Part two
17/day_17_2.py
import re
import sys
from enum import Enum, auto
input = open(sys.argv[1]).readlines()[0].strip()
line_regex = re.compile(r"^target area: x=(?P<x_min>-?\d+)..(?P<x_max>-?\d+), y=(?P<y_min>-?\d+)..(?P<y_max>-?\d+)$")
match = line_regex.search(input)
x_min = int(match.group('x_min'))
x_max = int(match.group('x_max'))
y_min = int(match.group('y_min'))
y_max = int(match.group('y_max'))
class Status(Enum):
IN_FLY = auto()
IN_TARGET_AREA = auto()
LOST = auto()
def calculate_trajectory(launch_x: int, launch_y: int):
current_x_velocity = launch_x
current_y_velocity = launch_y
current_x_position = 0
current_y_position = 0
while True:
status = check_position(current_x_position, current_y_position)
if status != Status.IN_FLY:
return status
current_x_position += current_x_velocity
current_y_position += current_y_velocity
if current_x_velocity > 0:
current_x_velocity -= 1
elif current_x_velocity < 0:
current_x_velocity += 1
current_y_velocity -= 1
def check_position(x: int, y: int) -> Status:
if y < y_min:
return Status.LOST
elif y > y_max:
return Status.IN_FLY
elif x_min <= x <= x_max:
return Status.IN_TARGET_AREA
else:
return Status.IN_FLY
total = 0
for x in range(1, x_max + 1):
for y in range(-1000, 1000):
current_status = calculate_trajectory(x, y)
if current_status == Status.IN_TARGET_AREA:
total += 1
print(total)Day 18
Part one
18/day_18_1.py
import math
import sys
import json
from enum import Enum, auto
lines = list(map(lambda l: json.loads(l), open(sys.argv[1]).readlines()))
class ExplosionStatus(Enum):
NO = auto()
JUST_EXPLODED = auto()
EXPLODED = auto()
def explode(values: [], level: int):
if isinstance(values, int):
return False, None, None
elif (level > 4) \
and isinstance(values, list) \
and isinstance(values[0], int) \
and isinstance(values[1], int):
return ExplosionStatus.JUST_EXPLODED, values[0], values[1]
else:
for value_index in range(0, len(values)):
value = values[value_index]
status, left_value, right_value = explode(value, level + 1)
if (status == ExplosionStatus.JUST_EXPLODED) or (status == ExplosionStatus.EXPLODED):
if status == ExplosionStatus.JUST_EXPLODED:
values[value_index] = 0
if (left_value is not None) and (value_index > 0):
if isinstance(values[value_index - 1], int):
values[value_index - 1] += left_value
else:
left_values = values[value_index - 1]
while not isinstance(left_values[- 1], int):
left_values = left_values[- 1]
left_values[-1] += left_value
left_value = None
if (right_value is not None) and (value_index < (len(values) - 1)):
if isinstance(values[value_index + 1], int):
values[value_index + 1] += right_value
else:
right_values = values[value_index + 1]
while not isinstance(right_values[0], int):
right_values = right_values[0]
right_values[0] += right_value
right_value = None
return ExplosionStatus.EXPLODED, left_value, right_value
return ExplosionStatus.NO, None, None
def split(values: []) -> bool:
for value_index in range(0, len(values)):
value = values[value_index]
if isinstance(value, int):
if value >= 10:
values[value_index] = [math.floor(value / 2), math.ceil(value / 2)]
return True
elif split(value):
return True
return False
def process(values: []):
while True:
status, _, _ = explode(values, 1)
if status != ExplosionStatus.NO:
return True
else:
return split(values)
def magniture(values: []):
left_value = values[0]
if isinstance(left_value, list):
left_value = magniture(left_value)
right_value = values[1]
if isinstance(right_value, list):
right_value = magniture(right_value)
return (left_value * 3) + (2 * right_value)
current_values = lines[0]
while process(current_values):
pass
for line_index in range(1, len(lines)):
current_values = [current_values, lines[line_index]]
while process(current_values):
pass
print(magniture(current_values))Part two
18/day_18_2.py
import math
import sys
import json
import copy
from enum import Enum, auto
lines = list(map(lambda l: json.loads(l), open(sys.argv[1]).readlines()))
class ExplosionStatus(Enum):
NO = auto()
JUST_EXPLODED = auto()
EXPLODED = auto()
def explode(values: [], level: int):
if isinstance(values, int):
return False, None, None
elif (level > 4) \
and isinstance(values, list) \
and isinstance(values[0], int) \
and isinstance(values[1], int):
return ExplosionStatus.JUST_EXPLODED, values[0], values[1]
else:
for value_index in range(0, len(values)):
value = values[value_index]
status, left_value, right_value = explode(value, level + 1)
if (status == ExplosionStatus.JUST_EXPLODED) or (status == ExplosionStatus.EXPLODED):
if status == ExplosionStatus.JUST_EXPLODED:
values[value_index] = 0
if (left_value is not None) and (value_index > 0):
if isinstance(values[value_index - 1], int):
values[value_index - 1] += left_value
else:
left_values = values[value_index - 1]
while not isinstance(left_values[- 1], int):
left_values = left_values[- 1]
left_values[-1] += left_value
left_value = None
if (right_value is not None) and (value_index < (len(values) - 1)):
if isinstance(values[value_index + 1], int):
values[value_index + 1] += right_value
else:
right_values = values[value_index + 1]
while not isinstance(right_values[0], int):
right_values = right_values[0]
right_values[0] += right_value
right_value = None
return ExplosionStatus.EXPLODED, left_value, right_value
return ExplosionStatus.NO, None, None
def split(values: []) -> bool:
for value_index in range(0, len(values)):
value = values[value_index]
if isinstance(value, int):
if value >= 10:
values[value_index] = [math.floor(value / 2), math.ceil(value / 2)]
return True
elif split(value):
return True
return False
def process(values: []):
while True:
status, _, _ = explode(values, 1)
if status != ExplosionStatus.NO:
return True
else:
return split(values)
def magniture(values: []):
left_value = values[0]
if isinstance(left_value, list):
left_value = magniture(left_value)
right_value = values[1]
if isinstance(right_value, list):
right_value = magniture(right_value)
return (left_value * 3) + (2 * right_value)
max_magniture = 0
for line_index_1 in range(0, len(lines) - 1):
for line_index_2 in range(line_index_1 + 1, len(lines)):
current_values = [copy.deepcopy(lines[line_index_1]), copy.deepcopy(lines[line_index_2])]
while process(current_values):
pass
current_magniture = magniture(current_values)
current_values = [copy.deepcopy(lines[line_index_2]), copy.deepcopy(lines[line_index_1])]
while process(current_values):
pass
current_magniture = magniture(current_values)
max_magniture = max(max_magniture, current_magniture)
print(max_magniture)Day 19
Part one
19/day_19_1.py
import re
import sys
class Scanner:
def __init__(self, index):
self.index = index
self.beacons = []
self.distances = []
def compute_distances(self):
permutations = self.beacons_permutations()
for permutation_index in range(0, len(permutations)):
permutation_value = permutations[permutation_index]
for index_1 in range(0, len(self.beacons)):
starting_beacon = permutation_value[index_1]
calculated_values = set()
for index_2 in range(0, len(self.beacons)):
if index_1 != index_2:
target_beacon = permutation_value[index_2]
calculated_values.add(
(
target_beacon[0] - starting_beacon[0],
target_beacon[1] - starting_beacon[1],
target_beacon[2] - starting_beacon[2]
)
)
self.distances.append((starting_beacon, permutation_index, calculated_values))
def __repr__(self) -> str:
return f"{self.index} {self.beacons}"
def beacons_permutations(self) -> [[tuple]]:
if self.index == 0:
self.beacons.sort()
return [self.beacons]
result = []
for i in range(0, 24):
result.append([])
for beacon in self.beacons:
x, y, z = beacon
values = [
(x, y, z),
(z, y, -x),
(-x, y, -z),
(-z, y, x),
(-x, -y, z),
(-z, -y, -x),
(x, -y, -z),
(z, -y, x),
(x, -z, y),
(y, -z, -x),
(-x, -z, -y),
(-y, -z, x),
(x, z, -y),
(-y, z, -x),
(-x, z, y),
(y, z, x),
(z, x, y),
(y, x, -z),
(-z, x, -y),
(-y, x, z),
(-z, -x, y),
(y, -x, z),
(z, -x, -y),
(-y, -x, -z)
]
for i in range(0, 24):
result[i].append(values[i])
for i in range(0, 24):
result[i].sort()
return result
scanners = []
scanner_regex = re.compile(r"^--- scanner (?P<scanner_id>\d+) ---$")
beacon_regex = re.compile(r"^(?P<x>-?\d+),(?P<y>-?\d+),(?P<z>-?\d+)$")
for line in open(sys.argv[1]).readlines():
line = line.strip()
scanner_match = scanner_regex.search(line)
if scanner_match:
scanners.append(Scanner(int(scanner_match.group('scanner_id'))))
else:
beacon_match = beacon_regex.search(line)
if beacon_match:
scanners[-1].beacons.append(
(int(beacon_match.group('x')), int(beacon_match.group('y')), int(beacon_match.group('z')))
)
for scanner in scanners:
scanner.compute_distances()
def check_pair(scanner_0, target_permutation_index_0, scanner_1):
for distance_0 in scanner_0.distances:
starting_beacon_0, permutation_index_0, calculated_values_0 = distance_0
if target_permutation_index_0 == permutation_index_0:
for distance_1 in scanner_1.distances:
starting_beacon_1, permutation_index_1, calculated_values_1 = distance_1
if len(calculated_values_0.intersection(calculated_values_1)) >= 11:
return distance_0, distance_1
return None
def search_match(scanners, found_scanners, beacons):
for found_scanner in found_scanners:
for searched_scanner_index in range(0, len(scanners)):
searched_scanner = scanners[searched_scanner_index]
check_pair_result = check_pair(found_scanner[1], found_scanner[2], searched_scanner)
if check_pair_result is not None:
distance_0, distance_1 = check_pair_result
origin = (
distance_0[0][0] - distance_1[0][0] + found_scanner[0][0],
distance_0[0][1] - distance_1[0][1] + found_scanner[0][1],
distance_0[0][2] - distance_1[0][2] + found_scanner[0][2],
)
beacons.add((distance_1[0][0] + origin[0],distance_1[0][1] + origin[1], distance_1[0][2] + origin[2]))
for beacon in distance_1[2]:
beacons.add((beacon[0] + distance_1[0][0] + origin[0], beacon[1] + distance_1[0][1] + origin[1], beacon[2] + distance_1[0][2] + origin[2]))
found_scanners.append(
(
origin,
searched_scanner,
distance_1[1])
)
scanners.pop(searched_scanner_index)
return True
return False
scanner_0 = scanners.pop(0)
found_scanners = [((0, 0, 0), scanner_0, 0)]
beacons = set(scanner_0.beacons)
while search_match(scanners, found_scanners, beacons):
pass
print(len(beacons))Part two
19/day_19_2.py
import re
import sys
class Scanner:
def __init__(self, index):
self.index = index
self.beacons = []
self.distances = []
def compute_distances(self):
permutations = self.beacons_permutations()
for permutation_index in range(0, len(permutations)):
permutation_value = permutations[permutation_index]
for index_1 in range(0, len(self.beacons)):
starting_beacon = permutation_value[index_1]
calculated_values = set()
for index_2 in range(0, len(self.beacons)):
if index_1 != index_2:
target_beacon = permutation_value[index_2]
calculated_values.add(
(
target_beacon[0] - starting_beacon[0],
target_beacon[1] - starting_beacon[1],
target_beacon[2] - starting_beacon[2]
)
)
self.distances.append((starting_beacon, permutation_index, calculated_values))
def __repr__(self) -> str:
return f"{self.index} {self.beacons}"
def beacons_permutations(self) -> [[tuple]]:
if self.index == 0:
self.beacons.sort()
return [self.beacons]
result = []
for i in range(0, 24):
result.append([])
for beacon in self.beacons:
x, y, z = beacon
values = [
(x, y, z),
(z, y, -x),
(-x, y, -z),
(-z, y, x),
(-x, -y, z),
(-z, -y, -x),
(x, -y, -z),
(z, -y, x),
(x, -z, y),
(y, -z, -x),
(-x, -z, -y),
(-y, -z, x),
(x, z, -y),
(-y, z, -x),
(-x, z, y),
(y, z, x),
(z, x, y),
(y, x, -z),
(-z, x, -y),
(-y, x, z),
(-z, -x, y),
(y, -x, z),
(z, -x, -y),
(-y, -x, -z)
]
for i in range(0, 24):
result[i].append(values[i])
for i in range(0, 24):
result[i].sort()
return result
scanners = []
scanner_regex = re.compile(r"^--- scanner (?P<scanner_id>\d+) ---$")
beacon_regex = re.compile(r"^(?P<x>-?\d+),(?P<y>-?\d+),(?P<z>-?\d+)$")
for line in open(sys.argv[1]).readlines():
line = line.strip()
scanner_match = scanner_regex.search(line)
if scanner_match:
scanners.append(Scanner(int(scanner_match.group('scanner_id'))))
else:
beacon_match = beacon_regex.search(line)
if beacon_match:
scanners[-1].beacons.append(
(int(beacon_match.group('x')), int(beacon_match.group('y')), int(beacon_match.group('z')))
)
for scanner in scanners:
scanner.compute_distances()
def check_pair(scanner_0, target_permutation_index_0, scanner_1):
for distance_0 in scanner_0.distances:
starting_beacon_0, permutation_index_0, calculated_values_0 = distance_0
if target_permutation_index_0 == permutation_index_0:
for distance_1 in scanner_1.distances:
starting_beacon_1, permutation_index_1, calculated_values_1 = distance_1
if len(calculated_values_0.intersection(calculated_values_1)) >= 11:
return distance_0, distance_1
return None
def search_match(scanners, found_scanners):
for found_scanner in found_scanners:
for searched_scanner_index in range(0, len(scanners)):
searched_scanner = scanners[searched_scanner_index]
check_pair_result = check_pair(found_scanner[1], found_scanner[2], searched_scanner)
if check_pair_result is not None:
distance_0, distance_1 = check_pair_result
origin = (
distance_0[0][0] - distance_1[0][0] + found_scanner[0][0],
distance_0[0][1] - distance_1[0][1] + found_scanner[0][1],
distance_0[0][2] - distance_1[0][2] + found_scanner[0][2],
)
found_scanners.append(
(
origin,
searched_scanner,
distance_1[1])
)
scanners.pop(searched_scanner_index)
return True
return False
scanner_0 = scanners.pop(0)
found_scanners = [((0, 0, 0), scanner_0, 0)]
while search_match(scanners, found_scanners):
pass
max_manhattan = 0
for index_0 in range(0, len(found_scanners)):
scanner_distance_0 = found_scanners[index_0][0]
for index_1 in range(0, len(found_scanners)):
if index_0 != index_1:
scanner_distance_1 = found_scanners[index_1][0]
max_manhattan = max(max_manhattan,
abs(scanner_distance_0[0] - scanner_distance_1[0]) + abs(scanner_distance_0[1] - scanner_distance_1[1]) + abs(scanner_distance_0[2] - scanner_distance_1[2])
)
print(max_manhattan)Day 20
Part one
20/day_20_1.py
import sys
input = open(sys.argv[1]).readlines()
algorithm = list(map(lambda c: False if (c == '#') else True, input[0].strip()))
data = dict()
initial_points = set()
initial_columns = len(input[2].strip())
initial_lines = len(input) - 2
for c in range(0, initial_columns):
for l in range(0, initial_lines):
data[(0, l, c)] = True if (input[2 + l][c] == '#') else False
def calculate_point(generation: int, line: int, column: int):
if not (generation, line, column) in data:
if generation == 0:
return False
else:
output_pixel_value = 0
for line_index in [line - 1, line, line + 1]:
for column_index in [column - 1, column, column + 1]:
output_pixel_value *= 2
if calculate_point(generation - 1, line_index, column_index):
output_pixel_value += 1
result = False if algorithm[output_pixel_value] else True
data[(generation, line, column)] = result
return result
else:
return data[(generation, line, column)]
generations = 2
result = 0
for l in range (-generations, initial_lines + generations + 1):
for c in range (-generations, initial_columns + generations + 1):
if calculate_point(generations, l, c):
result += 1
print(result)Part two
20/day_20_2.py
import sys
input = open(sys.argv[1]).readlines()
algorithm = list(map(lambda c: False if (c == '#') else True, input[0].strip()))
data = dict()
initial_points = set()
initial_columns = len(input[2].strip())
initial_lines = len(input) - 2
for c in range(0, initial_columns):
for l in range(0, initial_lines):
data[(0, l, c)] = True if (input[2 + l][c] == '#') else False
def calculate_point(generation: int, line: int, column: int):
if not (generation, line, column) in data:
if generation == 0:
return False
else:
output_pixel_value = 0
for line_index in [line - 1, line, line + 1]:
for column_index in [column - 1, column, column + 1]:
output_pixel_value *= 2
if calculate_point(generation - 1, line_index, column_index):
output_pixel_value += 1
result = False if algorithm[output_pixel_value] else True
data[(generation, line, column)] = result
return result
else:
return data[(generation, line, column)]
generations = 50
result = 0
for l in range (-generations, initial_lines + generations + 1):
for c in range (-generations, initial_columns + generations + 1):
if calculate_point(generations, l, c):
result += 1
print(result)Day 21
Part one
21/day_21_1.py
import sys
input = list(map(lambda l: int(l.strip().split(' ')[-1]), open(sys.argv[1]).readlines()))
player_positions = [input[0], input[1]]
player_scores = [0, 0]
def next_move(player_index: int, move_size: int):
player_positions[player_index] += move_size
while player_positions[player_index] > 10:
player_positions[player_index] -= 10
player_scores[player_index] += player_positions[player_index]
dice_number = 0
while True:
move_size = ((dice_number + 1) * 3) + 3
next_move(0, move_size)
dice_number += 3
if player_scores[0] >= 1000:
print(player_scores[1] * dice_number)
exit(0)
move_size = ((dice_number + 1) * 3) + 3
next_move(1, move_size)
dice_number += 3
if player_scores[1] >= 1000:
print(player_scores[0] * dice_number)
exit(0)
print(f"{player_positions} {player_scores} {dice_number}")Part two
21/day_21_2.py
import functools
import sys
input = list(map(lambda l: int(l.strip().split(' ')[-1]), open(sys.argv[1]).readlines()))
starting_positions = [input[0], input[1]]
DICES_THROWS = [3, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 9]
@functools.cache
def solve_situation(player_score_1, player_score_2, player_position_1, player_position_2):
player_wins_1 = 0
player_wins_2 = 0
for player_move_1 in DICES_THROWS:
new_player_position_1 = player_position_1 + player_move_1
while new_player_position_1 > 10:
new_player_position_1 -= 10
new_player_score_1 = player_score_1 + new_player_position_1
if new_player_score_1 >= 21:
player_wins_1 += 1
else:
solved_situation = solve_situation(
player_score_2,
new_player_score_1,
player_position_2,
new_player_position_1,
)
player_wins_1 += solved_situation[1]
player_wins_2 += solved_situation[0]
return player_wins_1, player_wins_2
print(max(solve_situation(0, 0, starting_positions[0], starting_positions[1])))Day 22
Part one
22/day_22_1.py
import re
import sys
grid = set()
instruction_regex = re.compile(
r"^(?P<status>on|off) x=(?P<x_min>-?\d+)..(?P<x_max>-?\d+),y=(?P<y_min>-?\d+)..(?P<y_max>-?\d+),z=(?P<z_min>-?\d+)..(?P<z_max>-?\d+)$")
for instruction in open(sys.argv[1]).readlines():
parsed_instruction = instruction_regex.search(instruction)
status = parsed_instruction.group('status')
x_min = int(parsed_instruction.group('x_min'))
x_max = int(parsed_instruction.group('x_max'))
y_min = int(parsed_instruction.group('y_min'))
y_max = int(parsed_instruction.group('y_max'))
z_min = int(parsed_instruction.group('z_min'))
z_max = int(parsed_instruction.group('z_max'))
for x in range(-50, 51):
if x_min <= x <= x_max:
for y in range(-50, 51):
if y_min <= y <= y_max:
for z in range(-50, 51):
if z_min <= z <= z_max:
if status == 'on':
grid.add((x, y, z))
else:
if (x, y, z) in grid:
grid.remove((x, y, z))
print(len(grid))Part two
22/day_22_2.py
import re
import sys
grid = set()
instruction_regex = re.compile(
r"^(?P<status>on|off) x=(?P<x_min>-?\d+)..(?P<x_max>-?\d+),y=(?P<y_min>-?\d+)..(?P<y_max>-?\d+),z=(?P<z_min>-?\d+)..(?P<z_max>-?\d+)$")
class Cuboid:
def __init__(self, x_min: int, x_max: int, y_min: int, y_max: int, z_min: int, z_max: int, status: bool):
self.x_min = x_min
self.x_max = x_max
self.y_min = y_min
self.y_max = y_max
self.z_min = z_min
self.z_max = z_max
self.status = status
def intersect(self, other) -> bool:
if not (self.x_min <= other.x_max and self.x_max >= other.x_min):
return False
if not (self.y_min <= other.y_max and self.y_max >= other.y_min):
return False
if not (self.z_min <= other.z_max and self.z_max >= other.z_min):
return False
return True
def intersection(self, other):
return Cuboid(
max(self.x_min, other.x_min),
min(self.x_max, other.x_max),
max(self.y_min, other.y_min),
min(self.y_max, other.y_max),
max(self.z_min, other.z_min),
min(self.z_max, other.z_max),
not other.status)
def volume(self) -> int:
return (self.x_max - self.x_min + 1) * (self.y_max - self.y_min + 1) * (self.z_max - self.z_min + 1)
known_cuboids = []
for instruction in open(sys.argv[1]).readlines():
parsed_instruction = instruction_regex.search(instruction)
status = parsed_instruction.group('status')
x_min = int(parsed_instruction.group('x_min'))
x_max = int(parsed_instruction.group('x_max'))
y_min = int(parsed_instruction.group('y_min'))
y_max = int(parsed_instruction.group('y_max'))
z_min = int(parsed_instruction.group('z_min'))
z_max = int(parsed_instruction.group('z_max'))
current_cuboid = Cuboid(x_min, x_max, y_min, y_max, z_min, z_max, status == 'on')
current_intersections = []
for cuboid in known_cuboids:
if current_cuboid.intersect(cuboid):
intersection = current_cuboid.intersection(cuboid)
current_intersections.append(intersection)
known_cuboids += current_intersections
if status == 'on':
known_cuboids.append(current_cuboid)
result = 0
for current_cuboid in known_cuboids:
current_volume = current_cuboid.volume()
result += current_volume * (1 if current_cuboid.status else -1)
print(result)Day 23
Part one
23/day_23_1.py
import sys
from enum import Enum, auto
from typing import NewType, Tuple
# #############
# #01.2.3.4.56#
# ###7#9#1#3###
# #8#0#2#4#
# #########
ItemType = NewType('ItemType', int)
ITEM_AMBER = ItemType(0)
ITEM_BRONZE = ItemType(1)
ITEM_COPPER = ItemType(2)
ITEM_DESERT = ItemType(3)
ITEM_EMPTY = ItemType(4)
Position = NewType('Position', int)
Move = Tuple[
ItemType, ItemType, ItemType, ItemType, ItemType, ItemType, ItemType, ItemType, ItemType, ItemType, ItemType, ItemType, ItemType, ItemType]
def slice_move(current_move: Move, min_position: Position, max_position: Position) -> Move:
current_move = list(current_move)
return tuple(
current_move[:min_position] +
current_move[max_position:(max_position + 1)] +
current_move[(min_position + 1):max_position] +
current_move[min_position:(min_position + 1)] +
current_move[max_position + 1:]
)
ITEM_TYPE_TO_ENERGY: dict[ItemType, int] = {
ITEM_AMBER: 1,
ITEM_BRONZE: 10,
ITEM_COPPER: 100,
ITEM_DESERT: 1000
}
CHAR_TO_ITEM_TYPE: dict[str, ItemType] = {
'A': ITEM_AMBER,
'B': ITEM_BRONZE,
'C': ITEM_COPPER,
'D': ITEM_DESERT,
'.': ITEM_EMPTY,
}
puzzle = open(sys.argv[1]).readlines()
initial_position: Move = tuple(
list(
map(
lambda c: CHAR_TO_ITEM_TYPE[c],
[
puzzle[1][1],
puzzle[1][2],
puzzle[1][4],
puzzle[1][6],
puzzle[1][8],
puzzle[1][10],
puzzle[1][11],
puzzle[2][3],
puzzle[3][3],
puzzle[2][5],
puzzle[3][5],
puzzle[2][7],
puzzle[3][7],
puzzle[2][9],
puzzle[3][9]]
)
)
)
TARGET_POSITION: Move = tuple(
([ITEM_EMPTY] * 7) + ([ITEM_AMBER] * 2) + ([ITEM_BRONZE] * 2) + ([ITEM_COPPER] * 2) + ([ITEM_DESERT] * 2))
print(initial_position)
known_moves: dict[Move, int] = dict()
known_moves[initial_position] = 0
min_energy = 0
max_energy = 0
min_solution_energy: int | None = None
moves_to_explores: dict[int, list[Move]] = dict()
moves_to_explores[0] = [initial_position]
class CanMoveInStatus(Enum):
TOP_ROOM = auto()
BOTTOM_ROOM = auto()
NO = auto()
TOP_ROOM_INDEX: dict[ItemType, Position] = {
ITEM_AMBER: Position(7), ITEM_BRONZE: Position(9), ITEM_COPPER: Position(11), ITEM_DESERT: Position(13)
}
BOTTOM_ROOM_INDEX: dict[ItemType, Position] = {
ITEM_AMBER: Position(8), ITEM_BRONZE: Position(10), ITEM_COPPER: Position(12), ITEM_DESERT: Position(14)
}
MOVE_RIGHT_TO_CHAMBER_MAX_POSITION: dict[ItemType, Position] = {
ITEM_AMBER: Position(1),
ITEM_BRONZE: Position(2),
ITEM_COPPER: Position(3),
ITEM_DESERT: Position(4)
}
MOVE_LEFT_TO_CHAMBER_MIN_POSITION: dict[ItemType, Position] = {
ITEM_AMBER: Position(2),
ITEM_BRONZE: Position(3),
ITEM_COPPER: Position(4),
ITEM_DESERT: Position(5)
}
def can_move_in(current_move: Move, item_type: ItemType) -> CanMoveInStatus:
top_content = current_move[TOP_ROOM_INDEX[item_type]]
bottom_content = current_move[BOTTOM_ROOM_INDEX[item_type]]
if top_content != ITEM_EMPTY:
return CanMoveInStatus.NO
elif bottom_content == ITEM_EMPTY:
return CanMoveInStatus.BOTTOM_ROOM
elif bottom_content == item_type:
return CanMoveInStatus.TOP_ROOM
else:
return CanMoveInStatus.NO
NUMBER_OF_MOVE_TO_TOP_ROOM: dict[ItemType, list[Position]] = {
ITEM_AMBER: [Position(3), Position(2), Position(2), Position(4), Position(6), Position(8), Position(9)],
ITEM_BRONZE: [Position(5), Position(4), Position(2), Position(2), Position(4), Position(6), Position(7)],
ITEM_COPPER: [Position(7), Position(6), Position(4), Position(2), Position(2), Position(4), Position(5)],
ITEM_DESERT: [Position(9), Position(9), Position(6), Position(4), Position(2), Position(2), Position(3)],
}
def move_right_to_chamber(current_move: Move, item_type: ItemType) -> Position | None:
for item_index in range(MOVE_RIGHT_TO_CHAMBER_MAX_POSITION[item_type], -1, -1):
if current_move[item_index] == item_type:
return Position(item_index)
elif current_move[item_index] != ITEM_EMPTY:
return None
return None
def move_left_to_chamber(current_move: Move, item_type: ItemType) -> Position | None:
for item_index in range(MOVE_LEFT_TO_CHAMBER_MIN_POSITION[item_type], 7):
if current_move[item_index] == item_type:
return Position(item_index)
elif current_move[item_index] != ITEM_EMPTY:
return None
return None
def process_move(move: Move, energy: int) -> None:
global max_energy
global known_moves
global moves_to_explores
if (move not in known_moves) or (known_moves[move] > energy):
print(f"\t\t\t\t\tNew move {move} for {energy}")
known_moves[move] = energy
if energy in moves_to_explores:
moves_to_explores[energy].append(move)
else:
moves_to_explores[energy] = [move]
max_energy = max(max_energy, energy)
def try_to_move_in(current_move: Move, current_energy: int, item_type: ItemType):
global min_solution_energy
global max_energy
move_in_status = can_move_in(current_move, item_type)
if move_in_status != CanMoveInStatus.NO:
move_right_index = move_right_to_chamber(current_move, item_type)
if move_right_index is not None:
number_of_moves = NUMBER_OF_MOVE_TO_TOP_ROOM[item_type][move_right_index]
target_index = TOP_ROOM_INDEX[item_type] if (move_in_status == CanMoveInStatus.TOP_ROOM) else \
BOTTOM_ROOM_INDEX[item_type]
new_move = slice_move(current_move, move_right_index, target_index)
if move_in_status == CanMoveInStatus.BOTTOM_ROOM:
number_of_moves += 1
new_energy = current_energy + (number_of_moves * ITEM_TYPE_TO_ENERGY[item_type])
if new_move == TARGET_POSITION:
if (min_solution_energy is None) or (min_solution_energy > new_energy):
min_solution_energy = new_energy
max_energy = new_energy
print(f"Found better solution for {new_energy}")
else:
process_move(new_move, new_energy)
move_left_index = move_left_to_chamber(current_move, item_type)
if move_left_index is not None:
number_of_moves = NUMBER_OF_MOVE_TO_TOP_ROOM[item_type][move_left_index]
target_index = TOP_ROOM_INDEX[item_type] if (move_in_status == CanMoveInStatus.TOP_ROOM) else \
BOTTOM_ROOM_INDEX[item_type]
new_move = slice_move(current_move, move_left_index, target_index)
if move_in_status == CanMoveInStatus.BOTTOM_ROOM:
number_of_moves += 1
new_energy = current_energy + (number_of_moves * ITEM_TYPE_TO_ENERGY[item_type])
if new_move == TARGET_POSITION:
if (min_solution_energy is None) or (min_solution_energy > new_energy):
min_solution_energy = new_energy
max_energy = new_energy
print(f"Found better solution for {new_energy}")
else:
process_move(new_move, new_energy)
def try_to_move_out(current_move: Move, current_energy: int, item_type: ItemType):
top_room_index = TOP_ROOM_INDEX[item_type]
top_room_item_type = current_move[top_room_index]
bottom_room_index = BOTTOM_ROOM_INDEX[item_type]
bottom_room_item_type = current_move[bottom_room_index]
if ((top_room_item_type != ITEM_EMPTY) and (top_room_item_type != item_type)) or \
((top_room_item_type == item_type) and (bottom_room_item_type != item_type)):
print(f"\t\tCan move from top room")
target_index: Position
for target_index in range(MOVE_RIGHT_TO_CHAMBER_MAX_POSITION[item_type], -1, -1):
if current_move[target_index] != ITEM_EMPTY:
break
print(f"\t\t\t\tCan move left to {target_index}")
number_of_moves = NUMBER_OF_MOVE_TO_TOP_ROOM[item_type][target_index]
new_energy = current_energy + (number_of_moves * ITEM_TYPE_TO_ENERGY[top_room_item_type])
new_move = slice_move(current_move, target_index, top_room_index)
process_move(new_move, new_energy)
for target_index in range(MOVE_LEFT_TO_CHAMBER_MIN_POSITION[item_type], 7):
if current_move[target_index] != ITEM_EMPTY:
break
print(f"\t\t\t\tCan move right to {target_index}")
number_of_moves = NUMBER_OF_MOVE_TO_TOP_ROOM[item_type][target_index]
new_energy = current_energy + (number_of_moves * ITEM_TYPE_TO_ENERGY[top_room_item_type])
new_move = slice_move(current_move, target_index, top_room_index)
process_move(new_move, new_energy)
else:
if (top_room_item_type == ITEM_EMPTY) and (bottom_room_item_type != ITEM_EMPTY) and (
bottom_room_item_type != item_type):
print(f"\t\tCan move from bottom room")
target_index: Position
for target_index in range(MOVE_RIGHT_TO_CHAMBER_MAX_POSITION[item_type], -1, -1):
if current_move[target_index] != ITEM_EMPTY:
break
print(f"\t\t\t\tCan move left to {target_index}")
number_of_moves = NUMBER_OF_MOVE_TO_TOP_ROOM[item_type][target_index] + 1
new_energy = current_energy + (number_of_moves * ITEM_TYPE_TO_ENERGY[bottom_room_item_type])
new_move = slice_move(current_move, target_index, bottom_room_index)
process_move(new_move, new_energy)
for target_index in range(MOVE_LEFT_TO_CHAMBER_MIN_POSITION[item_type], 7):
if current_move[target_index] != ITEM_EMPTY:
break
print(f"\t\t\t\tCan move right to {target_index}")
number_of_moves = NUMBER_OF_MOVE_TO_TOP_ROOM[item_type][target_index] + 1
new_energy = current_energy + (number_of_moves * ITEM_TYPE_TO_ENERGY[bottom_room_item_type])
new_move = slice_move(current_move, target_index, bottom_room_index)
process_move(new_move, new_energy)
def next_move() -> None:
global min_energy
global max_energy
global moves_to_explores
global min_solution_energy
for current_energy in range(min_energy, max_energy + 1):
#print(f"Trying {current_energy}")
min_energy = current_energy
if (min_solution_energy is not None) and (current_energy >= min_solution_energy):
print(f"Solution found: {min_solution_energy}")
exit(0)
if current_energy in moves_to_explores:
moves_with_right_cost = moves_to_explores[current_energy]
for current_move in moves_with_right_cost:
print(f"Process {current_move} for {current_energy}")
for item_type in [ITEM_AMBER, ITEM_BRONZE, ITEM_COPPER, ITEM_DESERT]:
print(f"\tTrying to move in {item_type}")
try_to_move_in(current_move, current_energy, item_type)
for item_type in [ITEM_AMBER, ITEM_BRONZE, ITEM_COPPER, ITEM_DESERT]:
print(f"\tTrying to move out from {item_type}")
try_to_move_out(current_move, current_energy, item_type)
moves_to_explores.pop(current_energy)
while True:
next_move()Part two
23/day_23_2.py
import sys
from heapq import heappush, heappop
from typing import NewType, List, Any
puzzle = open(sys.argv[1]).readlines()
CHAMBER_SIZE = len(puzzle) - 3
# #############
# #01.2.3.4.56#
# ###7#9#1#3###
# #8#0#2#4#
# #########
ItemType = NewType('ItemType', int)
ITEM_AMBER = ItemType(0)
ITEM_BRONZE = ItemType(1)
ITEM_COPPER = ItemType(2)
ITEM_DESERT = ItemType(3)
ITEM_EMPTY = ItemType(4)
Position = NewType('Position', int)
Move: list[ItemType] = []
def move_to_key(move: Move) -> str:
return ''.join(map(str, move))
def slice_move(current_move: Move, min_position: Position, max_position: Position) -> Move:
return current_move[:min_position] + \
current_move[max_position:(max_position + 1)] + \
current_move[(min_position + 1):max_position] + \
current_move[min_position:(min_position + 1)] + \
current_move[max_position + 1:]
ITEM_TYPE_TO_ENERGY: dict[ItemType, int] = {
ITEM_AMBER: 1,
ITEM_BRONZE: 10,
ITEM_COPPER: 100,
ITEM_DESERT: 1000
}
CHAR_TO_ITEM_TYPE: dict[str, ItemType] = {
'A': ITEM_AMBER,
'B': ITEM_BRONZE,
'C': ITEM_COPPER,
'D': ITEM_DESERT,
'.': ITEM_EMPTY,
}
initial_position_string = [
puzzle[1][1],
puzzle[1][2],
puzzle[1][4],
puzzle[1][6],
puzzle[1][8],
puzzle[1][10],
puzzle[1][11],
]
for t in range(0, 4):
for c in range(0, CHAMBER_SIZE):
initial_position_string.append(puzzle[2 + c][3 + (t * 2)])
initial_position: Move = list(
map(
lambda c: CHAR_TO_ITEM_TYPE[c],
initial_position_string
)
)
TARGET_POSITION: Move = (
[ITEM_EMPTY] * 7) + \
([ITEM_AMBER] * CHAMBER_SIZE) + \
([ITEM_BRONZE] * CHAMBER_SIZE) + \
([ITEM_COPPER] * CHAMBER_SIZE) + \
([ITEM_DESERT] * CHAMBER_SIZE)
print(initial_position)
known_moves: dict[Move, int] = dict()
known_moves[move_to_key(initial_position)] = 0
min_solution_energy: int | None = None
moves_to_explores: list[tuple[int, Move]] = []
heappush(moves_to_explores, (0, initial_position))
TOP_ROOM_INDEX: dict[ItemType, Position] = {
ITEM_AMBER: Position(7),
ITEM_BRONZE: Position(7 + CHAMBER_SIZE),
ITEM_COPPER: Position(7 + (2 * CHAMBER_SIZE)),
ITEM_DESERT: Position(7 + (3 * CHAMBER_SIZE))
}
MOVE_RIGHT_TO_CHAMBER_MAX_POSITION: dict[ItemType, Position] = {
ITEM_AMBER: Position(1),
ITEM_BRONZE: Position(2),
ITEM_COPPER: Position(3),
ITEM_DESERT: Position(4)
}
MOVE_LEFT_TO_CHAMBER_MIN_POSITION: dict[ItemType, Position] = {
ITEM_AMBER: Position(2),
ITEM_BRONZE: Position(3),
ITEM_COPPER: Position(4),
ITEM_DESERT: Position(5)
}
def can_move_in_chamber(current_move: Move, item_type: ItemType) -> Position | None:
for room_index in range(CHAMBER_SIZE - 1, -1, -1):
room_content = current_move[TOP_ROOM_INDEX[item_type] + room_index]
if room_content == ITEM_EMPTY:
return Position(room_index)
elif room_content != item_type:
return None
return None
NUMBER_OF_MOVE_TO_TOP_ROOM: dict[ItemType, list[Position]] = {
ITEM_AMBER: [Position(3), Position(2), Position(2), Position(4), Position(6), Position(8), Position(9)],
ITEM_BRONZE: [Position(5), Position(4), Position(2), Position(2), Position(4), Position(6), Position(7)],
ITEM_COPPER: [Position(7), Position(6), Position(4), Position(2), Position(2), Position(4), Position(5)],
ITEM_DESERT: [Position(9), Position(8), Position(6), Position(4), Position(2), Position(2), Position(3)],
}
def move_right_to_chamber(current_move: Move, item_type: ItemType) -> Position | None:
for item_index in range(MOVE_RIGHT_TO_CHAMBER_MAX_POSITION[item_type], -1, -1):
if current_move[item_index] == item_type:
return Position(item_index)
elif current_move[item_index] != ITEM_EMPTY:
return None
return None
def move_left_to_chamber(current_move: Move, item_type: ItemType) -> Position | None:
for item_index in range(MOVE_LEFT_TO_CHAMBER_MIN_POSITION[item_type], 7):
if current_move[item_index] == item_type:
return Position(item_index)
elif current_move[item_index] != ITEM_EMPTY:
return None
return None
def process_move(move: Move, energy: int) -> None:
global max_energy
global known_moves
global moves_to_explores
move_key = move_to_key(move)
if (move_key not in known_moves) or (known_moves[move_key] > energy):
print(f"\t\t\t\t\tNew move {move} for {energy}")
known_moves[move_key] = energy
heappush(moves_to_explores, (energy, move))
def try_to_move_in(current_move: Move, current_energy: int, item_type: ItemType):
global min_solution_energy
global max_energy
move_in_index = can_move_in_chamber(current_move, item_type)
if move_in_index is not None:
move_right_index = move_right_to_chamber(current_move, item_type)
if move_right_index is not None:
number_of_moves = NUMBER_OF_MOVE_TO_TOP_ROOM[item_type][move_right_index] + move_in_index
target_index = TOP_ROOM_INDEX[item_type] + move_in_index
new_move = slice_move(current_move, move_right_index, target_index)
new_energy = current_energy + (number_of_moves * ITEM_TYPE_TO_ENERGY[item_type])
if new_move == TARGET_POSITION:
if (min_solution_energy is None) or (min_solution_energy > new_energy):
min_solution_energy = new_energy
max_energy = new_energy
print(f"Found better solution for {new_energy}")
else:
process_move(new_move, new_energy)
move_left_index = move_left_to_chamber(current_move, item_type)
if move_left_index is not None:
number_of_moves = NUMBER_OF_MOVE_TO_TOP_ROOM[item_type][move_left_index] + move_in_index
target_index = TOP_ROOM_INDEX[item_type] + move_in_index
new_move = slice_move(current_move, move_left_index, target_index)
new_energy = current_energy + (number_of_moves * ITEM_TYPE_TO_ENERGY[item_type])
if new_move == TARGET_POSITION:
if (min_solution_energy is None) or (min_solution_energy > new_energy):
min_solution_energy = new_energy
max_energy = new_energy
print(f"Found better solution for {new_energy}")
else:
process_move(new_move, new_energy)
def try_to_move_out(current_move: Move, current_energy: int, item_type: ItemType):
top_room_index = TOP_ROOM_INDEX[item_type]
lower_item_want_to_get_out = False
for room_index in range(CHAMBER_SIZE - 1, -1, -1):
room_content = current_move[top_room_index + room_index]
if (room_content == item_type) and (not lower_item_want_to_get_out):
pass
elif room_content == ITEM_EMPTY:
return
else:
lower_item_want_to_get_out = True
can_move_out = True
for over_room_index in range(0, room_index):
if current_move[top_room_index + over_room_index] != ITEM_EMPTY:
can_move_out = False
if can_move_out:
print(f"\t\tCan move from room index {room_index}")
target_index: Position
for target_index in range(MOVE_RIGHT_TO_CHAMBER_MAX_POSITION[item_type], -1, -1):
if current_move[target_index] != ITEM_EMPTY:
break
print(f"\t\t\t\tCan move left to {target_index}")
number_of_moves = NUMBER_OF_MOVE_TO_TOP_ROOM[item_type][target_index] + room_index
new_energy = current_energy + (number_of_moves * ITEM_TYPE_TO_ENERGY[room_content])
new_move = slice_move(current_move, target_index, top_room_index + room_index)
process_move(new_move, new_energy)
for target_index in range(MOVE_LEFT_TO_CHAMBER_MIN_POSITION[item_type], 7):
if current_move[target_index] != ITEM_EMPTY:
break
print(f"\t\t\t\tCan move right to {target_index}")
number_of_moves = NUMBER_OF_MOVE_TO_TOP_ROOM[item_type][target_index] + room_index
new_energy = current_energy + (number_of_moves * ITEM_TYPE_TO_ENERGY[room_content])
new_move = slice_move(current_move, target_index, top_room_index + room_index)
process_move(new_move, new_energy)
def next_move() -> None:
global moves_to_explores
global min_solution_energy
while len(moves_to_explores) > 0:
current_energy, current_move = heappop(moves_to_explores)
if (min_solution_energy is not None) and (current_energy >= min_solution_energy):
print(f"Solution found: {min_solution_energy}")
exit(0)
print(f"Process {current_move} for {current_energy}")
for item_type in [ITEM_AMBER, ITEM_BRONZE, ITEM_COPPER, ITEM_DESERT]:
print(f"\tTrying to move in chamber {item_type}")
try_to_move_in(current_move, current_energy, item_type)
print(f"\tTrying to move out from chamber {item_type}")
try_to_move_out(current_move, current_energy, item_type)
while True:
next_move()
# 43815 too high
# 43814 ?!Day 24
Part one
24/day_24_1.py
import re
puzzle = open('input.txt').readlines()
input_index = 0
constants_values = {
'w': 0,
'x': 0,
'y': 0,
'z': 0,
}
def has_constant(variable):
return (variable in constants_values) and (constants_values[variable] is not None)
def flush_constant(f, variable):
if has_constant(variable):
f.write(f"{variable} = {constants_values[variable]} # Flush\n")
constants_values[variable] = None
line_index = 1
def write(f, content):
f.write(f"{content}\n")
with open('input.txt.py', 'w') as f:
f.write('import sys\n')
f.write('import math\n')
f.write('\n')
f.write('input_number = sys.argv[1]\n')
f.write('\n')
for line in puzzle:
f.write(f'# {line_index}: {line.strip()} {constants_values}\n')
line = line.strip().split(' ')
if len(line) == 0:
continue
match line[0]:
case 'inp':
constants_values[line[1]] = f'int(input_number[{input_index}])'
input_index += 1
case 'add':
if line[2] == '0':
pass
elif has_constant(line[2]):
if has_constant(line[1]):
if constants_values[line[1]] == 0:
constants_values[line[1]] = constants_values[line[2]]
else:
constants_values[line[1]] = f"({constants_values[line[1]]} + {constants_values[line[2]]})"
else:
write(f, f"{line[1]} = {constants_values[line[1]]} + {constants_values[line[2]]}")
constants_values[line[1]] = None
elif has_constant(line[1]) and line[2].isnumeric():
if constants_values[line[1]] == 0:
if line[2].isnumeric():
constants_values[line[1]] = int(line[2])
else:
constants_values[line[1]] = line[2]
else:
constants_values[line[1]] = f"({constants_values[line[1]]} + {line[2]})"
elif constants_values[line[1]] == 0:
constants_values[line[1]] = None
flush_constant(f, line[2])
write(f, f"{line[1]} = {line[2]}")
constants_values[line[1]] = None
else:
flush_constant(f, line[1])
flush_constant(f, line[2])
write(f, f"{line[1]} += {line[2]}")
constants_values[line[1]] = None
case 'mul':
if has_constant(line[1]) and (constants_values[line[1]] == 0):
pass
elif has_constant(line[2]) and (constants_values[line[2]] == 1):
pass
elif line[2] == '0':
constants_values[line[1]] = 0
elif has_constant(line[1]) and isinstance(constants_values[line[1]], int) and has_constant(line[2]) and isinstance(constants_values[line[2]], int):
constants_values[line[1]] = constants_values[line[1]] * constants_values[line[2]]
elif has_constant(line[1]):
flush_constant(f, line[2])
write(f, f"{line[1]} = {constants_values[line[1]]} * {line[2]}")
constants_values[line[1]] = None
else:
flush_constant(f, line[1])
flush_constant(f, line[2])
write(f, f"{line[1]} *= {line[2]}")
case 'div':
if line[2] != '1':
flush_constant(f, line[1])
flush_constant(f, line[2])
if line[2] != '1':
write(f, f"{line[1]} = math.ceil({line[1]} / {line[2]})")
case 'mod':
if line[2] == '1':
pass
elif has_constant(line[1]):
if isinstance(constants_values[line[1]], int) and line[2].isnumeric():
constants_values[line[1]] = int(constants_values[line[1]]) % int(line[2])
else:
write(f, f"{line[1]} = {constants_values[line[1]]} % {line[2]}")
constants_values[line[1]] = None
else:
flush_constant(f, line[1])
flush_constant(f, line[2])
write(f, f"{line[1]} = {line[1]} % {line[2]}")
case 'eql':
if has_constant(line[1]):
if has_constant(line[2]):
if (re.compile(r"^int\(input_number\[(\d+)\]\)$").match(constants_values[line[2]]) is not None) \
and isinstance(constants_values[line[1]], int) \
and (constants_values[line[1]] > 10):
constants_values[line[1]] = 0
else:
write(f,
f"{line[1]} = 1 if ({constants_values[line[1]]} == {constants_values[line[2]]}) else 0")
constants_values[line[1]] = None
else:
if line[2].isnumeric() and (constants_values[line[1]] == int(line[2])):
constants_values[line[1]] = 1
else:
write(f, f"{line[1]} = 1 if ({constants_values[line[1]]} == {line[2]}) else 0")
constants_values[line[1]] = None
else:
if has_constant(line[2]):
write(f, f"{line[1]} = 1 if ({line[1]} == {constants_values[line[2]]}) else 0")
else:
write(f, f"{line[1]} = 1 if ({line[1]} == {line[2]}) else 0")
constants_values[line[1]] = None
case _:
raise Exception(line)
line_index += 1
f.write('\n')
f.write('print(z)\n')Day 25
Part one
25/day_25_1.py
import copy
import sys
puzzle = list(map(lambda l: list(l.strip()), open(sys.argv[1]).readlines()))
puzzle_width = len(puzzle[0])
puzzle_height = len(puzzle)
step_index = 0
while True:
step_index += 1
number_of_moves = 0
new_puzzle = copy.deepcopy(puzzle)
for line in range(0, puzzle_height):
for column in range(0, puzzle_width - 1):
current_cell_content = puzzle[line][column]
target_cell_content = puzzle[line][column + 1]
if (current_cell_content == '>') and (target_cell_content == '.'):
new_puzzle[line][column] = '.'
new_puzzle[line][column + 1] = '>'
number_of_moves += 1
current_cell_content = puzzle[line][puzzle_width - 1]
target_cell_content = puzzle[line][0]
if (current_cell_content == '>') and (target_cell_content == '.'):
new_puzzle[line][puzzle_width - 1] = '.'
new_puzzle[line][0] = '>'
number_of_moves += 1
puzzle = new_puzzle
new_puzzle = copy.deepcopy(puzzle)
for line in range(0, puzzle_height - 1):
for column in range(0, puzzle_width):
current_cell_content = puzzle[line][column]
target_cell_content = puzzle[line + 1][column]
if (current_cell_content == 'v') and (target_cell_content == '.'):
new_puzzle[line][column] = '.'
new_puzzle[line + 1][column] = 'v'
number_of_moves += 1
for column in range(0, puzzle_width):
current_cell_content = puzzle[puzzle_height - 1][column]
target_cell_content = puzzle[0][column]
if (current_cell_content == 'v') and (target_cell_content == '.'):
new_puzzle[puzzle_height - 1][column] = '.'
new_puzzle[0][column] = 'v'
number_of_moves += 1
if number_of_moves == 0:
print(step_index)
exit(0)
puzzle = new_puzzle