Advent of Code - day 19b (Doesn't terminate in a reasonable time, but the first result it prints while running is the correct one)

day19b.rs

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

// Applies each transformation rule once on s
fn transform(s: &str, replacements: &Vec<(String, String)>) -> Vec<String> {
    let mut results: Vec<String> = Vec::new();
    for &(ref to, ref from) in replacements.iter() {
        for (ix, _) in s.match_indices(from) {
            let mut out_molecule = s[0 .. ix].to_string();
            out_molecule.push_str(to);
            out_molecule.push_str(&s[ix + from.len() ..]);
            results.push(out_molecule);
        }
    }
    results
}

fn main() {
    let input_fname = "day19_input.txt";
    let f = File::open(input_fname).unwrap();

    let mut replacements: Vec<(String, String)> = Vec::new();

    let mut reader = BufReader::new(f);
    for line in (&mut reader).lines() {
        let line = line.unwrap();
        if line.len() == 0 {
            break;
        }
        let v: Vec<&str> = line.splitn(2, " => ").collect();
        replacements.push((v[0].to_string(), v[1].to_string()));
    }
    let molecule = reader.lines().next().unwrap().unwrap();

    let mut explored: HashMap<String, u32> = HashMap::new();
    let mut unexplored: VecDeque<(String, u32)> = VecDeque::new();
    unexplored.push_back((molecule.to_string(), 0));

    // Sort the replacements from shortest to longest diff between the two sides,
    // so that the algorithm will handle the longest diffs first
    replacements.sort_by(|&(ref from, ref to), &(ref from2, ref to2)| (from.len() as i32 - to.len() as i32).abs().cmp(&(from2.len() as i32 - to2.len() as i32).abs()));

    while !unexplored.is_empty() {
        let (s, n) = unexplored.pop_front().unwrap();

        // Just in case our unexplored entry is stale, and we already explored it
        match explored.get(&s) {
            None => {},
            Some(distance) => {
                if n > *distance {
                    continue
                }
            }
        }

        // println!("Len: {}\t{}", s.len(), s);
        // println!("Transforming {}", s);
        let results = transform(&s, &replacements);
        for result in results.iter() {
            if result == "e" {
                println!("Reached e: {}", n + 1);
            }
            let mut should_insert = false;
            match explored.get(result) {
                None => {
                    should_insert = true;
                    unexplored.push_front((result.to_string(), n + 1));
                    //println!("Unexplored: {}", result);
                },
                Some(distance) => {
                    if n + 1 < *distance {
                        should_insert = true
                    }
                }
            }
            if should_insert {
                explored.insert(result.to_string(), n + 1);
            }
        }
    }

    println!("Shortest path: {}", explored.get("e").unwrap());
}