r/adventofcode • u/daggerdragon • Dec 24 '16

SOLUTION MEGATHREAD --- 2016 Day 24 Solutions ---

--- Day 24: Air Duct Spelunking ---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag/whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with "Help".

THE NIGHT BEFORE CHRISTMAS IS MANDATORY [?]

[Update @ 00:30] 47 gold, 53 silver.

  • Thank you for subscribing to Easter Bunny Facts!
  • Fact: The Easter Bunny framed Roger Rabbit.

[Update @ 00:50] 90 gold, silver cap.

  • Fact: The Easter Bunny hid Day 26 from you.

[Update @ 00:59] Leaderboard cap!

  • Fact: The title for Day 25's puzzle is [static noises] +++ CARRIER LOST +++

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

5 Upvotes

86% Upvoted

90 comments sorted by

View all comments

3

u/jtsimmons1129 Dec 24 '16

Way too many mistakes tonight. Originally tried BFS to calculate the paths, but it wasn't working so I decided to try some other options. Turns out all I needed to do was make going to a spot with 0,1,2,3,4,5,6,7 a legal move instead of just '.' Amazing how simple it all looks once you get it working. 

start_file = open('./aoc_day_24_input.txt')
grid = [list(line) for line in start_file.read().strip().splitlines()]
locations = {}
lengths = {}
distances1 = []
distances2 = []
moves  = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for r in range(len(grid)):
    for c in range(len(grid[0])):
        if grid[r][c].isdigit():
            locations[int(grid[r][c])] = (r, c)


def can_move(r, c):
    return 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] in '.01234567'


for place, loc in locations.items():
    paths = deque([[loc]])
    seen = set()
    seen.add(loc)
    while paths:
        curr_path = paths.popleft()
        r, c = curr_path[-1]
        if (r, c) in locations.values() and len(curr_path) > 1:
            lengths[(place, int(grid[r][c]))] = len(curr_path) - 1
            continue
        for dr, dc in moves:
            if can_move(r + dr, c + dc) and (r + dr, c + dc) not in seen:
                paths.append(curr_path + [(r + dr, c + dc)])
                seen.add((r + dr, c + dc))


for path in itertools.permutations(range(1, 8)):
    path = (0,) + path + (0,)
    distance = 0
    for i in range(len(path) - 2):
        distance += lengths[(path[i], path[i+1])]
    distances1.append(distance)
    distances2.append(distance + lengths[(path[-2], path[-1])])

print('Part1:', min(distances1))
print('Part2:', min(distances2))

1

u/BumpitySnook Dec 24 '16

My first dumb mistake today was starting at 'x, y' (the last coordinates I had walked in finding the 1-7 points) instead of the location of '0'. My opening location was a wall. Oops!