import { readFileSync } from 'fs'

type Point = [number, number]

function parse(input: string): Point[] {
    const lines = input.trim().split('\n')
    const points: Point[] = []
    for (let y = 0; y < lines.length; y++) {
        for (let x = 0; x < lines[0].length; x++) {
            if (lines[y][x] === '#') points.push([x, y])
        }
    }
    return points
}

function expand(points: Point[], factor: number): Point[] {
    const nonemptyYs = new Set<number>()
    const nonemptyXs = new Set<number>()
    let maxY = 0
    let maxX = 0
    for (const [x, y] of points) {
        nonemptyXs.add(x)
        nonemptyYs.add(y)
        maxY = Math.max(maxY, y)
        maxX = Math.max(maxX, x)
    }

    const prefixSumXs: number[] = new Array(maxX + 1).fill(0)
    const prefixSumYs: number[] = new Array(maxY + 1).fill(0)
    for (let x = 0; x <= maxX; x++) {
        prefixSumXs[x] =
            (prefixSumXs[x - 1] || 0) + (!nonemptyXs.has(x) ? 1 : 0)
    }
    for (let y = 0; y <= maxY; y++) {
        prefixSumYs[y] =
            (prefixSumYs[y - 1] || 0) + (!nonemptyYs.has(y) ? 1 : 0)
    }

    return points.map(([px, py]) => {
        return [
            px + prefixSumXs[px] * (factor - 1),
            py + prefixSumYs[py] * (factor - 1),
        ]
    })
}

function manhattanDistance([ax, ay]: Point, [bx, by]: Point): number {
    return Math.abs(ax - bx) + Math.abs(ay - by)
}

function sumPairDistances(points: Point[]): number {
    const considered = new Set<string>()
    let sum = 0
    for (const a of points) {
        for (const b of points) {
            if (a[0] === b[0] && a[1] === b[1]) continue
            // Sort points to ensure [a, b] and [b, a] are treated the same
            const [sortedA, sortedB] = [a, b].sort((p1, p2) => {
                if (p1[0] === p2[0]) return p1[1] - p2[1]
                return p1[0] - p2[0]
            })
            const key = `${sortedA[0]}-${sortedA[1]}:${sortedB[0]}-${sortedB[1]}`
            if (considered.has(key)) continue
            sum += manhattanDistance(a, b)
            considered.add(key)
        }
    }
    return sum
}

const input = `
...#......
.......#..
#.........
..........
......#...
.#........
.........#
..........
.......#..
#...#.....`

// const input = readFileSync('day11.txt', { encoding: 'utf8' })

console.log('part 1:', sumPairDistances(expand(parse(input), 2)))
console.log('part 2:', sumPairDistances(expand(parse(input), 1_000_000)))