import java.util.*

// Mostly boilerplate to prevent toString from infinite recursion
class Node<T : Comparable<T>>(
    val value: T,
    val children: MutableSet<Node<T>> = hashSetOf(),
    val parents: MutableSet<Node<T>> = hashSetOf()
) : Comparable<Node<T>> {
    override fun compareTo(other: Node<T>): Int = this.value.compareTo(other.value)

    override fun toString(): String =
        StringBuilder(Node::class.java.simpleName).apply {
            append('(')

            append("value=")
            append(value)
            append(", ")

            children.joinTo(this, prefix = "children=[", postfix = "], ", transform = { it.value.toString() })
            parents.joinTo(this, prefix = "parents=[", postfix = "], ", transform = { it.value.toString() })

            append(')')
        }.toString()

    // Identity equals and hashCode are fine
}

typealias Graph<T> = MutableMap<T, Node<T>>

typealias Step = Char
typealias StepNode = Node<Step>
typealias StepGraph = Graph<Step>

val STEP_PATTERN = Regex("""Step ([A-Z]) must be finished before step ([A-Z]) can begin.""")

fun graphSteps(text: CharSequence): StepGraph {
    val graph: Graph<Step> = hashMapOf()

    STEP_PATTERN.findAll(text)
        .forEach { match ->
            val curStep = match.groupValues[1][0]
            val parentStep = match.groupValues[2][0]

            val childNode = graph.getOrPut(curStep) { StepNode(curStep) }
            val parentNode = graph.getOrPut(parentStep) { StepNode(parentStep) }

            parentNode.children.add(childNode)
            childNode.parents.add(parentNode)
        }

    return graph
}

fun main(args: Array<String>) {
    timeIt { solvePart1(INPUT) }.apply { print("Day 1 Part 1: ") }
    timeIt { solvePart2(INPUT) }.apply { print("Day 1 Part 2: ") }
}

fun solvePart1(text: CharSequence): CharSequence {
    val graph = graphSteps(text)

    val leaves = graph.values.asSequence().filter { it.children.isEmpty() }

    val visited = hashSetOf<StepNode>()
    val frontier = leaves.toCollection(PriorityQueue())

    val output = StringBuilder()
    var next = frontier.poll()
    while (next != null) {
        visited.add(next)
        output.append(next.value)

        next.parents.forEach { parent ->
            if (parent.children.all { child -> child in visited }) {
                frontier.offer(parent)
            }
        }

        next = frontier.poll()
    }

    return output
}

// Part 2. Its not very elegant but it worked ¯\_(ツ)_/¯

data class Worker(private var remaningTime: Int, var job: StepNode?) {
    fun isDone(): Boolean {
        return remaningTime <= 0
    }

    fun takeJob(job: StepNode?) {
        if (job != null) {
            remaningTime = job.value - 'A' + 1  + 60
            this.job = job
        }
    }

    fun doWork() {
        remaningTime--
    }
}

fun solvePart2(text: CharSequence): Int {
    val graph = graphSteps(text)

    val leaves = graph.values.asSequence().filter { it.children.isEmpty() }

    val visited = hashSetOf<StepNode>()
    val completed = hashSetOf<StepNode>()
    val frontier = leaves.toCollection(mutableListOf())

    val workers = Array(5) { Worker(0, null) }

    fun tryGetJob(): StepNode? {
        return frontier.find { cand ->
            cand.children.all { child -> child in completed }
        }?.let { next ->
            visited.add(next)

            next.parents.forEach { parent ->
                if (parent.children.all { child -> child in visited }) {
                    frontier.add(parent)
                    frontier.sort()
                }
            }

            frontier.remove(next)
            next
        }
    }

    // Do the work. This actually does a tick every time step, a nicer solution would be event based

    val jobCount = graph.size
    var seconds = 0
    while (completed.size < jobCount) {
        for (worker in workers) {
            if (worker.isDone()) {
                worker.job?.also {
                    completed.add(it)
                    worker.job = null
                }

                worker.takeJob(tryGetJob())
            }

            worker.doWork()
        }

        seconds++

    }

    // The work loop marks completion the start of the loop, so it always does an extra iteration
    return seconds - 1
}

typealias BenchmarkResult<T> = Pair<T, Float>

inline fun <T> timeIt(f: () -> T): BenchmarkResult<T> {
    val result = f()

    val start = System.nanoTime()
    var x: Any? = null
    for (t in 1 .. 5) {
        x = f()
    }
    val elapsed = (System.nanoTime() - start)
    val millis = elapsed / 1_000_000f / 5f

    return result to millis
}

fun <T> BenchmarkResult<T>.print(prefix: CharSequence) {
    println("$prefix ${this.first} (${this.second}ms)")
}