Wtfs. I used to see them every year as a kid…
Wtfs. I used to see them every year as a kid…
straight-forward
Maybe for you 😅
Maaaannnn. Today’s solution was really something. I actually got so confused initially that I unknowingly wrote the algorithm for part 2 before I even finished part 1! As an upside, however, I did expand my own Advent of Code standard library ;)
import { AdventOfCodeSolutionFunction } from "./solutions";
import { Grid } from "./utils/grids";
import { LinkedPoint } from "./utils/structures/linkedPoint";
import { makeGridFromMultilineString, SumArray } from "./utils/utils";
class TrailPoint extends LinkedPoint<number, TrailPoint> {
constructor(x: number, y: number, item: number, grid: Grid<TrailPoint>) {
super(x, y, item, grid);
}
lookAroundValid(): Array<TrailPoint> {
return this.lookAround().filter(v => v.item == this.item + 1);
}
findAllValidPeaks(): Array<TrailPoint> {
if (this.item == 9)
return [this];
// filter for distinct references (this theoretically saves time)
return [...(new Set(this.lookAroundValid().flatMap(v => v.findAllValidPeaks())))];
}
findAllValidPeaksWithReps(): Array<TrailPoint> {
if (this.item == 9)
return [this];
// don't filter
return this.lookAroundValid().flatMap(v => v.findAllValidPeaksWithReps());
}
}
export const solution_10: AdventOfCodeSolutionFunction = (input) => {
const map: Grid<TrailPoint> =
makeGridFromMultilineString(input)
.map((row) => row.map((item) => item != "." ? Number(item) : -1))
.map((row, y) => row.map((item, x) => new TrailPoint(x, y, item, undefined!)));
map.flat().forEach((v) => v.grid = map); // promise is a promise
const startNodes: Array<TrailPoint> = map.flat().filter(v => v.item == 0);
const part_1 = SumArray(startNodes.map(v => v.findAllValidPeaks().length));
const part_2 = SumArray(startNodes.map(v => v.findAllValidPeaksWithReps().length));
return {
part_1, // 557
part_2, // 1062
}
}
Welp, quantum computers have certain advantages (finding elements in O(sqrt(n)) time complexity, factorizing primes, etc). The difficulty is actually making everything stable because these machines are pretty complex.
Actually kinda proud of my solution considering how hectic today has been! I actually didn’t spend too much time on this solution too :) Runs in ~0.5s.
import { AdventOfCodeSolutionFunction } from "./solutions";
import { MakeEmptyGenericArray } from "./utils/utils";
const pretty_print = (disk: Array<number>) => disk.reduce<string>((prev, curr) => prev + (curr == -1 ? "." : curr), "");
const checksum = (disk: Array<number>) => disk.reduce<number>((prev, curr, index) => prev + (curr == -1 ? 0 : curr * index), 0);
const findSlice = (disk: Array<number>, id: number, startFrom?: number) => {
const sectionStart = disk.indexOf(id, startFrom);
if (sectionStart == -1)
return [-1, -1];
let sectionEnd = sectionStart;
while (disk.length > ++sectionEnd && disk[sectionEnd] == id);
return [sectionStart, sectionEnd];
}
export const solution_9: AdventOfCodeSolutionFunction = (input) => {
let isFile = false;
let id = 0;
// make the disk
const disk = input.split("").flatMap((v) => {
isFile = !isFile;
const count = Number(v);
if (isFile) {
id++;
return MakeEmptyGenericArray(count, () => id - 1);
}
return MakeEmptyGenericArray(count, () => -1);
});
// make a copy of the disk
const fragmentedDisk = [...disk];
// start moving elements on the disk
let start = 0
let end = fragmentedDisk.length - 1;
while (start < end) {
if (fragmentedDisk[start] != -1) {
start++;
continue;
}
if (fragmentedDisk[end] == -1) {
end--;
continue;
}
// swap the values
fragmentedDisk[start] = fragmentedDisk[end]
fragmentedDisk[end] = -1;
start++;
end--;
}
main: while (id-- > 0) {
// find the section that has the file
const [sectionStart, sectionEnd] = findSlice(disk, id); // this will never return -1
const sectionLength = sectionEnd - sectionStart;
// find any section that can fit the file
let freeStart;
let freeEnd = 0;
do {
[freeStart, freeEnd] = findSlice(disk, -1, freeEnd);
// can't find any free spaces or too far right
if (freeStart == -1 || freeStart > sectionStart)
continue main;
} while (freeEnd - freeStart < sectionLength);
// switch places
let i = 0;
while(sectionStart + i < sectionEnd) {
disk[freeStart + i] = id;
disk[sectionStart + i++] = -1;
}
}
// calculate the checksums
return {
part_1: checksum(fragmentedDisk),
part_2: checksum(disk),
}
}
Most water?
Comment removed or am i dumb? What did it say?
As a public service announcement, recursively removing all of your files from / is no longer recommended.
When was it ever recommended?
There’s absolutely no reason to do this, ever.
To remove the French language from your system ofc (rm -fr /
)
Solution
pip
is Python’s package manager.