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" />
All others with `n_range=[2**k for k in range(5, 25)], # max n == pow(10, 7)` and `logy=True,`
https://ibb.co/hxUQaq" alt="img:half-finale" />
Finale with `n_range=[2**k for k in range(20, 45)], # max n == pow(10, 13)` and `# logy=True,`
https://ibb.co/nvzSMV" alt="img:finale" />
And we have winner brubru777. I hope @oduvan will mark his solution by "editor's choice".
P.S. I hope someone finds "perfplot" useful.
task.stick-sawing