Rust program occasionally gives inconsistent results

Question

I am working on part 1 of day 9 of the Advent of Code in Rust and ran into a strange problem. I wrote the following code, which works usually, but about 10% of the time it gives the wrong answer.

extern crate permutohedron;

use std::fs::File;
use std::io::{BufRead, BufReader};
use std::collections::HashMap;
use std::rc::Rc;

use permutohedron::LexicalPermutation;

fn get_distance(cities: &[Rc], paths: &HashMap<(Rc, Rc), i64>) -> i64 {
    cities.iter().fold((0, None), |(sum, last_city), city| {
        (last_city.map_or(0, |last_city| {
            sum + *paths.get(&(last_city, city.clone())).unwrap()
        }), Some(city.clone()) )
    }).0
}

fn main() {

    let file = File::open("input_9.txt").unwrap();
    let file = BufReader::new(file);

    let mut paths = HashMap::new();
    let mut cities = HashMap::new();

    for line in file.lines() {
        let line = line.unwrap();
        let mut words = line.split(' ');
        let from = words.nth(0).unwrap();
        let to = words.nth(1).unwrap();

        if !cities.contains_key(from) {
            cities.insert(from.to_owned(), Rc::new(from.to_owned()));
        }
        if !cities.contains_key(to) {
            cities.insert(to.to_owned(), Rc::new(to.to_owned()));
        }

        let from = cities.get(from).unwrap();
        let to = cities.get(to).unwrap();

        let dist = words.nth(1).unwrap().parse::().unwrap();
        paths.insert((from.clone(), to.clone()), dist);
        paths.insert((to.clone(), from.clone()), dist);
    }

    let mut cities_perm: Vec<_> = cities.values().map(|k| k.clone()).collect();

    let mut min_path = None;
    loop {
        let dist = get_distance(&cities_perm, &paths);

        min_path = Some(min_path.map_or(dist, |v|
            *[v, dist].iter().min().unwrap()
        ));

        if !cities_perm.next_permutation() { break }
    }

    println!("{}", min_path.unwrap());

}

I am running it with cargo run, and never changing the file input_9.txt, so I see no reason this should ever give different answers. I also tried building it, then running the executable that it built directly, like ./target/debug/day_9, and the same thing happens. I noticed it tends to give wrong results most often soon after building it, rather than later.

Usually, I am getting 141, which is correct. However it will sometimes print something like 210, 204, or 155. Why would this be happening?

Here's the input to the program in case it helps you: https://pastebin.com/XJzsMy5A

Rust program occasionally gives inconsistent results

1 Answers