• 1 Post
  • 9 Comments
Joined 1 year ago
cake
Cake day: June 20th, 2023

help-circle



  • TypeScript

    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 ;)

    Solution
    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
        }
    }
    

    Full code here.



  • TypeScript

    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.

    Solution
    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),
        }
    }