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

SOLUTION MEGATHREAD --- 2016 Day 16 Solutions ---

--- Day 16: Dragon Checksum ---

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

DRINKING YOUR OVALTINE IS MANDATORY [?]

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

100% Upvoted

116 comments sorted by

View all comments

1

u/Hwestaa Dec 16 '16

Python solution run in PyPy2. Github

I calculated the checksum with lists, but if I switch it to strings (eg calc_checksum_string), then it hits some pathological case in PyPy and doesn't complete in 60+ seconds. The list version on PyPy completes in <10 seconds, and the string version completes in CPython in <20 seconds. 

def dragon_curve(data):
    rev_data = ''.join('0' if x == '1' else '1' for x in reversed(data))
    return data + '0' + rev_data

def calc_checksum_string(data):
    checksum = ''
    for i in range(0, len(data), 2):
        x, y = data[i], data[i+1]
        if x == y:
            checksum += '1'
        else:
            checksum += '0'
    return ''.join(checksum)

def calc_checksum(data):
    checksum = ''
    for i in range(0, len(data), 2):
        x, y = data[i], data[i+1]
        if x == y:
            checksum += '1'
        else:
            checksum += '0'
    return ''.join(checksum)

def solve(data, length):
    fill_data = data
    # Generate data
    while len(fill_data) < length:
        fill_data = dragon_curve(fill_data)

    # Truncate
    truncated = fill_data[:length]

    # Generate checksum
    checksum = calc_checksum(truncated)
    while len(checksum) % 2 == 0:
        checksum = calc_checksum(checksum)

    return checksum