So I got a question that was delivered as a 2D List

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

It asks to find the shortest path between w and z. So obviously, BFS would be the best course of action here to find that path the fastest. Here's my code for it

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

    while (queue.size > 0){
        val node = queue[0].removeFirst()
        val distance = queue[0].removeAt(1)

        if (node == destination) return distance as Int

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

        }


    }
    queue.sortedByDescending { it.size }

    return queue[0][1]
}

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(b)
        }
    }
    return graph
}

I am stuck on the return part. I wanted to use a list to keep track of the incrementation of the char, but it wont let me return the number. I could have done this wrong, so any help is appreciated. Thanks.

CodePudding user response：

If I paste your code into an editor I get this warning on your return queue[0][1] statement:

Type mismatch: inferred type is {Comparable<*> & java.io.Serializable} but Int was expected

The problem here is queue contains lists that hold Chars and Int distances, mixed together. You haven't specified the type that list holds, so Kotlin has to infer it from the types of the things you've put in the list. The most general type that covers both is Any?, but the compiler tries to be as specific as it can, inferring the most specific type that covers both Char and Int.

In this case, that's Comparable<*> & java.io.Serializable. So when you pull an item out with queue[0][1], the value you get is a Comparable<*> & java.io.Serializable, not an Int, which is what your function is supposed to be returning.

You can "fix" this by casting - since you know how your list is meant to be organised, two elements with a Char then an Int, you can provide that information to the compiler, since it has no idea what you're doing beyond what it can infer:

val node = queue[0].removeFirst() as Char
val distance = queue[0].removeAt(1) as Int

...

return queue[0][1] as Int

But ideally you'd be using the type system to create some structure around your data, so the compiler knows exactly what everything is. The most simple, generic one of these is a Pair (or a Triple if you need 3 elements):

val queue = mutableListOf(Pair<Char, Int>(root, 0))
// or if you don't want to explicitly specify the type
val queue = mutableListOf(root to 0)

Now the type system knows that the items in your queue are Pairs where the first element is a Char, and the second is an Int. No need to cast anything, and it will be able to help you as you try to work with that data, and tell you if you're doing the wrong thing.

It might be better to make actual classes that reflect your data, e.g.

data class Step(node: Char, distance: Int)

because a Pair is pretty general, but it's up to you. You can pull the data out of it like this:

val node = queue[0].first
val distance = queue[0].second

// or use destructuring to assign the components to multiple variables at once
val (node, distance) = queue[0]

If you make those changes, you'll have to rework some of your algorithm - but you'll have to do that anyway, it's broken in a few ways. I'll just give you some pointers:

• your return queue[0][1] line can only be reached when queue is empty
• queue[0].removeAt(1) is happening on a list that now has 1 element (i.e. at index 0)
• don't you need to remove items from your queue instead?
• when building your graph, you call add(b) twice
• try printing your graph, the queue at each stage in the loop etc to see what's happening! Make sure it's doing what you expect. Comment out any code that doesn't work so you can make sure the stuff that runs before that is working.

Good luck with it! Hopefully once you get your types sorted out things will start to fall into place more easily