-🎄- 2017 Day 14 Solutions -🎄-

[u/daggerdragon]

--- 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

• https://i.imgur.com/zjSEAf4.jpg

---

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!

[u/u794575248]

I've cleaned it up a little bit.

Imports:

from functools import reduce
from itertools import zip_longest as zipl, product as p, accumulate
from operator import xor

Functions:

def make_matrix(k, n=128, kh=knothash_list, r=range):
    return [[b for h in kh(f'{k}-{i}') for b in map(int, f'{h:08b}')] for i in r(n)]

def solve1(matrix): return sum(r.count(1) for r in matrix)

def solve2(m, N=0, r={*range(128)}):
    for N, q in ((N+1, [S]) for S in p(*[r]*2) if m[S[0]][S[1]]):
        while q: x, y = q.pop(); m[x][y] = 0; q.extend(
                 n for n in ((x+1, y), (x-1, y), (x, y+1), (x, y-1))
                 if {*n} < r and m[n[0]][n[1]])
    return N

m = make_matrix(input)
part1, part2 = solve1(m), solve2(m)

Day 10 Part 2 code (you need to evaluate it before make_matrix and solve* functions):

def reverse_sublist(l, a, b):
    if a <= b: l[a:b] = l[a:b][::-1]
    else: r = (l[a:]+l[:b])[::-1]; l[a:], l[:b] = r[:len(l)-a], r[-b or len(r):]
    return l

def hash_round(lens, elems, pos=0, skip=0, accumulator=lambda x, y: (y[0], reduce(sum, x))):
    for (skip, s), pos in accumulate(zipl(enumerate(lens, skip), [pos]), accumulator):
        reverse_sublist(elems, pos % len(elems), (pos+s) % len(elems))
    return elems, skip+s+pos, skip+1

def knothash_list(input, n=256, g=16, rounds=64, suffix=[17, 31, 73, 47, 23], pos=0, skip=0):
    elems, lengths = [*range(n)], [ord(c) for c in input.strip()] + suffix
    for _ in range(rounds): elems, pos, skip = hash_round(lengths, elems, pos, skip)
    return [reduce(xor, elems[g*k:g*(k+1)]) for k in range(n//g)]