AoC 2021, day 19

package day19

import common.Point3
import kotlin.math.abs

import kotlin.math.abs

data class Point3(
    val x: Int,
    val y: Int,
    val z: Int
) {

    operator fun minus(point3: Point3): Point3 {
        return Point3(
            x - point3.x,
            y - point3.y,
            z - point3.z
        )
    }

    operator fun plus(point3: Point3): Point3 {
        return Point3(
            x + point3.x,
            y + point3.y,
            z + point3.z
        )
    }

    fun deltaAbs(point3: Point3): Point3 {
        return Point3(
            abs(x - point3.x),
            abs(y - point3.y),
            abs(z - point3.z)
        )

    }
}

enum class Axis(
    val originalName: String
) {
    X("x"),
    Y("y"),
    Z("z"),
    X_NEGATIVE("x"),
    Y_NEGATIVE("y"),
    Z_NEGATIVE("z")
}

private val defaultConfiguration = RotationConfiguration(
    facing = Axis.X,
    up = Axis.Z
)

private val allConfigurations = Axis.values().flatMap { axis ->
    (Axis.values().toList() - axis).mapNotNull { upAxis ->

        if (upAxis.originalName == axis.originalName) {
            return@mapNotNull null
        }

        RotationConfiguration(
            facing = axis,
            up = upAxis
        )
    }
}


data class RotationConfiguration(
    val facing: Axis,
    val up: Axis
) {

    fun apply(point: Point3): Point3 {
        val x = when (facing) {
            Axis.X -> point.x
            Axis.Y -> point.y
            Axis.Z -> point.z
            Axis.X_NEGATIVE -> -point.x
            Axis.Y_NEGATIVE -> -point.y
            Axis.Z_NEGATIVE -> -point.z
        }

        val y = when (facing) {
            Axis.X -> when (up) {
                Axis.X -> throw IllegalStateException()
                Axis.Y -> -point.z
                Axis.Z -> point.y
                Axis.X_NEGATIVE -> throw IllegalStateException()
                Axis.Y_NEGATIVE -> point.z
                Axis.Z_NEGATIVE -> -point.y
            }

            Axis.Y -> when (up) {
                Axis.X -> point.z
                Axis.Y -> throw IllegalStateException()
                Axis.Z -> -point.x
                Axis.X_NEGATIVE -> -point.z
                Axis.Y_NEGATIVE -> throw IllegalStateException()
                Axis.Z_NEGATIVE -> point.x
            }

            Axis.Z -> when (up) {
                Axis.X -> -point.y
                Axis.Y -> point.x
                Axis.Z -> throw IllegalStateException()
                Axis.X_NEGATIVE -> point.y
                Axis.Y_NEGATIVE -> -point.x
                Axis.Z_NEGATIVE -> throw IllegalStateException()
            }

            Axis.X_NEGATIVE -> when (up) {
                Axis.X -> throw IllegalStateException()
                Axis.Y -> point.z
                Axis.Z -> -point.y
                Axis.X_NEGATIVE -> throw IllegalStateException()
                Axis.Y_NEGATIVE -> -point.z
                Axis.Z_NEGATIVE -> point.y
            }

            Axis.Y_NEGATIVE -> when (up) {
                Axis.X -> -point.z
                Axis.Y -> throw IllegalStateException()
                Axis.Z -> point.x
                Axis.X_NEGATIVE -> point.z
                Axis.Y_NEGATIVE -> throw IllegalStateException()
                Axis.Z_NEGATIVE -> -point.x
            }

            Axis.Z_NEGATIVE -> when (up) {
                Axis.X -> point.y
                Axis.Y -> -point.x
                Axis.Z -> throw IllegalStateException()
                Axis.X_NEGATIVE -> -point.y
                Axis.Y_NEGATIVE -> point.x
                Axis.Z_NEGATIVE -> throw IllegalStateException()
            }
        }

        val z = when (up) {
            Axis.X -> point.x
            Axis.Y -> point.y
            Axis.Z -> point.z
            Axis.X_NEGATIVE -> -point.x
            Axis.Y_NEGATIVE -> -point.y
            Axis.Z_NEGATIVE -> -point.z
        }

        return Point3(x, y, z)
    }
}


private data class Deltas(
    private val deltas: Map<RotationConfiguration, Map<Pair<Point3, Point3>, Point3>>
) {

    operator fun get(rotation: RotationConfiguration): Map<Pair<Point3, Point3>, Point3> {
        return deltas[rotation]!!
    }

    fun points(): Points {
        return Points(
            deltas.mapValues { (_, value) -> getPointsMap(value) }
        )
    }

    private fun getPointsMap(map: Map<Pair<Point3, Point3>, Point3>): Map<Point3, List<Pair<Point3, Point3>>> {
        return map.entries.groupBy { (_, delta) ->
            delta
        }.mapValues { (_, value) ->
            value.map { (pair, _) ->
                pair
            }
        }
    }

}

private data class Points(
    val points: Map<RotationConfiguration, Map<Point3, List<Pair<Point3, Point3>>>>
) {
    operator fun get(rotation: RotationConfiguration): Map<Point3, List<Pair<Point3, Point3>>> {
        return points[rotation]!!
    }
}

