val input = readText("y2018/w3/d20/input.txt")

data class Point(val x: Int, val y: Int) {
    fun move(dir: Char) = when (dir) {
        'N' -> Point(x, y + 1)
        'E' -> Point(x + 1, y)
        'S' -> Point(x, y - 1)
        'W' -> Point(x - 1, y)
        else -> error("direction $dir")
    }
}

typealias Connections = MutableMap<Point, MutableSet<Point>>

fun Connections.connect(first: Point, second: Point) {
    getOrPut(first) { mutableSetOf() } += second
    getOrPut(second) { mutableSetOf() } += first
}

sealed class Regex {
    abstract fun walk(conn: Connections, start: Point): Set<Point>

    class Either(val list: List<Regex>) : Regex() {
        override fun walk(conn: Connections, start: Point) =
                list.flatMapTo(mutableSetOf()) { it.walk(conn, start) }

        override fun toString() = list.joinToString("|", "(", ")")
    }

    class Sequence(val list: List<Regex>) : Regex() {
        override fun walk(conn: Connections, start: Point) =
                list.fold(setOf(start)) { points, r ->
                    points.flatMapTo(mutableSetOf()) { r.walk(conn, it) }
                }

        override fun toString() = list.joinToString("")
    }

    class Simple(val str: String) : Regex() {
        override fun walk(conn: Connections, start: Point) =
                setOf(str.fold(start) { point, dir ->
                    point.move(dir).also { conn.connect(point, it) }
                })

        override fun toString() = str
    }
}

val stopChars = listOf(')', '|', null)

fun parseSequence(input: Queue<Char>): Regex {
    val list = mutableListOf<Regex>()
    while (input.peek() !in stopChars) {
        list += parseAtom(input)
    }
    return Regex.Sequence(list)
}

fun parseAtom(input: Queue<Char>): Regex =
        if (input.peek() == '(') {
            val list = mutableListOf<Regex>()
            while (input.poll() != ')') {
                list += parseSequence(input)
            }
            Regex.Either(list)
        } else {
            var str = ""
            while (input.peek()?.isLetter() == true)
                str += input.poll()
            Regex.Simple(str)
        }

fun main(args: Array<String>) {
    val cleanInput = input.replace("^", "").replace("\$", "")
    val inputQueue = LinkedList(cleanInput.toList())
    val regex = parseSequence(inputQueue)

    val conn: Connections = mutableMapOf()
    val start = Point(0, 0)
    regex.walk(conn, start)

    println(pathfind(start, conn))
}

fun pathfind(start: Point, conn: Connections): Pair<Int, Int> {
    val visited = mutableSetOf<Point>()
    val queue = ArrayDeque<Pair<Point, Int>>()

    queue.offer(start to 0)

    var maxDist = 0
    var farCount = 0

    while (queue.isNotEmpty()) {
        val (curr, dist) = queue.poll()
        visited += curr

        maxDist = dist
        if (dist >= 1000)
            farCount++

        queue.addAll(conn.getValue(curr).filter { it !in visited }.map { it to dist + 1 })
    }

    return maxDist to farCount
}