Puzzle - RPL and others - Printable Version +- HP Forums ( https://www.hpmuseum.org/forum)+-- Forum: HP Calculators (and very old HP Computers) ( /forum-3.html)+--- Forum: General Forum ( /forum-4.html)+--- Thread: Puzzle - RPL and others ( /thread-16722.html) |

Puzzle - RPL and others - Gene - 04-22-2021 06:55 PM
For the RPL (Let's make it an HP-50G oriented contest), judge by bytes x execution time. Problem: Social Security Numbers in the USA always have 9 digits. My friend has a very unusual social security number. The first two digits on the left are evenly divisible by 2, the first three digits are evenly divisible by three... and yes, it continues up that way all the way to the last digit... The first 8 digits on the left are evenly divisible by 8 and the full 9 digit number is evenly divisible by 9. What is my friend's social security number? Note: This number is 9 digits long, it does not contain any zeroes and no digits are repeated in the number. Also, putting the number on the stack inside the << and >> will not be considered a solution to this problem. For the other machines, post your solution and let's see what can be done. PLEASE DO NOT POST the actual number until about 18 hours after this post ? (6am EASTERN USA TIME 4/23/21). :-) As always have fun. RE: Puzzle - RPL and others - Valentin Albillo - 04-22-2021 11:52 PM
(04-22-2021 06:55 PM)Gene Wrote: For the other machines, post your solution and let's see what can be done. Ok,this 6-liner, 195-byte recursive HP-71B program will do: 1 DESTROY ALL @ STD @ FOR I=1 TO 9 @ CALL TST((I),2,9) @ NEXT I 2 SUB TST(N,D,M) @ N=10*N @ FOR I=1 TO 9 @ X=N+I @ IF MOD(X,D) THEN 6 3 A$=STR$(X) @ FOR J=1 TO LEN(A$) @ IF POS(A$[J+1],A$[J,J]) THEN 6 4 NEXT J @ IF LEN(A$)=9 THEN DISP X @ END ALL 5 IF D#M THEN CALL TST(X,D+1,M) 6 NEXT I Quote:PLEASE DO NOT POST the actual number until about 18 hours after this post ? (6am EASTERN USA TIME 4/23/21). :-) Ok, I won't post the result of running my program but rest assured that it's the correct number. By the way, if you add to it a final 0 it will cease to be a Social Security number but it will be a 10-digit number which meets all other requirements. Best regards V. RE: Puzzle - RPL and others - EdS2 - 04-23-2021 07:30 AM
I'll be interested to see the execution times: this puzzle can be solved using a determined brain and only a few case-by-case analyses. By brute force there are quite a few combinations, so I wonder if there are ways to short cut the search and make big improvements. RE: Puzzle - RPL and others - 3298 - 04-23-2021 09:17 AM
Ahh, an RPL puzzle! *cracks fingers, furious key clicking ensues* This time, I went for UserRPL first (somewhat unusual for me, but SysRPL might come soon too). Claiming a solution at 203.5 bytes, checksum #A034h, TEVAL results vary between 15.2 ... 15.25 seconds on my physical 50g. There's some list processing, so it's likely a somewhat memory-heavy solution, leading to possible garbage collection influence - I currently have 222KiB free in IRAM. Also have a modification of said program with a cache for a recurring slow computation. (2. n ^ R\->B for n in 1...9, if you're interested. The replacement is b n GET, where b is a local variable holding a 9-element list generated once at startup.) 248 bytes, checksum #3FD8h, TEVAL clocks in at about 13.62 ... 13.66 seconds. Code postponed till after the deadline. Now to see what shortcuts SysRPL enables... RE: Puzzle - RPL and others - Dave Britten - 04-23-2021 12:06 PM
(04-23-2021 07:30 AM)EdS2 Wrote: I'll be interested to see the execution times: this puzzle can be solved using a determined brain and only a few case-by-case analyses. By brute force there are quite a few combinations, so I wonder if there are ways to short cut the search and make big improvements. I put together a not-particularly-elegant 71B version that finds a solution in about 55 seconds, so that should set the bar for execution time. EDIT: Got it down to 219 bytes and about 36 seconds. There's still room to shave off a few bytes here and there. Code: `0010 OPTION BASE 1 @ DESTROY D @ DIM D(9),R` RE: Puzzle - RPL and others - ijabbott - 04-23-2021 03:57 PM
I think I worked out a solution by hand far quicker (about 5 minutes) than it would take me to write a program! EDIT: Oops! I missed the requirement about no digits repeating. I thought it seemed a bit too easy! RE: Puzzle - RPL and others - Albert Chan - 04-23-2021 04:08 PM
Let most significant digit = first digit (digit 1) Even digits must be even Odd digits must be odd 5th digit = 5. 4th digit + 8th digit must be 2 or 6 (Divisible by 4 only if last 2 digits divisible by 4. Example, 14 won't do it) This filled all even numbers Code: `1 2 3 4 5 6 7 8 9` This is perhaps optimized enough to start coding ... Brute force for 4! = 24 cases, done in Emu71/DOS Code: `10 DIM O(4),D(8) @ D(5)=5 @ O(1)=1 @ O(2)=3 @ O(3)=7 @ O(4)=9` >RUN 381654729 --- We can solve the puzzle, all by hand (without calculator !) Digits(123) divisible by 3. If 2nd digit is 4, top digits must have 1 somewhere (because 4%3=1) Digits(678) divisisble by 8 → 7th digit cannot be 1. Code: `1 2 3 4 5 6 7 8 9` If Digits(1 to 3) divisible by 3, Digits(1 to 7) divisible by 7, we are done. Note: 9th digit does not matter. If top 8 is correct, we found the solution. Modulo 7, we have 10≡3, 100≡3*3≡2, 1000≡3*2≡-1 We "remove" 7th digit, and do 2 groups of 3-digits, to test mod 7: 1/10 ≡ 100/1000 ≡ 2/-1 ≡ -2 (mod 7) 258-2*9 ≡ 254 ≡ 2, top 3 digits must be 2 (mod 7) 147 ≡ 0, 741 ≡ 6, all failed 654-2*3 ≡ 654+1 ≡ 4, top 3 digits must be 4 (mod 7) 789 ≡ 5, 987 ≡ 0, 189 ≡ 0, 981 ≡ 1, all failed 654-2*7 ≡ 654 ≡ 3, top 3 digits must be 3 (mod 7) 183 ≡ 1, 381 ≡ 3, 189 ≡ 0, 981 ≡ 1, 1 solution. Answer (proven unique): soc sec# 381-65-4729 RE: Puzzle - RPL and others - rprosperi - 04-23-2021 04:21 PM
(04-22-2021 11:52 PM)Valentin Albillo Wrote: Ok,this 6-liner, 195-byte recursive HP-71B program will do: Nice program Valentin!! This short, elegant program well illustrates the power and flexibility of the 71B's BASIC, clearly showing how its flexible string functions, recursion, call-by-value, etc. can be used to create unexpectedly powerful (if still somewhat slow by today's standards) and compact programs. I rarely read these contests closely, and even more rarely comment on solutions, but this one really made me smile. Thanks for that! RE: Puzzle - RPL and others - Didier Lachieze - 04-23-2021 04:23 PM
A recursive brute force program on the Prime, runs in ~.4s on my Prime G1, the .hpprgm file size is 1856 bytes: Code: `next(n,l)` RE: Puzzle - RPL and others - 3298 - 04-23-2021 09:05 PM
People are posting programs, the 18 hours are over, so here are mine: - UserRPL, smaller (203.5 bytes, #A034h, 15.2 ... 15.25 seconds): Code: `\<<` Code: `\<<` Adding a cache like the faster UserRPL program yields the fastest SysRPL program I could manage. 190 bytes, #3468h, 3.95 ... 3.97 seconds: Code: `::` Code: `::` About the algorithm I used: it's based on a brute-force approach, but it's skipping parts of the search space with early elimination of candidates. I'm keeping a list of candidates and attempting to append a not-yet-used digit to the candidate number, such that it also satisfies the divisibility condition. This generates a list of longer candidates, which get subjected to the same processing step, until all 9 digits are appended. Some optimization notes: - The trait of n leading digits being divisible by n can be expanded down to just the first digit as well, since any number is divisible by 1. Therefore it's possible to use 0 as starting point for building the number, with all 9 non-zero digits available for taking, instead of starting with the numbers 1 to 9 and only applying the expansion procedure from the second digit onwards. This keeps the program a bit smaller. - In the expansion step I could've kept a list of not-yet-taken digits for each candidate (or calculated them from scratch each time, but screw that, it's too slow), then checked each for divisibility. The divisibility test struck me as a potential performance hazard though, so I opted for the reverse: cycle through the digits satisfying the divisibility condition (evenly spaced by the divisor, and for the first one the expanded candidate can be calculated with just a single modulo operation as \((shorter\_candidate \cdot 10) - ((shorter\_candidate \cdot 10) \mod divisor) + divisor\)), then check using a bitset if the digit is still unused in the candidate. Edit: the UserRPL listings were swapped. Transcription error only, fixed now. RE: Puzzle - RPL and others - C.Ret - 04-24-2021 04:40 PM
Here a version for HP-28C/S RPL Advanced Scientific Calculator; As previous proposed code, it is based on a recursive approach, using the stack to store intermediate data. Code: `NTST:` Usage: Initiate the research by entering an empty string : "" NTST will return the solution in level 1: of the stack. Meanwhile, this code also verify that no other solution exists. One may spare running time by indicating a starting sequence such as "381" NST and the code will search for solution only starting with 381... eventually a solution may be found or the program ends leaving the stack unchanged. EDIT: On my HP-28S founding the solution starting with the empty string "" and scanning over all possibilities takes about 2'54". A shorter time may be reach (aka 1'22") by KILLing the process as soon as the unique solution is found. (by replacing DUP DEPTH ROLLD sequence by a KILL) EDIT #2: translating this RPL code into HP-71B's BASIC, I get a five liner of 158 octets: Code: `10 DESTROY ALL @ CALL NTST("") @ END` On my HP-71B, the solution is found in 1'12" RE: Puzzle - RPL and others - C.Ret - 04-25-2021 09:25 AM
Coding this puzzle on RPL's and powerful BASIC's pocket systems that natively support recurrence was an easy task ! A much more challenging is to adapt this algorithm on a pocket that have no support at all for recurrencies nor any serious structure for array ! Here is the same algorithm for SHARP PC-1211 (or other Tandy and SHARP equivalent), all you need is 129 steps and following variables: A to I: (respectively A(1) to A(9) ) for memorizing scanned values of increasing number of digits, J to R: (respectively A(10) to A(18) ) for noting at which level & position a digit is already used at, U & V: Pointers indicating the actual size of the scan value and at which digit is currently probe. T : Actual value to be probe, result at end of the whole seeking process, Z : Use for division testing of the scan figure. 1:CLEAR :FOR U=1TO 9:A(U)=T:FOR V=1TO 9 2:IF A(9+V)=0LET T=10A(U)+V,Z=T/U:IF Z=INT ZLET A(9+V)=U,V=99 :REM PAUSE A(U),T 3:IF V=9LET U=U-1,V=A(U+1)-10A(U),A(9+V)=0:GOTO 3 4:NEXT V:NEXT U:BEEP 1:PRINT T:END 129STEPS MEM 1295STEPS 161MEMORIES As for previous code post here, the trick is to memorize only correct partial figure in the stack (since there is no way here to use recurrence) A to I in the same time, the J to R stack memorize used digit and record at which position in the value which also correspond to the level of seek. A zero value in the J-R stack indicate a free digit. Note the affectation V=99 which is equivalent for an BREAK (or LEAVE) instruction missing on these venerable old fashion canonic BASIC. Without any intermediate message (the PAUSE at end of line 2: was heavily used for debugging the process), the solution is found in about 16'24" here the complet trace of the seek up to the solution: Code: `Seek levels: Target` [attachment=9414] RE: Puzzle - RPL and others - Claudio L. - 04-26-2021 04:56 PM
I'm very late to the party, sorry. Here's a version that doesn't use lists, or strings, all digits are stored in a number. It uses the DIGITS command from newRPL to isolate digits but it could easily be replaced using divisions, MOD 10, and IP to become plain userRPL. Also uses some local variable syntax from newRPL, but is could be turned into plain userRPL as well without too much trouble. Code is below, must be stored as 'DONXT' (or adjust the name in the code, it's recursive). It takes 2 arguments: initial number and number of digits in the initial guess. Use 0 0 to scan the entire scope, or for example provide 381 3 to start with 3 known digits. It returns nothing if no solution with 9 digits found. If the solution is found, it returns it in the same format: the number and the number of digits it contains. It's 392 bytes, won't win any contests there, could be reduced to 376 bytes if I had used variable names with less than 4 letters, but whatever. The speed is quite good: 0.133 seconds on 50g hardware 0.303 seconds on Prime G1 hardware (still a mystery why it's slower, my guess is SRAM vs DRAM timings, plus the LCD driver accessing the DRAM all the time to achieve 60 Hz refresh). The timings were measured using 0 0 as initial guess (no known digits at all). For comparison, C.Ret code (extremely clever) clocks at 172 bytes and 4.12 seconds on 50g hardware. Code:
The algorithm is quite simple: Given the initial digits and the number of digits, try to add one digit trying all possible combinations. Actually not all, the loop doesn't go from 1 to 9, it starts with the first digit that will meet the MOD n requirement, and it steps n digits each time. Each candidate digit is therefore known to meet the MOD requirement, it just needs to be checked for the repeated digit condition. If it's not repeated, recurse with that digit added to the number until we have 9 digits. RE: Puzzle - RPL and others - Albert Chan - 04-27-2021 12:14 PM
(04-23-2021 04:08 PM)Albert Chan Wrote: This filled all even numbers I noticed odd digits [1,3,7,9], mod7 is [1,3,0,2], or simply 0 to 3. This may simplify mod7 calculations (without calculator) For example, lets try to solve missing digits of last pattern. Let a = 1st digit, b = 3rd digit, c = 7th digit 10^6*a + 10^4*b + c + 806540 ≡ a - 3*b + c ≡ 0 (mod 7) a+c ≡ 3*b (mod 7) a+c ≡ 3*0 ≡ 0, no solution a+c ≡ 3*1 ≡ 3, [a,c] ≡ [0,3] or [3,0] a+c ≡ 3*2 ≡ 6, no solution a+c ≡ 3*3 ≡ 2, [a,c] ≡ [0,2] or [2,0] Passes mod7 test: [a,b,c] = [7,1,3], [3,1,7], [9,3,7], [7,3,9] Digit(6,7,8) for divisible by 8: 492 (mod 8) ≠ 0, last case rejected. Digit(1,2,3) for divisible by 3: 781, 381, 983, only 381 passes. -> soc-sec# = 381 654 729 RE: Puzzle - RPL and others - 3298 - 04-27-2021 08:16 PM
I tinkered with my programs a bit more. Traversing the search space depth-first (i.e. with recursion) instead of the breadth-first (iterative) approach I employed didn't do me any favors in UserRPL. The program just grew bigger and slower. In SysRPL on the other hand it worked out pretty well. I also found an improvement for what was the inner loop (now the only loop), which is now a DO...+LOOP like I wanted it to be (BINT range concerns previously prevented it). Code: `::` Code: `::` --- Small note on the theory side: I identified another reason for checking divisibility first, like Claudio and I did: it has a higher rejection rate than the duplicate digits check - and as you probably know it's usually prudent to run the more strict check first, giving you a higher chance to skip the other one altogether for a quicker rejection. (Unless the check with the higher rejection rate is significantly slower, that is. But in this case it's definitely not.) On the first digit, neither check rejects anything because divisibility by 1 is always true and there are no digits already taken ... but on the second only 1 out of 9 is a duplicate, whereas 5 out of 9 are odd. This continues through all recursion levels: - 2/9 vs. 6/9 on the third digit, - 3/9 vs. 7/9 on the fourth, - 4/9 vs. 8/9 on the fifth, - 5/9 vs. either 7/9 or 8/9 on the sixth (allowed digits are {2 8} or {4} or {6}, depending on the prior digits), - 6/9 vs. again either 7/9 or 8/9 on the seventh, and - 7/9 vs. 8/9 on the eighth digit. Only on the last digit they agree again on rejecting all but one digit. --- Now for something different: what if we expand the puzzle to arbitrary base-N, i.e. build a (N-1)-digit number in base-N where no digits are 0 or a duplicate, and the leading-digits requirement is satisfied too? Code: `::` This program tries to find all solutions, and therefore does not use an early abort mechanism like throwing a custom error. RE: Puzzle - RPL and others - Albert Chan - 04-28-2021 02:33 AM
(04-27-2021 08:16 PM)3298 Wrote: Interesting to note: odd bases never have solutions... We can let the number be x, with digits 1 to n, all distinct, in base n, integer n > 1: x = Σ(d _{k} * n^{k}, k = 0 to n-1)x (mod n-1) ≡ Σ(d _{k} * 1^{k}, k = 0 to n-1) ≡ Σ(d_{k}, k = 0 to n-1)This explained the shortcut for mod 9 by adding digits, in decimal. With all digits distinct: x (mod n-1) ≡ n*(n-1)/2 q*(n-1) + r = n*(n-1)/2 We restrict q as integer, such that 0 ≤ r < n-1 With this setup, x divisible by (n-1) is same as test for r = 0. If n is even, q*(n-1) + r = (n/2) * (n-1) + 0 ⇒ r = 0 If n is odd, q*(n-1) + r = (n-1)/2 * (n-1) + (n-1)/2 ⇒ r = (n-1)/2 ≠ 0 RE: Puzzle - RPL and others - Albert Chan - 04-28-2021 03:30 AM
(04-27-2021 08:16 PM)3298 Wrote: Small note on the theory side: I identified another reason for checking divisibility first, like Claudio and I did: it has a higher rejection rate than the duplicate digits check - and as you probably know it's usually prudent to run the more strict check first, giving you a higher chance to skip the other one altogether for a quicker rejection. (Unless the check with the higher rejection rate is significantly slower, that is. But in this case it's definitely not.) There is another side to this. If we did check divisibility first, then we need to check for duplicates, an O(n) operation. However, if we have O(1) array access, we could "check" duplicates in O(1) I tried this in Python. For n=10, this simple version is 60% faster. At the end of the day, both ways generate same test cases (albeit not same order) Code: `def recurse(lst, n, k=1, x=0):` >>> recurse(range(10), 10) 381654729 >>> recurse(range(14), 14) # = 9c3a5476b812d _{14}559922224824157 Update: restricting odd digits odd, even digits even, speed up a lot ! Not bad for a 3 bytes ", 2" patch. See the numbers: For n=10, mod calculations reduced from 1580 to 424, factor of 3.73 For n=14, mod calculations reduced from 29045 to 4422, factor of 6.57 Reduced search space is not quite as much. For n=10, recursive calls reduced from 311 to 156, factor of 1.99 For n=14, recursive calls reduced from 3928 to 1085, factor of 3.62 Overall, speed factor = 2.42X for n=10, 4.25X for n=14. RE: Puzzle - RPL and others - Allen - 04-28-2021 08:45 PM
I was traveling this past week and had no internet most of the time, so I am submitting a little late.. I propose a 63 Byte solution for 41c/42s with a slight rube-goldberg look to the code to minimize size, but maintains divisibility throughout. Registers Used: 5 Program Constants: 19, 3 Initial Entry: None Returns: X-register 381654729 ( possible I made some mistakes) Code:
RE: Puzzle - RPL and others - 3298 - 04-28-2021 10:14 PM
Thank you, Albert Chan, for expanding my observation and ideas into a proper proof, because that's not quite my area of expertise. I hope you didn't feel pressured into it. (04-28-2021 03:30 AM)Albert Chan Wrote: restricting odd digits odd, even digits even, speed up a lot !I was going to say that this doesn't work for odd bases, but as we just found out, we can reject those before we get here, since they can't have solutions anyway... But thinking about why it wouldn't apply to odd bases pushed me into another idea building on this: the shortcut works for any number that divides the base. You already applied this with the number 5 in base 10 ... the fifth position has to be 5, as it is the only base-10 digit divisible by 5. To take another example, in base 12 we would be looking at divisibility by 2, by 3, by 4, and by 6 (these are the numbers that divide 12 without remainder). Then we can sort all digits into buckets where all digits in the same bucket have the same divisibility results, and when we get to check if a digit is allowed in position <i>, add a third check into the mix: only digits in the bucket containing <i> are allowed. Not sure if all that complexity is worth it, but at least on bases with a high number of divisors it might eliminate another handful of checks. And the whole business of sorting digits into buckets only needs to be performed once per base, not at each recursion level. For an implementation of the check if a given digit is in the same bucket as another, I'm imagining a lookup table holding references to the buckets that correspond to the lookup table index (O(1)), and the buckets themselves are sets which can be implemented as an array of booleans, a.k.a. another bitset (also O(1)). That means an O(1) check overall. Maybe generating the buckets could even be optimized by cutting the list of factors down to prime factors with multiplicities, i.e. if we look at the base-12 example again (prime factors are 2 with a multiplicity of 2 and 3 with a multiplicity of 1), digit divisibility by 2 is separated into not divisible (=2^0), divisible by 2^1, and divisible 2^2, while 3 is sorted into not divisible (=3^0) and divisible (=3^1), for a total of three options times two options = six buckets. The last one will always stay empty, because if you multiply all prime factors in full multiplicities back together (2^2 * 3^1 = 12), you get the base, which isn't a valid digit (and neither are its multiples, for obvious reasons). The others are { 1 5 7 11 } { 2 10 } { 4 8 } { 3 9 } { 6 }. I don't have an implementation to run performance tests on, this is just an idea still. Maybe later. RE: Puzzle - RPL and others - Albert Chan - 04-29-2021 03:25 AM
(04-28-2021 10:14 PM)3298 Wrote:(04-28-2021 03:30 AM)Albert Chan Wrote: restricting odd digits odd, even digits even, speed up a lot !I was going to say that this doesn't work for odd bases, but as we just found out, we can reject those before we get here, since they can't have solutions anyway... This optimization actually force code to quit early, for odd base. For odd base, even digits must have same parity as the digit before it. odd * odd = odd even * odd = even Quote:But thinking about why it wouldn't apply to odd bases pushed me into another idea building on this: the shortcut works for any number that divides the base. You already applied this with the number 5 in base 10 ... the fifth position has to be 5, as it is the only base-10 digit divisible by 5. Yes, bucket idea work, but code would get complicated ... fast. Also, gain may not be what you expected. Example, with even base, we already have 2 factors. Odd digits odd, even digits even use the factor 2. At the cost of slight complexity, we can add the other factor: base/2 Code: `def recurse2(lst, n, k=1, x=0):` Code work the same way, just faster >>> recurse2(range(10), 10) 381654729 Compare against recurse(), recurse2() was expected to cut down search time. But, numbers are not impressive (factor also closely matched speed-up ratio) For n=10, recursive calls reduced from 156 to 131, factor of 1.19 For n=14, recursive calls reduced from 1085 to 790, factor of 1.37 |