Nice! It certainly interests me, although thorough analysis will have to
wait till I get back to my PC.
I think Raul's approach is similar, although mine, especially part B, is
more complicated.
NB. Day 14: Extended polymerization
in=: [: freads '.txt' ,~ _2 {.!.'0' ": NB. read input of day y (given as
num)
NB. part A: each rule indicates sequence to find, and letter to be inserted
at the found position.
prep=: (}:@>@{. ,&< rulesp)@(<;.2~ (2#LF)&E.)@,&LF
rulesp=: ([: ". ''''([,,~)]);._2@rplc&(' -> ';'')@}.@>@{:
i14=: prep in 14
t=: prep {{)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
}}
polymer=: {{
'temp ir'=: y NB. extract template and insertion rules
NB. replacement for insertion rule, orig first , new letter to insert (not
last orig, because part of next pair).
rep=: {. , (({:"1 ir)) {~ ((}:"1 ir))&i.
NB. apply insertion rules (add last dropped letter, because no following
pair
air=: {: ,~ [: , 2 rep\ ]
NB. range counts rules applied 10 times to the template
(>./-<./) #/.~ air^:x temp
}}
a14=: 10&polymer
NB. part B: now for 40 rounds; polymer is no good; both time and space
increase exponentially (+- 2x for every additional step)
NB. try keeping digraph counts
poly2=: {{
NB. alphabet lookup: convert to numeric domain
alu=. (alfa=.~.(,,)&>/y)&i.
N=. #alfa
'tn irn' =. alu each y NB. numeric template and insertion rules
irn=. /:~ irn NB. sort so consistent numbering for below
NB. digraphs are (implicitly) numbered i. *: # alfa
NB. dg =: alfa {~ (2#N)#:i.@*:N
NB. insertion rules are converted to digraph reproduction rules,
NB. in which each digraph (index) has two siblings
drr =. (2#N) #. |: (0 2 ,. 2 1) { |:irn
NB. matrix indicating for each digraph a mask of its siblings
drrm=. (i. *:N) e."1 drr
NB. get initial digraph counts
dgc =.x: (i. *:N) +/@(="0 1) (2#N)#.2]\tn
NB. insertion step: select from drr where *dgc, add to dgc with correct
multiplicity.
NB. update dgc x times by matrix multiplication
dgc =. drrm +/ .*~^:x dgc
NB. convert digraphs back to chars and count -: for each character,
except for first and last charactess: -:@>:
NB. so: add first and last mask (note, counts are in nub order of letters)
NB. letter counts from digraph cnts
cnt=. (|:@(2&# #: i.@*:) N) +//.&, ,~dgc
NB. mask for first and last
flm=. (i.N)e.({.,{:)tn
NB. final result
diff=.(>./-<./) -: flm+cnt
}}
b14=: 40& poly2
NB.
(a14;b14) i14
Jan-Pieter
On Tue, Jan 4, 2022, 04:06 Raul Miller <[email protected]> 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
