6
\$\begingroup\$

Codewars Kata: Given integers a and b, count all primes p where ap < b and the digits of p are all prime. b may be as large as 107.

To start with, I hardcoded all valid 1903 primes in \$[1, 10^7]\$ that can be formed from digits \$\{2, 3, 5, 7\}\$ and stored it in a list. Then I use binary search to locate the indexes corresponding to the given bounds, then return the difference of these indexes + 1, and my code times out. That is frankly baffling to me. Like I can't even coherently theorise why the program would be slow. All the heavy duty computation is handled by the binary search which is logarithmic time, and is called only a few times and on a 1903 element list (Also, the binary search function completes 1000 searches of 200,000 element lists in 228.67s in another kata, so I don't think I implemented it poorly).
enter image description hereenter image description here

My Code

def xbinsearch(pred, lst, *extras, type = "min", default = None):
    low, hi, best = 0, len(lst)-1, default
    while low <= hi:
        mid = (low+hi)//2
        p = pred(mid, lst, *extras)
        if p[0]:    #The current element satisfies the given predicate.
            if type == "min":
                if best == default or lst[mid] < lst[best]: best = mid
                hi = mid-1
            elif type == "max":
                if best == default or lst[mid] > lst[best]: best = mid
                low = mid+1
        elif p[1] == 1:     #For all `x` > `lst[mid]` not `P(x)`.
            hi = mid - 1
        elif p[1] == -1:    #For all `x` < `lst[mid]` not `P(x)`.
            low = mid + 1
    return best


def pred_a(idx, lst, *extras):
    tpl, val = [None, None], lst[idx], 
    if extras:  a, b = extras[0], extras[1]
    tpl[0] = a <= val < b 
    if val > b: tpl[1] = 1
    elif val < a:   tpl[1] = -1
    return tuple(tpl)

def get_total_primes(a, b):
    low, hi = xbinsearch(pred_a, primes, a, b), xbinsearch(pred_a, primes, a, b, type="max")
    return hi + 1 - low
\$\endgroup\$
  • \$\begingroup\$ I figured out the problem with this question. It was literally a missing token (well I checked for > instead of >= in my upper bounds check because I thought it was an inclusive upper bound while it was in reality exclusive. Should I delete my question or answer it. \$\endgroup\$ – Tobi Alafin Feb 21 at 13:52
  • 2
    \$\begingroup\$ You can answer it, there are more to improve than a change in comparison operator. \$\endgroup\$ – Mathias Ettinger Feb 21 at 14:24
  • \$\begingroup\$ Note: once you have determined low, high cannot possibly be before it... therefore only searching primes[low:] could be faster! \$\endgroup\$ – Matthieu M. Feb 21 at 19:47
10
\$\begingroup\$

Please read PEP8 and apply its advice; this will make your code look like Python code to others. Mainly, avoid code blocks on the same line as their conditions, and avoid cramming too many assignments on the same line.

You can also make your predicate function return a single value, as the first element of the returned tuple can be computed from the second (mainly p[0] is p[1] is None). You could also use the more common values -1, 0 and 1 and add an else clause in your xbinsearch loop to raise an exception. This would have caught the case where val == b in your usage.

Lastly, bisect should be the module to reach for when dealing with binary search in Python. In fact, having your list of primes ready, the code should be:

def get_total_primes(a, b):
    low = bisect.bisect_left(primes, a)
    high = bisect.bisect_left(primes, b)
    return high - low

And if you ever want to include the upper bound, you can:

def get_total_primes_inclusive(a, b):
    low = bisect.bisect_left(primes, a)
    high = bisect.bisect_right(primes, b)
    return high - low
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.