Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
import numpy as np
def lat_path(x):
grid = (x+1) * (x+1)
test_m = np.zeros(grid).reshape(x+1, x+1)
for row in range(x+1):
for col in range(x+1):
if row == 0 or col == 0:
test_m[row][col] = 1
else:
test_m[row][col] = test_m[row-1][col] + test_m[row][col-1]
print test_m
print ""
print "%d x %d grid has %d paths" % (x, x, test_m[x][x])
lat_path(5)
# [[ 1. 1. 1. 1. 1. 1.]
# [ 1. 2. 3. 4. 5. 6.]
# [ 1. 3. 6. 10. 15. 21.]
# [ 1. 4. 10. 20. 35. 56.]
# [ 1. 5. 15. 35. 70. 126.]
# [ 1. 6. 21. 56. 126. 252.]]
# 5 x 5 grid has 252 paths
# change `boxes` variable to get path counts for lattice
# https://projecteuler.net/problem=15
boxes = 4
max_dist = boxes * 2
steps = {0: [(0,0)]}
for step in range(1, max_dist+1):
steps[step] = []
# print step-1
# print steps[step-1]
# print steps[step-1][-1]
for path in steps[step-1]:
if step-1==0:
if steps[step-1][-1][0] < boxes:
pre_step1 = list(steps[step-1])
pre_step1.extend([(pre_step1[0][0]+1,pre_step1[0][1])])
steps[step].append(pre_step1)
if steps[step-1][-1][1] < boxes:
pre_step2 = list(steps[step-1])
pre_step2.extend([(pre_step2[0][0],pre_step2[0][1]+1)])
steps[step].append(pre_step2)
else:
if path[-1][0] < boxes:
pre_step1 = list(path)
pre_step1.extend([(pre_step1[-1][0]+1,pre_step1[-1][1])])
steps[step].append(pre_step1)
if path[-1][1] < boxes:
pre_step2 = list(path)
pre_step2.extend([(pre_step2[-1][0],pre_step2[-1][1]+1)])
steps[step].append(pre_step2)
print len(steps[max(steps.keys())])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.