package com.joelpedraza.aok2018.day13

import com.joelpedraza.collections.IntHeap
import kotlin.math.sign

fun main(args: Array<String>) {
    solve(INPUT).let(::println)
}

// INCLINE CLASSES
// ===============

inline class UVec2d8(val value: Int) {
    companion object {
        const val MASK: Int = 0xffff
    }

    val y: Int get() = value shr 8
    val x: Int get() = value and 0xff

    constructor(x: Int, y: Int) : this(((y and 0xff) shl 8) or (x and 0xff))

    infix operator fun plus(other: IVec2d2): UVec2d8 = UVec2d8(
        x = this.x + other.x,
        y = this.y + other.y
    )

    infix operator fun minus(other: IVec2d2): UVec2d8 = UVec2d8(
        x = this.x - other.x,
        y = this.y - other.y
    )

    operator fun component1(): Int = x
    operator fun component2(): Int = y

    override fun toString(): String {
        return "UVec2d8(x=$x, y=$y)"
    }
}

inline class IVec2d2(val value: Int) {
    companion object {
        const val MASK: Int = 0b1111
        val LEFT = IVec2d2(x = -1, y = 0)
        val UP = IVec2d2(x = 0, y = -1)
        val RIGHT = IVec2d2(x = 1, y = 0)
        val DOWN = IVec2d2(x = 0, y = 1)
    }

    val y: Int get() = ((value and 0b1100) shl 28).sign
    val x: Int get() = ((value and 0b0011) shl 30).sign

    constructor(x: Int, y: Int) : this(
        ((-y).zigzag() and 0b11 shl 2) or ((-x).zigzag() and 0b11)
    )

    fun rotCw() = IVec2d2(-y, x)
    fun rotCcw() = IVec2d2(y, -x)

    override fun toString(): String {
        return "IVec2d1(x=$x, y=$y)"
    }
}

fun IVec2d2.turnDown(): IVec2d2 = when (this) {
    IVec2d2.LEFT -> IVec2d2.DOWN
    IVec2d2.UP -> IVec2d2.RIGHT
    IVec2d2.RIGHT -> IVec2d2.UP
    IVec2d2.DOWN -> IVec2d2.LEFT
    else -> UNREACHABLE("MineCart oriented in an invalid direction")
}

fun IVec2d2.turnUp(): IVec2d2 = when (this) {
    IVec2d2.LEFT -> IVec2d2.UP
    IVec2d2.UP -> IVec2d2.LEFT
    IVec2d2.RIGHT -> IVec2d2.DOWN
    IVec2d2.DOWN -> IVec2d2.RIGHT
    else -> UNREACHABLE("MineCart oriented in an invalid direction")
}

fun IVec2d2.steer(steering: Steering): IVec2d2 = when (steering) {
    Steering.STRAIGHT -> this
    Steering.LEFT -> rotCcw()
    Steering.RIGHT -> rotCw()
    else -> UNREACHABLE("MineCart had invalid memory")
}

operator fun IVec2d2.Companion.invoke(char: Char): IVec2d2 {
    return when (char) {
        '<' -> LEFT
        '^' -> UP
        '>' -> RIGHT
        'v' -> DOWN
        else -> throw IllegalArgumentException("$char is not a valid orientation")
    }
}

inline class Steering(val value: Int) {
    companion object {
        val LEFT = Steering(0b00)
        val STRAIGHT = Steering(0b01)
        val RIGHT = Steering(0b10)
        val MASK: Int = 0b11
    }

    override fun toString(): String {
        return "Steering." + when (this) {
            LEFT -> "LEFT"
            STRAIGHT -> "STRAIGHT"
            RIGHT -> "RIGHT"
            else -> throw IllegalStateException()
        }
    }

    fun next(): Steering {
        return Steering((value + 1) % 3)
    }
}

