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

12312023, 05:00 PM
Post: #1




Happy New Year 2024 ... and 2023's last teaser !
.
Hi, all, Happy New Year 2024 to all of you but before 2023 truly elapses, this fateful year which brought us the awesome HP15C CE, let's amazinggrace it with a final teaser for those of you who would accept it. Very succinctly, concisely and even tersely:
and the teaser is that you use the new Christmas toy calc you got last Dec, 25th (or any other, for that matter) to obtain the permanent of this nice little matrix I just lovingly concocted specially for you. The result is sure to surprise you !  1 0 1 1 1 0 1 1 1 1 1 1   0 0 1 1 0 0 0 0 0 1 0 1   1 0 1 1 0 0 0 1 0 1 1 1   0 0 1 0 0 0 0 0 0 1 0 0   1 0 1 1 1 1 1 1 1 1 1 1   0 0 1 1 0 0 0 0 0 1 1 1   1 0 1 1 1 0 0 1 0 1 1 1   0 1 0 1 1 1 1 1 1 1 0 1   1 0 1 1 0 0 0 0 0 1 1 1   1 1 1 1 1 1 1 1 1 1 1 1   0 0 1 0 0 0 0 0 0 1 0 1   1 0 1 1 1 0 1 1 0 1 1 1  Best regards and, again, Happy New Year 2024 ! V. All My Articles & other Materials here: Valentin Albillo's HP Collection 

12312023, 07:24 PM
Post: #2




RE: Happy New Year 2024 ... and 2023's last teaser !
Happy New Year, Valentin! And Happy New Year, MoHPC members!


12312023, 08:11 PM
(This post was last modified: 12312023 08:16 PM by Jlouis.)
Post: #3




RE: Happy New Year 2024 ... and 2023's last teaser !
Happy New Year to you all!
Let 2024 brings much more Collectors Editions! Peace, love, Live long and Prosper! All the best JL 

12312023, 08:54 PM
(This post was last modified: 01012024 10:38 AM by Peter Klein.)
Post: #4




RE: Happy New Year 2024 ... and 2023's last teaser !
Happy New Year, all! May all your equations be solvable, whether in RPN, or in life.


01012024, 09:05 AM
Post: #5




RE: Happy New Year 2024 ... and 2023's last teaser !
Happy New Year!
Thanks for the teaser Valentin... from what I read, the permanent is expensive to compute... but then, you are not suggesting your program ran in a short time, only that it is a short program. I was almost tempted to compute this one by hand, but realised I'd misunderstood the definition. 

01012024, 10:02 AM
(This post was last modified: 01052024 08:18 AM by jthole.)
Post: #6




RE: Happy New Year 2024 ... and 2023's last teaser !
Happy new year as well! And that is a creative end to 2023 :)
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. 11C, 12C, 17Bii, DM42 

01012024, 11:49 AM
Post: #7




RE: Happy New Year 2024 ... and 2023's last teaser !
Happy new year and thank you for the little challenge!
Wikis are great, Contribute :) 

01012024, 01:13 PM
Post: #8




RE: Happy New Year 2024 ... and 2023's last teaser !
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! 

01012024, 01:27 PM
(This post was last modified: 01012024 06:46 PM by brouhaha.)
Post: #9




RE: Happy New Year 2024 ... and 2023's last teaser !
(12312023 05:00 PM)Valentin Albillo Wrote: The result is sure to surprise you ! The answer didn't surprise me at all. Sorry! :) Quote:Admittedly this teaser is only for power calc users so don't feel too bad if you're not up to the task (I only needed 3 lines of code for my 4decades old toy.) I'm not nearly clever enough to see how to solve it in three lines of code, but I did solve it using a general purpose matrixpermanent algorithm which I wrote in C++, using integer arithmetic. (It could easily use floating point if necesary, and that might actually be faster.). It computed the result in approximately 4ms on my power calc, which has an AMD Ryzen 7 3800X, 3.9+ GHz CPU. I briefly thought about also writing a 15C program, but the algorithm takes 2^(n1) * n^2 operations. With the algorithm I used, I think it would be faster to compute it using a 16C. Thanks for the fun challenge! I look forward to learning about your threeline solution. Happy new year! 

01012024, 01:43 PM
Post: #10




RE: Happy New Year 2024 ... and 2023's last teaser !  
01012024, 02:24 PM
Post: #11




RE: Happy New Year 2024 ... and 2023's last teaser !  
01012024, 06:34 PM
Post: #12




RE: Happy New Year 2024 ... and 2023's last teaser !
Happy New Year You All!
This should work only for 2x2 and 3x3 matrices, so not quite relevant for that particular problem. Anyway, FWIW, Code:
( HP49G, G+ and HP 50g) 

01012024, 08:29 PM
(This post was last modified: 01012024 08:47 PM by Maximilian Hohmann.)
Post: #13




RE: Happy New Year 2024 ... and 2023's last teaser !
Hello!
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. 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: You: "Can you please compute a 12x12 matrix whose permanent is xxxx using only 0 and 1 as values" ChatGTP: "Generating a specific 12x12 matrix with a permanent of xxxx using only 0 and 1 values involves finding an arrangement of elements such that their product sums up to xxxx when considering all possible permutations. The direct calculation of such a matrix might require a lot of computational effort due to the factorial complexity involved. Let's try a Python script to generate a 12x12 matrix with 0 and 1 values and check its permanent. Note that this approach might not guarantee a solution due to the complexity and exhaustive search required: Code:
This Python script attempts to generate random 12x12 matrices consisting of 0s and 1s and calculates their permanents. It continues the process until it finds a matrix whose permanent matches the specified value (xxxx in this case). However, due to the exhaustive search nature of this approach, it might take an extensive amount of time or might not find a suitable matrix within a reasonable timeframe. If you have specific constraints or additional information that can be used to narrow down the search space, it might help in devising a more targeted approach to finding such a matrix. < end of ChatGPT answer 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 :) Regads May 

