Day 1: Inverse Captcha → Solution
Warming up on:
- looping
- list indexing
- not reading the text precisely:
- for the first puzzle I missed the circularity of the list
- for the second one I misunderstood the target of the comparison being only one item
Day 2: Corruption Checksum → Solution
Warming up on:
- list operations
- regular expressions
\s
pattern for whitespace
- code factoring
is_integer()
function
Day 3: Spiral Memory → Solution
Nice and simple spatial map generation via looping.
- I started with an efficient formula for the first part that took me a long time to solve. But the proper solution was to actually build the map 😆
- Writing a help function to print the map, I again mixed the directions
(order of the indices
x
,y
)
Day 4: High-Entropy Passphrases → Solution
Warming up on:
set
tuple
collections.Counter
list.sort
with customkey
s
Warming up on:
- Reusing input
list
s list
indices- Using and updating a variable at the same step!
Day 6: Memory Reallocation → Solution
Warming up on:
list
max(list)
list.index()
tuple
set
dict
Day 7: Recursive Circus → Solution
Warming up on:
- regular expressions for reading inputs
collections.deque
for building a queuecollections.Counter
for finding the frequency of items in a list
Day 8: Heard You Like Registers → Solution
Warming up on:
eval()
function- regular expressions
- using
eval()
function!
- Using
eval(exp, variable_dict)
will add an unwanted__builtins__
key to thevariable_dict
- Solution is to use
eval(exp, None, variable_dict)
since the second argument is theglobals
and the third is actually thelocals
. - This unwanted key/value pair was preventing me from finding
max(variable_dict.values())
easily!
- Solution is to use
Day 9: Stream Processing → Solution
Simple "Stream Processing" exercise. The only important aspect of this day was to implement the proper order of the rules.
- My first quick implementation for the second part was missing the
<
s inside garbage sections.
Long unnecessary story to read 😆 Warming up on:
collections.deque
- Usage of
stack
for reversing the order items deque.rotate
hex()
functionstr.rjust
function
Finally a puzzle that needs some thinking to solve; yet easy one.
It's all about thinking how to aggregate hex steps.
As soon as you figure out how, the problem is solved!
Day 12: Digital Plumber → Solution
An easy connected-components of a graph problem.
- Of course, using sets
- Since inputs are only numbers,
re.findall(r"\d+", line)
easily extracts the numbers
Day 13: Packet Scanners → Solution
Another easy puzzle.
All you need to do is to simulate the described scenario, with a small optimization.
- No full path of the security scanner needs to be simulated. Every
(depth-1)*2
picoseconds, the scanner is back to the top of the layer and can catch us.
Day 14: Disk Defragmentation → Solution
The puzzle was to reuse the Knot Hash from Day 10.
The only thing to do is to generate the 128 hashes and count the number of 1
s in them.
For part 2, we need to find the number of connected components (1
s) in the grid of 0
s and 1
s.
To do so, I stored all the locations of 1
s in a set and iterated over them to find the connected components.
- While turning the hash to binary, I forgot to add the leading zeros to the binary representation, which led to wrong locations of
1
s.
Day 15: Dueling Generators → Solution
A modulus multiplication problem.
There are two generators that generate numbers based on the previous number with different factors in the same modulus.
And we need to count the number of pairs that have matching 16 least significant bits.
The second part is to find the number of pairs that have matching 16 least significant bits after 5 million iterations.
But this time each generator will generate the first number which is divisible by a specific number (4 for A and 8 for B).
The solution was to simply implement the generators and count the number of matching pairs.
- Instead of using
%16
orbin()
function, we can speed up by using&0xFFFF
to get the 16 least significant bits. - I spent some time trying to find a better solution using the modulus properties, but I couldn't find any 😅. The ad-hoc solutions run in about 10 seconds, which is acceptable.
Day 16: Permutation Promenade → Solution
A string manipulation problem.
We start with a string of characters and we need to apply a series of operations on it including:\
s
shift the programs (characters in the string) rotationallyx
swap two programs in the two input positionsp
swap the programs with two input values. In part one, we need to apply the operations in the input order only once; which is doable in a fraction of a second.
In part two, we need to apply the operations in the input order 1 billion times; which is not doable in a reasonable time.\
- The order of the programs is cyclic, so we can find the cycle length and apply the operations only the remaining times by fast-forwarding the operations.
An interesting puzzle to solve.
We have a circular list (starting at [0]) and we need to insert numbers in it based on an input step size.
At each step, we move forward the step size and insert the number after the current position.
The first part is to find the number after 2017 when it's inserted.
The ad-hoc solution of keeping the list as a list
was good enough for part one.
For part two, we need to find next value to 0
but after 50 million steps.
The ad-hoc solution is not more tractable, so we need to find a better solution.\
- First improvement was to switch to a
deque
instead of alist
to have O(1) insertion time.deque
can rotate the list very efficiently; This can give us the answer in about 10 seconds. - We don't need to keep the whole list for this part 😄, we can keep only the current position and the value after
0
. This speeds up the solution to about a couple of seconds.
An interesting puzzle to simulate concurrently running programs.
In part two we have two programs that run concurrently and communicate with each other.
The solution was to simulate the programs and their communication.
Python's generators seemed to be a good fit for this problem.
Day 19: A Series of Tubes → Solution
A simple path following problem.
We have a map of signs and we need to follow a path starting from the top row, catch all the alphabets and count the number of steps.
The only twist is that we need to follow the path in the direction of the arrow, and turn when we reach a +
sign.
Day 20: Particle Swarm → Solution
A simple physics simulation problem.
We have a list of particles with their positions, velocities, and accelerations, and need to simulation their movement over time.
For part one, we need to find the particle that stays closest to the origin in the long run.
For part two, we need to find the number of particles that do not collide with others.
The ad-hoc way of simulating the particles for a long time (1000 iterations) was good enough for both parts.
But one can analytically solve the quadratic equation to find the time of collision for part two.
Anyways, the analytical solution will not necessarily faster than the ad-hoc one, and it will be way more complex, because the colliding particles should be immediately removed from the list.
Day 21: Fractal Art → Solution
In this puzzle, we are provided with a set of expansion rules for inner grids of a grid.
Based on the size of the whole grid, we either expand each 2x2 grid to a 3x3 grid, or each 3x3 grid to a 4x4 grid.
We need to apply the rules for a number of iterations and count the number of #
s in the final grid.
The only effective optimization was to store the rules in a dictionary to speed up the lookup.
To implement the mechanics of the puzzle, we can either use a simple list of strings or a numpy
array.
It's good to recall the useful numpy
structures and functions for such puzzles:
np.ndarray
np.rot90
np.flipud
np.fliplr
np.concatenate
np.split
np.hsplit
np.vsplit
np.hstack
np.vstack
np.reshape
np.sum
Day 22: Sporifica Virus → Solution
A simple cellular automata problem.
We start with a grid of clean/infected cells and a virus career that moves based on the current cell state.
In part two, we have 4 states instead of two.
Day 23: Coprocessor Conflagration → Solution
Another assembly-code simulation problem.
Part 1 was to run the code in normal mode and count the number of times the mul
instruction is executed.
Part 2 was to run the code in debug mode (set register a
to 1) and get the final value of register h
, which apparently runs for a very long time.
- In the first part, I was checking the arguments if they are
is_numeric()
to distinguish between registers and values.
This fails when we have a negative value.
So I had to change it to check if the value is a key in the registers' dictionary instead, which is more robust. - At some of the steps, I was misinterpreting the subtracting of a negative value as a decrement operation, which was wrong.
As expected, for part 2 we had to translate the assembly code to higher level instructions and understand what it does.
The code was actually counting the non-prime numbers in a defined range and with a defined step, in its most inefficient way.
Registers:
a
is the input switch for debug modeb
is the loop counterc
is the range upper boundd
ande
are the inner loop counters to find the divisors for currentb
valuef
is the flag to indicate if the currentb
value is primeg
is mainly used to build jump conditionsh
is the counter for non-prime numbers in the range This way we should re-implement the logic in its efficient way to get the answer in a reasonable time.
Day 24: Electromagnetic Moat → Solution
A search problem to find the longest bridge in a list of components.
We are provided with a list of connections between components and we need to find the longest bridge that can be built.
A simply DFS search can solve the problem.
In part two, we need to find the longest bridge with the highest strength.
With a small modification to the DFS search, we can easily find the answer.
Day 25: The Halting Problem → Solution
A sweet puzzle of a super-simple Turing machine.
We are provided with a set of rules for a Turing machine and we need to simulate it for a number of steps.
The machine has multiple states and a tape that can be moved left or right.
After running it for the requested number of steps, we need to count the number of 1
s on the tape.
Reading multi-line rules from the input file by re
was not trivial to me.
But trying r"""..."""
worked fine.