Counting primes in a range whose digits are all prime

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP












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









share|improve this question











$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















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









share|improve this question











$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













6












6








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









share|improve this question











$endgroup$




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






python beginner programming-challenge time-limit-exceeded primes






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Feb 21 at 14:40









200_success

130k17153419




130k17153419










asked Feb 21 at 13:27









Tobi AlafinTobi Alafin

635110




635110











  • $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
















  • $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















$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




$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




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$
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




$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










1 Answer
1






active

oldest

votes


















9












$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





share|improve this answer











$endgroup$












    Your Answer





    StackExchange.ifUsing("editor", function ()
    return StackExchange.using("mathjaxEditing", function ()
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
    );
    );
    , "mathjax-editing");

    StackExchange.ifUsing("editor", function ()
    StackExchange.using("externalEditor", function ()
    StackExchange.using("snippets", function ()
    StackExchange.snippets.init();
    );
    );
    , "code-snippets");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "196"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: false,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    bindNavPrevention: true,
    postfix: "",
    imageUploader:
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    ,
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );













    draft saved

    draft discarded


















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f213960%2fcounting-primes-in-a-range-whose-digits-are-all-prime%23new-answer', 'question_page');

    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    9












    $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





    share|improve this answer











    $endgroup$

















      9












      $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





      share|improve this answer











      $endgroup$















        9












        9








        9





        $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





        share|improve this answer











        $endgroup$



        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






        share|improve this answer














        share|improve this answer



        share|improve this answer








        edited Feb 28 at 18:30









        Toby Speight

        26.4k742118




        26.4k742118










        answered Feb 21 at 14:39









        Mathias EttingerMathias Ettinger

        25.1k33185




        25.1k33185



























            draft saved

            draft discarded
















































            Thanks for contributing an answer to Code Review Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid


            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.

            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f213960%2fcounting-primes-in-a-range-whose-digits-are-all-prime%23new-answer', 'question_page');

            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown






            Popular posts from this blog

            How to check contact read email or not when send email to Individual?

            Displaying single band from multi-band raster using QGIS

            How many registers does an x86_64 CPU actually have?