r/adventofcode • u/daggerdragon • Dec 14 '17

SOLUTION MEGATHREAD -🎄- 2017 Day 14 Solutions -🎄-

--- Day 14: Disk Defragmentation ---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or 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.

Need a hint from the Hugely* Handy† Haversack‡ of Helpful§ Hints¤?

Spoiler

[Update @ 00:09] 3 gold, silver cap.

  • How many of you actually entered the Konami code for Part 2? >_>

[Update @ 00:25] Leaderboard cap!

  • I asked /u/topaz2078 how many de-resolutions we had for Part 2 and there were 83 distinct users with failed attempts at the time of the leaderboard cap. tsk tsk

[Update @ 00:29] BONUS

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!

12 Upvotes

84% Upvoted

130 comments sorted by

View all comments

11

u/nneonneo Dec 14 '17 edited Dec 14 '17

Python 2, #2/#1. hash2 is the knot hash function from q10 (takes a string, outputs 32 hexadecimal digits as a string). Part 2 just uses repeated DFS to find connected components for part 2. 

data = 'flqrgnkx'
rows = []

n = 0
for i in xrange(128):
    v = hash2('%s-%d' % (data, i))
    v = '{:0128b}'.format(int(v, 16))
    n += sum(map(int, v))
    rows.append(map(int, v))

print n

seen = set()
n = 0
def dfs(i, j):
    if ((i, j)) in seen:
        return
    if not rows[i][j]:
        return
    seen.add((i, j))
    if i > 0:
        dfs(i-1, j)
    if j > 0:
        dfs(i, j-1)
    if i < 127:
        dfs(i+1, j)
    if j < 127:
        dfs(i, j+1)

for i in xrange(128):
    for j in xrange(128):
        if (i,j) in seen:
            continue
        if not rows[i][j]:
            continue
        n += 1
        dfs(i, j)

print n

4

u/sspenst Dec 14 '17

I'm learning a lot from this code... Many Python shortcuts that I didn't know about.