Puzzle  RPL and others

04292021, 03:25 AM
(This post was last modified: 04292021 04:32 AM by Albert Chan.)
Post: #20




RE: Puzzle  RPL and others
(04282021 10:14 PM)3298 Wrote:(04282021 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 base10 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 speedup 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 

« Next Oldest  Next Newest »

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