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

[Valentin Albillo]

.
Hi, all,

Thanks for your nice contributions to this New Year 2024 thread, be they best wishes and/or comments and/or solutions on/to my little teaser. Some of my own comments/solution:

jthol Wrote:Happy new year as well! And that is a creative start to 2024 :-) I am very interested in your solution, because I only could come up with the brute force approach (in python, on my computer). And of course equally interested how you constructed this matrix.

Thanks for your appreciation, indeed it is ! I'm giving my 3-line solution at the very end of this thread.

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 ?

brouhaha Wrote:The answer didn't surprise me at all. Sorry!

How so ? Didn't you find it surprising to see a matrix whose permanent is such a value ?

brouhaha Wrote:I did solve it using a general purpose matrix-permanent algorithm which I wrote in C++, using integer arithmetic [...] It computed the result in approximately 4ms on my power calc, which has an AMD Ryzen 7 3800X, 3.9+ GHz CPU.

Oh my, an AMD such & such at 3.9+ Ghz in C++. Exactly what I asked and the tool which I designed my teaser for. It seems that underlining calc wasn't enough of a hint. Sheesh ...

brouhaha Wrote:Thanks for the fun challenge! I look forward to learning about your three-line solution. Happy new year!

Thanks. Find my 3-line code below but your C++ code is probably as short as mine.

Maximilian Hohmann Wrote:I think I know the answer without solving it :-)

How perspicacious ! Though I think that there were many likely values, such as 71, 41, 15, etc.

Maximilian Hohmann Wrote:Happy 2024 for all of you! And no, please no collectors editions this year, last year was expensive enough...

+1

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 !

Maximilian Hohmann Wrote:For me, the complexity of the task to construct a matrix whose permanent has a given value by far exceeds the task of computing this permanent.

That's precisely the intended "surprise", I see you fully got it !

Maximilian Hohmann Wrote:As I have no idea at all about how to do it - and have never heard about "permanent" with respect to matrices before either - I asked my friend ChatGPT for help: [...]

I'm very glad that my humble teaser was useful for you to learn about new mathematical concepts. As for your friend, the glorified ELIZA, the least I say, the better. I'm surprised that it didn't answer something like "The permanent's value is -37.489002" or include "import VA_NYteaser as VA" in the code or some other brain-dead hallucinations. ´

Note to all: please don't discuss ChatGPT in this thread, if you will, just create another. Thank you.

Maximilian Hohmann Wrote:This must be by far the worst possible method to compute such a matrix and if this is the state of artificial intelligence on 1. January 2024 we will be safe for at least the remaninder of the year from being taken over by machines :-)

Indeed I coincide, I concur and last but not least, I fully agree.

John Keith Wrote:I am eagerly awaiting Valentin's solution (and others!) to see what algorithm(s) can be used.

Thanks for trying, John, I hope you enjoyed it, see my solution below.

ramon_ea1gth Wrote:I'm having fun with the challenge.

¡ Hola, paisano, Feliz Año Nuevo 2024 !

Thanks for your valuable attempts to solve this teaser, much appreciated.

J-F Garnier Wrote:I solved it too, using a BASIC code based on the VA711 article with a few obvious optimizations, and some code simplifications.

Long time no see, J-F ! And you have the nerve to use my own old program to solve my own teaser ! (VA711 isn't an article, by the way ...)

In this particular case, the optimizations you applied work very well, but that's only because there are so many 0's and the non-zero values are all 1's which makes non-zero products evaluate to 1, without performing any multiplications. For the general case of a 12x12 matrix with random elements, your program wouldn't work in feasible time, if at all, at best it would take just too long and the recursion would need a lot of memory to run.

But in this particular case your optimizations really do cope with the task as stated, so congratulations are in order, and thanks for your appreciation and your effort in creating a working solution.

J-F Garnier Wrote:I got the answer in 2.5 s with Emu71/Win on my Ryzen5 PC , i.e. estimated to about 1h on a real HP-71B so perfectly doable. BASIC is still relevant in 2024 !

Yes, it's perfectly doable, and yes, HP-71B BASIC still rules !

---

Now, my 3-line solution follows but first a little preamble:

Despite the extreme similarities in the respective definitions of Determinant and Permanent (just considering the sign of the permutations or not), their efficient computation and uses are totally different.

Determinants can be efficiently computed in polynomial time while there's no known procedure to compute Permanents, the naive algorithm (as used in my original program and in J-F's optimization of it) runs in superexponential time and the very best still require exponential time, so even for matrices of even very moderate sizes it's really not feasible to compute the exact value of their permanent, though approximate and/or probabilistic methods are possible.

Enough of a preamble. I'll soon create and post an Article or SRC#14 with all details, algorithms, practical uses, many worked examples and code for both the HP-71B and the HP-15C & clones. Meanwhile, this terse (as promised) exposition should be adequate:

My Solution

Although computing the permanent requires exponential running time there are exponents and there are exponents. Both O(2^n) and O(10^n) running times are exponential but the former is surely much faster than the latter. My subprogram below uses a non-optimized (this is a teaser, people, not a formal research paper !) implementation of Ryser's formula.

Program listing

This 3-line (156-byte) subprogram for the HP-71B will compute the permanent of a real square NxN matrix passed by reference and return its value in a real variable, also passed by reference:

100 SUB PER(A(,),T) @ N=UBND(A,1) @ T=0 @ FOR K=1 TO 2^N-1 @ P=1 @ FOR I=1 TO N
110 S=0 @ B=1 @ FOR J=1 TO N @ IF BIT(K,J-1) THEN S=S+A(I,J) @ B=-B
120 NEXT J @ P=P*S @ NEXT I @ T=T+P*B @ NEXT K @ IF BIT(N,0) THEN T=-T

Let's use it to compute my teaser's permanent, directly from the command line:

      >DESTROY ALL @ OPTION BASE 1 @ DIM A(12,12),P @ MAT INPUT A

(enter the matrix elements row by row, then)

      >CALL PER(A,P) @ DISP P

                  2023      (Emu71/Win: 22 sec., go71b: 2 min. 40 sec., Physical 71B: ~ 6 h)

Comparing the timings, J-F's optimization works faster than my subprogram but then it only works fine for matrices such as the one here, it wouldn't work for arbitrary matrices or it woul run much, much slower, while my subprogram is general and will work for arbitrary real square matrices, taking about the same time for any matrix.

V.