Test speed solutions - python coding challenges

Test speed solutions

Question related to mission Saw the Stick

Accidentally during the search on the stackoverflow I saw a good tool called "perfplot".

It was decided to test the speed solutions of the Saw the Stick mission. Solutions for the test were chosen by @brubru777, @mogers, @DiZ, @nickie, @Beaxx, @mfurones, @diegueus9, @dmitrii606, @cbrunet, @sholtebeck, @yarmak_vladislav, @cyurys, @sulimo and my.

The code for test bellow:

[spoiler]

import perfplot


def nickie(number):    # O(sqrt(N)*log(sqrt(N)))
    t, s, triangular, sums = 0, 0, [], {0: 0}
    for n in range(1, number):  # it will finish much sooner...
        t += n
        triangular.append(t)
        s += t
        sums[s] = n
        if s < number: continue
        if t > number: break
        if s-number in sums: return triangular[sums[s-number]:n]
    return []


def sholtebeck(number):
    tri=[]
    t=len(tri)
    lengths=dict()
    for n in range(1,33):
        t+=n
        tri.append(t)
        l=len(tri)
        for r in range(l-1):
            s=sum(tri[r:l])
            if s<=number and (l-r)>len(lengths.get(s,[])):
                lengths[s]=tri[r:l] 
    return lengths.get(number,[])


from itertools import count

def cbrunet(number):
    """Find the first sequence of triangular numbers whose sum is number."""
    nlist = []
    for n in (n * (n + 1) // 2 for n in count(1)): # triangular numbers generator
        if n >= number: # stop condition
            return []
        nlist.append(n)
        s = sum(nlist)
        while s > number:
            s -= nlist.pop(0)
        if s == number:
            return nlist


def mogers(n):
    numbers = [1]
    while numbers[-1] < n:
        numbers.append(numbers[-1] + len(numbers) + 1)
    res = []
    s = i = 0
    for j in range(len(numbers)):
        s += numbers[j]
        while i < j and s > n:
            s -= numbers[i]
            i += 1
        if s == n and j-i+1 > len(res):
            res = numbers[i:j+1]
    return res


def yarmak_vladislav(number):
    A000217 = [ sum(range(n+1)) for n in range(42) ]
    low, high, X = 0, 0, 0
    while X != number and high < 41 and low < 41:
        if X < number and X + A000217[high] <= number:
            high += 1
            X += A000217[high]
            continue
        low += 1
        X -= A000217[low]
    return A000217[low+1:high+1] if X == number else []


from copy import copy

def triangular_numbers(number):
    n = 0
    v = 0
    while v < number:
        n += 1
        v = (n*(n+1))/2
        yield v


def diegueus9(number):
    numbers = [s for s in triangular_numbers(number)]
    results = []
    current = []
    for n in numbers:
        current.append(n)
        if sum(current)==number:
            results.append(copy(current))
        elif sum(current)>number:
            while sum(current)>number:
                current.pop(0)
            if sum(current)==number:
                results.append(copy(current))
    if len(results)>1:
        return sorted(results, key=len, reverse=True)[0]
    elif len(results)==1:
        return results[0]
    else:
        return results


def mfurones(number):
    a, b, c = [], 0, 0
    while c < number / 2:
        b += 1
        c += b
        a.append(c)
    l = len(a)
    for i in range(l-1):
        for j in range(i, l):
            if sum(a[i:j+1]) == number:
                return a[i: j+1]
    return []


def dmitrii606(number):
    tn, n = 1, 1
    res_nums = [tn]
    while tn < number:
        s = sum(res_nums) 
        if s == number:
            return res_nums
        elif s > number:
            res_nums.pop(0)
        else:
            n += 1
            tn = n * (n + 1) / 2
            res_nums.append(tn)        
    return []


def DiZ(n):
    s, tn, idx = 0, [0], {}
    while tn[-1] < n:
        idx[s] = len(tn)
        tn.append(tn[-1] + idx[s])
        s += tn[-1]
        if s - n in idx:
            return tn[idx[s - n]:]
    return []


def sulimo(number):
    triangles = [1]
    x=1
    i=1
    while x < 1024:
        i += 1
        x = x + i
        triangles.append(x)

    def checkio(number):
        i=0
        somme=0
        liste = []
        while triangles[i] <= number:
            while somme < number:
                liste.append(triangles[i])
                somme += triangles[i]
                i = i+1
            while somme > number:
                somme -= liste.pop(0)
            if somme == number:
                return liste
        return []
    return checkio(number)


def brubru777(number):
    def generate_triangle_series(number):
        total = 1
        rank = 1
        half = number // 2
        series = []
        while True:
            series.append(total)
            if total > half:
                return series
            rank += 1
            total += rank

    series = generate_triangle_series(number)
    lowest = 0
    total = 0
    for highest, value in enumerate(series):
        total += value
        while total > number:
            total -= series[lowest]
            lowest += 1
        if total == number:
            return series[lowest:highest + 1]

    return []


def Beaxx(number):
    import math

    series = [0]
    n = 0

    """Create a Series of triangular numbers from 0 - number/2"""
    while series[n] < 1/2 * number:
        series.append(int(n * (n+1) / 2))
        n += 1
    series.remove(series[0])

    """Find the longest slice of 'series' which's sum is == number"""  
    solution = []

    while len(series) > len(solution) and sum(series) >= number:
        series_instance = list(series)
        slice = []

        while sum(slice) < number and len(series_instance) > len(solution):
            slice.append(series_instance[-1])
            series_instance.remove(series_instance[-1])

            if sum(slice) > number:
                break

            if len(slice) > len(solution) and sum(slice) == number:
                solution = list(slice)

        series.remove(series[-1])

    return sorted(solution)


MAX_LENGTH = 1000

def _calculate_prefix_sum(iterable):
    prefix_sums = [next(iterable)]
    for item in iterable:
        prefix_sums.append(item + prefix_sums[-1])
    return prefix_sums

def triang(n):
    return (n * (n + 1)) // 2

def sumtriang(b, e):
    return (e * (e ** 2 - 1) - b * (b ** 2 - 1)) // 6

def cyurys(number, lower=1):
    b = 1
    e = 2
    while e != b:
        st = sumtriang(b, e)
        if st == number:
            return list(map(triang, range(b, e)))
        if st < number:
            e += 1
        else:
            b += 1
    return []


from itertools import accumulate

def merzix(number):
    triangle_seq = [int(i * (i + 1) / 2) for i in range(1, round(number**0.5) + 1)]
    while triangle_seq:
        acc = list(accumulate(triangle_seq))
        if number in acc:
            return triangle_seq[:acc.index(number) + 1]
        triangle_seq = triangle_seq[1:]
    return triangle_seq


perfplot.show(
    setup=lambda n: n,
    kernels=[
        brubru777, mogers, DiZ, nickie, diegueus9, dmitrii606, cbrunet  # winners
        # merzix, brubru777, mogers, DiZ, nickie, Beaxx, mfurones, diegueus9, dmitrii606, cbrunet  # all
        # sholtebeck, yarmak_vladislav, cyurys, sulimo  # n < 1000 (i added nickie for compare)
    ],
    n_range=[2**k for k in range(1, 11)],
    logx=True,
    # logy=True,

    xlabel='rows',
    equality_check=None,  # do not checks that the results of all solutions are equal
)

Some solutions had limitations on the source data in the code, so they were tested separately with `n_range=[2**k for k in range(1, 11)], # max n == pow(2, 10)`.

https://ibb.co/fyqZ1V" alt="img:solutions-with-limitations" />