OK - your approach is far more efficient than mine! I suspect you did
what I had in mind, but
couldn't quite get that mind to produce.
I see that you (Raul) didn't bother with truncating divide towards
zero. In testing, I fell foul of this,
and used
divt =: {{ s * y <.@%~ | x [ s =. * x }}
... but I think you're ok in the actual "program" as div only has
positive input as far as I can see!
I've eventually turned my type-a-line-at-a-time procedure into a
J-function, with this result
in elapsed time:
timer' 10#.(>./,:<./) program 14 '
done forwards creating q
done backwards creating r
+----+-----------------------------+
|32.4|92928914999991 91811211611981|
+----+-----------------------------+
A glance at Windows' Task Manager revealed usage of 3~ GB , while space
(7!:2@])
showed 6.7!
(I'm still pleased with the performance of my solution to day 22, though!)
The slow forward search produces q, a boxed array of all possible
outcomes (Z values), at each of
the 14 steps:
({.~5<.#)each 3 {.q NB. everything aligns in fixed font
+-+---------+-------------------+
|0|5 6 7 8 9|142 168 194 220 246|
+-+---------+-------------------+
3{.each _3 {.q
+--------------------------+--------------------------+--------------------------+
|64953057 76834433 88715809|64953048 76834424 88715800|64953058 76834434
88715810|
+--------------------------+--------------------------+--------------------------+
In the quite slow backward sweep, from 14 to 1, using q, and the fact
that 0 is the only required
value of the final set of q, we derive r, a boxed array of possible W Z
pairs:
({.~5<.#) each _5 {.}:r NB. fixed font! r has an extra empty
element
+------+--------+------+-----+----+
|1 9110|1 236863|9 9110|8 350|1 13|
|1 9136|1 237539|9 9136|9 351| |
|2 9110|2 236864| | | |
|2 9136|2 237540| | | |
|3 9110|3 236865| | | |
+------+--------+------+-----+----+
({.~5<.#) each 5 {.r
+---+----+-----+------+-----+
|9 0|1 13|8 350|1 9115|1 350|
| |2 13|8 351|1 9141|1 351|
| | |9 350|2 9116|2 350|
| | |9 351|2 9142|2 351|
| | | | |3 350|
+---+----+-----+------+-----+
Not quite done - we need to get those combinations of Ws at each stage
which achieve Z=0 at
the last stage. It works forward again. Here, it would examine W
pairs 9 1 and 9 2 to find both
can produce values in 350 351, then those triples 9 1 8, 9 1 9, ... 9 2
9 compatible with 9115 ... 9142
and so on. That step runs quite fast and in smallish space.
ts' 10#.(>./,:<./) ('''',&< r) program 14 ' NB. running with r
provided as input; q not needed
q & r already done
q & r already done
1.25349 2.3815e6
Here's my J-version of the alu for one input-step:
dodata18r1 =: 3 : 0
0 dodata18r1 y
:
'p q r' =. x NB. W X Y aren't re-used
'W Z' =. |: 2 {."1 y NB. Z is possibly the output of a previous run
X =. W ~: q + 26 | Z NB. q e. [_14 15] ... _14 _12 _10 _7 _4 _2 _1 10
11 12 13 15
NB. X is 0 or 1
Z =. Z divt p NB. p is 1 or 26 ... 1 <==> q > 0, 26 <==> q < 0
Z + X * r + W + Z * 25 NB. r e. [2 13] ... 2 3 4 6 7 9 11 12 13
)
I couldn't see quite what it was doing, though the business with 26
does strongly hint
at something to do with the Roman alphabet.
That's not too bad, but "program" is pretty ugly stuff. I won't share
that code unless
begged to do so!
Cheers,
Mike
On 15/01/2022 18:10, Raul Miller wrote:
I've got this solved now,
Eugene Nonko put me on the right path here.
The trick, from my perspective, was to convert the machine code into
executable J. And, to ensure that I could use J's dimensionality to
manage multiple tests at the same time.
Specifically, I parameterized the three "block specific" values as C,
B and A (I initially used D for digits, but later spelled that out).
parse=: {{
blks=: _18]\];._2 input
C=: ". 6}."1]4 {"_1 blks
B=: ". 6}."1]5 {"_1 blks
A=: ". 6}."1]_3{"_1 blks
}}
digits=:14#<1+i.9
BLOCK=: {{
W=: x{::digits
X7=: W~:/(x{B)+26|y
if.X7 -:&$ y do.
((W+x{A)*X7)+(1+25*X7)*<.y%x{C
else.
((W+x{A)*X7)+(1+25*X7)*"_1 _<.y%x{C
end.
}}
Here, x indicated the digit number (0 for the leftmost digit, 13 for
the right most digit), and y indicated the result from the previous
block (0 initially).
The if statement was because I could not figure out how to build a
rank statement that worked consistently for all of my example cases.
I'm not sure if this was due to my limited imagination, or if it's an
artifact of J's rank conjunction. Maybe I'll circle back on that
later...
With this in place, the ALU became:
ALU=: BLOCK/@((i.-14),0)
Except, of course, my laptop is not powerful enough to handle this
expression because there's too many possible digits.
But it's rather quick to run through all the possibilities to
constrain the search space:
plausible=: {{
hist=:<need=:,0
for_k.i.-14 do.
try=. ~.(<.need%26),,(26*need)+/i.26
need=. ~.;((k BLOCK try)e.need)<@#try
assert.1e8>#need assert.0<#need
hist=:(<need),hist
end.
trial=: {{(y BLOCK y{::hist) <@(#&(y{::digits))@:(+./"1)@:e. (y+1){::hist}}
ref=:digits=:trial"0 i.14
}}
And, once I had that, it was straightforward to find the largest
viable serial number:
a24=: {{
digits=:14#<1+i.9
plausible''
i=. #@>digits
k1=.+/7>10^.*/\.i
k0=.14-k1
for_j.(k0{.i)#:i.-*/k0{.i do.
NB. echo ;j {&.> k0{.ref
digits=: (j {&.> k0{.ref) (i.k0)} digits
t=: |:ALU''
if.0 e.,t do.
' '-.~":;(k0{.digits),(($t)#:>./I.,0=t){each k0}.digits return.
end.
end.
}}
timespacex 'a24 0'
2.26213 1.59913e8
Part b was to find the smallest viable serial number, and for that, I
got rid of the negative in the for loop:
for_j.(k0{.i)#:i.*/k0{.i do.
And changed the max reduce to a min reduce in the result line:
' '-.~":;(k0{.digits),(($t)#:<./I.,0=t){each k0}.digits return.
And that also ran quickly for me:
timespacex 'b24 0'
0.252415 1.59913e8
(But... caution: actual running time will depend on the puzzle input
you're working with. I am not sure how much of my running time here is
luck and how much is decent approach.)
I am somewhat disappointed that it took me so long to see some of the
(now) obvious features of this puzzle. But... I have to admit some of
my other efforts were at least kind of fun.
Thanks,
--
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
