Once in a while I like to test my J skills if and when I bump into a challenge
which seems worthwhile.
I was alerted when I saw this mail
http://www.jsoftware.com/pipermail/programming/2019-August/053890.html and read
the issues on
http://www.petecorey.com/blog/2018/12/14/advent-of-code-marble-mania/.
So I decided to solve both parts of the marble problem
(https://adventofcode.com/2018/day/9) in a proper J-way and within the 2
minutes Corey scored.
My first solution just added 23 marbles at a time and this was quick enough for
the first part:
et'foo0 424 71482' NB. 424 players with last marble
0.4885656
However it scaled rather badly:
et'foo0 424 714820' NB. Target input for second part is
424 7142800
85.939225
So a factor of almost 180 slower for 10 times higher input. This would result
in more then 4 hours for the second part of marble problem.
So instead a spent a few weeks (…) thinking about the structure in the marble
sequence and came up with another solution fooA:
ts'fooA 424 71482' NB. Some 25 times faster than foo0
0.019614 7948480
fooA 424 7148200 NB. The answer appeared to be correct,
not unimportant 😉
3443939356
ts'fooA 424 7148200'
1.5540415 7.7280275e8
Well, I succeeded well within the two minutes.
Even ten times more I could handle:
ts'fooA 424 71482000'
19.075672 6.9961013e9
For those interested, here is the rough(!) code, without explanation.
X=. 3 : '(6 ,@#,:0 1)' NB. y=n
Y1=. 3 : '13,@#,:0, y-1' NB. y= 2,3,4,...,n
Y2=. 3 : '3,@# ,:0, 0 _1 0+ y' NB. y= 2,3,4,...,n
Z=: 4 : '(x#0),~ 16,@#,:0, y'
fooA=: 3 :0 NB. y is # players, last marble
'pl lm'=: y
(lm <.@% 23) fooA y
:
'pl lm'=: y NB. =. 424 71482
t1=:$0
t=. (#~ 23>]) (,@,.>:@i.@# +>./)^:5[0
'a b'=. 14({.;}.) t
mx=.{: a
b=. b,6{.a
a=. 6}.a
t1=: t1, {.a
b=.b,1{a
a=. (2}.a),16{.b
b=. 16}.b NB. End of introduction
while. (#t1)< x do.
m=.#a
n=.<.1+16%~m-22
sr=. (X n), (,(Y1, Y2)"0 t), (m-22+16*n-1) Z n [ t=.2}.i.>:n
mx=.5{a NB. max
b=.mx+i22n=.1+,}."1 i.n,23
a1=.(a,b)({~/:@/:)sr
a2=.a1/:0(36+38*i.n)}(1#~ #a1)
t1=:t1,n{.a2
a=.(38+(38*n-1)-#a2)|.n}.a2
end.
>./(+//.)~/(((+{.),:{:@]) 23((*,:pl|<:@]) >:@i.@#) ]) (lm <.@% 23){.t1
)
R.E. Boss
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
