The Illusion of Easy in programming

Have you ever been programming, listening to songs in background, crushing it when suddenly

Test failed: Expected ligma got balls, lol have fun figuring this one out bud

The same thing happened to me when I was working on the LeetCode problem Minimum fuel to report to capital. It is a pretty standard graph problem which uses DFS/BFS and I had already solved the problem in Rust, C, and Java so I figured, I’d transcribe it to python because obviously the next step when you have solved a problem in 3 different languages is to solve it in a 4th language.

So, I basically did a one to one translation of my Rust code to my Python and…

Have a look at my code in rust and python and see if you can spot the bug

impl Solution {
    pub fn minimum_fuel_cost(roads: Vec<Vec<i32>>, seats: i32) -> i64 {
        const CAPITAL : usize = 0;

        let num_of_cities: usize = roads.len() + 1;
        let seats: i64 = i64::from(seats);

        let mut adj_list : Vec<Vec<usize>> = vec![Vec::with_capacity(num_of_cities); num_of_cities];

        for road in roads {
            adj_list[road[0] as usize].push(road[1] as usize);
            adj_list[road[1] as usize].push(road[0] as usize);
        }


        let mut distances: Vec<u32> = vec![0; num_of_cities];
        let mut frontier: Vec<(usize, u32)> = vec![(CAPITAL, 0)];
        let mut visited: Vec<bool> =  vec![false; num_of_cities];

        while let Some((city, dist)) = frontier.pop() {
            distances[city] = dist;
            visited[city] = true;
            for &neighbor in adj_list[city].iter() {
                if !visited[neighbor] {
                    frontier.push((neighbor, dist + 1));
                }
            }
        }

        let mut frontier : Vec<usize> = (0..num_of_cities).collect();
        let mut people_count : Vec<i64> = vec![1; num_of_cities];

        frontier.sort_unstable_by_key(|&city| distances[city]);

        while let Some(city) = frontier.pop() {
            for &neighbor in adj_list[city].iter() {
                if distances[neighbor] < distances[city] {
                    people_count[neighbor] += people_count[city];
                    break;
                }
            }
        }

        let car_count : Vec<i64> = people_count
        .into_iter()
        .map(|count| count / seats + if count % seats == 0 {0} else {1})
        .collect();

        let capital_count = car_count[CAPITAL];

        car_count.into_iter().sum::<i64>() - capital_count
    }
}

class Solution:
    def __init__(self):
        self._CAPITAL = 0

    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        number_of_cities: int = len(roads) + 1
        adj_list: List[List[int]] = [[]] * number_of_cities

        for road in roads:
            adj_list[road[0]].append(road[1])
            adj_list[road[1]].append(road[0])
        
        distances: List[int] = [0] * number_of_cities
        frontier: List[Tuple[int, int]] = [(self._CAPITAL, 0)]
        visited: List[bool] = [False] * number_of_cities

        while frontier:
            city, distance = frontier.pop(-1)
            distances[city] = distance
            visited[city] = True

            for neighbor in adj_list[city] :
                if not visited[neighbor]:
                    frontier.append((neighbor, distance + 1))
        
        frontier: List[int] = sorted(range(number_of_cities), key = lambda city : distances[city])
        people_count: List[int] = [1] * number_of_cities

        while frontier:
            city = frontier.pop()
            for neighbor in adj_list[city]:
                if distances[neighbor] < distances[city] :
                    people_count[neighbor] += people_count[city]
                    break
        
        people_count.pop(0)
        car_count: List[int] = [(count // seats) + (1 if count % seats != 0 else 0) for count in people_count]
        return sum(car_count)

Do you see it? If you don’t I’ll give you the line, see if you can find it with that

The problem is in the following line

Visit Now