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<String>], paths: &HashMap<(Rc<String>, Rc<String>), 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::<i64>().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

Answer 1

The problem is due to the fact that calling next_permutation gives you the next "ordered permutation" (link to the docs).

The caveat here is that you are not iterating permutations that are lexicaly ordered before the input slice - for example, if you started with this path:

["Norrath", "Faerun", "Tristram", "Tambi", "Straylight", "Snowdin", "Arbre", "AlphaCentauri"]

You will never arrive to this path:

["Arbre", "Snowdin", "Norrath", "Faerun", "Tambi", "Tristram", "AlphaCentauri", "Straylight"]

And since HashMap does not guarantee keys or values ordering, cities_perm ordering is different on each run, thus you iterate different subsets of all possible permutations and get different results.

One solution may be to sort the cities before starting permutations:

cities_perm.sort();