Solving the Travelling Salesman Problem with Kotlin and JGraphT (done for AdventOfCode day 9)

TravellingSalesMan.kt

// use regular Java imports: Kotlin is 100% compatible to Java
import org.jgrapht.DirectedGraph
import org.jgrapht.Graph
import org.jgrapht.graph.SimpleDirectedGraph

/**
 * A class defining an Edge in the Graph. The `val`s are automatically accessible via getters.
 * Additionally, the annotation `data`automatically generates equals(), hashcode() and more.
 */
data class Edge(val source: String, val target: String, val duration: Int)

/**
 * An extension function for all Iterable<Edge>, e.g. ArrayLists. Calling [duratin()] returns the sum
 * of all durations of all Edges stored in this Iterable.
 */
fun Iterable<Edge>.duration() = sumBy { it.duration }

/**
 * Another extension function. It returns a List containing all visited nodes, by concatenating
 * all sources of all Edges and the target of the last Edge.
 */
fun Iterable<Edge>.visited() = map { it.source } + last().target

/**
 * The following extension functions enable the usage of the += operator on Graph objects.
 */
operator fun <V> Graph<V, *>.plusAssign(vertex:V) { addVertex(vertex) }
operator fun Graph<String, Edge>.plusAssign(edge:Edge) { addEdge(edge.source, edge.target, edge) }

/**
 * The main entry point of our program - no class is needed!
 */
fun main(args: Array<String>) {
    // instantiation of a class is done without `new`
    val graph = SimpleDirectedGraph<String, Edge>(Edge::class.java)

    // split the input (found in the bottom of the file) into lines and parse each line
    input.lines().forEach { line ->
        val (route, duration) = line.split(" = ")
        val (source, target) = route.split(" to ")

        graph += source
        graph += target
        graph += Edge(source, target, duration.toInt())
        graph += Edge(target, source, duration.toInt())
    }

    // ?. is a null safe operator. If [findTravellingSalesmanRoute()] returns null, nothing happens.
    // If it returns a solution, the let {}-block is executed.
    graph.findTravellingSalesmanRoute()?.let { route ->
        // Kotlin enables string interpolation: the parts in ${} are executed!
        println("Visited ${route.visited()} in ${route.duration()}")
    }
}

/**
 * An extension function for DirectedGraphs: It calculates the Travelling Salesman Route via recursive bruteforce.
 */
fun DirectedGraph<String, Edge>.findTravellingSalesmanRoute(route: List<Edge>? = null): List<Edge>? {
    // Assign a variable, based on if-conditions.
    val routes = if (route == null) {
        // If no route is given, this is the first call.
        // For every Edge in the Graph, we try out a Route that starts with it
        edgeSet().map { findTravellingSalesmanRoute(listOf(it)) }
    } else if (route.visited().toSet() == vertexSet()) {
        // If the Route contains all vertices from the Graph, we found a solution
        listOf(route)
    } else {
        // [route] contains a partial, unfinished route.
        // First, search for all outgoing edges of the current position of the route
        outgoingEdgesOf(route.last().target)
                // Then, remove all Edges whose targets already were visited
                .filterNot { route.visited().contains(it.target) }
                // Finally, append the new Edge to the route and go on recursively
                .map { findTravellingSalesmanRoute(route + it) }
    }

    // Filter all invalid routes and return the best route - the one with minimum duration
    return routes.filterNotNull().minBy { it.duration() }
}

val input = """Faerun to Norrath = 129
Faerun to Tristram = 58
Faerun to AlphaCentauri = 13
Faerun to Arbre = 24
Faerun to Snowdin = 60
Faerun to Tambi = 71
Faerun to Straylight = 67
Norrath to Tristram = 142
Norrath to AlphaCentauri = 15
Norrath to Arbre = 135
Norrath to Snowdin = 75
Norrath to Tambi = 82
Norrath to Straylight = 54
Tristram to AlphaCentauri = 118
Tristram to Arbre = 122
Tristram to Snowdin = 103
Tristram to Tambi = 49
Tristram to Straylight = 97
AlphaCentauri to Arbre = 116
AlphaCentauri to Snowdin = 12
AlphaCentauri to Tambi = 18
AlphaCentauri to Straylight = 91
Arbre to Snowdin = 129
Arbre to Tambi = 53
Arbre to Straylight = 40
Snowdin to Tambi = 15
Snowdin to Straylight = 99
Tambi to Straylight = 70"""