I feel like I’m getting to the point with these problems where Python is just not going to be fast enough. It took over an hour for this one to run and unless there’s some clever and more logical way to do it, then I’m at a loss to figure out how it could run any faster than that.
With my first try at this problem, I found that I was having it calculate the same thing multiple times. This meant going through many for and while loops for each test. I solved this by creating a couple of arrays to store the values in. I think this is one place that I could find a way to work up the speed. There are probably faster ways to store data with Python, but I’m not sure how.
# bounds
low = 1
high = 500500
rows = 1000
# definitions
def random(low, high):
t = 0
for k in range(low, high):
t = (615949*t + 797807) % 2**20
yield t - 2**19
def trirow(k):
n = 1
while k > (n * (n + 1) / 2):
n += 1
return n
def trisum(start, depth):
diff = trirowdict[start]
total = randlist[start]
r = 1
while r < depth:
r += 1
next = start + diff
total += randlist[next]
for i in range(1, r):
total += randlist[next + i]
start = next + i
return total
def trisumiter(start, depth):
diff = trirowdict[start]
total = randlist[start]
yield total
r = 1
while r < depth:
r += 1
next = start + diff
total += randlist[next]
for i in range(1, r):
total += randlist[next + i]
start = next + i
yield total
# create arrays
randlist = [0]
for r in random(low, high + 1):
randlist.append(r)
randlist = tuple(randlist)
trirowdict = dict()
for n in range(low, high + 1):
trirowdict[n] = trirow(n)
# search by brute force
prev = 10**7
for start in range(len(randlist)):
if start == 0: continue
startrow = trirowdict[start]
if startrow == rows: continue
trisumdict = dict()
print start
for thissum in trisumiter(start, rows + 1 - startrow):
if thissum < prev:
prev = thissum
print prev