Advent of Code is a set of programming puzzles released every year from 1-25th December much like an advent calendar. Each day has 1 puzzle split into two related parts. I will outline my solutions below with the given example input.
Sorry ahead of time for the wierd code formatting choice.
It is a side effect of the column limit.
1abc2
pqr3stu8vwx
a1b2c3d4e5f
treb7uchet
Part 1 requires for each line to:
- Find the first and last digit
- Concatenate these digits
Then sum up all of these values.
Part 2 is much the same, but it is the first and last instance of a digit
or the written equivalent of that digit.
const lines = inp.split('\n');
const calib = x => {
const isdigit = x => x >= '0' && x <= '9';
const letters = x.split('');
return letters.find(isdigit) + letters.findLast(isdigit);
};
const speltnums = [
'one','two','three','four','five',
'six','seven','eight','nine'
];
const speltregex = new RegExp(
`[0-9]|${speltnums.map(x => `(?=${x})`).join('|')}`, 'g');
const calibspell = x => {
const matches = Array.from(x.matchAll(speltregex));
const _get = y => y[0]
|| `${speltnums.findIndex(z => x.startsWith(z, y.index)) + 1}`;
return _get(matches[0]) + _get(matches.pop());
};
const part1 = lines.reduce((acc,x) => acc+(calib(x)|0),0);
const part2 = lines.reduce((acc,x) => acc+(calibspell(x)|0),0);
Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green
Game 2: 1 blue, 2 green; 3 green, 4 blue, 1 red; 1 green, 1 blue
Game 3: 8 green, 6 blue, 20 red; 5 blue, 4 red, 13 green; 5 green, 1 red
Game 4: 1 green, 3 red, 6 blue; 3 green, 6 red; 3 green, 15 blue, 14 red
Game 5: 6 red, 1 blue, 3 green; 2 blue, 1 red, 2 green
Part 1 is fairly straightforward, we parse each input line, getting a map of each of the rounds, then we filter these based on if they match our criteria, then sum them.
const parseGame = game => {
let [id, info] = game.split(':');
id = id.substr('Game '.length)|0;
const rounds = info.split(';').map(round => {
const bucket = {red:0,green:0,blue:0};
round.split(',').forEach(x => {
const [,num,color] = x.match(/([0-9]+)\s+([a-z]+)/);
bucket[color] = num|0;
});
return bucket;
});
return { id, rounds };
};
const games = inp.split('\n').map(parseGame);
const part1 = games.reduce((acc, x) =>
acc + (x.rounds.some(x =>
x.red > 12 || x.green > 13 || x.blue > 14) ? 0 : x.id), 0);
Part 2 consists of progressively extending a map from zero until it could satisfy a round, then repeating for each round, then we know that we must be able to satisfy the whole game. If we minimally extend it at each step then we also know that we have the minimal amount to satisfy the whole game.
const min = games.map(x => {
const min = { red: 0, green: 0, blue: 0 };
x.rounds.forEach(x => {
Object.keys(x).forEach((key,_,a) => {
if (x[key] > min[key]) {
a.forEach(key => min[key] = Math.max(x[key],min[key]));
}
});
});
return min;
});
const part2 = min.reduce((acc, x) => acc + Object.keys(x).reduce((acc, k) => acc*x[k], 1), 0);
467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..
const isdigit = x => x >= '0' && x <= '9';
const lines = inp.split('\n');
const nums = lines.map(x => Array.from(x.matchAll(/[0-9]+/g)));
const traverseBounds = (x,y,w,f) => {
const t = y - 1; const b = y + 1;
const l = x - 1; const r = x + w;
for (let i = t; i <= b; ++i) {
for (let j = l; j <= r; ++j) {
if (f(lines[i]?.[j],i,j)) return true;
}
}
};
const parts = nums
.map((nums,y) => nums
.filter(num => traverseBounds(num.index, y, num[0].length,
ch => ch && ch !== '.' && !isdigit(ch))))
.flat()
.map(x => x[0]|0);
const part1 = parts.reduce((acc,x) => acc+x);
const pgears = nums.map((nums,y) => nums.map(num => {
const g = [];
traverseBounds(num.index, y, num[0].length, (ch,i,j) => {
if (ch === '*') {
g.push([`${i},${j}`,num[0]]);
}
});
return g;
}).filter(x => x.length)).flat(2);
const pgearsmap = {};
pgears.forEach(([k,v]) => {
pgearsmap[k] ??= [];
pgearsmap[k].push(v);
});
const gears = Object.keys(pgearsmap)
.filter(key => pgearsmap[key].length === 2)
.map(key => pgearsmap[key][0]*pgearsmap[key][1]);
const part2 = gears.reduce((acc,x) => acc+x);
Card 1: 41 48 83 86 17 | 83 86 6 31 17 9 48 53
Card 2: 13 32 20 16 61 | 61 30 68 82 17 32 24 19
Card 3: 1 21 53 59 44 | 69 82 63 72 16 21 14 1
Card 4: 41 92 73 84 69 | 59 84 76 51 58 5 54 83
Card 5: 87 83 26 28 32 | 88 30 70 12 93 22 82 36
Card 6: 31 18 13 56 72 | 74 77 10 23 35 67 36 11
Part 1 is fairly trivial. We find the size of the intersection between the winning set and number set. Then take this size and raise it to the power of 2, and divide by 2 (as if we win 1 we should only have 1 point). Then we sum together these points for all the cards.
Part 2 builds on this by replacing the collection with points with the collection of the proceeding scratchcards, each of which can be collected also.
Upon initial glance this may look like a problem ripe for recursion, but we can instead create a map, and traverse the cards backwards. This is valid as any cards gained past the range of cards we own do not count we can calculate the number of scratchcards gained at each level and use that information later on in the calculation. This solution means that we can do it in linear
-ish time, and we can use a preallocated array as the memoise storage.
const parseCard = card => {
const [win, nums] = card
.split(':')[1]
.split('|')
.map(x => x.split(' ').filter(x => x.trim())
.map(x => x | 0));
return { win, nums };
};
const cards = inp.split('\n').map(parseCard);
const points = cards
.map(x => x.nums.filter(y => x.win.includes(y)).length);
const pmap = new Array(points.length).fill(0);
for (let i = points.length; i--;) {
const p = points[i];
let sum = 0;
for (let j = 1; j <= p; ++j) {
const _p = pmap[i + j];
if (_p !== undefined) {
sum += _p + 1;
}
}
pmap[i] = sum;
}
const part1 = points.reduce((acc,x) => acc+((2**(x-1))|0), 0);
const part2 = pmap.reduce((acc,x) => acc+x)+points.length;
seeds: 79 14 55 13
seed-to-soil map:
50 98 2
52 50 48
soil-to-fertilizer map:
0 15 37
37 52 2
39 0 15
fertilizer-to-water map:
49 53 8
0 11 42
42 0 7
57 7 4
water-to-light map:
88 18 7
18 25 70
light-to-temperature map:
45 77 23
81 45 19
68 64 13
temperature-to-humidity map:
0 69 1
1 0 69
humidity-to-location map:
60 56 37
56 93 4
First, for each map we create a function that checks whether a value is within
src -> src + range, if it is we add
dest - src and return the result otherwise we just return the value.
Then we compose each of these functions together.
Then we find the minimum of calling this for all of our input seeds.
let [seeds, ...maps] = inp.split('\n\n').map(x => x.split('\n'));
seeds = seeds[0].split(':')[1].trim().split(' ').map(x => parseInt(x));
const mapf = maps.map(map => {
map = map.slice(1).map(x => x.split(' ').map(x => parseInt(x)));
return n => {
for (const [dest, src, range] of map) {
if (n >= src && n < src + range) {
return (n - src) + dest;
}
}
return n;
}
});
const f = mapf.reduce((acc, x) => _ => x(acc(_)));
const part1 = Math.min(...seeds.map(f));
Part 2 is a little more involved. The function this time takes a set of ranges as input, then for each entry in the map we check whether our range overlaps the range in any way, if it does we split into subranges accordingly setting an offset on our range to handle the
dest - src mapping. Once we have gathered all of our ranges for a map, then we resolve these ranges by adding the offset to the start and end of these ranges.
Like before, we compose all of these map functions together.
We split our seeds into groups of 2 and have the beginning ranges to our functions be
seed1, seed1+seed2, then we call the composed function for each of our seed ranges and find the minimum of these ranges (the left hand side of the range for each range).
const mapf2 = maps.map(map => {
map = map.slice(1).map(x => x.split(' ').map(x => parseInt(x)));
return ranges => ranges.map(([from,to]) => {
const ranges = [[from,to,0]];
for (const [dest, src, range] of map) {
const diff = dest-src;
let i = 0;
ranges.forEach(([from, to], i) => {
if (from >= src+range) return ++i;
if (from >= src) {
ranges.splice(i--, 1);
if (to < src + range) {
ranges.push([from, to, diff]);
}
else {
ranges.push([from, src+range-1, diff]);
ranges.push([src+range,to,0]);
}
}
else {
if (to < src) return ++i;
ranges.splice(i--, 1);
if (to < src + range) {
ranges.push([from,src-1,0]);
ranges.push([src, to, diff]);
}
else {
ranges.push([from, src-1,0]);
ranges.push([src,src+range-1, diff]);
ranges.push([src+range,to,0]);
}
}
++i;
});
}
return ranges.map(([a,b,d]) => {
a = a+d;
b = b+d;
return a<b ? [a,b] : [b,a];
});
}).flat();
});
const f2 = mapf2.reduce((acc, x) => _ => x(acc(_)));
const sgroups = seeds.reduce((acc,x,i) => (i % 2 ? acc.push([seeds[i - 1],seeds[i-1]+x]) : void 0, acc), []);
const part2 = Math.min(...sgroups.map(x => f2([x])).flat().map(x => x[0]))l
Time: 7 15 30
Distance: 9 40 200
This puzzle boils down to extracting a quadratic equation from the text, then solving it.
We are told that we have some number of seconds, t, to cover more than distance, d, and part of that time is spent pressing a button, a. We only move when we are no longer pressing the button, at a speed predicated by the time we have pressed the button. So our distance D can be expressed as:
D = a * (t - a)
And since we want to cover a distance greater than d we can set up the inequality:
D > d
a * (t - a) > d
-a^2 + at > d
-a^2 + at - d > 0
Using the quadratic formula we can simplify our range to.
(t - sqrt(t*t - 4*d)) / 2
(t + sqrt(t*t - 4*d)) / 2
We then take the range and count the number of integers within it.
const [time, dist] = inp
.split('\n')
.map(x => x.split(':')[1]
.split(' ')
.filter(x => x.trim())
.map(x => parseInt(x)));
const quadrange = (t,d) => {
const quad = Math.sqrt(t*t - 4*d);
const l = (t - quad) / 2;
const r = (t + quad) / 2;
let nl = Math.ceil(l);
let nr = Math.floor(r);
return [nl+(l===nl),nr-(r===nr)];
};
const nways = (t,d) => {
const [l,r] = quadrange(t,d);
return r-l+1;
};
const part1 = time
.map((x,i) => nways(x,dist[i]))
.reduce((acc,x) => acc * x);
const part2 = nways(parseInt(time.join('')), parseInt(dist.join('')));
32T3K 765
T55J5 684
KK677 28
KTJJT 220
QQQJA 483
This is an ordering task. The order is made up of two
sub-orders.
We first calculate the value for the first order, the hand type (this is where the majority of the work is), by checking if we match the hands specified.
The next order, face value, is only required if the hand type is equal. This is calculated by checking each card individually and comparing their associated order in
23456789TJQKA.
We make the points and type object a parameter to compare because it aides us in the next task.
const mkpoints = order => Object.fromEntries(order.split('').map((x,i) => [x, i]));
const createCount = hand =>
Object.entries(hand
.reduce((acc,x) => (acc[x] ??= 0, ++acc[x], acc), {}));
const type = (hand) => { // Requires array of chars
const count = createCount(hand);
const f = n => count.find(([,x]) => x === n);
if (f(5)) return 6;
if (f(4)) return 5;
if (f(3)) return f(2) ? 4 : 3;
if (f(2)) {
if (count.filter(([,x]) => x === 2).length === 2) return 2;
return 1;
}
return 0;
};
const compare = (points, type) => ([h1], [h2]) => {
h1 = h1.split(''); h2 = h2.split('');
const t1 = type(h1); const t2 = type(h2);
if (t1 !== t2) return t1 - t2;
for (let i = 0; i < h1.length; ++i) {
const p1 = points[h1[i]];
const p2 = points[h2[i]];
if (p1 !== p2) return p1 - p2;
}
return 0;
}
const hands = inp.split('\n').map(x => x.split(' '));
const part1 = hands
.slice()
.sort(compare(mkpoints('23456789TJQKA'), type))
.reduce((acc, x, i) => acc + x[1] * (i + 1), 0);
The second task builds upon the first by making all jacks into jokers and changing the face value.
The face value is easy to change, we just move
J to the front:
J23456789TQKA.
The hand type is a little more involved. We switch each of the outer count checks to match on the value minus the amount of jokers we have.
This is fine to do as any places where we would miss attribute a e.g.
J2222 f(3) does not match 4 of a kind; we would match on a prior rule e.g. f(4) for 5 of a kind.
Where this breaks down is when there is a potential full house or 2 pairs, in these cases we need to do a case match on the possibilities that we could have matched. Due to the filtering that the rules prior provide, there are few cases to match.
const type2 = (hand) => {
const count = createCount(hand);
const f = n => count.find(([,x]) => x === n);
const fa = n => count.filter(([,x]) => x === n).length;
const jokerOffset = count.find(x => x[0] === 'J')?.[1] || 0;
if (jokerOffset)
count.splice(count.findIndex(([c]) => c === 'J'), 1);
if (f(5 - jokerOffset) || jokerOffset === 5) return 6;
if (f(4 - jokerOffset)) return 5;
if (f(3 - jokerOffset)) {
// JJabc Jaabb aabbb
switch (jokerOffset) {
case 0: return f(2) ? 4 : 3;
case 1: return fa(2) === 2 ? 4 : 3;
case 2: return 3;
}
}
if (f(2 - jokerOffset)) {
// Jabcd aabbc aabcd
if (jokerOffset) return 1;
if (fa(2) === 2) return 2;
return 1;
}
return 0;
}
const part2 = hands
.sort(compare(mkpoints('J23456789TQKA'), type2))
.reduce((acc, x, i) => acc + x[1] * (i + 1), 0);
LLR
AAA = (BBB, BBB)
BBB = (AAA, ZZZ)
ZZZ = (ZZZ, ZZZ)
LR
11A = (11B, XXX)
11B = (XXX, 11Z)
11Z = (11B, XXX)
22A = (22B, XXX)
22B = (22C, 22C)
22C = (22Z, 22Z)
22Z = (22B, 22B)
XXX = (XXX, XXX)
Our data represents a graph preceeded by some instructions on how to navigate that graph. Part 1 requires us to count the number of times we have to execute our set of instructions, to go from
AAA to
ZZZ.
const [dir,mapdata] = inp.split('\n\n');
const map = Object.fromEntries(mapdata.split('\n').map(x => {
const [node, info] = x.split(' = ');
const edges = info.matchAll(/[A-Z0-9]{3}/g);
return [node, [...edges].map(x => x[0])];
}));
const navigate = (from, f) => {
let steps = 0;
let node = from;
while (!f(node)) {
for (const ch of dir.split(''))
node = map[node][ch === 'L' ? 0 : 1];
steps += dir.length;
}
return steps;
}
const part1 = navigate('AAA', node => node === 'ZZZ');
Part 2 differs somewhat in that instead of starting from a single node, we need to simultaneously navigate the graph from each node ending with
A to a node ending with
Z. We can skip over most of the combinations by instead getting how many steps each individual node will take, then taking the least common multiple for them.
const part2 = (() => {
const allNodes = Object.keys(map);
const endNodes = allNodes.filter(x => x.endsWith('Z'));
const stepCount = allNodes
.filter(x => x.endsWith('A'))
.map(x => navigate(x, node => node.endsWith('Z')));
const gcd = (n,m) => {
let r = m;
do {
m = n; n = r;
r = m % n;
} while (r !== 0);
return n;
};
return stepCount.reduce((acc,x) => acc*x/gcd(acc,x));
})();
})();
0 3 6 9 12 15
1 3 6 10 15 21
10 13 16 21 30 45
Part 1 asks us to extrapolate a value forward based on previous values. We find the difference between consecutive pairs of values for the sequence, producing a new sequence. We continue to produce sequences until all values are zero. Then we append zeros to the end and correct them according to the previous value and the expected difference.
const lines = inp
.split('\n')
.map(x => x.split(' ').map(x => parseInt(x)));
const diff = nums => {
const diff = Array(nums.length - 1);
for (let i = 1; i < nums.length; ++i) {
diff[i - 1] = nums[i] - nums[i - 1];
}
return diff;
}
const diffs = lines.map(line => {
const diffs = [line];
while (diffs[diffs.length - 1].some(x => x !== 0)) {
diffs.push(diff(diffs[diffs.length - 1]));
}
return diffs;
});
const extend = diffs => {
diffs.forEach(diff => diff.push(0));
for (let i = diffs.length - 1; i--;) {
const diff = diffs[i + 1].slice(-1)[0];
const prev = diffs[i][diffs[i].length - 2];
diffs[i][diffs[i].length - 1] = prev + diff;
}
};
diffs.forEach(extend);
const part1 = diffs.reduce((acc, x) => acc + x[0].pop(), 0);
Part 2 is much the same but we extrapolate backwards in the sequence.
const backextend = diffs => {
diffs.forEach(diff => diff.unshift(0));
for (let i = diffs.length - 1; i--;) {
const diff = diffs[i + 1][0];
const prev = diffs[i][1];
diffs[i][0] = prev - diff;
}
};
diffs.forEach(backextend);
const part2 = diffs.reduce((acc, x) => acc + x[0][0], 0);
7-F7-
.FJ|7
SJLL7
|F--J
LJ.LJ
...........
.S-------7.
.|F-----7|.
.||.....||.
.||.....||.
.|L-7.F-J|.
.|..|.|..|.
.L--J.L--J.
...........
Part 1 requires us to find the ⌊(length of a cycle containing
S) / 2⌋. First I build the graph, returning the edge map and starting position. I use this starting position to assign a distance for each neighbour of that node, then for their neighbours and so on until we reach the furthest point.
inp = inp.split('\n');
const nodeeq = (a,b) => a[0] === b[0] && a[1] === b[1];
const keyToEdge = k => k.split(',').map(x => parseInt(x));
const createGraph = inp => {
const width = inp[0].length;
const height = inp.length;
const edges = {};
const edge = (x1,y1,x2,y2) => {
const a = [x1,y1];
const b = [x2,y2];
edges[a] ??= [];
edges[a].push(b);
}
const S = [];
for (let y = 0; y < height; ++y) {
for (let x = 0; x < width; ++x) {
const ch = inp[y][x];
switch (ch) {
case '.': break; case 'S': S.push(x,y); break;
case '|': edge(x,y,x,y+1); edge(x,y,x,y-1); break;
case '-': edge(x,y,x+1,y); edge(x,y,x-1,y); break;
case 'L': edge(x,y,x,y-1); edge(x,y,x+1,y); break;
case 'J': edge(x,y,x,y-1); edge(x,y,x-1,y); break;
case '7': edge(x,y,x,y+1); edge(x,y,x-1,y); break;
case 'F': edge(x,y,x,y+1); edge(x,y,x+1,y); break;
}
}
}
Object.keys(edges).forEach(key => edges[key].some(to => nodeeq(S,to)) ? edge(S[0],S[1],...keyToEdge(key)) : void 0);
return { S, edges };
};
const getDist = ({ S, edges }) => {
const dist = {};
const queue = [S];
let currDist = 0;
while (queue.length) {
for (let i = queue.length; i--;) {
const item = queue.shift();
if (dist[item]) continue;
dist[item] = currDist;
queue.push(...edges[item]);
}
++currDist;
}
return dist;
};
const graph = createGraph(inp);
const dist = getDist(graph);
const part1 = Math.max(...Object.values(dist));
Part 2 requires us to find the number of tiles enclosed by the aforementioned cycle. I do this by marking cells that we know are on one side with 1 value, and cells on the otherside with another value. Then I expand the remaining cells until all cells are filled. This does not tell us which of the numbers are on the inside or outside, but we can just try twice :D.
I figured there must be a better way to do this, and there is:
Shoelace formula.
const getEnclosed = ({ S, edges }, dist) => {
inp = inp
.map((x,i) => x.split('')
.map((y,j) => dist[[j,i]] ? y : '.'));
let dir = edges[S]
.map(([x,y]) => [x-S[0],y-S[1]])
.reduce((acc, x) => [acc[0]+x[0],acc[1]+x[1]]); // The direction of the marked cell
let nnode = edges[S][0]; // Where to go next
let node = S.slice();
let mark = 'M'; let omark = 'm';
const queue = [];
const setdir = n => dir =
dir[0]+n[0] === 0 && dir[1]+n[1] === 0
? ([mark,omark]=[omark,mark], n)
: n;
do {
const [x,y] = node;
const [dx,dy] = dir;
const s = (x,y, m) => {
const r = inp[y];
if (r && r[x] === '.') {
r[x] = m;
queue.push([x,y]);
}
};
s(x+dx,y+dy, mark);
s(x-dx,y-dy, omark);
s(x+dx,y-dy, omark);
s(x-dx,y+dy, omark);
switch (inp[nnode[1]][nnode[0]]) {
case 'L': setdir([1,-1]); break;
case 'J': setdir([-1,-1]); break;
case '7': setdir([-1,1]); break;
case 'F': setdir([1,1]); break;
}
[node,nnode]=[nnode,node];
nnode = edges[node].find(x => !nodeeq(x, nnode));
} while (!nodeeq(S, node));
// Expand
while (queue.length) {
const [x,y] = queue.shift();
const ch = (x,y) => inp[y]?.[x];
const m = ch(x,y);
const setAndAdd = (x,y) => (inp[y][x] = m, queue.push([x,y]));
if (ch(x+1,y) === '.') setAndAdd(x+1,y);
if (ch(x-1,y) === '.') setAndAdd(x-1,y);
if (ch(x,y+1) === '.') setAndAdd(x,y+1);
if (ch(x,y-1) === '.') setAndAdd(x,y-1);
}
const count = c => inp
.reduce((acc, x) => acc + x
.reduce((acc, x) => acc + (x === c ? 1 : 0), 0), 0);
return [count('m'), count('M')];
};
const part2 = getEnclosed(graph, dist);
return [part1,part2];
...#......
.......#..
#.........
..........
......#...
.#........
.........#
..........
.......#..
#...#.....
We get the coordinates of every
# in the input. Then we alter these coordinates based on whether or not there is an empty column or row (consisting only of
.) that would affect them. We multiply the number of empty rows and cols before a coordinate, then add this difference at the end. We then calculate the Manhattan distance between each pair of coordinates, and sum the total distance.
const expand = (coords, by) => {
const rows = inp.split('\n').map((x,i) => [i, x]);
const cols = inp
.split('\n')
.map(x => x.split(''))
.reduce((acc, x) => {
x.forEach((x, i) => acc[i][1].push(x));
return acc;
}, Array(rows[0][1].length)
.fill(0)
.map((x,i) => [i, []]))
.map(x => [x[0], x[1].join('')]);
const isEmpty = ([,x]) => !x.replaceAll('.','');
const expandRows = rows.filter(isEmpty).map(x => x[0]);
const expandCols = cols.filter(isEmpty).map(x => x[0]);
return coords.map(([x,y]) => {
let diffx = 0;
let diffy = 0;
for (const col of expandCols) {
if (col < x) diffx += by - 1;
}
for (const row of expandRows) {
if (row < y) diffy += by - 1;
}
return [x+diffx, y+diffy];
});
};
const dist = coords => {
const calcDist = (x1, y1, x2, y2) =>
Math.abs(x1 - x2) + Math.abs(y1 - y2);
const dists = coords
.map(([x1,y1],i) => coords
.map(([x2, y2],j) => j > i
? calcDist(x1, y1, x2, y2)
: void 0))
.flat()
.filter(x => x);
return dists;
};
const coords = inp
.split('\n')
.map((x,i) => x
.split('')
.map((x,j) => x === '#' ? [[j,i]] : []))
.flat(2);
const part1 = dist(expand(coords, 2))
.reduce((acc, x) => acc+x);
Part 2 requires us to, instead of doubling, multiply each of the distances by
1,000,000.
const part2 = dist(expand(coords, 1_000_000))
.reduce((acc, x) => acc+x);
My computer got watered shortly after this which put me a bit off course for this, I will eventally get back to it.