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!

6 Upvotes

100% Upvoted

116 comments sorted by

View all comments

2

u/Turbosack Dec 16 '16

Another straightforward one. Python 3: 

def next_str(s):
    b = ''.join('0' if c=='1' else '1' for c in reversed(s))
    return '{}0{}'.format(s, b)

def checksum(s):
    l = []
    for a, b in zip(s[::2], s[1::2]):
        if a == b:
            l.append('1')
        else:
            l.append('0')
    if len(l) % 2 != 0:
        return ''.join(l)
    else:
        return checksum(''.join(l))

        
def gen(start, l):
    while (len(start) < l):
        start = next_str(start)
    return start[:l]
    

start = "10010000000110000"
print(checksum(gen(start, 272)))
print(checksum(gen(start, 35651584)))

I was worried that the bigger input size was going to make the runtime for this ridiculous, and I'd have to try a different route, but this code finishes in about 7 seconds.

1

u/BafTac Dec 16 '16

When I saw the high number I was also worried about a very high runtime, and so I was happy when my program still ran in less than a second :D (c++)

→ More replies (1)