Advent of Code - Day 13 and 14

Every day I fall farther and farther behind in the Advent of Code, but I figure this will give me something fun to do in the week of Christmas. Days 13 and 14 were a bit rough, but I got through them (with a lot of help).

Day 13

Day 13 basically involved generating a maze and then finding the solution. As you can imagine, this is a well known problem and loads of solutions exist. You can also find the general algorithm for it as well, but I decided to take the easy way out and simply find a JavaScript module that did it for me. I used PathFinding.js from Xueqiao Xu and it worked great. Here's my solution for part 1.


var PF = require('pathfinding');

let maxY = 50;
let maxX = 50;
const MGR_FAV = 1362;
//const MGR_FAV = 10;

//let targetX = 7;
//let targetY = 4;
let targetX = 31;
let targetY = 39;

let cells = [];

for(let x=0;x<maxX;x++) {
    cells[x] = [];
    for(let y=0;y<maxY;y++) {
        let thing = getThing(x,y);
        cells[x][y] = thing;
    }
}

renderMaze(cells);

var pfgrid = new PF.Grid(maxX, maxY);
for(let x=0;x<cells.length;x++) {
    for(let y=0;y<cells[x].length;y++) {
        let v = cells[x][y];
        let walkable = (v == ".");
        pfgrid.setWalkableAt(x,y,walkable);
    }
}
var finder = new PF.AStarFinder();
var path = finder.findPath(1, 1, targetX, targetY, pfgrid);
console.log(path.length-1);

/*
Horrible name, but this returns wall/empty space

Find x*x + 3*x + 2*x*y + y + y*y.
Add the office designer's favorite number (your puzzle input).
Find the binary representation of that sum; count the number of bits that are 1.
If the number of bits that are 1 is even, it's an open space.
If the number of bits that are 1 is odd, it's a wall.
*/
function getThing(x,y) {
//    console.log(x,y);
    let initialResult = (x*x) + (3*x) + (2*x*y) + y + (y*y);
    initialResult += MGR_FAV;
    //http://stackoverflow.com/a/16155417/52160
    let binaryVersion = (initialResult >>> 0).toString(2);
    let bitCount = 0;
    for(let i=0;i<binaryVersion.length;i++) {
        let char = binaryVersion.substr(i,1);
        if(char === "1") bitCount++;
    }
    if(bitCount % 2 === 0) return ".";
    return "#";
}

function renderMaze(cells) {
    /*
    for(let x=0;x<cells.length;x++) {
        for(let y=0;y<cells[x].length;y++) {
            process.stdout.write(cells[x][y]);
        }
        process.stdout.write('\n');
    }
    */
    for(let y=0;y<cells[0].length;y++) {
        for(let x=0;x<cells[y].length;x++) {
            process.stdout.write(cells[x][y]);
        }
        process.stdout.write('\n');        
    }
}

For me the fun part was actually seeing my maze. I didn't render the solution, but would have been easy.

The Maze

Part 2 simply has you find all the cells that are within a certain range. This was simple after I discovered that PathFinder modifies the original data and you need to clone it if you are 'walking' it more than once.


var PF = require('pathfinding');

let maxY = 50;
let maxX = 50;
const MGR_FAV = 1362;


let cells = [];

for(let x=0;x<maxX;x++) {
    cells[x] = [];
    for(let y=0;y<maxY;y++) {
        let thing = getThing(x,y);
        cells[x][y] = thing;
    }
}

//renderMaze(cells);

var pfgrid = new PF.Grid(maxX, maxY);
for(let x=0;x<cells.length;x++) {
    for(let y=0;y<cells[x].length;y++) {
        let v = cells[x][y];
        let walkable = (v == ".");
        pfgrid.setWalkableAt(x,y,walkable);
    }
}
var finder = new PF.AStarFinder();
var found = 0;
for(let x=0;x<maxX;x++) {
    for(let y=0;y<maxY;y++) {
        var gridBackup = pfgrid.clone();
        //good place?
        if(cells[x][y] == ".") {
            var path = finder.findPath(1, 1, x, y, gridBackup);
            if(path.length) {
                var steps = path.length - 1;
                if(steps <= 50) found++;
            }
        }
    }
}
//1242 is too high
console.log('found',found);
/*
Horrible name, but this returns wall/empty space

Find x*x + 3*x + 2*x*y + y + y*y.
Add the office designer's favorite number (your puzzle input).
Find the binary representation of that sum; count the number of bits that are 1.
If the number of bits that are 1 is even, it's an open space.
If the number of bits that are 1 is odd, it's a wall.
*/
function getThing(x,y) {
//    console.log(x,y);
    let initialResult = (x*x) + (3*x) + (2*x*y) + y + (y*y);
    initialResult += MGR_FAV;
    //http://stackoverflow.com/a/16155417/52160
    let binaryVersion = (initialResult >>> 0).toString(2);
    let bitCount = 0;
    for(let i=0;i<binaryVersion.length;i++) {
        let char = binaryVersion.substr(i,1);
        if(char === "1") bitCount++;
    }
    if(bitCount % 2 === 0) return ".";
    return "#";
}

