Tripartite Palindromic Partition of Integer (HP 50g) Challenge
|
03-20-2023, 02:12 AM
(This post was last modified: 04-07-2023 04:44 AM by 2old2randr.)
Post: #81
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
(03-19-2023 11:34 AM)Gerald H Wrote: Here a suggestion for a more economical "PALIN" programme in 2old2randr's submission Thank you, Gerald. I deliberately did not do this kind of optimization because I still don't "think" in RPL. However, I had incorporated your previous suggestions (the elimination of redundant RCL/STO instructions) in NTYPE and ALGO1-ALGO5. I'd done this last week but forgot to post here (it is available in my Github repository). Sudhir |
|||
03-21-2023, 01:31 AM
Post: #82
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
Here is the latest revised version from peruna. A bit quicker by dint of using the SREV command so Library 256 needs to be attached.
Code: DIR |
|||
03-22-2023, 12:08 PM
Post: #83
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
It is not an error, 2old2randr, but for input
110020 the programme returns 110011 0 9 which you may consider inelegant? |
|||
03-23-2023, 12:32 AM
Post: #84
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
Yes, indeed it is not pretty.
Fixed. Sudhir |
|||
03-24-2023, 01:35 PM
Post: #85
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
Okay, you've been waiting long enough, here's a pre-release of my SysRPL take. There's a lot going on under the hood - I optimized it to hell and back: starting with a CRLIB replacement which is capable of embedding one command inside another (inspired by hints from the Nosy readme). Then there's a lot of callbacks and other runstream and return stack manipulation, and finally I figured out how to merge Algorithms I to IV into a single piece of code which only branches out into four separate code paths after the main loop is done.
As far as I can tell, everything I've implemented so far is working properly. The 107-digit number from post #72 finishes after 4.7733 seconds on real hardware. Oh, by the way, you can use any base from 5 to 9999. I figured it wouldn't be much extra work, so I just built arbitrary-base support into it from the beginning. The (non-negative) number to be split goes on level 2, the base on level 1, and out come exactly three numbers which are palindromes in the given base. The three are sorted by magnitude, with the largest on level 3, and in cases where the proof's algorithms say that a less palindromes shall be generated, a 0 is used as placeholder. But there's something I haven't finished yet: 6-digit numbers with a 1 as first digit. Some small parts of that are not yet implemented at all, the rest is awaiting testing (and some more optimization) - and because buggy SysRPL code can cause crashes or even memory corruption, I have replaced all the code responsible for numbers of that form with a placeholder throwing the error #DE1Bh ("To be implemented"). That should be safe enough, though not satisfying yet. Hence, "pre-release". I'll go more in-depth in a future post, once I wrap up that 6-digit work. The rest of the code I consider finished, so you can dive in if you are feeling brave - both compiled library (L859) and source (as HPDIR) are attached. |
|||
03-25-2023, 02:25 AM
Post: #86
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
Bravo, 3298!
If you ever have the time, an annotated version of your program would be (I think) a great resource for anyone trying to learn SysRPL ... Sudhir |
|||
03-25-2023, 04:23 PM
Post: #87
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
Great stuff, 3298, congrats!
On my 49G, revision 1.19-6, the number in posting 1 is successfully partitioned in 1.45 sec. Similarly, 2old2randr, your programme takes 8.39 sec. |
|||
03-26-2023, 08:40 AM
(This post was last modified: 03-26-2023 09:04 AM by Gerald H.)
Post: #88
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
Further to posting # 76, towards the end of ALGO5 there is this segment
IF dn d3 - 10 MOD THEN p1 1 1 PUT p1 n 1 PUT d2 DUP p1 2 ROT PUT SWAP p1 n 1 - ROT PUT ADD ADD ADD 'p1' STO d3 1 - DUP p2 3 ROT PUT SWAP p2 n ROT PUT ADD 'p2' STO dn d3 - 10 MOD DUP p3 4 ROT PUT SWAP p3 n ROT PUT ADD 'p3' STO ELSE p1 1 1 PUT p1 n 1 PUT d2 DUP p1 2 ROT PUT SWAP p1 n 1 - ROT PUT ADD ADD ADD 'p1' STO d3 2 - DUP p2 3 ROT PUT SWAP p2 n ROT PUT ADD 'p2' STO p3 4 1 PUT p3 n 1 PUT ADD 'p3' STO END the bold part of which is never visited. Can you, 2old2randr, or anybody else construct a number using this branch? My own variant of ALGO5 is Code: CKSUM # 40685d |
|||
03-26-2023, 09:59 AM
Post: #89
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
I haven't looked at the UserRPL code at all, but from the info that it's in Algorithm V I'd hazard a guess that it's either handling the rare case of needing \(k=2\) (which happens when the central digits this algorithm is meant to change were \(20\) or \(01\)), or the even rarer case that the subtraction would make the longest palindrome of \(n'\) shorter than that of \(n\). The latter happens when:
- The top three digits of \(n\) qualify for type B1 or B2, but decrementing the third switches the type to A5 or A6. That is, they are \(103\) if the last digit is \(3\), or \(104\) otherwise. - The center digits generate a carry on the subtraction. This applies to \(20\), \(10\), and \(0x\) for any digit \(x\). - The digits between the top end and the center propagate the carry all the way through. The only way for that happening is if they are all \(0\). With all those conditions in mind, try \(104002067679\). That should satisfy both rare conditions at the same time. |
|||
03-26-2023, 10:10 AM
Post: #90
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
No, 3298, does not reach that branch - I imagine it has been dealt with under a different category, providing a correct partition.
|
|||
03-26-2023, 10:12 AM
Post: #91
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
Partition for
104002067679 is 101113311101 2236666322 652090256 |
|||
03-27-2023, 12:13 AM
Post: #92
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
I haven't been able to construct such a number.
What is happening here is that numbers of the form 103... with an even number of digits can be handled by either ALGO1 or ALGO4. However, if we classified them as A5/A6 and applied ALGO1, we would have an odd number of digits for p1 which causes a problem when adding back the number subtracted initially. So we pretend that the number is of type B1/B2 and apply ALGO4. The B2 path will be taken only if the last digit is '3' and this doesn't seem to be possible - at least I have not been able to find an example. |
|||
03-27-2023, 08:51 AM
Post: #93
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
ALGO5 now smaller:
Code: CKSUM #12287d |
|||
03-27-2023, 01:28 PM
(This post was last modified: 03-27-2023 01:31 PM by Gerald H.)
Post: #94
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
Concerning the branch mentioned in postings # 76 & #88, I have exhaustively tested all 8-digit integers beginning 103- & 104-, all of which were successfully partitioned without using the path in question.
Is that sufficient to say that no integer will require that section of the programme ALGO5? |
|||
04-02-2023, 08:47 AM
Post: #95
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
A week passes & not much development.
Should you, 3298, lack inspiration you might consider 2old2randr's solution for 6 digit inputs starting with a "1", my adaptation of which is here: Code: « DUP Alternatively you could adopt peruna's solution restricted to numbers with a maximum of six digits - this would not give a "canonical" partition as in the proof, but as far as I'm concerned any valid tripartite partition is good, the ones specified in the proof are just as good as any other, eg the partition in posting #1. |
|||
04-03-2023, 03:40 PM
Post: #96
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
No need for further inspiration, it's all finished. Most of the work was already done by the time I read your post, only those really hard-to-understand cases iv.b, v.d, and v.e still needed some attention. Bugfixes happened last night, and just now I applied some extra optimization across the rest of the library - mostly minor changes, the most notable ones are a slight restructuring of pickType to use only a single call to pickTypeB1B2 (which got properly inlined in the process, it only was a separate source file before due to a requirement of the unreleased CRLIB replacement I use to generate the 'compile' file), and switching the easy-access subroutine slot known as 2GETEVAL from the (previously unnamed) helper BINTmod over to computeCarryAndRem, which is used in a few more places.
Speaking of subroutine calls, since the library only has a single user-accessible entry point, I could convert it into a plain program with not much effort. I even have two different ideas how to call subroutines when the ROMPTRs of a library are out: shoving them all into LAMs bound at the start and doing xxGETLAM EVAL in every call site; or keeping them inline in one of the call sites (as I already have, thanks to the Nosy readme's library-in-MASD procedure) and doing position-relative calls from the other sites (loosely following the relative GOTO procedure) with the 2GETEVAL slot dedicated to the code object enabling this type of call. Not sure if such a conversion is worth it though, so I would do it on request. Next job: writing the promised wall of text going into the code's details. I don't think it'll be a suitable resource for people trying to learn SysRPL (sorry 2old2randr), that would be simply overwhelming with all the tricks I used; but an intermediate programmer may pick up something useful. For experts it's probably going to be just entertainment. |
|||
04-03-2023, 07:30 PM
Post: #97
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
Quite brilliant, 3298, & your programming is quite beyond me - I've never ventured into the vocabulary you articulate into executable units.
I hope some members will test your programme over the next week, I intend to & will report back. SysRPL at my level, entry level, is a translation of UserRPL, words dispensing with argument checking (which means you must supply correct arguments), unlike your User programme, 2old2randr, where "+" can add nearly any 2 types of argument together & produce a meaningful result, eg "A" + 2 -> "A2". A simple example of SysRPL is here https://www.hpmuseum.org/forum/thread-42...t=lagrange While 3298's pogramme is faster than yours I suspect a direct translation into SysRPL would not be slower than his - however, the first requirement is to make the User programme more efficient. Your programme is very useful didactically, it is much easier to follow the text of the proof when going through the programmes step by step & fortunately your nomenclature for the variables is based on that of the proof. I am enormously pleased with the three solutions to the challenge & should a fourth emerge.... |
|||
04-05-2023, 01:01 AM
(This post was last modified: 04-05-2023 01:02 AM by 2old2randr.)
Post: #98
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
I've gotten reasonably comfortable with simple programs in SysRPL that are pure numerical computations by studying examples in MoHPC and have embarked on translating my user RPL code to SysRPL.
Where I'm having trouble is with more complex data structures e.g., lists. I'm working with the Kalinowski & Dominik book "Programming in System RPL", 2nd ed. However, some of the documentation seems inaccurate and being hampered by not having an emulator (I don't have a Windows PC), I am making slow progress since everything needs to be tested on the calculator. For example, the following minimal program to extract the first element of a list crashes the calculator. Code: :: CK1NOLASTWD Replacing ^CKCARCOMP (supposedly specific to lists, p 73 of the book) by "1 NTHCOMPDROP" (generic function that works on any composite) works. I haven't been able to find example code that handles lists to see what the normal style is so I'm experimenting and learning ... |
|||
04-05-2023, 03:35 AM
Post: #99
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
Firstly
CARCOMP suffices, secondly FPTR2 ^CKCARCOMP is the correct form for the command you used. |
|||
04-05-2023, 03:54 AM
Post: #100
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
You can do all Sys programming on the calculator using the three libraries
Emacs SDiag Nosy all available at https://www.hpcalc.org/ |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 1 Guest(s)