And... I forgot to mention: the second column of my r (the first
column of your r) contains [partial] serial numbers (corresponding to
the z value in the first column of my r (the second column of your r)).
Conceptually, the second column is 0, then ,.D then ,.10 #.>,{D;D then
,.10 #.>,{D;D;D and so on (but the search space pruning means that
most such values are discarded). Or, put differently, the largest
possible value for the second column would initially be 0, then 9,
then 99, then 999, then 9999, and so on, ... except that many invalid
values are discarded early.
You (Stefan) knew this, but I worry that my having left out this
detail might have been discouraging for people trying to read my
writeup.
Sadly, I all-to-often make mistakes.
Oh well,
--
Raul
On Sat, Jan 22, 2022 at 8:30 AM Stefan Baumann <ste...@bstr.at> wrote:
>
> Very inspiring…
>
> 3 things I was not aware of:
> * „cut“ and how you use it with obverse ; in combination with &.
> * 'I0‘~ evokes the verb I0
> * 'q r'=. automatically unboxes a boxed argument
>
> and the nice use case for fold F..
>
> Thanks. Stefan.
>
> On Fri 21. Jan 2022 at 2:35 PM, Raul Miller <rauldmil...@gmail.com> wrote:
>
> > Here's a rephrasing of your (Stefan Baumann's) approach.
> >
> > Here, input contains the text of the AoC supplied input.txt file:
> >
> > input=: fread '~/Documents/aoc24input.txt'
> > D=:1+i.9
> > M=: <;._1'/inp w/:/-/_/add/+/mul/*/div/<.@%/mod/|~/eql/='
> > I=: ;@|."1(3 1 3 2 4 0{'[';'=.';])&.(cut :.;)L:0;._1<;._2 rplc&M input
> > I=: I,"1'''w x y z k''=.D;0;0;x;D+10*y'
> > ".I=: (;"1'I';&":&>i.14),"1'=:{{k,.~',"1 I,"1'}}'
> >
> > step=: {{
> > 'q r'=.y
> > (>./{."1 r);(#~ q>:{."1)^:(q e. {."1) dm ,/('I',":x)~/"1 r
> > }}
> >
> > MN=:{{
> > dm=: ~.@:({."1) ,. {."1 u//. {:"1
> > {:,(#~ 0={."1) (0;,:0 0) 1&{:: F..step i.#I
> > }}
> >
> > D is digits
> > M is search&replace values turning the AoC text into J words
> > I is text representing verb definitions corresponding to that AoC text
> > (one verb for the code specific to each digit).
> > I0 .. I13 are the corresponding verbs.
> > step is a wrapper for those verbs -- x is the digit position (0..13)
> >
> > Within 'step', the intermediate result (y) value is q;r where r is two
> > columns (first column is the candidate z values from the previous
> > block -- initially 0), q is the maximum such z value from the block
> > prior to the previous block.
> >
> > Search space reduction happens in each step:
> >
> > (*) when the same z value corresponds to multiple (partially formed)
> > serial numbers, only the best case serial number is retained (this is
> > the 'dm' filter).
> > (*) when ... how should this be put ... when z seems to be
> > accelerating downwards, large values of z are discarded (this is the
> > 'q' filter).
> >
> > MN sets up the final stages of the calculations, runs through the full
> > set of computations (pruning the search space along the way) and then
> > finds the serial number whose z value is 0.
> >
> > Mostly it's doing 13 step 12 step ... 2 step 1 step 0 step 0;,:0 0
> > (with some setup at the beginning and some teardown at the end).
> >
> > And, for example, 0 step 0;,:0 0 is 0;0 I0 0 and has a maximum z value of
> > 17
> >
> > And, continuing the example (1 step 0 step 0;,:0 0) is 17;,/I1/"1(0 I0 0)
> >
> > I'm not sure how we could have quickly guessed that that 'q' filter
> > would have been a good part of the puzzle solution -- any insight
> > there would be greatly appreciated. But it's a nice fit to the
> > problem, and once you realize it's possible it's certainly testable.
> >
> > Thanks again,
> >
> > --
> > Raul
> >
> > On Fri, Jan 21, 2022 at 7:52 AM Raul Miller <rauldmil...@gmail.com> wrote:
> > >
> > > I should add, after studying this a bit more:
> > >
> > > It looks you are also tracking the "maximum z value" from each digit's
> > > block of code -- p is the maximum z value from the previous block, and
> > > q is the maximum z value from the block before that -- and when q is
> > > greater than the minimum z value of the current block, you discard all
> > > possibilities whose z exceeds q.
> > >
> > > I don't know how you came up with this heuristic, but it does work,
> > > and it's critically important for your approach.
> > >
> > > Thanks,
> > >
> > > --
> > > Raul
> > >
> > > On Thu, Jan 20, 2022 at 2:46 PM Raul Miller <rauldmil...@gmail.com>
> > wrote:
> > > >
> > > > Hmm... that's really neat.
> > > >
> > > > Personally, I would use J's cut rather than <;._1 ' '&, but that's
> > > > pretty minor. (Also, I got rid of the fwrite -- to inspect i, I
> > > > instead used 9!:37]4$0 512).
> > > >
> > > > (Also, for my own sanity, I removed the "0 from the trailing edge of
> > > > the i0..i13 verbs and instead put had i',(":y),'"0/"1 in my definition
> > > > of mn. This did not accomplish anything useful for me. But,
> > > > hypothetically, if I had wanted to use the debugger on one of those
> > > > verbs this would have let me inspect x and y within an execution
> > > > instance.)
> > > >
> > > > Anyways, to avoid fwrite and load, you could use 0!:0 (or, if you are
> > > > like me and wanted to see what was being executed, 0!:1 -- but you
> > > > could also use echo to display the script).
> > > >
> > > > So, basically: you converted the input to literal J, using
> > > > instruction-at-a-time manipulation, and extracted the blocks as marked
> > > > by the inp statements. This is really nice, because it does not
> > > > require having inspected the code and taken advantage of the visible
> > > > regularities there. (Though it looks like you did take advantage of
> > > > the fact that w, x and y were irrelevant between these blocks...).
> > > >
> > > > And then the other thing you did was form up the successive partially
> > > > formed serial numbers (in 'k' in your i0..i13 verbs) and when you
> > > > encountered multiple z values corresponding to different serial
> > > > numbers you pruned the intermediate results to either the maximum k
> > > > (>. mn) or minimum k (<. mn) for those z values, depending on which
> > > > part of the puzzle you were working on. And *that* is what makes this
> > > > work without running out of memory.
> > > >
> > > > And, of course, like you mention -- <. mn and >.mn run to completion
> > > > right away because mn does not depend on y (nor x).
> > > >
> > > > Really slick. (Though it does require enough analysis of the input
> > > > data to discard w, x and y between blocks or (equivalently) to realize
> > > > that z was the controlling value for every block and not just the
> > > > final block.)
> > > >
> > > > Thanks!
> > > >
> > > > --
> > > > Raul
> > > >
> > > >
> > > >
> > > >
> > > >
> > > > On Thu, Jan 20, 2022 at 12:25 PM Stefan Baumann <ste...@bstr.at>
> > wrote:
> > > > >
> > > > > Almost gave up on that one - but got it solved somehow and still
> > don't know
> > > > > why it works...
> > > > > I started to parse the instructions into 14 iteration verbs i0-i13.
> > For
> > > > > this I used a mapping m for translating instructions into J verbs -
> > mapping
> > > > > inp to : is merely used for splitting; the jx verb then creates the
> > > > > corresponding J expression for the instructions which are eventually
> > > > > written to i, the J code to produce the iterations. I also wrote i
> > to disc
> > > > > for inspection in a spreadsheet:
> > > > >
> > > > > m=: 'inp
> > > > > ';':';'-';'_';'add';'+';'mul';'*';'div';'<.@%';'mod';'|~';'eql';'='
> > > > > d=: >: i.9
> > > > > jx=: {{ ('[ ', >@(1&{), '=.', [: ; 1 0 2&{) <;._1 ' '&, y }}
> > > > > NB. i holds the J code for iteration verbs i0, i1,... ,i13
> > > > > i=: ,/"2 ([: jx@> [: |.@}. <;._2);._1 rplc&m fread 'xxiv.txt'
> > > > > i=: i,"1 '[ ''w x y z''=. |:y,.~0,.~d,.0 [ k=.d+10*x }}"0'
> > > > > # ". i=: i,~"1 (,&'=. {{ k,.z')@('i'&,)@":"0 i.#i
> > > > > 14
> > > > > 'xxiv.ijs' fwrite~ (,~ ,&LF)~/ i NB. Write i to disc for
> > inspection
> > > > > 3681
> > > > >
> > > > > The maximum and minimum model number are then computed with the
> > adverb mn -
> > > > > which takes >. and <. as a verb resp.- constructed from the J code
> > stored
> > > > > in noun j. mn filters in 2 ways:
> > > > > 1. The verb dm calculates the distinct maximum/minimum. This was not
> > enough
> > > > > - ran out of memory.
> > > > > 2. Then it appeared that z can only get smaller when it is divided
> > by 26
> > > > > during the iteration and then it gets the same values as 2 iterations
> > > > > before. So in that case throw away all values larger than the
> > maximum 2
> > > > > iterations ago, which is stored in q - p is the maximum of the
> > previous
> > > > > iteration. Valid records are stored in r.
> > > > > This at least solved my puzzle input:
> > > > >
> > > > > NB. j holds the J code for the model number adverb mn
> > > > > j=: 'mn=: 1 : 0',LF
> > > > > j=: j, 'dm=. ([: ~. {:"1) ,.~ {:"1 u//. {."1',LF
> > > > > j=: j, '''q p''=. 0, >./ {:"1 r=. i0/ 0 0',LF
> > > > > j=: j, ; {{
> > > > > '''q p''=. p, >./ {:"1 r=. (#~ q>:{:"1)^:(0<[: I.&q {:"1)
> > > > > dm,/i',(":y),'/"1 r',LF
> > > > > }} &.> }.i.#i
> > > > > j=: j, '{., (#~ 0={:"1) r',LF ,')'
> > > > > {{ load y [ j fwrite y }} 'xxiv.ijs'
> > > > > >.mn NB. (*)
> > > > > 99394899891971
> > > > > <.mn NB. (**)
> > > > > 92171126131911
> > > > >
> > > > > I was puzzled that I had to write >.mn - first tried to use >.mn 0 -
> > but
> > > > > that's probably due to y missing in mn's definition.
> > > > > What also didn't work was executing j with ". - is there a way of
> > doing
> > > > > that without using fwrite and load?
> > > > >
> > > > > Resources used were quite small:
> > > > > timespacex '>.mn'
> > > > > 0.0939154 8786816
> > > > >
> > > > > Thanks. Stefan.
> > > > >
> > ----------------------------------------------------------------------
> > > > > For information about J forums see
> > http://www.jsoftware.com/forums.htm
> > ----------------------------------------------------------------------
> > For information about J forums see http://www.jsoftware.com/forums.htm
> >
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
