Puzzle  RPL and others

04282021, 03:30 AM
(This post was last modified: 04282021 11:42 AM by Albert Chan.)
Post: #17




RE: Puzzle  RPL and others
(04272021 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. 

« Next Oldest  Next Newest »

User(s) browsing this thread: