https://adventofcode.com/2021/day/14
For day 14, we were supposed to run a "polymerization sequence" for N
steps, and then find the difference in the quantity between the most
common and least common elements of the sequence.
For part A, we were supposed to run 10 steps. For part B, we were
supposed to run 40 steps.
The sample data looked like this:
sample=: {{)n
NNCB
CH -> B
HH -> N
CB -> H
NH -> C
HB -> C
HC -> B
HN -> C
NN -> C
BH -> H
NC -> B
NB -> B
BN -> B
BB -> N
BC -> B
CC -> N
CN -> C
}}
The first line was the starting sequence. The remainder was "insertion
sequences". An insertion sequence inserts the element on the right
between the pair on the left. So, my initial implementation was
basically a string replace, 'CH' became 'CBH' and so on...
But that falls over for part B, because my laptop does not have enough
terabytes of ram (and string replace on that scale would probably be
painfully slow).
Fortunately, we do not care about the order of these elements for this
problem. So we can represent the counts of each pair in a list, and
represent the insertion rule using inner product. Then we sum up the
numbers from the list (each value representing a count of the first
element of the pair), and add 1 for the final element of the initial
argument (since it doesn't have a pair to represent it).
Giving this as an example implementation:
unpack=:{{
(insertion;.2 (}.~ 2+i.&LF)y) ;({.~ i.&LF) y
}}
insertion=:{{
'before insert'=. <;._2@(rplc&(' -> ';LF)) y
before;({.before),insert,{:before
}}
b14=: {{
'pats polymer'=. unpack x
pairs=. ,{;~bases=. /:~~.polymer,;,pats
cnts=. <: #/.~ pairs,2 <\polymer
'before after'=. <"1 |: pats
ucnts=. (i.#pairs)e."1 pairs i.2 <\S:0 (before i. pairs) { after
(>./-<./) (({:polymer),{.@>pairs) +//. 1,+/ .*&ucnts^:y cnts
}}
sample b14 10
1588
sample b14 40
2188189693529
As usual, there are probably better ways of expressing this...
I hope this interests at least one other person,
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
