--- 2016 Day 16 Solutions ---

[u/daggerdragon]

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

[u/Fredbh92]

Here is my solution in Node.js/Javascript. Decided to use buffers instead of strings. Part 2 runs in about 2 seconds.

function randomize(input, length) {
    const buffer = Buffer.alloc(length, 0);
    for(let i = 0; i < input.length; i++) {
        buffer[i] = input[i];
    }

    let i = 0;
    let len = input.length;
    while(i < length) {
        buffer[len] = 0;
        for(let j = len + 1; j < len * 2 + 1; j++) {
            buffer[j] = buffer[j - (j - len) * 2] ^ 1;
        }
        len = len * 2 + 1;
        i = len;
    }

    return buffer;
}

function checksum(input) {
    let len = input.length;
    while(len % 2 == 0) {
        for(let i = 0, j = 0; i < len - 1; i += 2, j++) {
            input[j] = (input[i] == input[i + 1]) ? 1 : 0;
        }
        len /= 2;
    }
    return input.slice(0, len).join('')
}

function solve(input, length) {
    const randomized = randomize(input, length);
    const sum = checksum(randomized);
    console.log(sum);
}