private data class Scanner(
    val name: String,
    val beacons: List<Point3>
) {

    private fun delta(rotation: RotationConfiguration): Map<Pair<Point3, Point3>, Point3> {
        val appliedBeacons = beacons.map {
            rotation.apply(it)
        }

        val mutableMap = mutableMapOf<Pair<Point3, Point3>, Point3>()

        appliedBeacons.forEach { beaconA ->
            appliedBeacons.forEach innerForEach@{ beaconB ->
                if (beaconA == beaconB) {
                    return@innerForEach
                }

                val delta = beaconA - beaconB

                mutableMap[beaconA to beaconB] = delta
            }
        }

        return mutableMap
    }

    fun deltas(): Deltas {
        return Deltas(
            allConfigurations.map { configuration ->
                configuration to delta(configuration)
            }.toMap()
        )
    }
}


private fun String.toScanner(): Scanner {
    val lines = split("\n")

    val name = lines[0].removeSuffix(" ---").removePrefix("--- ")

    val beacons = lines.drop(1).map {
        val parts = it.split(",")
        Point3(
            parts[0].toInt(),
            parts[1].toInt(),
            parts[2].toInt()
        )
    }

    return Scanner(name, beacons)
}

fun main() {
    val scanners = input.split("\n\n").map {
        it.toScanner()
    }

    val scannerOrigins = mutableSetOf<Point3>()

    val scannerDeltas = scanners.map {
        it to it.deltas()
    }.toMap().toMutableMap()

    val deltasToPoints = scannerDeltas.map { (scanner, deltas) ->
        scanner to deltas.points()
    }.toMap().toMutableMap()

    val knownScanners = mutableListOf(
        scanners.first()
    ).toMutableList()

    val unknownScanners = (scanners.toMutableList() - knownScanners).toMutableList()

    while (unknownScanners.isNotEmpty()) {
        var knownScannerToAdd: Scanner? = null
        var unknownScannerToRemove: Scanner? = null

        println("\nStarting new iteration...")
        var foundSomething = false

        for (knownScanner in knownScanners) {
            if (foundSomething) {
                break
            }

            unknownScanners.forEach { unknownScanner ->
                val knownDelta = scannerDeltas[knownScanner]!![defaultConfiguration]
                val unknownDeltaAll = scannerDeltas[unknownScanner]!!

                val pointsForDeltaKnown = deltasToPoints[knownScanner]!![defaultConfiguration]
                val pointsForDeltaUnknownAll = deltasToPoints[unknownScanner]!!

                // figure out whether they're looking at the same drones
                // and at which orientation they are
                val rotations = allConfigurations
                val rotationAndIntersectingValues = rotations.firstNotNullOfOrNull { rotation ->
                    unknownDeltaAll[rotation].values.intersect(knownDelta.values).takeIf {
                        it.size >= REQUIRED_INTERSECTIONS
                    }?.let {
                        rotation to it
                    }
                }

                val intersectingValues = rotationAndIntersectingValues?.second
                val unknownRotation = rotationAndIntersectingValues?.first

                val pointsForDeltaUnknown = unknownRotation?.let {
                    pointsForDeltaUnknownAll[it]
                }

                if (pointsForDeltaUnknown != null && intersectingValues != null && intersectingValues.size >= REQUIRED_INTERSECTIONS) {
                    // we already know that their axises are aligned at this point
                    val commonDelta = intersectingValues.first()

                    val (knownPoint1, _) = pointsForDeltaKnown[commonDelta]!!.single()
                    val (unknownPoint1, _) = pointsForDeltaUnknown[commonDelta]!!.single()

                    val (dx, dy, dz) = knownPoint1 - unknownPoint1
                    println("Figured out that ${unknownScanner.name} is at ($dx, $dy, $dz)")

                    scannerOrigins.add(Point3(dx, dy, dz))

                    println("${unknownScanners.size - 1} scanners left...")
                    println("Marking scanner ${unknownScanner.name} as known, removing it from unknown scanners list")
                    unknownScannerToRemove = unknownScanner

                    val transform: (Point3) -> Point3 = { point ->
                        val transformed = unknownRotation.apply(point)

                        with (transformed) {
                            Point3(
                                x + dx,
                                y + dy,
                                z + dz
                            )
                        }
                    }

                    knownScannerToAdd = Scanner(
                        name = unknownScanner.name,
                        beacons = unknownScanner.beacons.map(transform)
                    )

                    foundSomething = true
                }
            }
        }

        knownScannerToAdd?.also { scanner ->
            knownScanners.add(scanner)

            val deltas = scanner.deltas()
            scannerDeltas[scanner] = deltas
            deltasToPoints[scanner] = deltas.points()

            println("Known scanners: ${knownScanners.size}")
        }

        unknownScannerToRemove?.also {
            unknownScanners.removeIf { scanner ->
                it.name == scanner.name
            }
        }
    }

    val unique = knownScanners.flatMap {
        it.beacons
    }.toSet()
    println("Drones: ${unique.size}")

    val maxDistance = scannerOrigins.flatMap { pointA ->
        scannerOrigins.mapNotNull { pointB ->
            if (pointA == pointB) {
                return@mapNotNull null
            }

            val (dx, dy, dz) = pointA - pointB

            abs(dx) + abs(dy) + abs(dz)
        }
    }.maxOrNull()

    println(maxDistance)
}

private const val REQUIRED_INTERSECTIONS = 132