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