package com.adventofcode.y2018

import com.adventofcode.y2018.utils.*
import com.soywiz.kds.Queue

// https://adventofcode.com/2018/day/20
fun solve_day20_part1(input: String): Int {
    return solve(input).values.max() ?: 0
}

fun solve_day20_part2(input: String): Int {
    return solve(input).values.count { it >= 1000 }
}

private fun solve(input: String): MutableMap<Position, Int> {
    val graph = GraphBuilder(input).build()
    val field = buildField(input, graph)
    return bfs(field)
}

private class Graph(val initialIndexes: List<Int>, val transitions: Map<Int, List<Int>>)

private class GraphBuilder (val input: String) {
    private var index = input.lastIndex - 1

    private val transitions = mutableMapOf<Int, List<Int>>()

    fun build(): Graph {
        val initialIndexes = parseSequence(listOf())
        return Graph(initialIndexes, transitions)
    }

    private fun parseSequence(nextIndexes: List<Int>): List<Int> {
        var initialIndexes = nextIndexes
        while (index > 0 && input[index] != '|' && input[index] != '(') {
            initialIndexes = parseOne(initialIndexes)
        }
        return initialIndexes
    }

    private fun parseOne(nextIndexes: List<Int>): List<Int> {
        return when (input[index]) {
            ')' -> parseBranch(nextIndexes)
            else -> parseDirection(nextIndexes)
        }
    }

    private fun parseDirection(nextIndexes: List<Int>): List<Int> {
        val initialIndexes = listOf(index)
        transitions[index] = nextIndexes
        index--
        return initialIndexes
    }

    private fun parseBranch(nextIndexes: List<Int>): List<Int> {
        val initialIndexes = mutableListOf<Int>()
        index--
        do {
            initialIndexes += parseSequence(nextIndexes)
            index--
        } while (input[index + 1] != '(')
        return initialIndexes
    }
}

private fun buildField(input: String, graph: Graph): Map<Position, Set<Direction>> {
    val field = mutableMapOf<Position, MutableSet<Direction>>()

    val visited = graph.initialIndexes.map { index -> Position(0, 0) to index }.toMutableSet()
    val queue = Queue(*visited.toTypedArray())

    while (queue.isNotEmpty()) {
        val (position, index) = queue.dequeue()
        val direction = Direction.fromCardinal(input[index])
        field.getOrPut(position) { mutableSetOf() }.add(direction)
        val newPosition = position.move(direction)
        graph.transitions.getValue(index)
            .map { newPosition to it }
            .filter { visited.add(it) }
            .forEach { queue.enqueue(it) }
    }

    return field.withDefault { mutableSetOf() }
}

private fun bfs(field: Map<Position, Set<Direction>>): MutableMap<Position, Int> {
    val distances = mutableMapOf(Position(0, 0) to 0)
    val queue = Queue(Position(0, 0))

    while (queue.isNotEmpty()) {
        val position = queue.dequeue()
        val distance = distances.getValue(position)

        field.getValue(position)
            .map { direction -> position.move(direction) }
            .filter { it !in distances }
            .forEach {
                distances[it] = distance + 1
                queue.enqueue(it)
            }
    }

    return distances
}