Advent of Code: 2020 Day 1Advent of Code: 2020 Day 2Advent of Code: 2020 Day 3Advent of Code: 2020 Day 4Advent of Code: 2020 Day 5Advent of Code: 2020 Day 6Advent of Code: 2020 Day 7Advent of Code: 2020 Day 8Advent of Code: 2020 Day 9Advent of Code: 2020 Day 10Advent of Code: 2020 Day 11Advent of Code: 2020 Day 12Advent of Code: 2020 Day 13Advent of Code: 2020 Day 14Advent of Code: 2020 Day 15Advent of Code: 2020 Day 16Advent of Code: 2020 Day 17Advent of Code: 2020 Day 18Advent of Code: 2020 Day 19Advent of Code: 2020 Day 21Advent of Code: 2020 Day 22Advent of Code: 2020 Day 23Advent of Code: 2020 Day 24Advent of Code: 2020 Day 25
Advent of Code: 2020 Day 20
function parse(input) {
const tilesInput = input.split("\n\n").map((t) => t.split("\n"));
return tilesInput.map((t) => ({
id: Number(t[0].slice(5, -1)),
grid: t.slice(1).map((row) => row.split(""))
}));
}
function edges(tile) {
const getEdgeCols = (grid) => {
const lCol = new Array();
const rCol = new Array();
grid.forEach((row) => {
lCol.push(row[0]);
rCol.push(row[row.length - 1]);
});
return [lCol, rCol];
};
const [lCol, rCol] = getEdgeCols(tile.grid);
return [
tile.grid[0].join(""),
tile.grid[tile.grid.length - 1].join(""),
lCol.join(""),
rCol.join("")
];
}
function equalID(tile1, tile2) {
return tile1.id === tile2.id;
}
function neighbours(tile, tiles) {
const otherTiles = tiles.filter((t) => !equalID(tile, t));
const es = edges(tile);
const es2 = new Set(es.concat(es.map((s) => s.split("").reverse().join(""))));
return otherTiles.filter((t) => {
const otherEdges = new Set(edges(t));
return AOC.intersection(es2, otherEdges).size > 0;
});
}
function corners(tiles) {
return tiles.filter((t) => neighbours(t, tiles).length === 2);
}
function part1(input) {
const tiles = parse(input);
const cornerTiles = corners(tiles);
return AOC.product(cornerTiles.map((t) => t.id));
}
Side = ({
Top: "Top",
Bottom: "Bottom",
Left: "Left",
Right: "Right"
})
function opposite(side) {
switch (side) {
case Side.Top:
return Side.Bottom;
case Side.Bottom:
return Side.Top;
case Side.Left:
return Side.Right;
case Side.Right:
return Side.Left;
}
}
function edgeOn(side, tile) {
switch (side) {
case Side.Top:
return tile.grid[0].join("");
case Side.Right:
const rCol = new Array();
tile.grid.forEach((row) => {
rCol.push(row[row.length - 1]);
});
return rCol.join("");
case Side.Bottom:
return tile.grid[tile.grid.length - 1].join("");
case Side.Left:
const lCol = new Array();
tile.grid.forEach((row) => {
lCol.push(row[0]);
});
return lCol.join("");
}
}
function tileVariants(tile) {
// Creates a tile with contents flipped horizontally.
const flipH = (t) => {
const newGrid = AOC.cloneArray(t.grid).reverse();
return { id: t.id, grid: newGrid };
};
// Creates a tile with the contents filpped verttically.
const flipV = (t) => {
const newGrid = AOC.cloneArray(t.grid).map((row) => row.reverse());
return { id: t.id, grid: newGrid };
};
// Transpose a tile's cells (rows become columns, columns become rows)
const transpose = (arr) => {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < i; j++) {
const tmp = arr[i][j];
arr[i][j] = arr[j][i];
arr[j][i] = tmp;
}
}
return arr;
};
// Creates a tile with the contents rotated right by 90 degrees.
const rotate90 = (t) => {
const newGrid = transpose(AOC.cloneArray(t.grid)).map((row) =>
row.reverse()
);
return { id: t.id, grid: newGrid };
};
// Apply all 8 possible transformations of a tile.
return [
AOC.identity,
rotate90,
(t) => flipV(flipH(t)),
(t) => flipV(flipH(rotate90(t))),
flipH,
flipV,
(t) => rotate90(flipV(t)),
(t) => rotate90(flipH(t))
].map((fn) => fn(tile));
}
function neighbourOn(side, tile, tiles) {
const edge = edgeOn(side, tile);
const availableTrasforms = tiles
.filter((t) => !equalID(t, tile))
.map(tileVariants)
.flat();
const matches = availableTrasforms.filter(
(t) => edge === edgeOn(opposite(side), t)
);
return matches.length === 1 ? matches[0] : null;
}
function topLeftTile(tiles) {
return tileVariants(corners(tiles)[0]).filter(
(t) =>
neighbourOn(Side.Left, t, tiles) === null &&
neighbourOn(Side.Top, t, tiles) === null
)[0];
}
function rightBottomNeighbours(tile, available) {
const availableTransforms = available.map(tileVariants).flat();
const rTile = availableTransforms.filter(
(t) => edgeOn(Side.Right, tile) === edgeOn(Side.Left, t)
);
const bTile = availableTransforms.filter(
(t) => edgeOn(Side.Bottom, tile) === edgeOn(Side.Top, t)
);
return [
rTile.length === 1 ? rTile[0] : null,
bTile.length === 1 ? bTile[0] : null
];
}
function buildMosaic(tiles) {
const gSize = Math.sqrt(tiles.length);
const mosaic = new Array(gSize).fill(0).map(() => new Array(gSize).fill(0));
mosaic[0][0] = topLeftTile(tiles);
let remaining = tiles;
for (let row = 0; row < gSize; row++) {
for (let col = 0; col < gSize; col++) {
const currentTile = mosaic[row][col];
remaining = remaining.filter((t) => !equalID(t, currentTile));
const [rTile, bTile] = rightBottomNeighbours(currentTile, remaining);
if (rTile !== null) {
mosaic[row][col + 1] = rTile;
}
if (bTile !== null) {
mosaic[row + 1][col] = bTile;
}
}
}
return mosaic;
}
function largeGrid(mosaic) {
const tileSize = mosaic[0][0].grid[0].length - 2;
const gSize = mosaic.length * tileSize;
const grid = new Array(gSize).fill(0).map(() => new Array(gSize).fill(0));
for (let gRow = 0; gRow < gSize; gRow++) {
const mRow = Math.floor(gRow / tileSize);
const r = 1 + (gRow % tileSize);
for (let gCol = 0; gCol < gSize; gCol++) {
const mCol = Math.floor(gCol / tileSize);
const c = 1 + (gCol % tileSize);
grid[gRow][gCol] = mosaic[mRow][mCol].grid[r][c];
}
}
return { id: 0, grid: grid };
}
function countMonsters(largeTile) {
const monster = [
[0, 18],
[1, 0],
[1, 5],
[1, 6],
[1, 11],
[1, 12],
[1, 17],
[1, 18],
[1, 19],
[2, 1],
[2, 4],
[2, 7],
[2, 10],
[2, 13],
[2, 16]
];
const gSize = largeTile.grid.length;
const monsterAt = (rOff, cOff) => {
return AOC.sum(
monster.map((c) =>
largeTile.grid[rOff + c[0]][cOff + c[1]] === "#" ? 1 : 0
)
) === 15
? 1
: 0;
};
let numMonsters = 0;
for (let row = 0; row < gSize - 3; row++) {
for (let col = 0; col < gSize - 20; col++) {
numMonsters += monsterAt(row, col);
}
}
return numMonsters;
}
function part2(input) {
const tiles = parse(input);
const lGrid = largeGrid(buildMosaic(tiles));
const numHashes = lGrid.grid.flat().filter((s) => s === "#").length;
const numMonsters = Math.max(...tileVariants(lGrid).map(countMonsters));
return numHashes - 15 * numMonsters;
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
