Search
Member List
Calendar
Help
HP Forums
/
HP Calculators (and very old HP Computers)
/
General Forum 
/
Tripartite Palindromic Partition of Integer (HP 50g) Challenge
/
Tripartite Palindromic Partition of Integer (HP 50g) Challenge
|
Tripartite Palindromic Partition of Integer (HP 50g) Challenge
|
|
03-04-2023, 03:57 AM
(This post was last modified: 03-05-2023 11:20 AM by Gerald H.)
Post: #41
|
|||
|
|||
|
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
Edit: The programme as below causes errors, some, believe it or not, introduced by me.
Please do not use - remains here for documentary considerations. I have shortened ALGO4 CKSUM 3914h SiIZE 9277.5 Code: « → d p1 p2 p3 |
|||
|
|
03-04-2023, 02:13 PM
Post: #42
|
|||
|
|||
|
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
Sorry, Gerald. There was a bug (same one in several places in ALGO4) caused by my poor attempt at premature optimization.
I have corrected the code and updated the original post. I think all is OK now. I have tested numbers that execute almost all paths through ALGO4 - the only remaining untested paths are IV.iii and IV.vi. I could not find numbers that would execute these bits. I must have been tired / sleepy when I typed in the original given the number of corrections I've made. Sudhir |
|||
|
|
|
03-04-2023, 05:33 PM
(This post was last modified: 05-03-2023 06:29 AM by Gerald H.)
Post: #43
|
|||
|
|||
|
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
Fewer errors ... but
For input 126189874318615808
The programme returns120111001100111021
5878186006818785 200686111686002 Which sums to 126189873218615808
|
|||
|
|
|
03-04-2023, 06:05 PM
(This post was last modified: 03-15-2023 07:43 PM by Albert Chan.)
Post: #44
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
(03-03-2023 10:57 AM)Gerald H Wrote: I believe ALGO5 is not necessary. It may not be necessary for this particular number, but we want to be safe in general. With center 0, it may lead to a palindrome with invalid center, which may be messy to fix. I like my simpler "palindrome" pair algorithm. At the center, there are less special cases to consider. If no carry, center cell is always vaild = (0 .. 9) - (0 .. 9) = (-9 .. 9) Even with carry, if (n-y) center is not 0 or 9, we are also safe: (1 .. 8) - (0 .. 9) ± 1 = (-9 .. 9) Only 2 cases may lead to problem: (n-y) - x = z + (non-zero carry) 0 - 9 = (−10) + 1 9 - 0 = (+10) − 1 To get into these situations are rare. Almost always, no backtracking fix needed. Here is an example that generated invalid center (±10), required backtracking to fix. NOTE: n is quoted number, but with center adjusted, to purposely get into trouble. n = 12267420150203532444 (20 digits) y = 10^19 - 1 (we always pick odd digits y) (n-y) also 19 digits, so we search for n = (x+y, both 19 digits) + (z, 18 digits) (*) Code: n-y 2 2 6 7 4 2 0 1 5 0 2 0 3 5 3 2 4 4 5Except for center, x digits are generated from LHS, without carry, thus always valid. With (n-y) center = 0 AND (last z = 9) AND (carry = +1), x center is invalid. There is no need to backtrack a lot. All we needed is to avoid last z = 9. z center of 229 → 218 is enough, guaranteed valid x center. Code: n-y 2 2 6 7 4 2 0 1 5 0 2 0 3 5 3 2 4 4 512267420150203532444 = 9899550931390559989 + 2014000000000004102 + 353869218812968353 (*) We only switch to n = x + (y+z) if (n-y) > y (i.e. balance with more digits) Otherwise, we do n = (x+y) + z, pad with zeroes if necessary. Above example, n of 122... changed to 100... Code: 7998995386835998997 |
|||
|
|
|
03-04-2023, 07:05 PM
Post: #45
|
|||
|
|||
|
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
Please remember, Albert, that the proof delivers an algorithm for any larger counting system base - some parts may only be required for bases other than 10.
|
|||
|
|
|
03-05-2023, 02:56 AM
Post: #46
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
(03-04-2023 05:33 PM)Gerald H Wrote: Fewer errors ... but Aargh! This was caused by an inadvertent deletion of two lines that set the two central digits in the first palindrome to two (120111001100111021) in my "fixed" version yesterday. I have updated the original post with those two lines restored - I honestly hope there are no more mistakes. Sudhir |
|||
|
|
|
03-05-2023, 11:00 AM
Post: #47
|
|||
|
|||
|
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
In post #28 you forgot to mention LPOP.
|
|||
|
|
|
03-05-2023, 11:31 AM
Post: #48
|
|||
|
|||
|
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
I now dismiss removing ALGO5 - it is necessary for cetain base 10 numbers.
|
|||
|
|
|
03-09-2023, 04:53 AM
Post: #49
|
|||
|
|||
|
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
On the other hand, I haven't found a number that gets to the "B7" branch of programme "NTYPE" - Has anyone found such a number?
|
|||
|
|
|
03-09-2023, 08:23 PM
Post: #50
|
|||
|
|||
|
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
Yes, ther are numbers of form "B7", but this form is subsumed under "B2", consequently the programme returns a correct partition via "B2", the form of the partition is as described for "B7".
Either "B7" is redundant or could be placed before "B2" to catch some numbers. All in all, "B7" is redundant. |
|||
|
|
|
03-09-2023, 11:15 PM
Post: #51
|
|||
|
|||
|
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
Type B7 is indeed wholly contained in type B2. Type B4 also overlaps with type B6, with the overlap making up half the numbers in type B4 (those with \(\delta_{l-3}=3\), to be precise).
The declaration of \(x_1, y_1, z_1\) between types B7 and B2 is also compatible, so you can just treat B7 as a special case of B2. Types B6 and B1 are similarly compatible (even though they are merely adjacent, not overlapping). But merging them makes stating the conditions for the combined type quite messy, so that may not be worth doing (it is worth it in my implementation, but not by a lot). The overlap between types B4 and B6 is not as pretty. You will get different results depending on which one you give preference, because their \(x_1, y_1, z_1\) declarations are different. This is one of two places I saw so far where the proof's algorithm lets you pick between multiple outcomes, the other being the cases in 6-digit numbers where it explicitly tells you to choose \(x_1, y_1\) or \(x_2, y_2\) or \(x_3, y_3\) within some constraints (which are a set of allowed digits (all, or all except zero), and the sum of the pair). --- My SysRPL implementation is progressing much slower than I anticipated. It's still missing a few cases in 6-digit numbers and a whole lot of testing (and the bugfixes resulting from that). In its incomplete state it's a standalone library weighing just about 3.6 KiB though, so I'm at least winning the code size race against the UserRPL one.  On the other hand, there's no way to beat the backtracking-based one in that.
|
|||
|
|
|
03-10-2023, 02:15 AM
(This post was last modified: 03-12-2023 01:24 AM by 2old2randr.)
Post: #52
|
|||
|
|||
|
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
Hi 3298,
(03-09-2023 11:15 PM)3298 Wrote: My SysRPL implementation is progressing much slower than I anticipated. It's still missing a few cases in 6-digit numbers and a whole lot of testing (and the bugfixes resulting from that). Attached is an updated set of User RPL programs that use the algorithms in the paper for all numbers including those with 2-6 digits (in SML2-SML6). I've tested all numbers exhaustively up to 199999 so there are no bugs in the code specific to the 2-6 digit cases. Algo2 has been modified to handle the callback from SML6 for numbers that don't begin with 1 in case the 6-digit no. is a "special" number (case II.2.ii.c). I have not tested exhaustively beyond 200000 since I am running the code on a physical 50g and it takes a long time to do so. I am very curious to see how much smaller / faster your SysRPL version turns out to be. I have been trying to learn SysRPL but it has been pretty heavy going so far. Sudhir Attachment removed since there was an additional case that was not covered by the paper I was referring to - the fixed code (as per the later version of the paper) is attached to a later post |
|||
|
|
|
03-10-2023, 10:15 AM
Post: #53
|
|||
|
|||
|
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
Your programme, 2old2randr, for input
109025 returns 99299 9090 636 The sum is correct. Have I transcribed programme erroneously? |
|||
|
|
|
03-10-2023, 11:43 AM
(This post was last modified: 03-10-2023 11:45 AM by 3298.)
Post: #54
|
|||
|
|||
|
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
You're evil picking such an input number, you know that?
While I haven't looked at the UserRPL program, from the proof alone I can see that it runs into one of the mentioned choose-numbers cases in the 6-digit algorithm. There it apparently disregards the non-zero digit restriction and chooses \(x_1=9\) and \(y_1=0\), causing the y palindrome to become invalid. To fix it, I recommend implementing the "choose" part as picking (sum / 2) and (sum / 2) + (sum mod 2). As long as the sum is >=2, the chosen digits will be >=1 as well. If it isn't, the restriction can't be fulfilled anyway, and the proof obviously takes care to avoid such failures. There are no other digit restrictions for these, so you're safe as long as you avoid accidental zeroes. In UserRPL, the implementation could look like: Code: 2. IDIV2 OVER +Code: BINT2 #/ SWAPOVER #+Code: DUP#1+ #2/ SWAP #2/ |
|||
|
|
|
03-10-2023, 12:40 PM
Post: #55
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
(03-10-2023 11:43 AM)3298 Wrote: While I haven't looked at the UserRPL program, from the proof alone I can see that it runs into one of the mentioned choose-numbers cases in the 6-digit algorithm. There it apparently disregards the non-zero digit restriction and chooses \(x_1=9\) and \(y_1=0\), causing the y palindrome to become invalid. That is exactly correct - I've handled it correctly in other positions but not for x1 and y1. I'll fix it on the weekend. Sudhir |
|||
|
|
|
03-10-2023, 07:12 PM
Post: #56
|
|||
|
|||
|
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
Your current SML2 programme, 2old2randr, looks like this in Sys:
Code: Size: 253.5 |
|||
|
|
|
03-11-2023, 05:10 AM
Post: #57
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
(03-10-2023 07:12 PM)Gerald H Wrote: Your current SML2 programme, 2old2randr, looks like this in Sys: Thank you Gerald, much appreciated. I will try to see if I can come up with a similar program on my own if I write it from scratch in SysRPL. I've corrected the bug in SML6 w.r.t. the choices of x1 and y1 and updated the attachment in my previous post. I finally did not use 3298's suggested Code: 2 IDIV2 OVER +Code: 2 / IP 'y' STOThe reason for this is that when calling PALIN from a test harness program, the IDIV2 instruction pops up a choose box with the message 'Purge current variable?'. Choosing ok continues normally but choosing cancel aborts execution with the message 'Mode switch cancelled'. I have no idea why this happens and could not find anything in the AUR that would explain it (the message itself is listed as DE51 in the Appendix). Sudhir |
|||
|
|
|
03-11-2023, 06:31 AM
Post: #58
|
|||
|
|||
|
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
Your latest edition, 2old2randr, now gives a correct partition of
109025 Well done. I find it commendable that you use the algorithms for small numbers from the proof - Although it would be odd to declare the winner of the competition one who uses a competitor's programme as a sub-programme! This website http://www.rnta.eu/cgi-bin/three_palindr...al3algo.py claims to use the algorithms in the proof but produces a different & correct answer. I am pleased to assist as much as I can. I remember the problem with "mode switch" from some years ago but have forgotten the solution - perhaps a more knowledgable member can assist? |
|||
|
|
|
03-11-2023, 06:58 AM
(This post was last modified: 03-11-2023 07:10 AM by 2old2randr.)
Post: #59
|
|||
|
|||
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
(03-11-2023 06:31 AM)Gerald H Wrote: This website That is because there is a choice in the first digit i.e., the constraint is x1+y1=9. I try to return the three palindromes in descending order i.e., x >= y >= z so I select the value 5 for x1 and 4 for y1. On the website you have pointed to, he has done the reverse. Sudhir |
|||
|
|
|
03-11-2023, 01:37 PM
Post: #60
|
|||
|
|||
|
RE: Tripartite Palindromic Partition of Integer (HP 50g) Challenge
I always think it might be me, 2old2randr, but your programme for input
3000 returns 3003 -3 0 Have I copied badly? |
|||
|
|
|
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 2 Guest(s)