HP Forums

I have a 48GX, bought Not Working and revived by Randy Sloyer. I am using Project Euler to help me learn to use it, purely for fun; I have no practical application in mind.

Project Euler Problem 11 seeks the largest product of four adjacent integers in a 20 x 20 matrix. I solved it by compiling a list of the maximum such products for each row, column, and diagonal and then using RNRM to extract the greatest of those.

Can anyone suggest smarter ways to solve the problem, and/or applicable commands more sophisticated than those required to extract rows, columns, and diagonals?

Hi,

I solved it like this (with the 50G). My solution is quick & dirty and not very smart. I am not sure it's pefect but it gave the good answer. I remember now i was lucky to find the solution without testing others diagonals (just few lines to add). The first try was the good one so i stopped here.

How do you do with RNRM ?

EDIT : "I solved it by compiling a list of the maximum such products for each row, column, and diagonal and then using RNRM to extract the greatest of those."

To find the greatest value (num, alpha ...) in a list , you can also do :

<< MAX >> STREAM

«

{

{ 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 }

{ etc...}

}

0 0

  -> t t2 m

  «

    t AXL 't2' STO

    @ Diag 1

    « n '61+(n-4)*20' EVAL 2 ->LIST » 'n' 4 20 1 SEQ 

    1

     « 

       « 't2' n GET » 'n' ROT LIST-> DROP 19 SEQ

     »

    DOSUBS

    t + t AXL TRAN AXL +

    1 

      « 

        4 « * * * DUP m < « DROP » « 'm' STO » IFTE » DOSUBS

      » 

    DOSUBS

    m

  »

»

Edited: 7 July 2011, 4:13 a.m.

Hello Gilles,

And thanks for the helpful reply.

You say,

"To find the greatest value (num, alpha ...) in a list , you can also do :

<< MAX >> STREAM"

That's clearly the best way; thanks for pointing out the MAX/STREAM combination and for showing me the format that makes it work. They're both valuable lessons, and just what I hoped for when I posted this.

To use RNRM I had to turn the list into an array with OBJ-> ->ARRY, a waste of time.

I used ->DIAG to extract the diagonals, successively paring away rows or columns of the matrix to expose successive diagonals. I thought that that was efficient; is there a better way?

To extract the oppositely directed diagonals, I extracted all the columns, made them a list, used REVLIST to reverse them, and reconstituted the matrix. Then I could use ->DIAG as before. Is there a better way to do that? Would a loop to swap symmetrically located pairs of matrix columns be better, for example?

Unfortunately, I am a very poor reader of RPL, so I can't appreciate any additional lessons contained in your code.

All the best,

Peter

Nice code, Gilles! (As always...)

I skipped this problem when I worked through the first PE problems because it just seemed tedious and unrewarding...

Peter's mention of \->DIAG instilled some curiosity and glimpse of a possible elegant solution.
The command was missing in ND1, so I went ahead and implemented it, along with a couple more.

Here's the RPL+ result:

<< #11_data =m

   0 @ max product kept on stack

   m

   m transpose concat

   m diagonals concat

   m flip diagonals concat

   1

   << 4 [ * * * MAX ] DOSUBS >>

   DOSUBS

>>

The new command "diagonals" returns a matrix of the diagonals of a given matrix, and "flip" mirrors a matrix horizontally.

(MorphEngine commands outside the 50g command set are in small letters, for easier typing on a mobile device.)

The running max product is maintained on the stack, and I believe that should also be applicable to your solution, and maybe speed things up somewhat. (It does make the code smaller.)

The solution thread to this problem reveals there were no clever solutions. Everyone brute-forced it and many guessed the right numbers. The solutions in "J" are concise but (to me) not exactly readable.

Oh, in RPL+, lists and vectors are unified. Hence no need for conversions back and fro.

(Peter: Gilles AXL command does conversion, too. Your OBJ\-> \->ARRAY conversion isn't redundant. AXL is just the nicer 50g syntax to accomplish the same.)

Hello !

You wrote :

"I had to turn the list into an array with OBJ-> ->ARRY, a waste of time."

AXL do the job and toggle list <-> matrice :

{ 1 2 3 } AXL -> [ 1 2 3 ]

[ 1 2 3 ] AXL -> { 1 2 3 }

It's very quick (but i've a doubt. perhaps it's a new 49/50 command)

About ->DIAG, as I understand it returns only the larger diagonal...

"Would a loop to swap symmetrically located pairs of matrix columns be better, for example?"

Have you try the TRAN command ?

TRAN
Type: Command
Description: Transpose Matrix Command: Returns the transpose of a matrix.

(not sure it works on a 48...)

Generaly, you can avoid using loops for list processing with DOLIST and DOSUBS commands

Edited: 7 July 2011, 6:44 p.m.

If TRAN doesn't exist, TRN will (this one's been around since the 28C), which does the same for real matrices.

DOSUBS is so worth learning... it's the swiss army knife of list processing.

Hi !

Oliver Unter Ecker wrote :

"The running max product is maintained on the stack, and I believe that should also be applicable to your solution, and maybe speed things up somewhat. (It does make the code smaller.)"

Very fine ! It works ;)
For better comprehension, here a version without diagonal :

«

0

