There is a typo in the line of code you posted. It should read:
>./ +/"1 (+/\"1 ]0,.15+#:i.2^14){,t
Project Euler problem 18 <https://projecteuler.net/problem=18> provides a
triangle t of positive integers, and the task is to find a path from top to
bottom with the maximal sum.
The triangle, padded with 0s to form a (lower triangular) matrix, is as
follows:
t=: 0&".;._2 (0 : 0)
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
)
$t
15 15
>./ +/"1 (+/\"1 ]0,.15+#:i.2^14){,t
1074
A path can be encoded as a boolean vector, 0 means go to the left at the
next level, 1 to the right. (And in the matrix, 0 means go straight down,
1 means go one step to the right at the next level.) Since t is only 15 by
15, there are only 2^14 (16384) possible paths, well within the capability
of modern machines.
J has an interactive environment amenable to exploring an expression bit by
bit. You do have to know J syntax to inform the exploration.
,t - ravel t, convert the matrix t to a vector
2^14 - 2 to the power 14
i.2^14 - the integers from 0 to 2^14 less 1
#:i.2^14 - the same integers encoded as a boolean matrix
15+ - add 15 to each element
0,. - prepend a 0 column (every path starts at the top)
] - identity function serving to separate the 1 and the 0 (1 0 would
be a 2-element vector)
+/\"1 - "plus scan" (cumulative sum) on each row (each rank 1
subarray). These are the indices required to index into ,t .
(){,t - index into the ravel of t, thereby getting the integer values
for each element of a path. The indices are a matrix so the result is a
matrix. [matrix x below]
+/"1 - sum each row of the matrix [vector s below]
>./ - find the maximum of each sum
And what is the path? To facilitate the answer, assign names to some
intermediate results:
>./ s=: +/"1 x=: (+/\"1 ]0,.15+#:i.2^14){,t
1074
s i. >./s NB. index in s of the maximum
12925
12925{x NB. the actual path
75 64 82 87 82 75 73 28 83 32 91 78 58 73 93
What are the indices of paths with the maximal sum?
I. s=>./s
12925
So there is only one such path.
On Tue, Jan 6, 2015 at 8:24 AM, oventarb oventarb <[email protected]>
wrote:
>
>> ./ +/"1 (+/\"1 ]0,.15+#:i.2^14){,t
>>
>
> This code was written by Roger Hui as the solution for Project Euler
> Problem 18.
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
