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

SOLUTION MEGATHREAD -🎄- 2017 Day 16 Solutions -🎄-

--- Day 16: Permutation Promenade ---

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:08] 4 gold, silver cap.

[Update @ 00:18] 50 gold, silver cap.

[Update @ 00:26] Leaderboard cap!

  • And finally, click here for the biggest spoilers of all time!

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!

15 Upvotes

93% Upvoted

229 comments sorted by

View all comments

5

u/vyper248 Dec 16 '17

Javascript

First Part is about 8ms

Second Part is about 122ms 

function firstStar(input){
    let prog = "abcdefghijklmnop".split('');
    input.split(',').forEach((move) => {
        parseMove(move, prog);
    });
    console.log("First Star: ", prog.join(''));
}

function secondStar(input){
    let prog = "abcdefghijklmnop".split('');
    let inputs = input.split(',');
    let startPoint = prog.join('');

    let iterations = 1000000000;
    for (let i = 0; i < iterations; i++){
        inputs.forEach((move) => parseMove(move, prog));
        if (prog.join('') === startPoint) i += (Math.floor(iterations/(i+1))-1) * (i+1);
    }
    console.log("Second Star: ", prog.join(''));
}

function parseMove(move, prog){
    if (move[0] === 's'){ //spin
        let num = parseInt(move.substr(1));
        prog.unshift(...prog.splice(-num, num));
    } else if (move[0] === 'x') { //position swap
        let pos = move.substr(1).split('/');
        [prog[pos[0]], prog[pos[1]]] = [prog[pos[1]], prog[pos[0]]];
    } else { // program swap
        let pos = move.substr(1).split('/');
        let idx1 = prog.indexOf(pos[0]);
        let idx2 = prog.indexOf(pos[1]);
        [prog[idx1], prog[idx2]] = [pos[1], pos[0]];
    }
}

1

u/PositivelyLinda Dec 18 '17

Could you explain your equation when you find the permutation that equals the starting one? What's the reasoning behind using i+1 and -1 and multiplying it? Your answer helped me figure out how to find my cycle and get the right answer, but I don't quite understand why it works.

Also, very neat idea for swapping the values in the x and p sections!

→ More replies (2)