{

{ 08 02 22 97 etc ...........

}

DUP AXL TRAN AXL +

 1 

  « 

   4 « * * * MAX » DOSUBS

  » 

 DOSUBS 

»

I don't like at all my diagonals solution ;)
But i've a new idea to test ....

Edited: 8 July 2011, 1:49 a.m.

Bonjour Gilles,

->DIAG indeed returns a vector that contains the major diagonal elements of a matrix. But the input matrix does not have to be square.

So if I lop off the leftmost column (or the topmost row) of a 20 x 20 matrix, ->DIAG will return a vector containing 19 elements; lop off another column (or another row) and get a vector containing 18 elements. etc. COL- or ROW- do the surgery.

Thus I get all 33 diagonals of the principal orientation.

I had hoped that taking the transpose of the matrix would allow me to get the oppositely oriented diagonals, but it does not; TRN swaps column 1 with row 1, column 2 with row 2, ..., column 20 with row 20, but it leaves those diagonals in the same orientation.

Swapping columns 1 and 20, columns 2 and 19, ..., and columns10 and 11 does the trick, however. That's where I chose to extract the columns as a list, reverse the list, and reconstitute the matrix; a loop seemed to be the only other way to do the swapping.

Thanks very much for suggesting DOLIST and DOSUBS as a better alternative.

Add those to MAX and STREAM, you've enlarged my vocabulary by four comands. Now I must learn how to use them!

All the best,

Peter

Here is new idea to tests the 2 diagonals:

«

 0               @ Initialise maximun 

 {

  { 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 etc ..... 20x20 list

 }

 DUP             @ Horizontal

 AXL TRAN AXL    @ Vertical

 OVER            @ For Diagonales 1 & 2 

 1

  «

    « 0 » 'n' 1.  NSUB 1. SEQ 

    « 0 » 'n' 1. 21. NSUB - 1. SEQ 

    2. PICK 4. PICK + OVER +          @ Diag 1

    2. ROLL 4. ROLL + ROT +           @ Diag 2

    +

  »

 DOSUBS

 AXL TRAN AXL

 + +              @ Add horiz. + vert. + diago.

 1 

  « 4 « * * * MAX » DOSUBS »

 DOSUBS 

»

Edited: 10 July 2011, 3:01 p.m.

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, up-left, up-right, down-right, down-left.
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 (down-right '\') and indirect diagonal (up-right 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 j-th element of four-product)  

              { 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

»

Bonjour C.Ret !

I like your sense of bytes economy and optimisation :D I like the idea of a index table.

But is there a problem here ? : it seems to me your algo don't test horizontal & vertical products for the lines 18 to 20 ?

Edited: 11 July 2011, 7:01 a.m.

Bonjour Gilles

You are right! My code miss to check any horizontal products from line 18 to 20 as well as any vertical products from column 17 to 20 !
This makes two gross errors!
Lucky I am than the greatest four elements product was not in the edge of the data matrix!

I have to correct my code by using a more ‘complex’ approach!
In fact, my second attempt seems not to be so complex, it’s only using a complex INDex matrix instead of the too loosely mono-dimensional indexing of first attempt.

As testing if line, row (l,c) element are in the correct interval is too much code and tests, I propose to short-cut all these tests by using the IFERR THEN END structure. Any attempt to get an element out of the matrix bound will be detected and trapped.

[[ 

       ... 20 x 20 ...

 [                         ]]

'DATA11' STO

[[ (0,0) (1,0) (2,0) (3,0) ]

 [ (0,0) (0,1) (0,2) (0,3) ]

 [ (0,0) (1,1) (2,2) (3,3) ]

 [ (0,3) (1,2) (2,1) (3,0) ]]

'IND'

As in previous version IND is the table of offsets, but using complex (x,y) coordinate for line/column offset values.

«

  0                              @ initialize max

  1 20 FOR l                     @ scan ALL lines

     1 20 FOR c                  @ scan ALL columns

        1 4 FOR d                @ scan ALL directions

           1 4 FOR j             @ scan 4 elements in each direction

               'DATA11'

                 l c R->C        @ (l,c) position  into complex number

                'IND'            @ complex index Table 

              { d j }

                      GET +      @ get index offset (x,y) and add it to index i of (l,c) position

              C->R 2 ->LIST      @ convert (l+x,c+y) complex position index into list index { l+x c+y }

                IFERR

                            GET  @ try getting (l+x,c+y) element from DATA11

                THEN             

                        DROP2 0  @ if error (out of matrix bound, return 0 )

                END

           NEXT                 

           * * *                 @ product of the 4 extracted elements

           MAX 

        NEXT

     NEXT

   NEXT

»

Thank you for your attentive readings !

Hi,

another way would be to add 3 lines and columns fill with 0 and use your first version just changing the loop values

Yes, you are right again.

Extending the matrix and padding the matrix with 0 makes it !

But, why padding with 0, why not with 1 ? Supposing we have en matrix full of low numbers (i.e. less than 20), and suppose that the greatest products appears to be at one borders with only 2 or 3 elements (supposing that only border's element are great numbers!

Perhaps, I may change my last version by returning 1 instead of 0 ?

Another question is whenever or not is it needed to take this border effect into consideration?
I have notice that may first version don't scan the end-border regions (last three columns or rows) of the data matrix only after your notice it !
Fortunately, the greatest four element product is not in one of these regions, so even the erroneous first version of my code is able to found the expected result.

That's the problem with Euler, of few of us may get the expected answer by using an erroneous algorithm or a buggy code!