Solved by hand by visualizing the filesystem as
a grid, and put into a simple formula.
In Sweden, this is called a "Femtonspel".
https://sv.wikipedia.org/wiki/Femtonspel
Did brute force, but earlier drafts of the code
failed to exit the while loop correcly.
By manual testing, an odd number is required in reg
a to set the first output to 0 (for my puzzle
input at least). Hence, only odd numbers are tested.
Solution cide works, but is slow. According to the
subreddit, pt 2 is meant to be an exercise in
optimization.
Turns out the assembly instructions do a factorial,
i.e 7! and 12! and adds a salt (5840).
Got that spoiled. :)
A good day to utilize lots of unit testing!
For pt 2, the code initially tried to reverse
the scramble algorithm. The final code however
got the unscrambled version by the traditional
method most password crackers would resolve to:
basic brute forcing with permutations as a list
of candidates.
The code at one time used cached responses for
in range bools, but it seems that does not improve
performance.
Some IP addresses are allowed multiple times, so
min() and set() are used to find the distinct
values.
Learned a lot about the Josephus' Problem today!
Solved part 1 by using a dict, but eventually
ended up just adding the mathematical shortcut
and rewriting both parts to use deque() for
performance.
Part 2 was tricky, since k (the elf to remove
after all presents were stolen from them) is a
index that changes over time. No tries for a
solution that was performant enough using lists
and dicts were succesfull, so by inspiration from
the subreddit the final solution code is based on
2 deque() that pops and appends between them.
There are 2 part 1 solutions.
- A correct implementation of the Josephus' Problem,
using deque(). Recursion would have worked as well,
but Python do not like recursions.
- The mathematical superior version, with a link
to the Youtube video were it is introduced.
Figured out that the center position did not matter,
as long as left hand side tile and right hand side
tile on previous row are not equal.
Also tried to find a recurring pattern to speed
p2 up a bit, but it seems it does not have a
recurring pattern in the 400 000s first rows.
Lost 60 minutes due to misinterpreting this in p2:
> *whenever* you generate a hash
The code initially only did the 2016 stretching for
the triplet hash, not the quintet hash. By doing it
to both, pt 2 is solved.
Not sure the lru cache actually speeds anything up.
Many on the subreddit used the approach to generate
the quintet first and look backwards 1000 times
for a matching quintet (since quintets are more
rare than triplets), this will most likely speed
things up.
Also, this solution do not store the found keys.
Many other solutions do, I believe this is some
presumptions.
Hard one, an infamous AoC puzzle according to
Reddit.
Apparently, this is a classic logic problem named
"Missionaries and cannibals", or "Jealous husbands".
Hard lessons:
- Always use set() for visited nodes during BFS.
- Always use collections.queue() to create to queue
traversals for BFS.
- itertools permutations(), combinations() and
pairwise() may look similar, but they are not.
- Learned to use (?:chunk of text)? in regex.
Test data was achieved without bigger hazzles, but
to optimize code required a lot of Reddit browsing
and code reading from blogs. I have mentioned the
sources in a doc string.
