Puzzle - RPL and others
05-03-2021, 03:43 PM
Post: #24
 3298 Member Posts: 206 Joined: Oct 2014
RE: Puzzle - RPL and others
After I theorycrafted this scheme of sorting base-N digits into buckets based on their GCD with the base (this is what the divisibility stuff boils down to, I just failed to realize that earlier)... I couldn't resist the temptation to try and implement it. Yes, I'm jumping past the odd/even and ==base/2 checking stages, but the way I baked it into my program should make the recursive subroutine faster in all situations than with those two simple tests, even in situations like bases 6 and 8 where my buckets match up perfectly with those tests, thanks to bitset juggling and the fact I already have a bitset check in there.
Code:
::   CK1NoBlame FPTR2 ^CK1Z   DUP FPTR2 ^Z># DUP #2-   BINT63 #> caseSIZEERR   DUPONE #AND #0<> case2DROP   WORDSIZE 1LAMBIND   ERRSET ::     BINT64 dostws BINT1 #>HXS     OVER ONE_DO       DUP ONE{}N 4UNROLL       DUP4UNROLL bitSL     LOOP     DROP' ::       OVER #2* #3+ GETLAM       4PICK bitAND UNROT       3GETLAM FPTR2 ^QMul 1GETLAM       3PICK 3PICKOVER FPTR2 ^#>Z       FPTR2 ^Mod FPTR2 ^Z># #-       DO         INDEX@ #2* #2+ GETLAM         4PICKOVER bitAND         OVER HXS==HXS %0=         ITE_DROP ::           bitNOT 5PICK bitAND           3PICK#1+_ 3PICK INDEX@           FPTR2 ^#>Z FPTR2 ^QAdd           OVER 1GETLAM #<>case           2GETEVAL           ROTDROPSWAP           #2* #2* #3- UNROLL         ;       OVER +LOOP       4DROP     ;     SWAP' NULLLAM OVER #2* #1+     NDUPN DOBIND     1GETLAM ONE_DO       1GETLAM INDEX@       BEGIN         SWAPOVER #/ DROP       #0=UNTIL       DROP #2* #3+ DUP GETLAM       INNERCOMP INDEX@ ROTOVER       #2* #2+ GETLAM bitOR       ROT#1+ {}N SWAP PUTLAM     LOOP     1GETLAM ONE_DO       INDEX@ #2* #3+ GETLAM       DUPTYPEHSTR?       ITE_DROP ::         INNERCOMP ONE_DO           DUPROT #2* #3+ PUTLAM         LOOP         DROP       ;     LOOP     BINT0 #>HXS bitNOT BINT1 Z0_     2GETEVAL     ABND   ; ERRTRAP ::     1GETLAM dostws ERRJMP   ;   1GETABND dostws ;
(405.5 bytes, #C476h)
The goal was to make the check for whether a digit is in the right bucket for the currently processed place as quick as I could: another bitset, which gets ANDed into the bitset of not-yet-taken digits before the digit-testing loop in the recursive subroutine starts. (My previous programs used a bitset of already-taken digits, but that's just an inversion away.) The preprocessing that goes into constructing the bucket bitsets is pretty quick too, since it doesn't use many loops or particularly slow commands, and especially not recursively nested loops.
This new part is just a loop over all valid digits taking the GCD between it and the base, using an indefinite loop for a custom BINT version of the Euclidean Algorithm (since I didn't want slow back-and-forth conversion to a slower type which would likely also use that algoithm in ROM). With this GCD a list is recalled, the digit appended to it, a bitset at the end of the list updated by ORing the digit's single-bit bitset into it, and the resulting list stored back. A separate loop over the GCDs (actually over all digits, but everything that doesn't have a list gets ignored) and distributes the finished bitset to the digits in the list. This re-uses the same local variables for lists and extracted bitsets, but I made sure that's safe.
If I comment out the part that sets up the three parameters for the outermost recursive subroutine call along with the call itself (i.e. leaving only this new setup part and the small setup which existed before), the time spent is around 0.16_s for bases 22 and 24 (the highest bases I tried so far). Compare that to how long the recursive part took: 150_s for base 24, which benefits greatly from all that bucket-sorting, and a staggering 1304_s (over 21 minutes!) for base 22, which does not benefit from it at all beyond the simple odd/even and ==base/2 checks. Good ol' base 10 takes just under 2.5 seconds.
Other changes include switching the types employed for the under-construction number and bitsets from reals and BINTs to ZINTs and HXSs, respectively. ZINTs slow things down, but reals broke down partially in base 13 and fully in base 14 and beyond (because they only hold 12 decimal digits), and extended reals push this limit up by only 3. So infinite-precision integers are the way to go; I don't need a fractional part anyway. Similarly, BINTs have only 20 bits, so they only work as bitsets up to base 21; HXSs are theoretically infinite (though the ROM math routines only support up to 64 bits), but also slower. Still, slow results is better than wrong results - base 65 is the upper limit now. Without these type changes base 10 was in the neighborhood of 1 second.
Oh, and I added an early exit in basically constant time for odd bases. No point checking those anymore, just return no results immediately.

---

While climbing the ladder up to base 24, I also noticed that quite a few of the bigger even bases don't have solutions either. Assuming my code is correct, these are the solutions by base:
- 2: $$1_2 = 1_{10}$$
- 4: $$123_2 = 27_{10}, 321_2 = 57_{10}$$
- 6: $$14325_6 = 2285_{10}, 54321_6 = 7465_{10}$$
- 8: $$3254167_8 = 874615_{10}, 5234761_8 = 1391089_{10}, 5674321_8 = 1538257_{10}$$
- 10: $$381654729_{10}$$, the original puzzle target
- 12: nothing
- 14: $$9C3A5476B812D_{14} = 559922224824157_{10}$$
- 16 to 24: nothing

I would have liked to dump some Babylonian numerals on you eventually (base 60), but I don't think that's going to happen if I look at the TEVAL reports for 22 and 24. The preprocessing isn't too bad (without the recursive subroutine I measured it to take 0.44 seconds for base 60), but 60 levels of recursion with a loop in each surely is just asking too much from a tortured little pocket calculator. We'd need more shortcuts to make that even remotely feasible.
 « Next Oldest | Next Newest »

 Messages In This Thread Puzzle - RPL and others - Gene - 04-22-2021, 06:55 PM RE: Puzzle - RPL and others - Valentin Albillo - 04-22-2021, 11:52 PM RE: Puzzle - RPL and others - rprosperi - 04-23-2021, 04:21 PM RE: Puzzle - RPL and others - EdS2 - 04-23-2021, 07:30 AM RE: Puzzle - RPL and others - Dave Britten - 04-23-2021, 12:06 PM RE: Puzzle - RPL and others - 3298 - 04-23-2021, 09:17 AM RE: Puzzle - RPL and others - ijabbott - 04-23-2021, 03:57 PM RE: Puzzle - RPL and others - Albert Chan - 04-23-2021, 04:08 PM RE: Puzzle - RPL and others - Albert Chan - 04-27-2021, 12:14 PM RE: Puzzle - RPL and others - Didier Lachieze - 04-23-2021, 04:23 PM RE: Puzzle - RPL and others - 3298 - 04-23-2021, 09:05 PM RE: Puzzle - RPL and others - C.Ret - 04-24-2021, 04:40 PM RE: Puzzle - RPL and others - C.Ret - 04-25-2021, 09:25 AM RE: Puzzle - RPL and others - Claudio L. - 04-26-2021, 04:56 PM RE: Puzzle - RPL and others - 3298 - 04-27-2021, 08:16 PM RE: Puzzle - RPL and others - Albert Chan - 04-28-2021, 02:33 AM RE: Puzzle - RPL and others - Albert Chan - 04-28-2021, 03:30 AM RE: Puzzle - RPL and others - 3298 - 04-28-2021, 10:14 PM RE: Puzzle - RPL and others - Albert Chan - 04-29-2021, 03:25 AM RE: Puzzle - RPL and others - Allen - 04-28-2021, 08:45 PM RE: Puzzle - RPL and others - Albert Chan - 04-29-2021, 05:16 PM RE: Puzzle - RPL and others - Allen - 04-29-2021, 07:03 PM RE: Puzzle - RPL and others - C.Ret - 05-02-2021, 06:40 AM RE: Puzzle - RPL and others - 3298 - 05-03-2021 03:43 PM RE: Puzzle - RPL and others - Albert Chan - 05-04-2021, 03:29 AM RE: Puzzle - RPL and others - 3298 - 05-04-2021, 06:48 AM RE: Puzzle - RPL and others - Albert Chan - 05-05-2021, 06:29 PM RE: Puzzle - RPL and others - 3298 - 05-06-2021, 04:24 PM RE: Puzzle - RPL and others - Albert Chan - 05-06-2021, 09:09 PM RE: Puzzle - RPL and others - Albert Chan - 05-07-2021, 10:35 AM RE: Puzzle - RPL and others - 3298 - 05-07-2021, 04:17 PM RE: Puzzle - RPL and others - Albert Chan - 05-09-2021, 01:21 AM RE: Puzzle - RPL and others - 3298 - 05-09-2021, 01:39 PM RE: Puzzle - RPL and others - Albert Chan - 05-10-2021, 03:57 AM RE: Puzzle - RPL and others - Albert Chan - 05-07-2021, 02:56 AM RE: Puzzle - RPL and others - Albert Chan - 05-10-2021, 05:13 PM RE: Puzzle - RPL and others - 3298 - 05-10-2021, 08:23 PM RE: Puzzle - RPL and others - Albert Chan - 05-11-2021, 11:58 AM RE: Puzzle - RPL and others - 3298 - 05-11-2021, 02:14 PM RE: Puzzle - RPL and others - John Keith - 05-11-2021, 03:55 PM RE: Puzzle - RPL and others - ijabbott - 05-11-2021, 10:37 PM RE: Puzzle - RPL and others - Albert Chan - 05-13-2021, 11:38 PM

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