AdventOfCode2025/Day9.js

// Run this by pasting it into the browser window of the URL "https://adventofcode.com/2025/day/9/input"
// It is very slow, takeing multiple seconds

{
    const response = await fetch(window.location.href)
    const input = await response.text()
    // const input = "7,1\n11,1\n11,7\n9,7\n9,5\n2,5\n2,3\n7,3"

    const points = []

    for (const line of input.split("\n")) {
        const [x, y] = line.split(",")
        if (x) {
            const point = [parseInt(x), parseInt(y)]
            points.push(point)
        }
    }
    
    let parity = 0
    {
        let p1 = points[points.length-2]
        let p2 = points[points.length-1]
        for (let i = 0; i < points.length; i++) {
            const p3 = points[i]
            if (p1[0] === p2[0] && p2[1] == p3[1]) {
                parity = parity - Math.sign((p2[1] - p1[1]) * (p3[0] - p2[0]))
            } else if (p1[1] === p2[1] && p2[0] == p3[0]) {
                parity = parity + Math.sign((p2[0] - p1[0]) * (p3[1] - p2[1]))
            }
            p1 = p2
            p2 = p3
        }
    }

    let rightIsInside = parity > 0;
    console.log(rightIsInside ? "Right is inside" : "Left is inside")
    
    let squares = []
    for (const [i, p1] of points.entries()) {
        for (let j = 0; j < i; j++) {
            const p2 = points[j]
            const size = (Math.abs(p1[0] - p2[0]) + 1) * (Math.abs(p1[1] - p2[1]) + 1)
            squares.push([size, p1, p2])
        }
    }
    
    squares.sort(([s1], [s2]) => s2 - s1)
    console.log("Answer part 1:", squares[0][0])

    function cornersToRange(c1, c2) {
        return square = [
            [Math.min(c1[0], c2[0]), Math.min(c1[1], c2[1])],
            [Math.max(c1[0], c2[0]), Math.max(c1[1], c2[1])]
        ]
    }
    
    function lineToVerticalRange(p1, p2) {
        if (p1[1] == p2[1]) {
            const lineParity = Math.sign(p2[0] - p1[0]) * parity
            return [
                [Math.min(p1[0], p2[0]), lineParity > 0 ? p1[1] : - Infinity],
                [Math.max(p1[0], p2[0]), lineParity > 0 ? Infinity : p1[1]]
            ]
        }
        return null
    }

    function intersect([lb1, ub1], [lb2, ub2]) {
        const intersection = [
            [Math.max(lb1[0], lb2[0]), Math.min(ub1[0], ub2[0])],
            [Math.max(lb1[1], lb2[1]), Math.min(ub1[1], ub2[1])]
        ]
        if (intersection[0][0] > intersection[1][0] || intersection[0][1] > intersection[1][1]) {
            return null
        }
    }

    function combineVerticalRange([lb1, ub1], [lb2, ub2]) {
        if (ub1[1] <= lb2[1] || ub2[1] <= lb1[1] || (ub1[1] > ub2[1] && lb1[1] < lb2[1]) || (ub2[1] > ub1[1] && lb2[1] < lb1[1])) {
            return [[[lb1, ub1]], [[lb2, ub2]], []]
        }
        const x1 = Math.max(lb1[0], lb2[0])
        const x2 = Math.min(ub1[0], ub2[0])
        if (x2 <= x1) {
            return [[[lb1, ub1]], [[lb2, ub2]], []]
        }

        const split1 = []
        const split2 = []
        const union = []
        if (lb1[0] < lb2[0]) {
            split1.push([
                [lb1[0], lb1[1]], 
                [lb2[0], ub1[1]]
            ])
        } else if (lb2[0] < lb1[0]) {
            split2.push([
                [lb2[0], lb2[1]], 
                [lb1[0], ub2[1]]
            ])
        }
        if (ub2[0] > ub1[0]) {
            split2.push([
                [ub1[0], lb2[1]],
                [ub2[0], ub2[1]]
            ])
        } else if (ub1[0] > ub2[0]) {
            split1.push([
                [ub2[0], lb1[1]],
                [ub1[0], ub1[1]]
            ])
        }
        if (lb1[1] < lb2[1]) {
            if (lb1[1] > -Infinity) {
                split1.push([
                    [x1, lb1[1]],
                    [x2, lb2[1]]
                ])
            }
        } else if (lb2[1] < lb1[1]) {
            if (lb2[1] > -Infinity) {
                split2.push([
                    [x1, lb2[1]],
                    [x2, lb1[1]]
                ])
            }
        }
        const y1 = Math.max(lb1[1], lb2[1])
        if (ub2[1] > ub1[1]) {
            if (ub2[1] < Infinity) {
                split2.push([
                    [x1, ub1[1]],
                    [x2, ub2[1]]
                ])
            }
        } else if (ub1[1] > ub2[1]) {
            if (ub1[1] < Infinity) {
                split1.push([
                    [x1, ub2[1]],
                    [x2, ub1[1]]
                ])
            }
        }
        const y2 = Math.min(ub1[1], ub2[1])
        union.push([
            [x1, y1],
            [x2, y2]
        ])
        return [split1, split2, union]
    }
    
    function splitByYBound([lb, ub], [lyb, uyb]) {
        if (lyb > ub[1] || uyb < lb[1]) {
            return [[[lb, ub]], null]
        }
        const outside = []
        if (lb[1] < lyb) {
            outside.push([
                [lb[0], lb[1]],
                [ub[0], lyb - 1]
            ])
        }
        if (ub[1] > uyb) {
            outside.push([
                [lb[0], uyb + 1],
                [ub[0], ub[1]]
            ])
        }
        const inside = [
            [lb[0], Math.max(lb[1], lyb)],
            [ub[0], Math.min(ub[1], uyb)]
        ]
        return [outside, inside]
    }
    
    function splitByXBound([lb, ub], [lxb, uxb]) {
        if (lxb > ub[0] || uxb < lb[0]) {
            return [[[lb, ub]], null]
        }
        const outside = []
        if (lb[0] < lxb) {
            outside.push([
                [lb[0], lb[1]],
                [lxb - 1, ub[1]]
            ])
        }
        if (ub[0] > uxb) {
            outside.push([
                [uxb + 1, lb[1]],
                [ub[0], ub[1]]
            ])
        }
        const inside = [
            [Math.max(lb[0], lxb), lb[1]],
            [Math.min(ub[0], uxb), ub[1]]
        ]
        return [outside, inside]
        
    }
    
    function subtractRange([lb1, ub1], [lb2, ub2]) {
        const [outsideY, insideY] = splitByYBound([lb1, ub1], [lb2[1], ub2[1]])
        if (insideY) {
            const [outsideX, _] = splitByXBound(insideY, [lb2[0], ub2[0]])
            outsideY.push(...outsideX)
        }
        return outsideY
    }
    
    function combineLists(ranges1, ranges2) {
        for (let i = 0; i < ranges1.length; i++) {
            for (let j = 0; j < ranges2.length; j++) {
                const range1 = ranges1[i]
                const range2 = ranges2[j]
                if (!range1) {
                    break
                }
                if (range2) {
                    const [split1, split2, union] = combineVerticalRange(range1, range2)
                    split1.push(...union)
                    ranges1[i] = split1.pop()
                    ranges2[j] = split2.pop()
                    ranges1.push(...split1)
                    ranges2.push(...split2)
                }
            }
        }
        ranges1.push(...ranges2)
        return ranges1.filter((x) => !!x)
    }
    
    function subtractLists(ranges1, ranges2) {
        for (let j = 0; j < ranges2.length; j++) {
            const range2 = ranges2[j]
            for (let i = 0; i < ranges1.length; i++) {
                const range1 = ranges1[i]
                if (!range1) {
                    break
                }
                if (range2) {
                    const res = subtractRange(range1, range2)
                    ranges1[i] = res.pop()
                    ranges1.push(...res)
                }
            }
        }
        return ranges1.filter((x) => !!x)
    }

    let ranges = []
    let p1 = points[points.length-1]
    for (let i = 0; i < points.length; i++) {
        const p2 = points[i]
        const range = lineToVerticalRange(p1, p2)
        if (range) {
            ranges = combineLists(ranges, [range])
        }
        p1 = p2
    }

    for (const [s, c1, c2] of squares) {
        const empty = subtractLists([cornersToRange(c1, c2)], ranges)
        if (empty.length == 0) {
            console.log("Answer part 2:", s)
            break
        }
    }
}