Puzzle  RPL and others

04232021, 09:05 PM
(This post was last modified: 04262021 10:56 PM by 3298.)
Post: #10




RE: Puzzle  RPL and others
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 bruteforce 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 notyetused 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 nonzero 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 notyettaken 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. 

« Next Oldest  Next Newest »

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