((λ (x) (x x)) (λ (x) (x x)))

Thoughts on Eternity, God, and lesser endeavors

Subscribe to RSS feed

Posts tagged with "euler"

APL Hacking: Project Euler Daily (#15)

Wednesday, March 16, 2011 2:56:57 AM

, , , ...

This was a problem to find all of the forward searching paths in a 20 by 20 grid. This is one that we actually use a lot in our introductory programming courses, but I did not want to do it the way that we do it in those classes, where it is a lesson in recursion. Instead, I applied my rusty knowledge of combinatorics to the problem and remembered how to compute the answer to this problem using binomial coefficients.

The solution, of course, would be too easy if I could just use 20!40 in APL. This number is too large for 32-bit integers, so it goes to floating point, and I lose two digits that I need. I could have done this the long way, but I decided that this would be a great chance to play with the Foreign Function interface to Java.

Problem #15:

∇R←PEFIFTEEN;N;K;FACT;TIMES;NBI;STR;DIV;⎕IO
⎕IO←1

⍝ Compute the number of paths through a 20×20 grid
⍝ which is just 20!40.

N←40 ⋄ K←20

⊣⎕FX 'R←NBI X' 'R←''java'' ⎕NEW ''java.math.BigInteger''(⍕X)'
⊣⎕FX 'R←X TIMES Y' 'R←X.multiply Y'
⊣⎕FX 'R←FACT N' 'R←TIMES/NBI¨⍳N'
⊣⎕FX 'R←STR J' 'R←J.toString'
⊣⎕FX 'R←X DIV Y' 'R←X.divide Y'

R←STR(FACT N)DIV(FACT K)TIMES FACT N-K
∇

3 comments

APL Hacking: Project Euler Daily (#14)

Monday, March 14, 2011 11:23:32 PM

, , , ...

This problem was interesting in all different ways. It asks for Collatz Sequence counts. First, I tried to do the naive way, and discovered how that won't work. I then tried to find a more sophisticated algorithm, and realized that I wouldn't find one that suited me. Instead, I decided to go with a caching algorithm, or, basically, to memoize the results. This still left me with some things to play with. There were issues of just when and where I should do the caching. I wanted the code to be as simple as possible, but I didn't know whether caching should be done step-wise, or if it should be done on each main call to the subroutine.

In the end, I decided to cache all the values that I collected, but to only do it once, at the end of each call to the subroutine. This meant that I had to collect the results of each value. It gained me a bit in that I was able to make large contributions to the cache early on.

I also made the optimization of eliminating the first 500,000 possible choices right of the bat, because I knew they could not possibly be one of the answers through some basic analysis of the problem.

Eventually, I was lead to this solution.

Problem #14:

∇R←PEFOURTEEN;⎕IO
⎕IO←1

⍝ The starting number of the longest Collatz Sequence
⍝ that is less than 1,000,000.

COLLATZ∆CACHE←(2*20)⍴0
COLLATZ∆STATS←⍬
R←500000+⌈/1↑⍒COLLATZCOUNT¨500000↓⍳999999
∇

∇R←COLLATZCOUNT M;C;F;N;S;⎕IO
⎕IO←1

N←M ⋄ S←⍬

⍝ This appears to eat up the most amount of time,
⍝ comment it out for much better performance.
→(10000|M)/LOOP ⋄ M÷10000
COLLATZ∆STATS←COLLATZ∆STATS,+/0=COLLATZ∆CACHE

LOOP:
⍝ Use cached value if there is one.
→(N≥⍴COLLATZ∆CACHE)/NOCACHE ⋄ →(0≠COLLATZ∆CACHE[N])/DONE
NOCACHE:S←N,S ⋄ →(1=N)/DONE
→(2|N)/ODD ⋄ N←N÷2 ⋄ →LOOP
ODD:N←1+3×N ⋄ →LOOP

DONE:
F←S≤⍴COLLATZ∆CACHE
COLLATZ∆CACHE[F/S]←COLLATZ∆CACHE[N]+F/⍳⍴S
R←COLLATZ∆CACHE[M]
∇


Notice my comment in the COLLATZCOUNT function. I used the profiler on my code after I noticed that it took almost three minutes to run this code. To my utter amazement (though, less so after I thought about it), I saw that almost all the time was taken up by my book keeping and progress reporting code. I disabled this code and it ran much more quickly, roughly within my minute time-limit.

I couldn't leave it at that, of course, I re-enabled things and decided to try out some more of the statistics and charting features in APLX. This gave me the following information about how the cache population changes over iterations. Smaller means a fuller cache.

collatz_stats.svg

2 comments

APL Hacking: Project Euler Daily (#13)

Sunday, March 13, 2011 4:13:26 AM

, , , ...

So, this is actually my post for Friday, but since I was traveling, I was not able to post anything for that day.

This one was pretty fun. The problem is that the input to the incoming function was a series of 100 50-digit numbers. Now, this won't fit within 32-bit integers on my system (bah, 32-bit APL on a 64-bit machine, oh well). This required that I split the integers up, do the additions on them in small chunks, and finally apply a carry algorithm to them.

I initially wanted to do this with a scan and a CARRY operator, but I realized that this won't work because of the nature of the scan algorithm. Instead, I had to collect the results of the carry as I went and do a reduce. That seems to work okay, though. Here's the basic use:

⍝ First ten digits of the sum of the numbers in X.

⌽⊃(100000 CARRY)/⍬,+⌿100 10⍴⎕FI(6000⍴(5⍴1),0)\(~⎕R=X)/X


I used the following carry algorithm:

R←E(B CARRY)S

⍝ Performs a carry operation.
R←(¯1↓S),(B|¯1↑S),E+⌊(¯1↑S)÷B

No comments

APL Hacking: Project Euler Daily (#12)

Thursday, March 10, 2011 10:12:56 PM

, , , ...

This was the first problem that I had to deal with that didn't work right or quickly if I used the standard operators the way that I was used to using them. Instead, I had to create some helper functions that made sense. In this case, they were really small, but I decided that now was as good a time as any to play with the Object Oriented features of APLX. In the end, it was actually pretty easy to use compared to what it might have been, and for that, I am grateful that APLX favors simple solutions.

I also took this opportunity to come up with a decent way to give feedback that indicates a not found error.

This is the class that I wrote for the system;

Twelve; D;R;Match {
D←0⍴0
R←0⍴0

∇X←Match N
X←D<2×+/0=(⍳⌊N*0.5)|N
∇

∇Twelve A
(D R)←A
∇

∇X←Solve;Y;⎕IO
⎕IO←1
X←(⊃(Y,(⊂'Not found'))[(Match¨Y)⍳1])⊣Y←+\⍳R
∇
}


And this is my function that uses it for Problem #12:

∇R←PETWELVE;T

⍝ What is the value of the first triangle number
⍝ to have over five hundred divisors?

T←⎕NEW 'Twelve' 500 13000
R←T.Solve
∇

No comments

APL Hacking: Project Euler Daily (#11)

Thursday, March 10, 2011 12:27:55 AM

, , , ...

I really liked doing this one. I had no idea how to approach this idea at first. I couldn't think of any simple approach to it at all. I decided to look at the APLX Scrapbook and see if I could glean any inspiration from there. Lo, and behold, what did I find, but a snippet of code for raveling the diagonal of a matrix! I did not really understand what the grade up and grade down functions did until I went through this problem. After playing around with the scrapbook entry for a while, it made sense to me, and I could see how to apply it to this problem.

I am fairly certain that after figuring out the diagonals, I neglected to properly think about the rest of the code, but here it is anyways.

Problem #11:

∇R←PEELEVEN;B;DA;DB;G;S;⎕IO
⎕IO←1

⍝ What is the greatest product of four adjacent numbers in any direction
⍝ (up, down, left, right, or diagonally) in the following 20×20 grid?

G←'08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 '
G←G,'49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 '
G←G,'81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 '
G←G,'52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 '
G←G,'22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 '
G←G,'24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 '
G←G,'32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 '
G←G,'67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 '
G←G,'24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 '
G←G,'21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 '
G←G,'78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 '
G←G,'16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 '
G←G,'86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 '
G←G,'19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 '
G←G,'04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 '
G←G,'88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 '
G←G,'04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 '
G←G,'20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 '
G←G,'20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 '
G←G,'01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48'
G←20 20⍴⎕FI G

⍝ Diagonal selector
S←6↓394↑⍋+⌿(⍴G)⊤(⍳⍴,G)-⎕IO

⍝ Edge partition
B←1+0,+\2>/S

⍝ Grab the diagonals
DA←⊃B⊂(,G)[S]
DB←⊃B⊂(,⊖G)[S]

⍝ Best of the products of each way to grab numbers
R←⌈/,4×/DA⍪DB⍪G⍪⍉G
∇

2 comments

APL Hacking: Project Euler Daily (#10)

Tuesday, March 8, 2011 6:29:26 AM

, , , ...

This was a bit of a fun one, since I had trouble trying to get the result into a 32-bit integer. I had to do a bit of math to get that to work. This one I did a while back, actually, so I am not sure that it contains all of the wisdom that I have learned from the previous feedback!

Problem #10:

∇R←PETEN;D;I;N;X;⎕IO
⎕IO←1

⍝ Find the Sum of all the primes below two million.


N←2000000 ⋄ I←2 ⋄ X←N⍴1 ⋄ D←10000
LOOP:X[I×1↓⍳⌊N÷I]←0 ⋄ I←I+(I↓X)⍳1 ⋄ →((I*2)≤N)/LOOP
X←+/(2⍴D)⊤X/⍳N

I←(⍴X[1])-4 ⋄ R←(X[1]+⌊X[2]÷D)(D|X[2])
∇

1 comment

APL Hacking: Project Euler Daily (#9)

Sunday, March 6, 2011 7:30:43 PM

, , , ...

Finally, we get an interesting one. In this problem, I struggled with a desire to express the solution simply, and to also make it computable in a reasonable amount of time. To make things worse, the simplest approach also uses the most memory. I had to figure out a way to fit things within the limited memory constraints that I have (2GB, yeah, really limited, I know), and also get good, fast results out of the system. More than either of these though, I wanted to have a solution that was immediately comprehensible for what it was doing.

In the end, my solution was to do some initial analysis of the problem, which allowed me to be very confident that there were many less pythagorean triples than there were possible triples summing to 1000. Thus, I started by generating the pythagorean triples in a reasonable range that I figured would contain the solution. After that, I extracted the triples from that and reduced them to only the one combinations that add up to 1000. This will give only a single set of triples, but two different results in two orderings.

This is an especially inefficient operation memory-wise, because it is computing way too many results. On the other hand, for what it is doing, it generates these triples and filters them plenty quick enough.

Problem #9:

R←PENINE;X;Y;I;⎕IO
⎕IO←1

⍝ Product of the pythagorean triple where a + b + c = 1000.

X←500 ⋄ Y←(⍳X)*2
Y←Y∘.=Y∘.+Y
I←1+(⍴Y)⊤(,Y)/0,⍳(×/⍴Y)-1
R←×⌿1↑[2](1000=+⌿I)/I

3 comments

« Prev 1 2 3 4 5 Next »