The Illusion of Easy in programming
<p>Have you ever been programming, listening to songs in background, crushing it when suddenly</p>
<pre>
Test failed: Expected ligma got balls, lol have fun figuring this one out bud</pre>
<p>The same thing happened to me when I was working on the LeetCode problem <a href="https://leetcode.com/problems/minimum-fuel-cost-to-report-to-the-capital/description/" rel="noopener ugc nofollow" target="_blank">Minimum fuel to report to capital</a>. 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.</p>
<p>So, I basically did a one to one translation of my Rust code to my Python and…</p>
<p> </p>
<p>Have a look at my code in rust and python and see if you can spot the bug</p>
<pre>
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
}
}</pre>
<pre>
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)</pre>
<p>Do you see it? If you don’t I’ll give you the line, see if you can find it with that</p>
<p>The problem is in the following line</p>
<p><a href="https://medium.com/@tandonhiten/the-illusion-of-easy-in-programming-b66a8734c776">Visit Now</a></p>