function renderMaze(cells) {
    /*
    for(let x=0;x<cells.length;x++) {
        for(let y=0;y<cells[x].length;y++) {
            process.stdout.write(cells[x][y]);
        }
        process.stdout.write('\n');
    }
    */
    for(let y=0;y<cells[0].length;y++) {
        for(let x=0;x<cells[y].length;x++) {
            process.stdout.write(cells[x][y]);
        }
        process.stdout.write('\n');        
    }
}

Day 14

Day 14 seemed easy enough. Loop from 0 and create a hash of some salt plus the number. Look for 3 matching characters in a row. Remember where you found it. Now keep looping and if you find the same character but with 5 in a row and if the previous match was within one thousand loops, you add it as a valid key. Once you hit 64 keys, stop.

I struggled like crazy with this because I missed an important detail. If you have found the 'closing' 5 character match, it can actually 'close' multiple earlier matches. Credit goes to some smart users on Reddit: the4ner and AustinVeolnaut.


/*
https://www.reddit.com/r/adventofcode/comments/5ioh1b/2016_day_14_part_1_missing_something_stupid_im/
credit goes to 
    https://www.reddit.com/user/the4ner
and
https://www.reddit.com/user/AustinVelonaut
*/

var crypto = require('crypto');


let input = 'qzyelonm';
//let input = 'abc';

let threeKeys = {};
let keys = [];

for(var i=0;i<999999;i++) {
    let test = input + i;
    let hash = crypto.createHash('md5').update(test).digest('hex').toLowerCase();
    let matches5 = hash.match(/(\w)(\1{4})/);

    if(matches5) {
        let match = matches5[0];
        let smatch = match.substr(0,3);

        if(threeKeys[smatch]) {

            let threeKey = threeKeys[smatch];

            for(var x=0;x<threeKey.length;x++) {

                if(i - threeKey[x] <= 1000) {
                    keys.push(threeKey[x]);
                    if(keys.length === 900) {

                        keys = keys.sort(function(a,b) {
                            if(a > b) return 1;
                            if(a < b) return -1;
                            return 0;
                        });
                        console.log(keys[63]);
                        process.exit();
                    }
                }
            }

            delete threeKeys[smatch];
        }
    }


    let matches = hash.match(/(\w)(\1{2})/);
    if(matches) {
        let match = matches[0];
        if(!threeKeys[match]) {
            threeKeys[match] = [i];
        } else {
            threeKeys[match].push(i);
        }
    }

}

Part 2 simply had you re-hash your hash 2017 times, which slowed things down quite a bit, but still returned an answer in about 5 minutes. I saw folks on Reddit who did theirs a heck of a lot faster, but I was ok with five minutes.


var crypto = require('crypto');

let input = 'qzyelonm';
//let input = 'abc';

let threeKeys = {};
let keys = [];

function makeHash(s) {
    for(var x=0;x<2017;x++) {
        s = crypto.createHash('md5').update(s).digest('hex').toLowerCase();
    }
    return s;
}

for(var i=0;i<999999;i++) {
    let test = input + i;
//    let hash = crypto.createHash('md5').update(test).digest('hex').toLowerCase();
    let hash = makeHash(test);
    if(i % 2000 === 0) process.stdout.write('#');
    let matches5 = hash.match(/(\w)(\1{4})/);

    if(matches5) {
        let match = matches5[0];
        let smatch = match.substr(0,3);

        if(threeKeys[smatch]) {

            let threeKey = threeKeys[smatch];

            for(var x=0;x<threeKey.length;x++) {

                if(i - threeKey[x] <= 1000) {
                    keys.push(threeKey[x]);
                    if(keys.length === 900) {

                        keys = keys.sort(function(a,b) {
                            if(a > b) return 1;
                            if(a < b) return -1;
                            return 0;
                        });
                        process.stdout.write('\n');
                        console.log(keys[63]);
                        process.exit();
                    }
                }
            }

            delete threeKeys[smatch];
        }
    }


    let matches = hash.match(/(\w)(\1{2})/);
    if(matches) {
        let match = matches[0];
        if(!threeKeys[match]) {
            threeKeys[match] = [i];
        } else {
            threeKeys[match].push(i);
        }
    }

}

You can find my repo of solutions here: https://github.com/cfjedimaster/adventofcode

Like This?

If you like this article, please consider visiting my Amazon Wishlist or donating via PayPal to show your support. You can also subscribe to the email feed to get notified of new posts.

See Also