[Intermediate] /r/dailyprogrammer challenge 266

main.rs

use std::collections::BTreeMap;

// char to usize
fn parse_int(str: String) -> usize {
    str.chars().fold(0, |val, c|  (val*10 + (c.to_digit(10).unwrap()) as usize))
}

fn read_input(filename: &str) -> String {
    use std::io::Read;
    use std::fs::File;
    let mut f = File::open(filename).expect("Unable to open the file.");
    
    let mut str = String::new();
    
    f.read_to_string(&mut str);
    str
}

fn build_map (input: &String) -> (Vec<usize>, BTreeMap<usize, Vec<usize>>) {
    let mut map: BTreeMap<usize, Vec<usize>> = BTreeMap::new();
    let mut keys: Vec<usize> = Vec::new();
    for (index, line) in input.split('\n').enumerate() {
        if index <= 0 {
            // discard first line
            continue;
        }
        let connections: Vec<_> = line.split_whitespace().collect();
        let conn_from:usize = parse_int(connections[0].to_string());
        let conn_to:usize = parse_int(connections[1].to_string());
        
        let mut vec_from = map.entry(conn_from).or_insert(Vec::new());
        (*vec_from).push(conn_to);
        keys.extend_from_slice(&[conn_from, conn_to]);
    }
    keys.sort();
    keys.dedup();
    (keys, map)
}

// custom method to allow to check uniqueness (a set might have been better)
fn push_all(list: &mut Vec<usize>, other_list: &Vec<usize>, uniqueness: bool) {
    for v in other_list.iter() {
        if !uniqueness || !list.contains(v) {
            list.push(*v);
        }
    }
}

fn challenge_266(input: String) {
    let (keys, map) =  build_map(&input);
    //let keys: Vec<usize> = map.iter().map(|(k, _)| *k).collect();
    println!("Keys are : {:?}", keys);
    let mut radius = keys.len();
    let mut diameter = 0;
    for (key, val) in map.iter() {
        //println!("{} : {:?}", key, val);
        let mut found_nodes:Vec<usize> = vec![*key];
        let mut new_nodes: Vec<usize> = Vec::new();
        let mut ecc = 1;
        let mut prev_length = 0;
        push_all(&mut found_nodes, val, true);
        // all keys found
        while found_nodes != keys {
            prev_length = found_nodes.len();
            // can't alter the list we're iterating over
            for v in found_nodes.iter() {
                if map.contains_key(v) {
                    push_all(&mut new_nodes, map.get(v).unwrap(), true);
                }
            }
            push_all(&mut found_nodes, &new_nodes, true);
            found_nodes.sort();
            
            // get out of the loop if we're done (no more nodes to find)
            // without incrementig the counter
            if(found_nodes.len() == prev_length) {
                break;
            }
            
            ecc += 1;
        }
        radius = std::cmp::min(radius, ecc);
        diameter = std::cmp::max(diameter, ecc);
    }
    println!("Radius : {}", radius);
    println!("Diameter : {}", diameter);
}

fn main() {
    // Test sample
    challenge_266(read_input("./res/challenge_266_example.txt"));
    // Actual challenge
    challenge_266(read_input("./res/challenge_266.txt"));
}