Blunder - Episode 2 - Puzzle discussion

Dijkstra algorithm is for finding the shortest path in the graph - that is the one with the minimum sum of edge weights. Another constraint is that all weights must be non-negative. This is coming from how the algorithm works (by gradually extending the current path in a BFS manner using edge weight as priority/order).
The wikipedia article is quite detailed: https://en.wikipedia.org/wiki/Dijkstra's_algorithm

Here we need the maximum cost path of the graph which is different from the minimum. If you simply multiply all weights by (-1), then minimum becomes maximum, but then your weights will become negative and the algo will fail. You can use Floyd-Warshall or Bellman-Ford algorithms (see https://en.wikipedia.org/wiki/Floydā€“Warshall_algorithm, https://en.wikipedia.org/wiki/Bellmanā€“Ford_algorithm for explanation and pseudocode) to find the minimum cost path of the graph with negative weights, but these algorithms are computationally more complex than Dijkstra. For me, they timeouted above 5000 rooms.

In the end, a simple DFS with some memoization was the working AND fast-enough solution for me, and not any of these generic graph algorithms.

3 Likes

No need to use any of these: Breadth First Search, Dijkstra, Pathfinding, Memoization, Dynamic programming, Recursion, DFS.

One can get the solution in single FOR loop when reading input.
BigO(n)

[disclaimer] this could be a spoiler
Iā€™ve made this :

// start function with R = first room
function(R)
1. if R has no neighbors, go to (5.)
2. for each neighbors of R,
    2.0. if neighbour is marked as visited, T = neighbour.money + neighbour.total, go to (2.2.)
    2.1. T = function(neighbour)
    2.2. add T to L
3. R.total = highest value of L
4. mark R as visited
5. return R.money + R.total

I just wonder if that algo has a name, it look like something between IDA* and the Backpropagation of a MCTS, anyone ?

Hi there
I use a BFS kind of solution.
The longest test takes 12 ms.
The test are all good, but when I submit, I get between two and six tests ok, and with every submit, there are other tests that work, even without changing anything on the code.
I have no idea how this i possible

Please read the discussion above to look for some inspiration. In particular, memoisation may help.

Continuing the discussion from Blunder - Episode 2 - Puzzle discussion:

I implemented with Dijkstra but failed at test case 04 (Found: 379, expected: 358).
Would you please help to check from which part, my solution will return the incorrect value.

import java.util.*
import java.io.*
import java.math.*

fun main(args : Array<String>) {
    val input = Scanner(System.`in`)
    val N = input.nextInt()
    if (input.hasNextLine()) {
        input.nextLine()
    }
    val edges: Array<IntArray> = Array(N + 1) { IntArray(N + 1) }
    for (i in 0 until N) {
        val room = input.nextLine()
        val data = room.split(" ")
        val roomNumber = data[0].toInt()
        val money = data[1].toInt()
        (2..data.size - 1)
            .map {
                if (data[it] == "E") {
                    N
                } else {
                    data[it].toInt()
                }
            }
            .forEach {
                edges[roomNumber][it] = money
            } 
    }
    println(dijkstra(0, edges, N))    
}

fun dijkstra(start: Int, edges: Array<IntArray>, end: Int): Int {
    val V = IntArray(end + 1)
    val Q = (0..end).toMutableList()

    while (Q.isNotEmpty()) {
        val u = extractMax(Q, V)
        edges[u].forEachIndexed { index, value ->
            if (value != 0 && V[index] < V[u] + value) {
               V[index] = V[u] + value     
            }
        }
    }
    return V[end]
} 

fun extractMax(Q: MutableList<Int>, V: IntArray): Int {
    var maxNode = Q[0]
    var maxValue = V[0]
    Q.forEach {
        if (V[it] > maxValue) {
            maxValue = V[it]
            maxNode = it
        }
    }
    Q.remove(maxNode)
    return maxNode
}

I think it is better for you to check your code yourself, given this is a hard puzzle and you are relatively skilled. I can give you the breakdown of the answer so it may be easier for you to check:

Room Money
  0    46
  1    29
  4    36
  7    21
 12    38
 18    31
 25    40
 32    43
 41    27
 50    47
      ___
      358
      ===

I fixed my implementation by changing the way to calculate the cost but seems we cannot use Dijkstra algorithm in this scenario as Dijkstra only return the max value at the traversal time but may be not the maximum one after finish traversal

Finally, I solved it by using DFS plus memorization techniques like hash map to store the previous money amount!

1 Like

Hi everyone,

I have some trouble with this puzzle.

So far, Iā€™ve coded a sort of modified Djikstraā€™s algorithm. I know itā€™s not working in all situations, especially if there are cycling paths, but thatā€™s not my main problem for now. When I execute my code against the third test (15 rooms), my code find a path that earns 127. But the response should be 88.
Iā€™ve checked manually the solution found by my algorithm and Iā€™va come up with the same result.

This probably means that I missed or misunderstood one of the puzzleā€™s rules, but I canā€™t find which one.

The puzzle data :

Room Id Room Mny Link 1 Link 2
0 17 1 2
1 15 0 4
2 15 4 5
3 20 1 7
4 12 2 8
5 11 8 9
6 18 3 11
7 19 4 12
8 12 5 13
9 11 13 14
10 13 6 -1
11 14 7 6
12 17 8 7
13 19 9 8
14 15 -1 9
-1 0 10 14

(Iā€™ve made a beautiful graph from this data to paste here, only to discover new users canā€™t upload images. Sorry).

The solution found by my algo is :
0 ā†’ 1 ā†’ 4 ā†’ 2 ā†’ 5 ā†’ 8 ā†’ 13 ā†’ 9 ā†’ 14 ā†’ -1
17 + 15 + 12 + 15 + 11 + 12 + 19 + 11 + 15 = 127

The problem may lay in my understanding of the rule ā€œBlunder can never go backā€. I thought first that it means blunder cannot travel to an already visited room (which my solution complies with). In a second time I thought that maybe it means that he cannot travel to a room that have an Id inferior to the current room Id, but in this case the max money I earn is 69.

So anybody here can help me find what I am doing wrong please ?

Thanks !

It looks like the data you have is different from the actual data:

You may access the actual inputs by clicking the button above the test cases (see the screenshot below), and then selecting a case.

1 Like

Iā€™m so ashamed ! :flushed: :flushed:
Iā€™m using an external IDE and I must have changed the test case for some reason I canā€™t remember.
With the correct set of data, it eventually works.
Thanks for pointing me the good direction and for the usefull tip for accessing test cases data !

1 Like

Lately Iā€™ve been trying to use the generic pathfinder implementations in scipy and this felt like a good case for it. Indeed, once the input is prepared I could get the answer in one line, but it timed out on the 9870 rooms case. I spent some time trying to optimize it. In the end the simplest recursive DFS with memoization solved it.