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
