My "all factors algorithm" isn't quite as slick as Henry's, and for part
2 I computed the presents for days one through eight-hundred thousand
all at once, rather than a day at a time. I chose against testing for a
finished condition. For some reason I didn't seem to get the amend in
place working and ran into several out of memory problems, which,
thankfully, occurred immediately. The first version I had working used
the insert into a boxed list trick. And I discovered after the fact
that amending multiple times to the same location is ok. Rather than
truncating out-of-bounds indexes I mapped these to some junk elements.
Run time is longer than Henry's but not intolerably so. My input was
the same as Henry's, which differed from Pascal's.
For day 19 part 2 I've not looked at the spoilers posted here, and am
currently thinking about the problem involving a directed graph and the
answer lying in those terminal elements which cannot transmute.
Anyway, here's my factoring algorithm used for part 1 sum of factors,
and my slowish part 2 day 20 solution:
factors=: [: */S:0 [: { [: <@(^i.@:>:)/"1 [: |: __&q:
sorted_factors=: [: /:~ factors
assert 1 2 4 5 10 20 -: sorted_factors 20
PRESENTS=: 29000000
M=:1 :'m*1000' NB. I dislike counting digits
N=:800 M
A=: (N + 54) $ 0
I=:>:i.50
i=:(I+N)<.I&*
deliver=: (({~i)~+11*[)`(i@:[)`]}
+/A~:0
0
B=:deliver&.>/(;/>:i.N),<A
$B
C=:>B
$C
800054
I.(C>PRESENTS)
705600 718200 720720 725760 728280 730800 735840 737100 739200 740880
742560 743400 745920 748440 749700 750960 752400 753480 756000 757680
758520 760320 761040 762300 763560 764400 766080 766920 767340 767520
768240 768600 769440 769860 771120 772200 7728...
Date: Sun, 20 Dec 2015 22:26:14 +0000 (UTC)
From: "'Pascal Jasmin' via Programming"<[email protected]>
To: Programming Forum<[email protected]>
Subject: [Jprogramming] advent 20
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=UTF-8
div=: /:~ @: , @: > @: (*/&.>/) @: ((^ i.@>:)&.>/) @: (__&q:)
p:1
p1 =. >:^:(3600000> +/@:div"0)^:(_) 100000
p:2
>:^:(36000000 > 11 * +/@:(] (] #~ 50 >: <.@%) div@]))^:_ p1
an interesting part about timing part 2, is that typically I would not use ^:_
when writting the function out of fear that a bug causes an infinite loop
using ^:200000 for example gets the same result as ^:_ , but timings:
timespacex '>:^:(36000000 > 11 * +/@:(] (] #~ 50 >: <.@%) div@]))^:_ p1'
0.68445 23424
timespacex '>:^:(36000000 > 11 * +/@:(] (] #~ 50 >: <.@%) div@]))^:200000
p1'
5.31956 21376
The reason its much longer is that the while condition is evaluated 200k times
even if the result has converged.
A trick that adds a small complication, but keeps the speed, is to use a simple
transform to signal an end of loop.
timespacex '0&,^:(36000000 <: 11 * +/@:(] (] #~ 50 >: <.@%)
div@]))@>:^:(1=#)^:200000 p1'
0.76082 23168
main condition is turned from while to until, and the response is to alter shape. This
shape altering signal is also useful when applying to multiple items, and 1 item can
"find a solution" and halt the entire program.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
