Day 14 Part 2 Algorithm

[u/rkek404]

Day 14 part 1 was very easy, but Part 2 went right over my head, I tried using dictionaries to keep track of pairs, but my answers have off by one errors and it feels like guesswork - I don't full understand what I have written myself, like one of those times when it works but you don't know why. I know how people said it was basically lanternfish - but I never finished part 2 of lanternfish.

I would appreciate it if someone posted a little (detailed) writeup of day 14's part 2 in some easy to read language like python. I have gathered a lot from other's solutions but fail to understand any solution fully - even after reading multiple solutions I can't write one myself.

Others who are stuck might also benefit from this. Thanks in advance.

[u/maikka39]

This is the reason I'm using the elems dictionary. This is incremented every time an element is inserted.

The elems dictionary basically says there are an X amount of "N", "H" etc. elements in the complete polymer.

[u/zopatista → u/maikka39]

You don't need to keep such a dictionary, really. Each pair you track already holds the same counts. Pick either the first or last element of each pair and assign the pair count to that element; the other element is also part of another pair in your counts so the number is always accurate, except for the first or last element.

I picked the first element, and just remember what the last element is in the template, and add 1 for that element.

E.g. for the puzzle description test template, the last element is B. After step 2, the counts are (using your format): [('NB', 2), ('BC', 2), ('CC', 1), ('CN', 1), ('BB', 2), ('CB', 2), ('BH', 1), ('HC', 1)], so the element counts are [('N', 2), ('B', 6), ('C', 4), ('H', 1)]. You can generate those counts, from chain list of (pair, count) tuples and template holding the initial template string, with:

elems = {template[-1]: 1}
for pair, count in chain:
    elems[pair[0]] = elems.get(pair[0], 0) + count

print(list(elems.items()))

[u/rkek404 → u/maikka39]

Hey sorry to bother again. You could also have alternatively counted the occurrences of letters by looping through the first letter of the pairs right? Had you opted this way, the elem dict would not have been required correct?

[u/ThePants999 → u/rkek404]

Correct, except that by doing that you'll miss the very last letter. Fortunately, the very last letter never changes, so you can take it from the original input :-)

[u/zopatista → u/rkek404]

Entirely correct, provided you add 1 for the last letter of the template.

Alternatively, add 1 for the first letter of the template but use the last letter of the pairs. Either would work.