import java.io.File
import java.io.BufferedReader

val infile = File("puzzle.aoc")
val puzzle = infile.readLines()

Day 9: All in a Single Night

Part 1

Every year, Santa manages to deliver all of his presents in a single night.

This year, however, he has some new locations to visit; his elves have provided him the distances between every pair of locations. He can start and end at any two (different) locations he wants, but he must visit each location exactly once. What is the shortest distance he can travel to achieve this?

For example, given the following distances:

London to Dublin = 464
London to Belfast = 518
Dublin to Belfast = 141

The possible routes are therefore:

Dublin -> London -> Belfast = 982
London -> Dublin -> Belfast = 605
London -> Belfast -> Dublin = 659
Dublin -> Belfast -> London = 659
Belfast -> Dublin -> London = 605
Belfast -> London -> Dublin = 982

The shortest of these is London -> Dublin -> Belfast = 60, and so the answer is605 in this example.

Task 1: What is the distance of the shortest route?

var destinations : Set<String> = emptySet()

for (line in puzzle) {
    val route = line.split(" ")
    destinations = destinations.plus(arrayOf(route[0], route[2]))
}

// Get an alphabetical List of the destinations
val dests = destinations.sorted()

// Load the adjacency matrix for the loaded graph
fun loadAdjacency() : Array<IntArray> {
    var matrix = Array(dests.size) { IntArray(dests.size) }

    for (line in puzzle) {
        val route = line.split(" ")
        val x = dests.indexOf(route[0])
        val y = dests.indexOf(route[2])
    
        matrix[x][y] = route[4].toInt()
        matrix[y][x] = route[4].toInt()    
    }
    
    return matrix
}

// Print a M² Matrix
fun printMatrix(matrix : Array<IntArray>) {
    matrix.forEach { it.forEach { x -> when(x) {
        Int.MAX_VALUE -> print("X,\t")
        Int.MIN_VALUE -> print("A,\t")
        else ->         print("$x,\t") }}; println() }
}

Find distances and draw Paths from every starting point

var minDistances = IntArray(dests.size)
var matrixCopy = loadAdjacency()

for (start in 0 until dests.size) {
    matrixCopy = loadAdjacency()
    var dest = start 
    
    print("${dests[start]}")
    for (step in 0 until dests.size-1) {
        var min = matrixCopy[dest].filter { it > 0 }.minOrNull()     
        var position = matrixCopy[dest].indexOf(min!!)
         
        matrixCopy[dest][position] = 0
        
        for (x in 0 until dests.size) {
            matrixCopy[x][dest] = 0
        }
    
        minDistances[start] += min
        print(" -> ${dests.get(position)}")
        dest = position
    }
    
    println("\nDistanz:\t ${minDistances[start]}\n")  
}

AlphaCentauri -> Faerun -> Tristram -> Norrath -> Snowdin -> Tambi -> Straylight -> Arbre
Distanz:	 211

Arbre -> Straylight -> Norrath -> Tristram -> AlphaCentauri -> Faerun -> Snowdin -> Tambi
Distanz:	 222

Faerun -> AlphaCentauri -> Tambi -> Snowdin -> Norrath -> Tristram -> Arbre -> Straylight
Distanz:	 117

Norrath -> Tristram -> Arbre -> Straylight -> Tambi -> AlphaCentauri -> Faerun -> Snowdin
Distanz:	 193

Snowdin -> Norrath -> Tristram -> Arbre -> Straylight -> Tambi -> AlphaCentauri -> Faerun
Distanz:	 130

Straylight -> Arbre -> Tristram -> Norrath -> Snowdin -> Tambi -> AlphaCentauri -> Faerun
Distanz:	 117

Tambi -> AlphaCentauri -> Faerun -> Tristram -> Norrath -> Snowdin -> Arbre -> Straylight
Distanz:	 212

Tristram -> Norrath -> Snowdin -> Tambi -> AlphaCentauri -> Faerun -> Straylight -> Arbre
Distanz:	 240

Get Minimum Distance

minDistances.minOrNull()!!

117

Part 2

The next year, just to show off, Santa decides to take the route with the longest distance instead.

He can still start and end at any two (different) locations he wants, and he still must visit each location exactly once.

For example, given the distances above, the longest route would be 982 via (for example) Dublin -> London -> Belfast.

Task 2: What is the distance of the longest route?

var maxDistances = IntArray(dests.size)
var matrixCopy = loadAdjacency()

for (start in 0 until dests.size) {
    matrixCopy = loadAdjacency()
    var dest = start 
    
    print("${dests[start]}")
    for (step in 0 until dests.size-1) {
        var max = matrixCopy[dest].filter { it > 0 }.maxOrNull()     
        var position = matrixCopy[dest].indexOf(max!!)
         
        matrixCopy[dest][position] = 0
        
        for (x in 0 until dests.size) {
            matrixCopy[x][dest] = 0
        }
    
        maxDistances[start] += max
        print(" -> ${dests.get(position)}")
        dest = position
        
        /*println()
        printMatrix(matrixCopy)
        println()*/
        
    }
    
    println("\nDistanz:\t ${maxDistances[start]}\n")
}

AlphaCentauri -> Norrath -> Faerun -> Arbre -> Tambi -> Straylight -> Tristram -> Snowdin
Distanz:	 867

Arbre -> Faerun -> Norrath -> AlphaCentauri -> Straylight -> Tristram -> Snowdin -> Tambi
Distanz:	 818

Faerun -> Arbre -> Tambi -> Norrath -> AlphaCentauri -> Straylight -> Tristram -> Snowdin
Distanz:	 833

Norrath -> Faerun -> Arbre -> Tambi -> Straylight -> Tristram -> Snowdin -> AlphaCentauri
Distanz:	 815

Snowdin -> Tristram -> Straylight -> Faerun -> Arbre -> Tambi -> Norrath -> AlphaCentauri
Distanz:	 863

Straylight -> Faerun -> Arbre -> Tambi -> Norrath -> AlphaCentauri -> Snowdin -> Tristram
Distanz:	 822

Tambi -> Arbre -> Faerun -> Norrath -> AlphaCentauri -> Straylight -> Tristram -> Snowdin
Distanz:	 909

Tristram -> Straylight -> Faerun -> Arbre -> Tambi -> Norrath -> AlphaCentauri -> Snowdin
Distanz:	 842

Get Maximum Distance

maxDistances.maxOrNull()!!

909