As I recall, a killer question until one realises there’s no need to preserve the order; then it’s just a matter of maintaining counts, as you observe.
I’m currently wondering how to acquire the tera- or peta-bytes of storage to deal with day 22 part 2. Part 1 is easy, of course. No spoilers, though. I haven’t given up yet! Cheers, Mike Sent from my iPad > On 4 Jan 2022, at 03:06, Raul Miller <rauldmil...@gmail.com> wrote: > > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
