day20.kt

/*
Day 20 of Adventofcode 2019 in Kotlin

Run like this:
    val maze = Maze.loadFrom("prod") // prod is a file with the puzzle input
    maze.scan()
    maze.prepareSegments()
    maze.createNodeMesh()
    maze.createPortalConnections()
    maze.shortestPathLength(maze.findPortal("AA"), maze.findPortal("ZZ"))
 */

import java.io.File
import kotlin.math.absoluteValue

data class Pos(val row: Int, val col: Int) {

    fun dist(other: Pos) =
       (row - other.row).absoluteValue + (col - other.col).absoluteValue
}

enum class Orientation {
    Outer,
    Inner
}

data class Portal(val pos: Pos , val label:String, val orientation: Orientation)

data class Node(val pos: Pos, val connectedSegments: List<Maze.Segment>)

data class PortalConnection(val portals: List<Portal>, val length: Int) {
    override fun toString(): String {
        return "${portals.first().label}-${portals.last().label}"
    }
}

data class Maze(private val data: Map<Pos, Char>, private val nRows: Int, private val nCols: Int) {
    val rawSegments = mutableListOf<Segment>()
    val preparedSegments = mutableListOf<Segment>()
    var nodes = mapOf<Pos, Node>()
    var portals = mutableListOf<Portal>()
    var portalConnections = listOf<PortalConnection>()

    companion object {
        fun loadFrom(fileName: String) : Maze {
            val data = mutableMapOf<Pos, Char>()
            var row = 0
            File(fileName).forEachLine { line ->
                line.trimEnd().forEachIndexed{ col,c  -> data[Pos(row, col)] = c }
                row += 1
            }
            val dim = data.keys.fold(-1 to -1){(max_row, max_col), (row, col) -> max_row.coerceAtLeast(row) to max_col.coerceAtLeast(col) }
            return Maze(data, dim.first, dim.second)
        }
    }

    data class Segment(val endA: Pos, val endB: Pos) {
        override fun toString(): String {
            return "$endA-$endB"
        }

        fun otherEnd(pos: Pos) = if (pos == endA) endB else endA

        fun getIntersection(other: Segment) : Pos? {
            return if (other.endA.row > endB.row || other.endA.col > endB.col || endA.row > other.endB.row || endA.col > other.endB.col)
                null
            else if (endA.row == endB.row)
                Pos(endA.row, other.endA.col)
            else
                Pos(other.endA.row, endA.col)
        }
    }

    fun findPortal(label: String): Portal {
        val p = portals.find { p -> p.label == label }
        require(p != null) {"Find attempted for non-existing portal"}
        return p
    }

    private fun splitSegments(segments: List<Segment>, other: List<Segment>) : List<Segment> {
        val res: MutableList<Segment> = mutableListOf()
        for (s in segments) {
            val intersections = other.mapNotNull { os -> s.getIntersection(os) }.toMutableList()
            if (intersections.isEmpty() || intersections[0] != s.endA) intersections.add(0, s.endA)
            if (intersections.isEmpty() || intersections.last() != s.endB) intersections.add(s.endB)
            for (ind in 1 until intersections.size) {
                res.add(Segment(intersections[ind - 1], intersections[ind]))
            }
        }
        return res
    }

    fun createNodeMesh() {
        val rawNodes = preparedSegments.fold(mutableListOf<Node>(), {acc, seg -> acc.add(Node(seg.endA, mutableListOf(seg))); acc.add(Node(seg.endB, mutableListOf(seg))); acc})
        val groupedNodes = rawNodes.groupBy{it.pos}
        nodes = (groupedNodes.map {entry ->  entry.key to Node(entry.key, entry.value.flatMap {node -> node.connectedSegments}) }).toMap()
    }

    fun findPortalConnections(portal: Portal) : List<PortalConnection> {
        val rootNode = nodes[portal.pos]!!
        return findPortalConnections(portal, listOf(), rootNode)
    }

    private fun findPortalConnections(start: Portal, visits: List<Node>, cursor: Node) : List<PortalConnection> {
        if (visits.isNotEmpty()) {
            val foundPortal = portals.find { p -> p.pos == cursor.pos }
            if (foundPortal != null) {
                val v = visits.toMutableList()
                v.add(cursor)
                val pathLength = (1 until v.size).fold(0, { acc, ind -> acc + v[ind].pos.dist(v[ind - 1].pos) })
                return listOf(PortalConnection(listOf(start, foundPortal), pathLength))
            }
        }
        val nextNodes = cursor.connectedSegments.mapNotNull { seg -> nodes[seg.otherEnd(cursor.pos)] }.filter{ node -> !visits.contains(node)}
        val nextVisits = visits.toMutableList()
        nextVisits.add(cursor)
        return nextNodes.flatMap { node -> findPortalConnections(start, nextVisits, node) }
    }

    fun createPortalConnections() {
        portalConnections = portals.flatMap {portal ->
            findPortalConnections(portal)
        }
    }

