Re: Project Euler Problem 11 on the HP 28C/S ? Message #10 Posted by C.Ret on 11 July 2011, 4:31 a.m., in response to message #9 by Gilles Carpentier
Hi,
The uses of AXL and TRAN to manipulate the list of data are interresinting. But I am in difficulty to clearly understand how much computation are made by the calculator, especially in DOSUB sequences.
In comparison, here is the way I resolve Euler11 on my HP 28S.
First step is to enter the array of 20x20 datas. This is really a lot of typing (and double check), HP28C/S have no i/o facility.
[[ 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 ]
[ 49 49 99 40 17 ...
20x20 arry
[ ... ]]
'DATA11' STO
Second step, computing the product of 4 consecutive elements in any directions.
Thericaly, we have 8 directions to consider: left, right, up, down, upleft, upright, downright, downleft.
By luck, multiplication is commutative; we don't have to seek in all the 8 directions, only half of it since right is equivalent to left, up to down etc.
The reduce set of scan we have to perform are only horizontal, vertical, direct diagonal (downright '\') and indirect diagonal (upright or '/') of the matrix. This is dividing the number of scans by two.
Now, considering the organization of the data matrix, one may notice a regular disposition of the element position (or indexes):
[[ 1 2 3 ... 18 19 20 ]
[ 21 22 23 ... 38 39 40 ]
[ 41 42 43 ... 58 59 60 ]
[ 61 62 63 ... 78 79 80 ]
[ ...
..400 ]]
This mean that horizontal scanning can be performed by increasing indexes by one, vertical scanning by increasing index by 20, direct diagonal scanning by increasing index of 21 or 19 for inderct diagobal.
Horizontal indexing vertical indexing diagonal \ indexing diagonal / indexing
[* 1* 2* 3* 4* 5 ... [* 1* 2 3 4 5 ... [* 1* 2 3 4 5 ... [ 1 2 3 *4* 5 ...
[ 21 22 23 24 25 ... [*21*22 23 24 25 ... [ 21*22*23 24 25 ... [ 21 22*23*24 25 ...
[ 41 42 43 44 45 ... [*41*42 43 44 45 ... [ 41 42*43*44 45 ... [ 41*42*43 44 45 ...
[ 61 62 63 64 65 ... [*61*62 63 64 65 ... [ 61 62 63*64*65 ... [*61*62 63 64 65 ...
0 +1 +1 +1 0 +20 +20 +20 0 +21 +21 +21 4 + 19 + 19 + 19
To minimize computation time, I paln to scan the entire data matrice only one time, from element 1 up to 400. At each step, the HP28S have to compute product of consecutive element in the four directions by playing with index increases from this INDEX table :
[[ 0 1 2 3 ] @ horizontal
[ 0 20 40 60 ] @ vertical
[ 0 21 42 63 ] @ diagonal \
[ 3 22 41 60 ]] @ diagonal /
'IND' STO
Please note that we don’t have to scan the full matrix since the last 3 lines and the 3 last columns are already involved in previous steps of the run. This reduce again the among of computation, only 72.25% of the matrix positions have to be consider.
This lead to the ‘quite’ brute force scan algorithm :
«
0 @ initialize max
0 16 FOR l @ scan line
1 17 FOR c @ scan column
1 4 FOR d @ scan directions
1 4 FOR j @ scan element in each direction
'DATA11'
20 l * c + @ index i of (l,c) position
'IND' @ index Table : (direction x jth element of fourproduct)
{ d j }
GET + @ get index offset and add it to index i of (l,c) position
GET @ get element from DATA11
NEXT
* * * @ product of the 4 extracted elements
MAX
NEXT
NEXT
NEXT
»
This code is a bit “crude”. It uses no elaborated strategy or sophisticate instruction, since HP28C/S have few appropriate commands for matrix manipulations.
By the less, any of you who have any idea or comment or any other strategy to optimize this problem on aged RPL is welcome.
