Advent of Code 2020 Day 17 - Solution + Tutorial (TypeScript)
- [ 1 ]
- [ 2 ]
- [ 3 ]
- [ 4 ]
- [ 5 ]
- [ 6 ]
- [ 7 ]
- [ 8 ]
- [ 9 ]
- [ 10 ]
- [ 11 ]
- [ 12 ]
- [ 13 ]
- [ 14 ]
- [ 15 ]
- [ 16 ]
- [ 17 ]
- [ 18 ]
I'll try to update asap. Please bear in a mind that I'll probably lag one or multiple days behind.
Prerequisites
I assume you've put your puzzle input into an array called lines
where each array item is a line of the input text file.
It's up to you to either parse the text file or create an array by hand.
const lines = [
"#..#..#.",
".#..#..#",
".#..#...",
…
];
Solution
Preface
Starting with Day 10, I'll just publish my solution for both parts without explaining every single step. Unfortunately, I can't continue providing full step-by-step tutorials for each day. The concepts used get more difficult day by day. So, I've concluded that it's better if I wrote separate blog posts about these concepts later.
Also, it's holiday season. This makes it much more difficult creating well-thought-out tutorials. However, I'll try to annotate my code examples a little. This way, you might understand what I've done.
I will now move on to sharing useful tips for web developers regularly. These should help you become a better developer. Also, the shared tips should help with solving problems like those we encounter in Advent of Code. Here's my first post: 14 Awesome JavaScript Array Tips You Should Know About
Puzzle
Just to make sure, you know what I'm talking about, take a look at today's puzzle:
Part 1
TODO: The code is ready, I'm working on the description.
let pocketDimension = new PocketDimension();
const initialSize = lines.length;
lines.forEach((line, y) => {
const z = 0;
[...line].forEach((cube, x) => {
if (cube !== "#") return;
pocketDimension.activate([x, y, z]);
});
});
for (let cycle = 1; cycle <= 6; cycle++) {
const newPocketDimension = new PocketDimension();
// Use pad to take growing dimension into account.
const pad = cycle;
for (let x = -pad; x < initialSize + pad; x++) {
for (let y = -pad; y < initialSize + pad; y++) {
for (let z = -pad; z <= pad; z++) {
const point = [x, y, z] as Point3D;
const isActive = pocketDimension.isActive(point);
const activeNeighbors = countActiveNeighbors(pocketDimension, point);
if ((isActive && activeNeighbors === 2) || activeNeighbors === 3) {
newPocketDimension.activate(point);
}
}
}
}
pocketDimension = newPocketDimension;
}
return pocketDimension.activeCount;
type Point3D = [x: number, y: number, z: number];
class PocketDimension {
protected _xMap: Map<number, Map<number, Set<number>>>;
public constructor() {
this._xMap = new Map<number, Map<number, Set<number>>>();
}
public get activeCount(): number {
let active = 0;
for (const yMap of this._xMap.values()) {
for (const zMap of yMap.values()) {
active += zMap.size;
}
}
return active;
}
public isActive([x, y, z]: Point3D): boolean {
return this._xMap.get(x)?.get(y)?.has(z) ?? false;
}
public activate([x, y, z]: Point3D): void {
let yMap = this._xMap.get(x);
if (!yMap) {
yMap = new Map<number, Set<number>>();
this._xMap.set(x, yMap);
}
let zMap = yMap.get(y);
if (!zMap) {
zMap = new Set<number>();
yMap.set(y, zMap);
}
zMap.add(z);
}
}
function countActiveNeighbors(
pocketDimension: PocketDimension,
[x, y, z]: Point3D,
threshold = 4
): number {
let activeNeighbors = 0;
// Use delta to look for neighbors.
for (let dx = -1; dx <= 1; dx++) {
for (let dy = -1; dy <= 1; dy++) {
for (let dz = -1; dz <= 1; dz++) {
if (dx === 0 && dy === 0 && dz === 0) continue;
const isActive = pocketDimension.isActive([x + dx, y + dy, z + dz]);
if (isActive) {
activeNeighbors++;
// We don't need to count more than threshold (default: 4).
if (activeNeighbors >= threshold) {
return activeNeighbors;
}
}
}
}
}
return activeNeighbors;
}
Part 2
TODO: The code is ready, I'm working on the description.
let pocketDimension = new PocketDimension();
const initialSize = lines.length;
lines.forEach((line, y) => {
const z = 0;
const w = 0;
[...line].forEach((cube, x) => {
if (cube !== "#") return;
pocketDimension.activate([x, y, z, w]);
});
});
for (let cycle = 1; cycle <= 6; cycle++) {
const newPocketDimension = new PocketDimension();
const pad = cycle;
for (let x = -pad; x < initialSize + pad; x++) {
for (let y = -pad; y < initialSize + pad; y++) {
for (let z = -pad; z <= pad; z++) {
for (let w = -pad; w <= pad; w++) {
const point = [x, y, z, w] as Point4D;
const isActive = pocketDimension.isActive(point);
const activeNeighbors = countActiveNeighbors(
pocketDimension,
point
);
if ((isActive && activeNeighbors === 2) || activeNeighbors === 3) {
newPocketDimension.activate(point);
}
}
}
}
}
pocketDimension = newPocketDimension;
}
return pocketDimension.activeCount;
type Point4D = [x: number, y: number, z: number, w: number];
class PocketDimension {
protected _xMap: Map<number, Map<number, Map<number, Set<number>>>>;
public constructor() {
this._xMap = new Map<number, Map<number, Map<number, Set<number>>>>();
}
public get activeCount(): number {
let active = 0;
for (const yMap of this._xMap.values()) {
for (const zMap of yMap.values()) {
for (const wMap of zMap.values()) {
active += wMap.size;
}
}
}
return active;
}
public isActive([x, y, z, w]: Point4D): boolean {
return this._xMap.get(x)?.get(y)?.get(z)?.has(w) ?? false;
}
public activate([x, y, z, w]: Point4D): void {
let yMap = this._xMap.get(x);
if (!yMap) {
yMap = new Map<number, Map<number, Set<number>>>();
this._xMap.set(x, yMap);
}
let zMap = yMap.get(y);
if (!zMap) {
zMap = new Map<number, Set<number>>();
yMap.set(y, zMap);
}
let wMap = zMap.get(z);
if (!wMap) {
wMap = new Set<number>();
zMap.set(z, wMap);
}
wMap.add(w);
}
}
function countActiveNeighbors(
pocketDimension: PocketDimension,
[x, y, z, w]: Point4D,
threshold = 4
): number {
let activeNeighbors = 0;
for (let dx = -1; dx <= 1; dx++) {
for (let dy = -1; dy <= 1; dy++) {
for (let dz = -1; dz <= 1; dz++) {
for (let dw = -1; dw <= 1; dw++) {
if (dx === 0 && dy === 0 && dz === 0 && dw === 0) continue;
const isActive = pocketDimension.isActive([
x + dx,
y + dy,
z + dz,
w + dw,
]);
if (isActive) {
activeNeighbors++;
if (activeNeighbors >= threshold) {
return activeNeighbors;
}
}
}
}
}
}
return activeNeighbors;
}
Conclusion
TODO: I'm working on it.