So yep - I definitely didn't finish Advent of Code before Christmas, but I'm mostly done (20 out of 25 days) and I plan to keep at it in the next week or so. This post will cover a bunch of days, so forgive the length!
Day 15
Day 15 had an interesting concept. Given a set of discs with holes in them that turn every second, at what point would you be able to drop a ball so that as it fell, it would always hit holes. The ball falls through one disc at a time, so you have to simulate the discs turning and the ball trying to fall over time. The solution involves finding out what time to drop the ball so it falls perfectly.
My solution was a brute force solution that was very slow:
let initTime = 0;
let input2 = `Disc #1 has 5 positions; at time=0, it is at position 4.
//Disc #2 has 2 positions; at time=0, it is at position 1.`;
let input = `Disc #1 has 5 positions; at time=0, it is at position 2.
Disc #2 has 13 positions; at time=0, it is at position 7.
Disc #3 has 17 positions; at time=0, it is at position 10.
Disc #4 has 3 positions; at time=0, it is at position 2.
Disc #5 has 19 positions; at time=0, it is at position 9.
Disc #6 has 7 positions; at time=0, it is at position 0.`;
function initDiscs(s) {
let discs = [];
s.split('\n').forEach(function(i) {
let parts = i.split(' ');
let numpos = Number(parts[3]);
let inipos = Number(parts[11].substr(0, parts[11].length-1));
discs.push({name:parts[1], numpos:numpos, inipos:inipos, pos:inipos});
});
return discs;
}
function moveDiscs(d) {
d.forEach(function(disc) {
disc.pos++;
if(disc.pos == disc.numpos) disc.pos = 0;
//console.log('Disc '+disc.name+' is at position '+disc.pos);
});
return d;
}
sanity = 0;
while(1) {
discs = initDiscs(input);
//do initial moves
for(x=0;x<initTime;x++) { discs = moveDiscs(discs); }
time = initTime++;
// console.log('TESTING TIME '+time);
if(time % 10000 === 0) process.stdout.write('#');
let capsule = 0;
done = false;
while(!done) {
time++;
discs = moveDiscs(discs);
// console.log('At time '+time+' the capsule is at '+capsule);
//move the discs
if(discs[capsule].pos === 0) {
// console.log('i can fall');
capsule++;
if(capsule === discs.length) {
done = true;
console.log('\nSuccess for time '+(initTime-1));
process.exit();
}
} else {
done = true;
// console.log('Failure for time '+(initTime-1));
}
sanity++;
//if(sanity > 3) process.exit();
}
}
//right answer was 148737
You'll notice the last line is a comment with the right answer. How did I get that? I cheated. This Reddit post points out that it can be solved with simple math. Insane.
/*
https://www.reddit.com/r/adventofcode/comments/5ifn4v/2016_day_15_solutions/db7ttta/
*/
function d1(t) { return ((t+2) % 5 == 0); };
function d2(t) { return ((t+7) % 13 == 0); };
function d3(t) { return ((t+10) % 17 == 0); };
function d4(t) { return ((t+2) % 3 == 0); };
function d5(t) { return ((t+9) % 19 == 0); };
function d6(t) { return ((t+0) % 7 == 0); };
let t = 0;
while(true) {
if(
d1(t+1) &&
d2(t+2) &&
d3(t+3) &&
d4(t+4) &&
d5(t+5) &&
d6(t+6)
) {
console.log(t);
process.exit();
}
t++;
}
The second part of the day simply added another disc - so my solution simply took the above solution and added the additional logic. So yep - I cheated - but it was still cool.
Day 16
Day 16 was an easy one. Given an input string, you simply transform it in such a way that it grows to a certain point. When it hits that point, you generater a checksum that shrinks the string again. The second part simply changes the desired length. Here is my solution.
let input = '10001110011110000';
//let neededSize = 272;
let neededSize = 35651584;
let result = input;
while(result.length <= neededSize) {
result = doIt(result);
}
console.log('Done with initial...');
//we only want neededSize
result = result.substr(0, neededSize);
console.log('Checksum:');
console.log(checkSum(result));
//console.log(doIt('111100001010')=='1111000010100101011110000');
function doIt(a) {
let b = reverse(a);
//prob could be regex
let newB = '';
for(let i=0;i<b.length;i++) {
let char = b.substr(i, 1);
if(char === '1') {
newB += '0';
} else if(char === '0') {
newB += '1';
} else newB += char;
}
return a + '0' + newB;
}
function reverse(s) {
let result = '';
for(let i=0;i<s.length;i++) {
result = s.substr(i,1) + result;
}
return result;
}
function checkSum(s) {
let done = false;
while(!done) {
let checksum = '';
for(var i=0;i<s.length;i=i+2) {
let set1 = s.substr(i,1);
let set2 = s.substr(i+1,1);
if(set1 === set2) checksum += '1';
else checksum += '0';
}
if(checksum.length % 2 === 1) {
return checksum;
} else {
s = checksum;
}
}
}
Day 17
Day 17 involves moving through a room where the possible allowed directions based on a hash of a path you've taken through the room. Yeah, weird. The first part involves just finding the shortest path.
var crypto = require('crypto');
function hash(s) {
return crypto.createHash('md5').update(s).digest('hex');
}
let pos = {x:1, y:1};
var input = 'njfxhljp';
let path = '';
let sanity = 0;
let doIt = true;
while(doIt) {
var h = hash(input);
var dir = h.substr(0,4);
console.log(dir);
let doors = checkDoors(dir);
console.log(doors);
// prefer R or D if we can
if(doors.d && pos.y <=3) {
console.log('move down');
pos.y++;
input += 'D';
path += 'D';
} else if(doors.r && pos.x <= 3) {
console.log('move right');
pos.x++;
input += 'R';
path += 'R';
} else if(doors.u && pos.y > 1) {
console.log('move up');
pos.y--;
input += 'U';
path += 'U';
} else if(doors.l && pos.x > 1) {
console.log('move left');
pos.x--;
input += 'L';
path += 'L';
}
//are we at 4 4?
if(pos.x === 4 && pos.y === 4) {
console.log('WIN');
console.log(path);
doIt = false;
}
sanity++; if(sanity > 10) process.exit();
}
function checkDoors(s) {
let u = s.substr(0,1);
let d = s.substr(1,1);
let l = s.substr(2,1);
let r = s.substr(3,1);
let result = {};
result.u = isOpen(u);
result.d = isOpen(d);
result.l = isOpen(l);
result.r = isOpen(r);
return result;
}
function isOpen(x) {
if(x === 'b' || x === 'c' || x === 'd' || x === 'e' || x === 'f') return true;
return false;
}
The second part asks you to reverse this and find the longest path. I couldn't do it so I cheated again using this solution I could paste in my browser console: https://www.reddit.com/r/adventofcode/comments/5isvxv/2016_day_17_solutions/dbatx5a/
Day 18
Day 18 was another simple one. The concept is that you are in a room full of tiles and traps and you have to figure out how many safe tiles there are. You generate the room data by simply taking an initial string of room data and generating one line at a time, where each line is based on the last line. Simple! Part 2 just increases the number of lines.
//let totalRows = 40;
//part 2
let totalRows = 400000;
let input = '.^.^..^......^^^^^...^^^...^...^....^^.^...^.^^^^....^...^^.^^^...^^^^.^^.^.^^..^.^^^..^^^^^^.^^^..^';
let room = [];
//let input = '.^^.^.^^^^';
room.push(input);
for(var i=0;i<totalRows-1;i++) {
let newRow = getRow(room[room.length-1]);
room.push(newRow);
}
//console.log(room);
let safeTiles = 0;
for(var i=0;i<room.length;i++) {
let row = room[i];
for(var x=0;x<row.length;x++) {
let char = row.substr(x,1);
if(char === '.') safeTiles++;
}
}
//2047 is too high
console.log(safeTiles);
function getRow(input) {
let newRow = '';
for(var i=0;i<input.length;i++) {
let left, center, right;
if(i === 0) {
left = '.';
} else {
left = input.substr(i-1,1);
}
center = input.substr(i,1);
if(i < input.length -1) {
right = input.substr(i+1,1);
} else {
right = '.';
}
// console.log('for '+i+ ' l='+left+' c='+center+' r='+right);
if(
(left === '^' && center === '^' && right === '.')
||
(center === '^' && right === '^' && left === '.')
||
(left === '^' && center === '.' && right === '.')
||
(right === '^' && left === '.' && center === '.')
) {
newRow += '^';
} else {
newRow += '.';
}
}
return newRow;
}
Day 19
Day 19 involved simulating a game where elves sit in a circle and each elf takes the gifts of the person to their left. When you lose your gifts, you're taken out of the circle. The idea is to figure out which elf will get all the gifts. Part one was easy enough:
//let numElves = 5;
let numElves = 3005290;
let elves = [];
for(var i=0;i<numElves;i++) {
elves[i] = 1;
}
let done = false;
let sanity = 0;
while(!done) {
//go around
for(var i=0;i<numElves;i++) {
let nextElfPos;
// console.log('Working with elf '+(i+1));
if(elves[i] > 0) {
/*
if(i < numElves-1) {
nextElfPos = i+1;
} else {
nextElfPos = 0;
}
*/
// nextElfPos is the next elf with presents
if(i < numElves-1) {
nextElfPos = i+1;
} else {
nextElfPos = 0;
}
while(elves[nextElfPos] === 0) {
nextElfPos++;
if(nextElfPos == numElves) nextElfPos = 0;
}
elves[i] += elves[nextElfPos];
elves[nextElfPos] = 0;
// console.log('Took from elf '+(nextElfPos+1));
if(elves[i] === numElves) {
console.log('Winner for '+(i+1));
process.exit();
}
} else {
// console.log('No presents, skipping.');
}
}
sanity++;
if(sanity > 2000) { console.log('Abort'); process.exit(); }
}
Part two added the twist that instead of taking the gift from the elf next to you, you take the one "across" from you. Figuring out which elf to take from was incredibly difficult for me. My logic was:
the elf across from me is: floor(len/2)+1 offset
When len is the number of elves. My solution tooked about 40 minutes to run and ended up giving the wrong answer. (I checked it into the repo anyway.) This solution from Reddit ran near instantly:
function solve(input) {
let target = +input, pow = Math.pow(3, target.toString(3).length - 1)
if (pow === target) return pow
else if (pow >= target / 2) return target - pow
else return pow + (2 * (target - 2 * pow))
}
console.log(solve(3005290));
Some people are scary smart.
Day 20
Day 20 seemed simple at first. Imagine you have a set of restricted numbers:
0-2 5-9 4-8
Given that set, what is the first allowed number? You can see it is three. Your input is a huge set of ranges like this. My solution was to sort by the lower end of the range and then loop over the ranges creating a smaller set of ranges. For example, imagine:
0-50 30-90
You can rewrite that as 0-90. Now imagine:
0-50 51-60
That can be merged into 0-60. While this seems simple, this took me forever to get working right.
const fs = require('fs');
const input = fs.readFileSync('./input.txt','utf8');
let gates = [];
let lines = input.split('\n');
const MAX = 4294967295;
lines.forEach((l)=>{
let [min,max] = l.split('-');
gates.push({min:Number(min), max:Number(max)});
});
gates.sort(function(a, b) {
if(a.min < b.min) return -1;
if(a.min > b.min) return 1;
return 0;
});
console.log('len is '+gates.length);
//simplify gates
for(var i=1;i<gates.length;i++) {
let thisGate = gates[i];
let lastGate = gates[i-1];
/*
imagine:
last 0-100
this: 49-150
we can say that's the same as 0-150
imagine:
last 0-100
this: 101-150
*/
if(
(thisGate.min > lastGate.min && thisGate.min < lastGate.max && thisGate.max > lastGate.max && thisGate.max <= MAX)
||
(thisGate.min-1 == lastGate.max && thisGate.max <= MAX)) {
let newGate = { min:lastGate.min, max:thisGate.max};
// remove i
gates[i-1] = newGate;
gates.splice(i, 1);
//reset i
i=0;
}
}
console.log('new len is '+gates.length);
//console.log('Winner='+format(gates[0].max+1));
console.log('Winner='+(gates[0].max+1));
function format(r) {
return new Intl.NumberFormat().format(r);
}
Part two had you determining how many 'available' numbers were allowed.
const fs = require('fs');
const input = fs.readFileSync('./input.txt','utf8');
let gates = [];
let lines = input.split('\n');
const MAX = 4294967295;
lines.forEach((l)=>{
let [min,max] = l.split('-');
gates.push({min:Number(min), max:Number(max)});
});
gates.sort(function(a, b) {
if(a.min < b.min) return -1;
if(a.min > b.min) return 1;
return 0;
});
console.log('len is '+gates.length);
//simplify gates
for(var i=1;i<gates.length;i++) {
let thisGate = gates[i];
let lastGate = gates[i-1];
/*
imagine:
last 0-100
this: 49-150
we can say that's the same as 0-150
imagine:
last 0-100
this: 101-150
*/
/*
if inside last one, just plain kill it
*/
if(thisGate.min > lastGate.min && thisGate.max < lastGate.max) {
gates.splice(i, 1);
//reset i
i=0;
}
else if(
(thisGate.min > lastGate.min && thisGate.min < lastGate.max && thisGate.max > lastGate.max && thisGate.max <= MAX)
||
(thisGate.min-1 == lastGate.max && thisGate.max <= MAX)) {
let newGate = { min:lastGate.min, max:thisGate.max};
// remove i
gates[i-1] = newGate;
gates.splice(i, 1);
//reset i
i=0;
}
}
console.log('new len is '+gates.length);
let allowed = 0;
for(var i=1;i<gates.length;i++) {
if(gates[i].min > gates[i-1].max) {
//console.log(gates[i], gates[i-1],gates[i].min-gates[i-1].max);
allowed += gates[i].min - gates[i-1].max - 1;
}
}
// 6460818460 is too much
console.log(allowed);
function format(r) {
return new Intl.NumberFormat().format(r);
}
Whew! Only five more days to solve. If I can solve two of them without cheating I'll consider myself lucky.
You can find my repo of solutions here: https://github.com/cfjedimaster/adventofcode