AdventOfCode2021/Day12/Caves.ts

import { readLines } from "https://deno.land/std@0.177.1/io/read_lines.ts";

interface Cave {
    name: string;
    LargeNeighbours: number[];
    SmallNeighbours: number[];
    big: boolean;
}

async function Part1() {
    const file = await Deno.open("./Day12/input.txt");
    const lines = readLines(file);

    const smallCaves: Cave[] = [];
    const bigCaves: Cave[] = [];

    for await (const line of lines) {
        const [start,end] = line.split("-");
        addCave(smallCaves,bigCaves,start)
        addCave(smallCaves,bigCaves,end)
        addNeighbour(smallCaves,bigCaves,start,end)
    }

    const visited: boolean[] = [];
    let curr = smallCaves[0];
    for (const i in smallCaves) {
        visited.push(false)
        if (smallCaves[i].name == "start") {
            visited[i] = true;
            curr = smallCaves[i]
        }
    }

    return DFS(curr, visited, 0, smallCaves, bigCaves);
}

async function Part2() {
    const file = await Deno.open("./Day12/input.txt");
    const lines = readLines(file);

    const smallCaves: Cave[] = [];
    const bigCaves: Cave[] = [];

    for await (const line of lines) {
        const [start,end] = line.split("-");
        addCave(smallCaves,bigCaves,start)
        addCave(smallCaves,bigCaves,end)
        addNeighbour(smallCaves,bigCaves,start,end)
    }

    const visited: boolean[] = [];
    let curr = smallCaves[0];
    for (const i in smallCaves) {
        visited.push(false)
        if (smallCaves[i].name == "start") {
            visited[i] = true;
            curr = smallCaves[i]
        }
    }
    return DFS2(curr, visited, 0, smallCaves, bigCaves, false);

}

console.log("Part1: " + await Part1());
console.log("Part2: " + await Part2());

function DFS(curr: Cave, visited: boolean[], paths: number, smallCaves: Cave[], bigCaves: Cave[]) {
    if (curr.name == "end") {
        return ++paths;
    }
    for (const i of curr.LargeNeighbours) {
        paths = DFS(bigCaves[i],visited,paths,smallCaves,bigCaves)
    } 
    for (const i of curr.SmallNeighbours) {
        if (visited[i]) {
            continue
        }
        const VisitedCopy = Array.from(visited);
        VisitedCopy[i] = true;
        paths = DFS(smallCaves[i],VisitedCopy,paths,smallCaves,bigCaves)
    }
    return paths;
} 

function DFS2(curr: Cave, visited: boolean[], paths: number, smallCaves: Cave[], bigCaves: Cave[], twice: boolean) {
    if (curr.name == "end") {
        return ++paths;
    }
    for (const i of curr.LargeNeighbours) {
        paths = DFS2(bigCaves[i],visited,paths,smallCaves,bigCaves,twice)
    } 
    for (const i of curr.SmallNeighbours) {
        if (visited[i] && twice) {
            continue
        }
        if (smallCaves[i].name == "start") {
            continue
        }
        const VisitedCopy = Array.from(visited);
        VisitedCopy[i] = true;
        const TwiceCopy = visited[i] || twice
        paths = DFS2(smallCaves[i],VisitedCopy,paths,smallCaves,bigCaves, TwiceCopy)
    }
    return paths;
} 


function addCave(smallCaves: Cave[], bigCaves: Cave[], c: string) {
    let list = (c == c.toUpperCase()) ? bigCaves : smallCaves;
    for (const d of list) {
        if (d.name == c) {
            return
        }
    }
    list.push({
                        name: c,
                        LargeNeighbours: [], 
                        SmallNeighbours: [], 
                        big: c == c.toUpperCase()
    })
}

function addNeighbour(smallCaves: Cave[], bigCaves: Cave[], s: string, t: string) {
    const slist = (s == s.toUpperCase()) ? bigCaves : smallCaves;
    const tlist = (t == t.toUpperCase()) ? bigCaves : smallCaves;
    let sIndex = 0
    let tIndex = 0
    for (const c in slist) {
        if (slist[c].name == s) {
            sIndex = +c;
            break
        }
    }
    for (const d in tlist) {
        if (tlist[d].name == t) {
            tIndex = +d;
            break
        }
    }
    const sgoal = (t == t.toUpperCase()) ? slist[sIndex].LargeNeighbours : slist[sIndex].SmallNeighbours;
    const tgoal = (s == s.toUpperCase()) ? tlist[tIndex].LargeNeighbours : tlist[tIndex].SmallNeighbours;
    if (!sgoal.includes(+tIndex)) {
        sgoal.push(+tIndex)
    }
    if (!tgoal.includes(+sIndex)) {
        tgoal.push(+sIndex)
    }
}