Last active
November 17, 2016 04:09
-
-
Save kot-behemoth/ad47a32d08c543bc78b12f522ec1cbad 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
# elementary arrays I'll use to define directions | |
pos = [i for i in range(4)] | |
neg = [-i for i in pos] | |
zer = [0]*4 | |
# First, compute the direction vectors. Given a coordinate and a direction vector, | |
# we can generate four coordinates in a desired direction. We'll care about 8 directions. | |
# Even though left/right, and up/down are the same, let's no worry about that for now. | |
# 1 2 3 | |
# \ | / | |
# 4 - - 5 | |
# / | \ | |
# 6 7 8 | |
dirs = [ | |
list(zip(neg, neg)), # 1 | |
# [(0, 0), (-1, -1), (-2, -2), (-3, -3)] | |
list(zip(zer, neg)), # 2 | |
# [(0, 0), (0, -1), (0, -2), (0, -3)], | |
list(zip(pos, pos)), # 3 | |
# etc | |
list(zip(neg, zer)), # 4 | |
list(zip(pos, zer)), # 5 | |
list(zip(neg, pos)), # 6 | |
list(zip(zer, pos)), # 7 | |
list(zip(pos, pos)) # 8 | |
] | |
input = """08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 | |
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 | |
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 | |
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 | |
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 | |
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 | |
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 | |
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 | |
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 | |
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 | |
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 | |
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 | |
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 | |
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 | |
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 | |
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 | |
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 | |
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 | |
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 | |
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48""" | |
def read_input(input): | |
""" | |
Util function to read in the input array. | |
""" | |
rows_str = input.split('\n') | |
rows = [] | |
for row in rows_str: | |
nums_str = row.split(' ') | |
rows.append([int(n) for n in nums_str]) | |
return rows | |
arr = read_input(input) | |
def add(p1, p2): | |
""" | |
Util function for adding two tuples, element-wise. | |
""" | |
return (p1[0]+p2[0], p1[1]+p2[1]) | |
def get_coords(p): | |
""" | |
Given a coordinate `p`, generate points in all 8 directions. | |
""" | |
points = [] | |
for i, d in enumerate(dirs): | |
points.append([add(p, p2) for p2 in d]) | |
return points | |
def check_bounds(coords, n=20): | |
""" | |
Given a list of coordinates, check if any of them falls outside of matrix bounds. | |
""" | |
for coord in coords: | |
x = coord[0] | |
y = coord[1] | |
if x < 0 or x >= n or y < 0 or y >= n: | |
return False | |
return True | |
# Generate all possible indices into our 20x20 matrix, as 2-tuples | |
idxs = [] | |
for i in range(20): | |
for j in range(20): | |
idxs.append((i, j)) | |
# Walk through all those indices, generating lists of continous lines, in the shape of indices | |
vecs = [] | |
for idx in idxs: | |
for coord in get_coords(idx): | |
vecs.append(coord) | |
# Filter out lines that lead outside the matrix | |
good_coords = [] | |
for v in vecs: | |
if check_bounds(v): | |
good_coords.append(v) | |
def get_product(coords, arr=arr): | |
""" | |
Given vector of indices into arr, get all of them and get the product. | |
[(0, 0), (1, 1), (2, 2), (3, 3)] | |
""" | |
# idxs = [(i, j) for i in range(4) for j in range(2)] | |
vals = 1 | |
for c in coords: | |
v = arr[c[0]][c[1]] | |
vals *= v | |
return vals | |
# This is the running larges product | |
max_prod = 0 | |
# Go through all "good" coordinates, compute their product, and update max if needed | |
for coords in good_coords: | |
prod = get_product(coords) | |
print('Temp prod', prod) | |
if prod > max_prod: | |
max_prod = prod | |
print('Maximum product found is ', max_prod) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment