Skip to content

Instantly share code, notes, and snippets.

@gpiancastelli
Last active December 3, 2017 15:45
Show Gist options
  • Save gpiancastelli/ea2263bd76bb82faa79f2a00acfcd37f to your computer and use it in GitHub Desktop.
Save gpiancastelli/ea2263bd76bb82faa79f2a00acfcd37f to your computer and use it in GitHub Desktop.
Advent of Code 2017 day 3 problem solved in Python
n = 361527
##########
# Part I #
##########
FRONTIER_SIZE_MULTIPLIER = 8
def distance(n):
frame = 1
max_num_in_frame = 1
while max_num_in_frame < n:
max_num_in_frame = sum(FRONTIER_SIZE_MULTIPLIER * i for i in range(frame + 1)) + 1
frame += 1
frame = frame - 1
min_num_in_frame = max_num_in_frame - FRONTIER_SIZE_MULTIPLIER * frame + 1
idx = (n - min_num_in_frame) % (frame * 2)
min_dis_in_frame_idx = frame - 1
dis = frame + abs(idx - min_dis_in_frame_idx)
return dis
print(distance(n)) # 326
###########
# Part II #
###########
def first_larger(n):
value = 1
x, y = 0, 0
cells = {(x, y): value}
frame = 1
# for lack of a better solution, we generate the numbers in
# each frame of the spiral by moving around the previous one
# until we know that the latest frame contains our number
while value < n:
# move right
while x < frame:
x += 1
value = calculate_value(cells, x, y)
cells[(x, y)] = value
# move up
while y < frame:
y += 1
value = calculate_value(cells, x, y)
cells[(x, y)] = value
# move left
while x > -frame:
x -= 1
value = calculate_value(cells, x, y)
cells[(x, y)] = value
# move down
while y > -frame:
y -= 1
value = calculate_value(cells, x, y)
cells[(x, y)] = value
# and finally move right again
while x < frame:
x += 1
value = calculate_value(cells, x, y)
cells[(x, y)] = value
frame += 1
return [v for v in sorted(cells.values()) if v > n][0]
def calculate_value(cells, x, y):
return sum(cells.get(coords) for coords in neighbors(x, y) if cells.get(coords))
def neighbors(x, y):
return (
(x - 1, y + 1),
(x, y + 1),
(x + 1, y + 1),
(x + 1, y),
(x + 1, y - 1),
(x, y - 1),
(x - 1, y - 1),
(x - 1, y)
)
print(first_larger(n)) # 363010
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment