So I got some pointers and now I got this error.

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0
    at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:64)
    at java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:70)
    at java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:248)
    at java.base/java.util.Objects.checkIndex(Objects.java:372)
    at java.base/java.util.ArrayList.get(ArrayList.java:459)
    at udacity.GraphPraticeKt.shortestPath(GraphPratice.kt:159)
    at udacity.GraphPraticeKt.main(GraphPratice.kt:264)
    at udacity.GraphPraticeKt.main(GraphPratice.kt)

The goal is to find the shortest path to the following graph

  val SPE = listOf(
        listOf('w', 'x'),
        listOf('x', 'y'),
        listOf('z', 'y'),
        listOf('z', 'v'),
        listOf('w', 'v')
    )

Here's my code that I have so far

fun shortestPath(edges: List<List<Char>>, root: Char, destination: Char): Any {
    val graph =  buildGraph3(edges)
    val visited = hashSetOf(root)
    val queue = mutableListOf(Pair(root, 0))

    while (queue.size > 0){
        val current = queue.removeFirst()
        val node = current.first
        val distance = current.second

        if (node == destination) return distance

        graph[node]!!.forEach{
            if (!visited.contains(it)){
                visited.add(it)
                queue.add(Pair(node, distance   1))
            }

        }


    }
    queue.sortedByDescending { it.second }

    return println(queue[0].second)
}

fun buildGraph3(edges: List<List<Char>>): HashMap<Char, MutableList<Char>> {
    val graph = HashMap<Char, MutableList<Char>>()

    for (i in edges.indices){
        for (n in 0 until edges[i].size){
            var a = edges[i][0]
            var b = edges[i][1]
            if (!graph.containsKey(a)) { graph[a] = mutableListOf() }
            if (!graph.containsKey(b)) { graph[b] = mutableListOf() }
            graph[a]?.add(b)
            graph[b]?.add(a)
        }
    }
    return graph
}

If I was to put w and z as the root and destination, I should get 2. Any help or tips is welcomed. Thanks again.

CodePudding user response：

It was minor things that needed to be changed.

1. The return type had from Any to change to Int. I had it at Any so that I could print the output with the function, but it's not necessary and it's actually better to do it that way.

2. I didn't realize I put node instead of it inside the forEach loop. That was causing the error

3. I took off the queue.sortedByDescending { it.second } because I realized that the queue was already in that order. so no need to add a sorting algorithm to it.

Here's the correct code

fun shortestPath(edges: List<List<Char>>, root: Char, destination: Char): Int {
    val graph =  buildGraph3(edges)
    val visited = hashSetOf(root)
    val queue = mutableListOf(Pair(root, 0))


    while (queue.isNotEmpty()){
        val current = queue.removeFirst()
        val node = current.first
        val distance = current.second

        if (node == destination) return distance

        graph[node]!!.forEach{
            if (!visited.contains(it)){
                visited.add(it)
                queue.add(Pair(it, distance   1))
            }

        }


    }

    return queue[0].second
}

fun buildGraph3(edges: List<List<Char>>): HashMap<Char, MutableList<Char>> {
    val graph = HashMap<Char, MutableList<Char>>()

    for (i in edges.indices){
        for (n in 0 until edges[i].size){
            val a = edges[i][0]
            val b = edges[i][1]
            if (!graph.containsKey(a)) { graph[a] = mutableListOf() }
            if (!graph.containsKey(b)) { graph[b] = mutableListOf() }
            graph[a]?.add(b)
            graph[b]?.add(a)
        }
    }
    return graph
}