Sean McLemon | Advent of Code

2016-12-16 - Dragon Checksum

(original .ipynb)

puzzle_input_str = "10001110011110000"


def swap(c):
    return 1 if c == 0 else 0


def dragon_curve(a):
    b = [swap(c) for c in a[::-1]]
    return a + [0] + b


def stringify(curve):
    return "".join(str(d) for d in curve)


def unstringify(pattern):
    return [ int(c) for c in pattern ]


assert "100" == stringify(dragon_curve([1]))
assert "001" == stringify(dragon_curve([0]))
assert "11111000000" == stringify(dragon_curve(unstringify("11111")))
assert "1111000010100101011110000" == stringify(dragon_curve(unstringify("111100001010")))


def checksum(pattern, length):
    pattern = pattern[:length]
    while len(pattern) % 2 == 0:
        i = 0
        new_pattern = list()
        while i < len(pattern):
            a = pattern[i]
            b = pattern[i+1]
            new_pattern.append(1 if a == b else 0)            
            i += 2
        pattern = new_pattern
    return pattern


assert "100" == stringify(checksum(unstringify("110010110100"), 12))
assert "01100" == stringify(checksum(unstringify("10000011110010000111110"), 20))


def part_one(initial_state, disc_length):
    state = unstringify(initial_state)
    
    while len(state) < disc_length:
        state = dragon_curve(state)
        
    return stringify(checksum(state, disc_length))


assert "01100" == part_one("10000", 20)

print("part one:", part_one(puzzle_input_str, 272))

part one: 10010101010011101

# print("part one:", part_one(puzzle_input_str, 35_651_584))
#      ^
#      |
# ok this takes far too much memory for the little DigitalOcean droplet
# that my notebook lives on (which iirc has 2GB) so I ran it locally to get the answer below
print("part two: 01100111101101111")

part two: 01100111101101111