    fun shortestPathLength(start: Portal, end: Portal) : Int {
        val startConnections = portalConnections.filter{conn -> !conn.portals.any{ p -> p.orientation == Orientation.Outer && !listOf("AA", "ZZ").contains(p.label)} }.filter{ conn -> conn.portals.first() == start}
        val paths = startConnections.fold(mutableListOf<List<PortalConnection>>(), {acc, conn -> val contrib = findPathsTo(end, 0, conn, listOf()); acc.addAll(contrib); acc})
        return paths.map{p -> p.fold(-1, {acc, conn -> acc + conn.length + 1})}.min()!!
    }

    private fun findPathsTo(end: Portal, level: Int, nextConn: PortalConnection, rootConnectionPath: List<Pair<PortalConnection, Int>>) : List<List<PortalConnection>> {
        if (nextConn.portals.last().pos == end.pos && level == 0) {
            // If we have reached the end return the path
            val connectionPath = rootConnectionPath.toMutableList()
            connectionPath.add(nextConn to level)
            return listOf(connectionPath.map{it.first})
        } else if (rootConnectionPath.contains(nextConn to level) || level > 25) {
            // If there is a loop return empty
            return listOf()
        }  else {
            // Now passing through an inner portal will recurse downwards
            // While passing through an outer portal will pop the level
            // On the top level only AA and ZZ are functioning outer labels
            // On all other levels AA and ZZ are functioning as walls.
            val newRootConnectionPath = rootConnectionPath.toMutableList()
            newRootConnectionPath.add(nextConn to level)
            val newLevel = if (nextConn.portals.last().orientation  == Orientation.Inner) level + 1 else level - 1
            val nextConnections = portalConnections
                .filter{conn -> conn.portals.first().label == nextConn.portals.last().label && conn.portals.first().orientation != nextConn.portals.last().orientation}
                .filter{conn -> (newLevel == 0 && (conn.portals.last().orientation == Orientation.Inner || listOf("AA", "ZZ").contains(conn.portals.last().label))) || (newLevel > 0 && conn.portals.last().label != "ZZ" && conn.portals.last().label != "AA")}
            return nextConnections.fold(mutableListOf(),
                {acc, next ->
                    val contrib = findPathsTo(end, newLevel, next, newRootConnectionPath)
                    acc.addAll(contrib)
                    acc
                } )
        }
    }

    fun prepareSegments() {
        val horizontal = rawSegments.filter { p -> p.endA.row == p.endB.row }
        val vertical = rawSegments.filter { p -> p.endA.col == p.endB.col }
        preparedSegments.addAll(splitSegments(horizontal, vertical))
        preparedSegments.addAll(splitSegments(vertical, horizontal))
    }

    fun scan() {
        var pathStart: Pos? = null
        for (row in 0..nRows)  {
            for (col in 1..nCols) {
                val pos = Pos(row, col)
                val prevPos = Pos(row, col - 1)
                val nextPos = Pos(row, col + 1)
                val prevPrevPos = Pos(row, col - 2)
                val c = data[pos]
                if (c != null) {
                    if (c == '.') {
                        if (pathStart == null) pathStart = pos
                    } else {
                        if (pathStart != null) {
                            if (pos.col - pathStart.col > 1) rawSegments.add(Segment(pathStart, Pos(pos.row, pos.col -1 )))
                            pathStart = null
                        }
                        val prevC = data[prevPos]
                        if (prevC  != null && c.isUpperCase() && prevC.isUpperCase()) {
                            if (data[prevPrevPos] == '.') {
                                // In this case the portal is to the left of the label
                                val orientation = if (col == nCols) Orientation.Outer else Orientation.Inner
                                portals.add(Portal(prevPrevPos, "$prevC$c", orientation))
                            } else if (data[nextPos] == '.') {
                                // In this case the portal is to the right of the level
                                val orientation = if (col == 1) Orientation.Outer else Orientation.Inner
                                portals.add(Portal(nextPos, "$prevC$c", orientation))
                            }
                        }
                    }
                }
            }
        }
        pathStart = null
        for (col in 0..nCols)  {
            for (row in 1..nRows) {
                val pos = Pos(row, col)
                val prevPos = Pos(row - 1, col)
                val prevPrevPos = Pos(row - 2, col)
                val nextPos = Pos(row + 1, col)
                val c = data[pos]
                if (c != null) {
                    if (c == '.') {
                        if (pathStart == null) pathStart = pos
                    } else {
                        if (pathStart != null) {
                            if (pos.row - pathStart.row > 1) rawSegments.add(Segment(pathStart, Pos(pos.row - 1, pos.col)))
                            pathStart = null
                        }
                        val prevC = data[prevPos]
                        if (prevC != null && c.isUpperCase() && prevC.isUpperCase()) {
                            if (data[prevPrevPos] == '.') {
                                // In this case the portal is above the label
                                val orientation = if (row == nRows) Orientation.Outer else Orientation.Inner
                                portals.add(Portal(prevPrevPos, "$prevC$c", orientation))
                            } else if (data[nextPos] == '.') {
                                // In this case the portal is below the label
                                val orientation = if (row == 1) Orientation.Outer else Orientation.Inner
                                portals.add(Portal(nextPos, "$prevC$c", orientation))
                            }
                        }
                    }

                }
            }
        }
    }

    fun paint() {
        for (row in 0..nRows) {
            for (col in 0..nCols) {
                val c = data[Pos(row, col)]
                if (c != null) print(c)
            }
            println()
        }
    }
}