01012024, 10:21 PM
Post: #14




RE: Happy New Year 2024 ... and 2023's last teaser !
Happy new year everyone!
My permanent program fails miserably for this challenge It will not work for any matrix larger than 9 x 9. I am eagerly awaiting Valentin's solution (and others!) to see what algorithm(s) can be used. 

01022024, 09:20 AM
(This post was last modified: 01022024 12:02 PM by EdS2.)
Post: #15




RE: Happy New Year 2024 ... and 2023's last teaser !
By erbeqrevat ebjf naq pbyhzaf jr pna frr this matrix unf n fcrpvny sbez. It wouldn't surprise me (having looked at it just a little) to find gung bar bs gur ebjf (be pbyhzaf) vf n ovanel rapbqvat bs gur qrfverq answer.
Edit: applied a bit of rot13 to avoid very mild spoilers 

01022024, 10:53 AM
(This post was last modified: 01042024 09:47 AM by ramon_ea1gth.)
Post: #16




RE: Happy New Year 2024 ... and 2023's last teaser !
I'm having fun with the challenge. After programming a cute RPL recursive program in my HP 50g to manage matrices/permanents and realise, as said in other posts, that the required calculations grow insanely, now I'll try the binary way, base2 approach, with shifting registers, but with the usual base10 numbers. Let's see
Edit: I'm testing this binary shifting approach to obtain the cofactors. A 5x5 matrix full of ones takes about 25 seconds to compute in my HP 50g. With zeroes, the code saves operations. Thus, I will let the calculator work overnigth and let's see if I get something in the morning (I started a TICKS command so I can measure the elapsed time). I know, I know: if I were serious I should have tried to make an estimation of the required time for the algorithm Edit 2: I got it! (after about 11 hours computing!). At least, after such a long calculation, the result is the expected I'll write my code later here, just as a curiosity, though it's not the most efficient solution. Edit 3: And this is my version of PERMANT. It takes two arguments from the stack:
Code:
Code:
And the previous code even more optimised for binary matrices: Code:
With the optimised code, computing time is 9 hours in a physical HP 50g, instead of the previous 11 hours. Ramón Valladolid, Spain TI50, Casio fx180P, HP48GX, HP50g, HP Prime G2 

01022024, 12:53 PM
(This post was last modified: 01022024 01:05 PM by JF Garnier.)
Post: #17




RE: Happy New Year 2024 ... and 2023's last teaser !
(01012024 01:27 PM)brouhaha Wrote: ... I did solve it using a general purpose matrixpermanent algorithm which I wrote in C++, using integer arithmetic. (It could easily use floating point if necesary, and that might actually be faster.). It computed the result in approximately 4ms on my power calc, which has an AMD Ryzen 7 3800X, 3.9+ GHz CPU. I solved it too, using a BASIC code based on the VA711 article with a few obvious optimizations, and some code simplifications. I got the answer in 2.5 s with Emu71/Win on my Ryzen5 PC , i.e. estimated to about 1h on a real HP71B so perfectly doable. BASIC is still relevant in 2024 ! Code: 1 ! VA2023 

01032024, 12:56 AM
(This post was last modified: 01032024 02:23 AM by Valentin Albillo.)
Post: #18




RE: Happy New Year 2024 ... and 2023's last teaser !
.
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 3line 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 matrixpermanent 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 threeline solution. Happy new year! Thanks. Find my 3line 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 braindead 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. JF 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, JF ! 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 nonzero values are all 1's which makes nonzero 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. JF 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 HP71B so perfectly doable. BASIC is still relevant in 2024 ! Yes, it's perfectly doable, and yes, HP71B BASIC still rules ! Now, my 3line 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 JF'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 HP71B and the HP15C & 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 nonoptimized (this is a teaser, people, not a formal research paper !) implementation of Ryser's formula. Program listing This 3line (156byte) subprogram for the HP71B 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:
110 S=0 @ B=1 @ FOR J=1 TO N @ IF BIT(K,J1) 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 >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, JF'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. All My Articles & other Materials here: Valentin Albillo's HP Collection 

01032024, 07:14 AM
Post: #19




RE: Happy New Year 2024 ... and 2023's last teaser !
Wait wait … so my algorithm gave the proper solution after all! (2023).
I assumed that I had overlooked a tiny detail, and it should have been 2024. Thanks for posting your program; I don’t have a 71B (with or without math module), but I will certainly study your short algorithm. I am looking forward to your article :) 11C, 12C, 17Bii, DM42 

01032024, 10:59 AM
Post: #20




RE: Happy New Year 2024 ... and 2023's last teaser !
Hello!
(01032024 12:56 AM)Valentin Albillo Wrote: .... implementation of Ryser's formula. ... I have come across that one when I looked for "permanent" and even tried it out with python (which is really not my favorite programming language...) on my Mac. For me is interesting that something seemingly trivial as the permanent has not yet inspired some mathematical genius to come up with a computerfriendly method of calculation. Perhaps because there is so little practical use for the permanent? Anyway, I still wonder how you constructed that matrix! Regards Max 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)