Solved by total rewrite, since part 1 solution was too slow and was
killed by the OS. I tried to use deque and prepending instead of
appending, but no luck.
I looked for inspiration on AOC subreddit, and realized I could
solve the puzzle without constructing a new polymer string.
Instead, **it should be solved by counting pairs**.
First of all, a little zip trick is used to construct an initial list of
pairs from the initial polymer.
collections.defaultdicts are excellent tools for storing the counts,
since they will default to a value of 0 for any key that is added.
the initial count of the initial polymer is this:
{
('N', 'N'): 1,
('N', 'C'): 1,
('C', 'B'): 1
}
And the initial character count looks like this, and was constructed by
collections.Counter. This is what we increase and use after the 40 steps.
{
'N': 2,
'C': 1,
'B': 1
}
So, lets see what happens after the first step.
First of all, all existing pair counts should be reset each step, since
this will be faster. nxt is used to store the next step pairs.
the current pairs are iterated.
- for NN, the new pairs NC and CN are added for the next step. Since NN exists
1 time, the pairs NC and CN also will exist exactly 1 more time each. The char C will also
exist 1 more time, so add it to the char counter.
- for NC, the new pairs NB and BC are added for the next step. Pair
counter is once again synced with NC, and B is added to the char
counter.
- and the same for CB, where CH and HB is added.
The count looks like this after step 1.
{
('N', 'C'): 1,
('C', 'N'): 1,
('N', 'B'): 1,
('B', 'C'): 1,
('C', 'H'): 1,
('H', 'B'): 1,
}
The pair counts are all 1 for step 2, since **no pairs have reoccured yet**.
The char counts looks like this, and matches polymer 'NCNBCHB', even
though it does not matter in which order the chars are written:
{
'N': 2,
'C': 2,
'B': 2,
'H': 1
}
Lets see the counts for step 2.
{
('N', 'B'): 2,
('B', 'C'): 2,
('C', 'C'): 1,
('C', 'N'): 1,
('B', 'B'): 2,
('C', 'B'): 2,
('B', 'H'): 1,
('H', 'C'): 1
}
Polymer NBCCNBBBCBHCB are present in the char count:
{
'N': 2,
'C': 4,
'B': 6,
'H': 1
}
Here some pairs have started to reoccour, and the char counts have
increased. So it will continue up to 40 steps, smooth and fast.
It works, since the char count are increased to match the polymer, and
it is fast, since the program does not care about the order of the
chars.
I struggled a lot with the direction, but realised way too much later
that the mappings are bidirectional.
Part 2 was exceptionally hard, but I realised early that the order did
not matter and that a simple boolean lock was all that was needed. The
challenge was to know when to watch for duplicates.
The seen was initially a set, but since new sets must be sent instead of
references, a list is used instead to be able to use the seen + [] hack.
Spent over an hour trying to figure out the incomplete sequenses, only
to realize it was easier to begin from the other way around.
After that, solution came out nice and clean.
Yet again I got stuck in the common AOC trap: The example input worked,
but not the actual input.
2 things got me stuck.
> The size of a basin is the number of locations within the basin, including the low point. The example above has four basins.
1. I missed the obvious part to only check the low points.
2. Based on the example, I asumed that the adjacent locations would
increase by one to count. This is wrong: What matters is that their
height is a larger value.
Way too long time for a simple problem. Never read puzzles sloppy.
For part 1, it took way longer than necessary since I read the
instructions over and over again. Gotta love AOC WOT.
Part 2 was a PITA. I got stuck at the last 2 examples since I at the
time did not find any clever way to determine which of the 2 outputs for
'1' mapped to c and f.
Since I already spent far too much time and effort, a try/except with
ValueError (digits.index will fail if c and f are flipped wrong) will do
for now.
There is probably a more efficient and smart way to do this.
Part 2 requires more clever code. In the first part, I kept track on
every single fish on order, much like the output of the example in the
puzzle.
However, by increasing the day count to 256, my code became obese and
would not run to the end: the OS killed it before it was done. It halted
around 150 days.
Browsing the sub reddit, I quickly realised that the current state of
each fish individually did not matter. For example:
3,4,3,1,2
This says 2 fishes has a timer set to 3, and 1 fish each has a timer of
1, 2 and 4.
Add one day, and we have
2,3,2,0,1
This says 2 fishes has a timer set to 2, and 1 fish each has a timer of
0, 1 and 3.
Notice how **the relative count does not change** (2, 1, 1, 1).
By using the excellent collections.counter, you get
>>> from collections import Counter
>>> Counter([3,4,3,1,2])
Counter({3: 2, 4: 1, 1: 1, 2: 1})
>>> Counter([2,3,2,0,1])
Counter({2: 2, 3: 1, 0: 1, 1: 1})
>>>
If visualized in a tabulat view, you get this:
0 1 2 3 4 5 6
----------------------------------
Initial 1 1 2 1
Day 1 1 1 2 1
The sequence moves **one step to the left each day**. Add another day,
and something extra happens.
0 1 2 3 4 5 6 7 8
----------------------------------------
Initial 1 1 2 1
Day 1 1 1 2 1
Day 2 1 2 1 1 1
2 things:
* A value higher than zero pops out on the left. By rules, 1 fish
has created 1 new fish, and resets its timer to 6.
* The new fish created has a timer of 8, since it will need 2 days
before it is able to start the create timer.
There are now 6 fishes.
Now, what happens on day 3?
0 1 2 3 4 5 6 7 8
----------------------------------------
Initial 1 1 2 1
Day 1 1 1 2 1
Day 2 1 2 1 1 1
Day 3 2 1 1 1 1 1
Now this happened:
* The fish on 0 creates a new fish, resets to 6.
* The created fish, once again, has a timer of 8.
* The fish created on day 2 decreases timer to 7.
There are now 7 fishes.
And so it continues. In Python, the most memory efficient and performant
method of leftpadding a list of values is to use collections.deque, with
the functions popleft and append.
Tricky part, got the test data correct at part 1 long before the actual input gace the correct answers. Pure luck I guess.
Part 2 I got stuck on, and resolved to visualization by a loop of
prints.
Yes, I do "".join(). Python is not always beautiful.
I began reusing part 1 for part 2, until I realised you cannot reuse the
Counter.most_common, and you need the actual values to be able to se
equal occourences.
I probably lost 5-15 minutes just to dribble with 3 levels of nested
objects. In GMT+1 before coffee, that cost me.
Part 2 was way uglier before some well motivated refactoring. Since all
tests and expected output were in place, refactoring was easy.
Felt a bit slow and rusty. Tooling was not set up properly on the
computer which decreased the flow.
Anyhow, fun first day! Could have been done more pythonic with list sequences, and readability would have increased with more use of sum() and lambdas. But this is not what Advent of Code is about.
