For LeetCode Problem 2467, I am using the following Python solution that is posted on Leetcode which passes all tests.
import collections
class Solution:
def mostProfitablePath(self, edges, bob: int, amount) -> int:
graph = collections.defaultdict(list)
for n1, n2 in edges:
graph[n1].append(n2)
graph[n2].append(n1)
# depth of bob traversal path (DFS)
self.bob_path = []
def dfs(node, parent, path):
if node == 0:
self.bob_path = list(path)
return True
for neighbor in graph[node]:
if neighbor == parent:
continue
path.append(neighbor)
if dfs(neighbor, node, path):
return True
path.pop()
return False
dfs(bob, -1, [bob])
step = dict()
for i in range(len(self.bob_path)):
step[self.bob_path[i]] = i
# loop all possible Alice traversal path (BFS)
ans = float('-Inf')
# Base case if bob is also at node 0
profit_ini = amount[0] if bob != 0 else amount[0] // 2
que = collections.deque([(0, -1, profit_ini)])
depth = 0
while que:
# For loop is to make sure we iterate over every node in level before moving on to next level and seperate nodes on each level with depth counter
for _ in range(len(que)):
cur, parent, profit = que.pop(0)
# Not the root node and it only has one connection == leaf node ==> update potential answer
if cur != 0 and len(graph[cur]) == 1:
ans = max(ans, profit)
for neighbor in graph[cur]:
if neighbor == parent:
continue
# case where either alice node was not encountered by bob or it is in bob's path but he is not yet there
if neighbor not in step or depth + 1 < step[neighbor]:
new_profit = amount[neighbor]
# Reached at same time (depth of neighbor == the depth of bob (as indicated by i in step))
elif depth + 1 == step[neighbor]:
new_profit = amount[neighbor] // 2
else:
new_profit = 0
que.append((neighbor, cur, profit + new_profit))
depth += 1
return ans
I am attempting to translate the solution to Javascript and one test case fails and I don't understand why. Could this be caused by a typo or by the way Javascript handles comparisons, division, etc.?
/**
* @param {number[][]} edges
* @param {number} bob
* @param {number[]} amount
* @return {number}
*/
var mostProfitablePath = function (edges, bob, amount) {
let n = amount.length
let graph = new Array(n).fill(0).map(() => [])
for (const [n1, n2] of edges) {
graph[n1].push(n2)
graph[n2].push(n1)
}
var DFS = (node, parent, path) => {
if (node === 0) {
return path
}
for (const neighbor of graph[node]) {
if (neighbor === parent) {
continue
}
path.push(neighbor)
let result = DFS(neighbor, node, path)
if (result !== undefined && result !== false) {
return result
}
path.pop()
}
return false
}
let bob_path = DFS(bob, -1, [bob])
let step = {}
for (let i = 0; i < bob_path.length; i++) {
step[bob_path[i]] = i
}
let ans = -Infinity
let ini_profit = bob_path[0] === 0 ? Math.floor(amount[0] / 2) : amount[0]
let depth = 0
let queue = [[0, -1, ini_profit]]
while (queue.length) {
for (let j = 0; j < queue.length; j++) {
let [cur, parent, profit] = queue.shift()
if (graph[cur].length === 1 && cur != 0) {
ans = Math.max(profit, ans)
}
for (const neighbor of graph[cur]) {
if (neighbor === parent) continue
let new_profit
if (!step.hasOwnProperty(neighbor) || depth + 1 < step[neighbor]) {
new_profit = amount[neighbor]
}
else if (depth + 1 === step[neighbor]) {
new_profit = Math.floor(amount[neighbor] / 2)
} else {
new_profit = 0
}
queue.push([neighbor, cur, new_profit + profit])
}
}
depth++
}
return ans
};
Test Case for which is fails:
edges =
[[0,38],[0,59],[1,30],[1,62],[1,53],[2,41],[2,37],[3,21],[4,35],[4,54],[5,32],[5,69],[6,26],[6,16],[6,61],[6,52],[7,34],[8,10],[9,11],[9,43],[10,48],[11,29],[12,63],[12,58],[12,13],[13,36],[13,34],[14,65],[14,15],[15,17],[15,49],[16,40],[17,20],[17,24],[18,58],[19,25],[21,34],[22,55],[23,45],[23,59],[25,43],[27,32],[28,49],[28,33],[31,61],[33,39],[33,51],[33,53],[34,68],[34,69],[37,52],[42,52],[43,61],[44,58],[46,49],[47,55],[47,50],[48,56],[48,66],[50,58],[52,66],[52,65],[53,57],[54,63],[55,57],[59,60],[59,67],[59,65],[64,69]]
bob =
47
amount =
[4664,5822,-9152,7258,-5468,4698,2568,9880,-4046,9884,-3540,-2260,5264,-7050,-6998,-1688,-6256,-5350,5136,7476,-4108,1288,1336,-6126,2940,698,-2900,-2342,-2310,858,572,640,-9674,5746,5068,7128,636,6680,-1840,3574,7592,-5882,-1974,-2766,-620,1088,-8930,7756,9966,380,8884,-954,-8198,-5862,-3100,7728,7090,-4648,4076,994,4232,9810,-2904,-1106,-4172,-5884,-9582,5320,-4086,6346]
Output
16435
Expected
17590
You have not converted the Python code correctly at this point:
for _ in range(len(que)):
to:
for (let j = 0; j < queue.length; j++) {
The difference is that Python evaluates len(que) once, while your JavaScript code evaluates queue.length at the start of each iteration. And this has an impact because the loop adds items to the queue.
So make sure to only evaluate queue.length once. For example, it could be like this:
for (let j = queue.length; j > 0; j--) {
With that correction it will work.