inline class MineCart(val value: Int) {
    val pos: UVec2d8 get() = UVec2d8(value ushr (4 + 2))
    val vel: IVec2d2 get() = IVec2d2((value ushr 2) and IVec2d2.MASK)
    val steering: Steering get() = Steering(value and Steering.MASK)

    constructor(pos: UVec2d8, vel: IVec2d2, steering: Steering) : this(
        pos.value.shl(4)
            .or(vel.value).shl(2)
            .or(steering.value)
    )

    constructor(pos: UVec2d8, vel: IVec2d2) : this(pos, vel, Steering.LEFT)

    override fun toString(): String {
        return "MineCart(pos=$pos, vel=$vel, steering=$steering)"
    }

    operator fun component1(): UVec2d8 = pos
    operator fun component2(): IVec2d2 = vel
    operator fun component3(): Steering = steering
}


// SOLVE FUNCTION
// ==============


fun solve(input: String): Pair<Pair<Int, Int>?, Pair<Int, Int>?> {
    val tracks = input.replace(HORIZ_CARTS, "-")
        .replace(VERT_CARTS, "|")
        .replace(NOT_TRACK, " ")
        .explode()

    var firstCollision: Pair<Int, Int>? = null
    var soleSurvivor: Pair<Int, Int>? = null

    var currentCarts = IntHeap()
    var nextCarts = IntHeap()

    input.replace(NOT_CART, " ").lineSequence().forEachIndexed { y, line ->
        line.forEachIndexed { x, c ->
            if (c != ' ') {
                val pos = UVec2d8(x, y)
                val vel = IVec2d2(c)

                val cart = MineCart(
                    pos = pos,
                    vel = vel
                )
                currentCarts.offer(cart.value)
            }
        }
    }

    var stepCount = 0

    while (currentCarts.isNotEmpty()) {
        currentCarts.drain { value ->
            val (srcPos, vel, steering) = MineCart(value)
            val dstPos = srcPos + vel

            // collision detection
            val collided = currentCarts.removeFirst { dstPos == MineCart(it).pos }
                    || nextCarts.removeFirst { dstPos == MineCart(it).pos }

            // collision response
            if (collided) {
                if (firstCollision == null) {
                    firstCollision = dstPos.x to dstPos.y
                }

                if (currentCarts.size + nextCarts.size == 1) {
                    if (currentCarts.size == 1) {
                        val (solePos) = MineCart(currentCarts.poll())
                        soleSurvivor = solePos.x to solePos.y
                    } else if (nextCarts.size == 1) {
                        val (solePos) = MineCart(nextCarts.poll())
                        soleSurvivor = solePos.x to solePos.y
                    }
                }
            }

            // movement
            var nextVel = vel
            var nextSteering = steering
            when (tracks[dstPos]) {
                '-', '|' -> Unit
                '/' -> nextVel = vel.turnDown()
                '\\' -> nextVel = vel.turnUp()
                '+' -> {
                    nextVel = vel.steer(steering)
                    nextSteering = steering.next()
                }
                else -> UNREACHABLE("Ran out of track!")
            }

            if (!collided) {
                val nextCart = MineCart(dstPos, nextVel, nextSteering)
                nextCarts.offer(nextCart.value)
            }
        }

        val tmp = currentCarts
        currentCarts = nextCarts
        nextCarts = tmp

        stepCount++
    }

    return firstCollision to soleSurvivor
}

val HORIZ_CARTS = Regex("""[<>]""")
val VERT_CARTS = Regex("""[v^]""")
val NOT_TRACK = Regex("""[^-|\\/+\n]""")
val NOT_CART = Regex("""[^<^>v\n]""")

fun String.explode(): Array<CharArray> = lineSequence()
    .map { it.toCharArray() }
    .toList()
    .toTypedArray()

operator fun Array<CharArray>.get(vec: UVec2d8): Char = this[vec.y][vec.x]

fun Int.zigzag(): Int = (this shl 1) xor (this shr 31)

fun UNREACHABLE(msg: String): Nothing = throw IllegalStateException(msg)

inline fun IntHeap.removeFirst(predicate: (Int) -> Boolean): Boolean {
    forEachIndexed { i, value ->
        if (predicate(value)) {
            removeAt(i)
            return true
        }
    }
    return false
}