Last active
September 21, 2016 18:45
-
-
Save endlesspint8/676acf4c618ecbc8aac09f1e2a67fd2e to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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