-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathday03_spiral.py
144 lines (110 loc) · 4.59 KB
/
day03_spiral.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
"""Advent of Code 2017 -- Day 3
http://adventofcode.com/2017/day/3"""
from collections import OrderedDict
import itertools
from typing import Dict, List
PUZZLE_INPUT = 312_051
class MemorySquare:
def __init__(self, value, x, y):
self.value = value
self.x = x
self.y = y
def __repr__(self):
return f'{self.value} @ ({self.x}, {self.y})'
def create_memory_table(top_limit: int) -> List:
# add first node
memory_table = {}
value = 1
memory_table[value] = MemorySquare(value, 0, 0)
step_size = 1
while value < top_limit:
if step_size % 2 == 1:
# x direction
last_added = memory_table[list(memory_table.keys())[-1]]
for new_x in range(last_added.x, last_added.x + step_size):
value += 1
new_memory_square = MemorySquare(value, new_x + 1, last_added.y)
memory_table[value] = new_memory_square
# y direction
last_added = memory_table[list(memory_table.keys())[-1]]
for new_y in range(last_added.y, last_added.y + step_size):
value += 1
new_memory_square = MemorySquare(value, last_added.x, new_y + 1)
memory_table[value] = new_memory_square
else:
last_added = memory_table[list(memory_table.keys())[-1]]
for new_x in range(last_added.x, last_added.x - step_size, -1):
value += 1
new_memory_square = MemorySquare(value, new_x - 1, last_added.y)
memory_table[value] = new_memory_square
# y direction
last_added = memory_table[list(memory_table.keys())[-1]]
for new_y in range(last_added.y, last_added.y - step_size, -1):
value += 1
new_memory_square = MemorySquare(value, last_added.x, new_y - 1)
memory_table[value] = new_memory_square
step_size += 1
return memory_table
def manhattan_distance(square: MemorySquare) -> int:
x_value = square.x
y_value = square.y
return abs(x_value) + abs(y_value)
def score_adjacent_blocks(memory: Dict, pos: tuple) -> int:
"""Add up diagonal if they exist"""
x_offsets = [-1, 0, 1]
y_offsets = [-1, 0, 1]
value = 0
for (x, y) in itertools.product(x_offsets, y_offsets):
check_pos = (pos[0] + x, pos[1] + y)
if check_pos in memory:
value += memory[check_pos]
return value
def create_cummulative_memory_table(top_limit: int) -> List:
# add first node
memory_table = OrderedDict()
value = 1
memory_table[(0, 0)] = value
step_size = 1
while value < top_limit:
if step_size % 2 == 1:
# x direction
last_added = list(memory_table.keys())[-1]
for new_x in range(last_added[0], last_added[0] + step_size):
new_block_x = new_x + 1
new_block_y = last_added[1]
new_pos = (new_block_x, new_block_y)
value = score_adjacent_blocks(memory_table, new_pos)
memory_table[new_pos] = value
# y direction
last_added = list(memory_table.keys())[-1]
for new_y in range(last_added[1], last_added[1] + step_size):
new_block_x = last_added[0]
new_block_y = new_y + 1
new_pos = (new_block_x, new_block_y)
value = score_adjacent_blocks(memory_table, new_pos)
memory_table[new_pos] = value
else:
last_added = list(memory_table.keys())[-1]
for new_x in range(last_added[0], last_added[0] - step_size, -1):
new_block_x = new_x - 1
new_block_y = last_added[1]
new_pos = (new_block_x, new_block_y)
value = score_adjacent_blocks(memory_table, new_pos)
memory_table[new_pos] = value
# y direction
last_added = list(memory_table.keys())[-1]
for new_y in range(last_added[1], last_added[1] - step_size, -1):
new_block_x = last_added[0]
new_block_y = new_y - 1
new_pos = (new_block_x, new_block_y)
value = score_adjacent_blocks(memory_table, new_pos)
memory_table[new_pos] = value
step_size += 1
return memory_table
if __name__ == '__main__':
# memory = create_memory_table(312_051)
# assert manhattan_distance(memory[1]) == 0
# assert manhattan_distance(memory[12]) == 3
# assert manhattan_distance(memory[23]) == 2
# assert manhattan_distance(memory[1024]) == 31
pass