Happy New Year 2024 ... and 2023's last teaser !

[3298]

(01-03-2024 12:56 AM)Valentin Albillo Wrote:  

3298 Wrote:Solved it without even bothering to fetch and unpack a calc. Hint: Boolean logic and tracing diagonals through the matrix with a finger was enough. Happy new year anyway!

Anyway ? You posted neither code nor the logic process nor the value of the permanent. That's terseness indeed. Is this the way you usually use to tackle teasers ?

It is when I'm afraid of spoiling the challenge for others. For instance, in the (online version of the) HHC contests I generally submit program size and checksum only (and maybe a cryptic hint), withholding the code and proper explanation until after the deadline is over.
However, this time I misunderstood the challenge, so i "solved" something that was far easier than the actual challenge, enabling me to do so without a calculator. In my defense, I never needed to calculate the determinant of a matrix larger than 3x3 by hand, so I failed to realize that the rule of thumb I remembered from my school days will not work beyond this size. Based on that I ended up with a 0 result, which surprised me only in the way that your previous challenges usually resulted in the number naming the old or the new year. It seemed like the obvious answer otherwise ... again, due to my flawed understanding.

It kind of felt too easy for one of your challenges, almost boring actually. (That's what prompted the "anyway" part of my post...) It should have made me realize that I got something wrong. I feel stupid now.

On a slightly more serious note, the RPL code looks clearer to me than your Basic code. The names of the RPL commands called throughout are a better documentation than trying to trace what each Basic variable is subjected to. But I'm RPL-trained, which allows me to see stackrobatics as necessary but uninteresting fluff, much like variable assignments in a C-derived language. Readability is subjective.

[Gerson W. Barbosa]

(01-03-2024 12:56 AM)Valentin Albillo Wrote:  

Gerson W. Barbosa Wrote:Happy New Year You All! This should work only for 2x2 and 3x3 matrices, so not quite relevant for that particular problem [...]

Thanks for your wishes and for the code ... though I don't understand most of it, at all, but that's my bad, not yours ... (I think). Nice to see that RPL's legendary unfathomability remains as strong in 2024 as ever !

Hi, Valentín,

There’s a mistake in my program. I’ve used RANK when all I need with the order of the matrix. As a result it was taking longer that it needed to for a 3x3 matrix (0.81 seconds instead of 0.23 seconds). This is better:

Code:


« DUP →DIAG NEG DUP AXL ΠLIST 
UNROT DUP SIZE HEAD UNROT 
PICK3 DIAG→ + LASTARG NIP + 
DET ROT DUP + - -1 ROT OVER + ^ *
»

Not any more readable than the previous version though.
It’s based on a little formula I came up with.
Thanks for this teaser, even if I wasn’t up to the task. Until then I didn’t know there was something like the permanent of a matrix.

Best regards,

Gerson.

———————

Per(M) = Det(M’) - 2p

where

M’ is M with elements of the main diagonal multiplied by -1

and

p is the product of the elements of the main diagonal of M’.

This works for order 3 matrices. For order 2 matrices the sign of the result must be changed.

For example,

M:
[[ -1 3 2 ]
[ 7 -4 5 ]
[ 6 8 9 ]]

M’:
[[ 1 3 2 ]
[ 7 4 5 ]
[ 6 8 -9 ]]

Det(M’) = 267

p = 1×4×(-9) = -36

Per(M) = 267 - 2×(-36) = 339

[Ajaja]

There are many rows and columns with zeros. I think, the fastest way to calculate permanent of the matrix is to sort it first, then transpose, sort again and after that use J-F Garnier optimized subprogram. It turns this 12x12 permanent into sum of 8 9x9 permanents if I'm not mistaken.
And result should be the same:

Code:


    |\^/|     Maple 7 (IBM INTEL NT)
._|\|   |/|_. Copyright (c) 2001 by Waterloo Maple Inc.
 \  MAPLE  /  All rights reserved. Maple is a registered trademark of
 <____ ____>  Waterloo Maple Inc.
      |       Type ? for help.
> with(LinearAlgebra):
> Permanent(<
> <0,0,0,0,0,1,1,1,1,1,1,1>|
> <0,0,0,0,1,0,0,0,0,0,0,1>|
> <0,0,0,0,1,0,0,0,0,0,1,1>|
> <0,0,0,0,1,0,0,0,0,1,1,1>|
> <0,0,0,0,1,0,0,0,1,1,1,1>|
> <0,0,0,0,1,0,0,1,1,1,1,1>|
> <0,0,0,0,1,0,1,1,1,1,1,1>|
> <0,0,0,1,0,1,1,1,1,1,1,1>|
> <0,0,1,1,1,1,1,1,1,1,1,1>|
> <0,1,1,1,1,1,1,1,1,1,1,1>|
> <1,1,1,1,0,1,1,1,1,1,1,1>|
> <1,1,1,1,1,1,1,1,1,1,1,1>>);
                                                         2023

[John Keith]

(01-03-2024 12:17 PM)Gerson W. Barbosa Wrote:  Per(M) = Det(M’) - 2p

where

M’ is M with elements of the main diagonal multiplied by -1

and

p is the product of the elements of the main diagonal of M’.

This works for order 3 matrices. For order 2 matrices the sign of the result must be changed.

For example,

M:
[[ -1 3 2 ]
[ 7 -4 5 ]
[ 6 8 9 ]]

M’:
[[ 1 3 2 ]
[ 7 4 5 ]
[ 6 8 -9 ]]

Det(M’) = 267

p = 1×4×(-9) = -36

Per(M) = 267 - 2×(-36) = 339

That is quite interesting. In my (obsolete) program, I compute the 3 x 3 permanent with inline code as follows, requiring 9 multiplications and 5 additions.

Code:


        OBJ\-> DROP                            @ Explode matrix onto stack
        5. PICK OVER * PICK3 6. PICK * +
        9. ROLLD 6. PICK * PICK3 5. ROLL * +
        6. ROLLD 4. ROLL * UNROT * + *
        UNROT * + UNROT * +                    @ 3 * 3 permanent

This may be faster than using DET.

[Gerson W. Barbosa]

(01-03-2024 02:59 PM)John Keith Wrote:  

(01-03-2024 12:17 PM)Gerson W. Barbosa Wrote:  Per(M) = Det(M’) - 2p

where

M’ is M with elements of the main diagonal multiplied by -1

and

p is the product of the elements of the main diagonal of M’.

This works for order 3 matrices. For order 2 matrices the sign of the result must be changed.

For example,

M:
[[ -1 3 2 ]
[ 7 -4 5 ]
[ 6 8 9 ]]

M’:
[[ 1 3 2 ]
[ 7 4 5 ]
[ 6 8 -9 ]]

Det(M’) = 267

p = 1×4×(-9) = -36

Per(M) = 267 - 2×(-36) = 339

That is quite interesting. In my (obsolete) program, I compute the 3 x 3 permanent with inline code as follows, requiring 9 multiplications and 5 additions.

Code:


        OBJ\-> DROP                            @ Explode matrix onto stack
        5. PICK OVER * PICK3 6. PICK * +
        9. ROLLD 6. PICK * PICK3 5. ROLL * +
        6. ROLLD 4. ROLL * UNROT * + *
        UNROT * + UNROT * +                    @ 3 * 3 permanent

This may be faster than using DET.

You’re definitely right! Actually about 4.5 times as fast. Size is the only advantage here (67 bytes versus 100 bytes).

Code:


« DUP →DIAG NEG DUP 
AXL ΠLIST UNROT 3. 
DIAG→ + LASTARG NIP + 
DET SWAP DUP + -
»

[ramon_ea1gth]

(01-03-2024 12:56 AM)Valentin Albillo Wrote:  ¡ Hola, paisano, Feliz Año Nuevo 2024 !
Thanks for your valuable attempts to solve this teaser, much appreciated.

¡Hola Valentín!
I have to refrain tackling your challenges. They are addictive! Even after finishing I was back revising my, anyway, suboptimal code, realising that I can save more operations with binary matrix values.
It was a good excuse to think and read further from your hints: now I also find challenging how to prepare the matrix with the predefined result.
¡Feliz Año Nuevo también!

[J-F Garnier]

(01-03-2024 12:51 PM)Ajaja Wrote:  There are many rows and columns with zeros. I think, the fastest way to calculate permanent of the matrix is to sort it first, then transpose, sort again and after that use J-F Garnier optimized subprogram.

If you look closely at my solution, you will see that I sorted the array rows by the number of 1 in each row, not by the value of the binary representation:

20 DATA 0,0,1,0,0,0,0,0,0,1,0,0
21 DATA 0,0,1,0,0,0,0,0,0,1,0,1
22 DATA 0,0,1,1,0,0,0,0,0,1,0,1
23 DATA 0,0,1,1,0,0,0,0,0,1,1,1
24 DATA 1,0,1,1,0,0,0,0,0,1,1,1
25 DATA 1,0,1,1,0,0,0,1,0,1,1,1
26 DATA 1,0,1,1,1,0,0,1,0,1,1,1
27 DATA 0,1,0,1,1,1,1,1,1,1,0,1
28 DATA 1,0,1,1,1,0,1,1,0,1,1,1
29 DATA 1,0,1,1,1,0,1,1,1,1,1,1
30 DATA 1,0,1,1,1,1,1,1,1,1,1,1
31 DATA 1,1,1,1,1,1,1,1,1,1,1,1

This was the most important part of my 'optimization'. The other one was to consequently skip the minor calculation for the zero elements:

135 IF A(1,K)=0 THEN 145 ! little optimization

In that way, the recursive tree was reduced to 2 paths at each level instead of 11 (up to row 8), mostly important for the first recursive steps to cut calculation time.
I did notice the structure of the sorted array and the exception of row 8 (of the sorted array), but without paying too much attention to it.
I was quite happy to get a solution in HP BASIC in a sensible time, even on a machine as slow as the 71B.

Of course, as Valentin pointed out, this solution is only effective for this case with this special array structure.

J-F

[Gjermund Skailand]

Update/Small speed improvement
Here is a sys-RPL implementation of Valentin's code for a general matrix computation of permanent :
Compiles to 255.5 bytes, chksum #917Dh
On my HP50g it solves the 12x12 matrix in slightly less than 13,5 minutes.

calculations can be aborted by pushing ON/cancel

Code:


:: 
  CH1NOLASTWD
  CK&DISPATCH2
  #4
  ::
    FPTR2 ^CKNUMARRY                          ( Ensure numeric array )
    DUP FPTR2 ^MDIMS ?SKIP #0             ( 2 dimensions square matrix )
    OVER #<>case FPTR2 ^ErrBadDim      ( give error message if not )
    #0 #0 %0 %0 %0 %0
    {{ P B S T IN K N }}                          ( declare local variables )
    #1 SWAP                                          ( stack: Matrix, bit_index )
    %2 N UNCOERCE %^ COERCE           ( calculate 2^N)
    ONE_DO                                           ( for k )
      INDEX@ !K                                      ( make k easily accessible as K )
      %1 !P
      #0 !IN                                             
      N #1+_ONE_DO                                ( for I=1 to n )
        %0 !S
        TRUE !B
        #1 ROTDROPSWAP                            ( update bit_index )
        n #1+_ONE_DO                                (for j=1 to n )
          K 3PICK #AND #0<> IT                   ( if k AND j )
          :: 
            IN INDEX@ #+ PULLREALEL          ( A[i,j] )
            S %+ !S                                       ( s = s + A[i,j ] )
            B NOT !B                                    ( b = -b )
          ;
          SWAP #2* SWAP                              (update bit index used in the AND clause)
        LOOP                                               ( next j)
        P S %* !P                                          ( p = p*s)
        IN N #+ !IN                                       ( update i*n )
      LOOP                                                  ( next i )
      P B ?SKIP %CHS  T  %+ !T                      ( t = p*b + t )
      ?ATTNQUIT                                            ( abort if ON/cancel is pressed)
    LOOP
    2DROP
    T
    N #1 #AND #1= IT %CHS                      (if n AND 1 change sign )
    ABND
  ;
;
@

Updated formatting
best regards
Gjermund

[Gjermund Skailand]

How do I avoid that space indenting is not stripped away??)

[Didier Lachieze]

(01-05-2024 10:12 AM)Gjermund Skailand Wrote:  How do I avoid that space indenting is not stripped away??)

By using the code tags (the # in the message editor toolbar).

[Gjermund Skailand]

Thanks, Didier

I was curious to test the real speed of hp50g, running hpgcc3 code at 120MHz, so I ported to a hpgcc3 program, 1084bytes, program and code, enclosed.
This program calculates the 12x12 matrix in less than 1 sec.
It calculates permanents up size {15,15} in about 4 sec.
It requires a modified rom to run this, but if anyone is interested, let me know.
PS anyone got timings on other calculators?

best regards
Gjermund