11
\$\begingroup\$

I've been working through the British Informatic Olympiad's 2016 Paper, and I've been struggling with some of the larger cases for question 3, specifically the larger cases on the mark scheme (the 3 before last specifically).

  • Two prime numbers are connected if the difference between them is 2n for some whole number n ≥ 0.
  • A path is a sequence of (at least two) prime numbers, without repetition, where adjacent numbers in the sequence are connected. If the first number in the sequence is p and the last number is q then we say the path is between p and q.
  • The length of a path is the total number of prime numbers used. There may be multiple paths between two prime numbers; the lengths of these paths may be different.

Write a program to determine the length of the shortest path between two primes. Your program should accept three integers in order: l (4 ≤ l ≤ 224) indicating the highest value you are allowed to use, followed by the primes p then q (2 ≤ p < q < l). You will only be given input where there is a path between p and q using values below l. You should output the length of the shortest path.

Inputs I was struggling with:

614700 3643 90149 | outputs 18
987654 3643 90149 | outputs 16
1000000 2 968137  | outputs 18

How can I improve its performance?

import math

primes = None
upper_limit = 0
powers_of_two = []

class Node:
    def __init__(self, value, parent):
        self.value = value
        self.parent = parent
    def get_adjacent(self):
        for i in powers_of_two:
            if (self.value + i < upper_limit
            and self.parent != self.value + i
            and self.value + i in primes):
                yield Node(i+self.value, self)
            if (self.value - i >= 2
            and self.parent != self.value - i
            and self.value - i in primes):
                yield Node(self.value - i, self)

def sieve(n):
    numbers = list(range(0, n))
    for prime in numbers:
        if prime < 2:
            continue
        elif prime > n ** 0.5:
            break
        for i in range(prime ** 2, n, prime):
            numbers[i] = 0
    return [x for x in numbers if x > 1]

def bfs(f, to):
    f = Node(f, None)
    q = [f]
    visited = [f.value]
    while len(q) != 0:
        if q[0].value == to:
            return q[0]
        else:
            for x in q[0].get_adjacent():
                #print(q[0].value, x.value)
                if x.value not in visited:
                    #print("added", x.value)
                    visited.append(x.value)
                    q.append(x)
        del q[0]
while True:
    inp = [int(x) for x in input().split(' ')]
    upper_limit = inp[0]
    m = int(math.ceil(math.log2(inp[0]))) if math.log2(inp[0]) % 1 != 0 else int(math.log2(inp[0]))
    for i in range(0, m):
                   powers_of_two.append(2**i)
    primes = sieve(inp[0])
    x = bfs(inp[1], inp[2])
    counter = 0
    while x is not None:
        print(x.value)
        x = x.parent
        counter += 1

    print("--------------------")
    print(counter)
\$\endgroup\$
11
\$\begingroup\$

There are 3 major performance problems you currently have:

  • the primes is currently a list and every time you do something in primes - this is O(n) average-time complexity (where n is the length of primes) - define primes as a set instead
  • the visited is a list, same O(n) lookups - define it as a set instead
  • the del q[0] is also a O(n) operation - removing an element from the beginning of a list requires rearranging all following elements - use a collections.deque in place of a list for O(1) deletes from both ends (.popleft() for the left-end deletion)

Revised version (works for me in an instant for all the test inputs):

import math
from collections import deque


class Node:
    __slots__ = ['value', 'parent']

    def __init__(self, value, parent):
        self.value = value
        self.parent = parent

    def get_adjacent(self, primes):
        for i in powers_of_two:
            if self.value + i < upper_limit and self.parent != self.value + i and self.value + i in primes:
                yield Node(i + self.value, self)
            if self.value - i >= 2 and self.parent != self.value - i and self.value - i in primes:
                yield Node(self.value - i, self)


def sieve(n):
    numbers = list(range(0, n))
    for prime in numbers:
        if prime < 2:
            continue
        elif prime > n ** 0.5:
            break

        for i in range(prime ** 2, n, prime):
            numbers[i] = 0

    return {x for x in numbers if x > 1}


def bfs(f, to, primes):
    f = Node(f, None)

    q = deque([f])
    visited = set([f.value])
    while q:
        if q[0].value == to:
            return q[0]
        else:
            for x in q[0].get_adjacent(primes):
                # print(q[0].value, x.value)
                if x.value not in visited:
                    # print("added", x.value)
                    visited.add(x.value)
                    q.append(x)
        q.popleft()


if __name__ == '__main__':
    upper_limit, p, q = [int(x) for x in input().split(' ')]

    m = int(math.ceil(math.log2(upper_limit))) if math.log2(upper_limit) % 1 != 0 else int(math.log2(upper_limit))
    powers_of_two = [2 ** i for i in range(m)]

    primes = sieve(upper_limit)

    x = bfs(p, q, primes)

    counter = 0
    while x is not None:
        print(x.value)
        x = x.parent
        counter += 1

    print("--------------------")
    print(counter)

You can also see some other changes:

  • removed the while True loop (from what I understand you just need a single run)
  • using if __name__ == '__main__':
  • avoiding using globals and passing the primes set to the bfs() and get_adjacent() as an argument
  • using __slots__ for the Node class
  • used list unpacking for reading the input numbers
  • used upper_limit, p and q variables to increase readability (p and q variable names are used in the problem description)
\$\endgroup\$
  • 1
    \$\begingroup\$ According to this, average search time for a list is O(n) and average for a set is O(1) (with worse case being O(n)). \$\endgroup\$ – NonlinearFruit Mar 13 '17 at 12:59
  • 2
    \$\begingroup\$ @Nonlinear The worst case very, very rarely comes up in practice, though, as long as you are (a) not willfully trying to make it happen (in which case it's easy) and (b) following all the expectations about what your __hash_code__ returns. \$\endgroup\$ – Nic Hartley Mar 13 '17 at 14:52
  • \$\begingroup\$ This was really useful, also for my general knowledge of python :) I didn't know about __slots__ and also naively assumed that python lists were internally sets. Thank you! \$\endgroup\$ – It'sNotALie. Mar 13 '17 at 17:45
3
\$\begingroup\$

Just to add to @alecxe's answer, the sieve function can be re-written as:

def sieve(n):
    numbers = range(2, n ** 0.5)
    for prime in numbers:
        for i in range(prime ** 2, n, prime):
            numbers[i] = 0
    return {x for x in numbers if x > 1}

But you should be careful with that ** 0.5, because floating point numbers may be rounded at some point.

EDIT: to fix the code above I started thinking about it and I didn't really like it, so here's another version which returns a set of primes:

def sieve(n):
    primes = [False, False] + [True] * (n - 2)
    for (prime, isprime) in enumerate(primes):
        if isprime:
            for i in range(prime*prime, n, prime):
                primes[i] = False
    return {prime for prime, val in enumerate(primes) if val}
\$\endgroup\$
  • 1
    \$\begingroup\$ This code doesn't work for me, complains about firstly n ** 0.5 not being integral (I cast to int() for a fix), then numbers[i] not being assignable to (list()), and then numbers[i] being out of range (not sure where to fix it. Always good to see more Eratosthenes sieves though :) \$\endgroup\$ – It'sNotALie. Mar 13 '17 at 17:48

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.