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