You can find the puzzle inputs here: https://adventofcode.com/2024
- A good reminder that
.by default matches any character except a new line. So, I learned about DOTALL flag. - I came across this website: https://regexcrossword.com/
- The better solution is to use sorting with a custom comparator function →
- Used
time python Day_06/task_6b.pyto measure the execution time of the script
- The go-to solution:
itertools.product
-
Using the next iterator from
itertools→combinations -
A cleaner way to handle this kind of logic. Instead of writing:
if cell not in antenna_positions:
antenna_positions[cell] = [(row_ind, col_ind)]
else:
antenna_positions[cell].append((row_ind, col_ind))
We can refactor it to be more concise:
antenna_positions.setdefault(cell, []).append((row_ind, col_ind))
Alternatively, we can use defaultdict from collections, which automatically provides a default value for the key that doesn't exist.
In part two, I got rid of OrderedDict since I hadn't actually used it in part one anyway.
To improve performance, I changed the structure from index: file_id to file_id: [list of indices], as searching through the old dictionary was painfully slow.
I also replaced the while loop with a for loop (always a pleasure) 😇
Been there, done that 😅
The choice of a dynamic list as a data container was not the best. It turns out that order was not important at all, and it would have been much better to use a hash map where the key would be the engraved number and the value the number of occurrences.
I also read that returning from a with block (e.g., when opening a file) works fine, and the file is automatically closed. The with statement ensures cleanup happens, whether the block exits normally or via a return. 🔗
I probably would have done better if my puzzle_input had been correct instead of last year's 😅
But this was one of those tasks I really liked (aside from the wrong input), where I had to grab a sheet of paper and a pen to plan it out.
What I’m proud of is that I came up with the correct perimeter formula right away. Even though it’s a bit basic, it works!
I didn't want to reinvent the wheel, so I just went with sympy. Two equations with two unknowns. It was fun to solve the test examples on paper.
In my case, searching for the Easter egg using the smallest safety factor didn’t work (though it turns out it was the second smallest result!). However, I listed all the possible cases, and after entering 5000 as an answer, I knew the range I should focus on (which at least halved my search efforts 😅).
I think it wasn’t the best idea to store robot positions as JSON. Using images with PIL would probably have been faster, but I wanted to avoid libraries that require additional installation (tqdm doesn’t count—it’s just a little helper to check if my program is still running).
I know some people enjoyed this task, but after browsing Reddit, I feel it’s too input-dependent. I don’t like that someone might solve it just because they got lucky, rather than because their method works for everyone or because they noticed something critical in the task description. It feels like the solutions on Reddit are post hoc reasoning because, based on the task description, we didn’t even know what we were looking for.
What helped me optimize this task is that the robots align horizontally and vertically after every map width or map height iteration. In the vertical alignment we see all x repetitions with pseudorandom y and in the horizontal alignment we see all y repetitions with pseudorandom x. 🔗
So, after seeing the generated data, I was able to determine that my vertical offset (X) is 9 and horizontal offset (Y) is 65, which allowed me to narrow down the range being searched.
Additionally, once we find X and Y, we can simply find the smallest number N, where:
N%101==X and N%103==Y 🔗
101 is grid's width, 103 - length.
There's the interesting Chinese Remainder Theorem, which is implemented in sympy and allows solving this problem in a few lines from this point 🔗 :
from sympy.ntheory.modular import crt
moduli = [101, 103]
remainders = [9, 65]
N,_ = crt(moduli, remainders)
where N is the solution, a place where both alignments, vertical and horizontal, coincide.
The match statement is a more elegant alternative to if...elif...else ✨
Plus, instead of struggling with split to parse a file, like this:
def load_data(filename):
with open(filename, "r") as file:
registers, program = file.read().split("\n\n")
registers = [int(register.split(": ")[1]) for register in registers.split("\n")]
program = program.strip().split(": ")[1].split(",")
return registers, list(map(int, program))
I could simply use regex and unpack it in one line:
a, b, c, *prog = map(int, re.findall(r'\d+', open('in.txt').read())) 🔗
Brute force was good enough, so I stuck with it. Apparently, you can practically reuse part 2 from day 16 (you just need to remove the condition about 1000 points → 🔗), but I don’t have that part ready yet, so we’ll see in the future 😅
Part I: Initially, I tried to avoid checking all towel patterns and thought I could prevent the algorithm from being too greedy by starting with the largest patterns.
max_len = max([len(pattern) for pattern in towels])
to_check = design
while len(to_check) > 0:
is_found = False
for i in range(max_len):
if to_check[:i] in towels:
to_check = to_check[i:]
is_found = True
break
if not is_found:
return False
return True
This approach worked in cases like this:
Towels: ab, abc, def
Design: abcdef
Even though the first towel pattern was ab, because I started from the sorted list, I checked abc first. Combining abc and def gave the correct result: abc + def = abcdef.
However, while the algorithm was still greedy, it was greedy from the end 😅.
For example:
Towels: abcd, abc, def
Design: abcdef
Starting from the longest pattern (abcd), the remainder ef didn’t match. The correct configuration, abc + def = abcdef, was missed because the algorithm didn’t check all possible combinations.
So, I abandoned the while loop and switched to recursion. There, I check all the patterns, and if there is a combination of patterns that matches, the function returns True. If the design fails at some point, it backtracks to the previous state and tries the next possible pattern.
Additinaly, I could simplify function by replacing the loop:
valid = 0
for design in designs:
valid += is_design_valid(design)
with sum(map(is_design_valid, designs)) ✨
Part 1: I forgot that two picoseconds are needed for the cheating, so the distance isn’t simply the difference between the end position index and the start position index—we need to reduce it by 2.