Problem about traversing HashMap

help
1

Hello everyone! I am a beginner of rust. I am trying to exercise iterator and HashMap. There is something I can not understand and can't solve.

I am trying to write about finding a number that can be added by which two numbers in the array.


fn main() {
    let cumulus = vec![3, 1,4,1,5,9, // 5
                       2,6,5,3,5, 8,9,7,9,3, // 15
                       2,3,8,4,6, 2,6,4,3,3, // 25
                       8,3,2,7,9, 5,0,2,8,8, // 35
                       4,1,9,7,1, 6,9,3,9,9, // 45
                       3,7,5,1,0, 5,8,2,0,9, // 55
                       7,4,9,4,4, 5,9,2,3,0, // 65
                       7,8,1,6,4, 0,6,2,8,6, // 75
                       2,0,8,9,9, 8,6,2,8,0, // 85
                       3,4,8,2,5, 3,4,2,1,1, // 95
                       7,0,6,7,9];
    let n:i32 = 18;
    let a = find_num_combine(&cumulus, &n, 2).expect("Error");
    println!("{:?}", a);
}



fn find_num_combine<T>(amass: &Vec<T>, target: &T, parts: usize) -> Result<Vec<Vec<usize>>, String>
    where T: Sub<Output=T> + Copy + Eq + Hash
{
    let empty_or_return = |result: Vec<Vec<usize>>| {
        match result.len() {
            0 => Err("Can not find target".to_string()),
            _ => Ok(result)
        } };

    if parts >= 3 {
        // let result:Vec<Vec<usize>> = Vec::new();
        todo!();
        // empty_or_return(result)
    } else if parts == 2 {
        let mut result:Vec<Vec<usize>> = Vec::new();
        let mut happy_map:HashMap<T,usize> = HashMap::new();
        amass.iter().enumerate().for_each(|(index, value)| {
            happy_map.iter().for_each(|(k,v)| {
                if *target - *value == *k {
                    result.push(vec![index, *v]);
                } } );
            happy_map.entry(*value).or_insert(index); } );
        empty_or_return(result)
    } else if parts == 1 {
        empty_or_return(
            amass.iter()
                .enumerate()
                .filter(|&(_, value)| *value == *target)
                .map(|(index, _)| vec![index])
                .collect())
    } else { Err("At least parts >= 1".to_string()) }
}

The program only print something as below. Why there is no [14, 12].
[[12, 5], [14, 5], [30, 5], [38, 5], [42, 5], [44, 5], [45, 5], [55, 5], [58, 5], [62, 5], [79, 5], [80, 5], [100, 5]]

2

From your posted output, it is obvious that the second position is always 5 (with value 9) so the program searches only for all other positions containing a matching value, which is again 9 for your sum of 18. So the issue is obvious, and as you wrote the code, you should know what is should do, and it should be not difficult for you to locate the error? Sorry, I have not really studied your code yet, I might do at end of the day :slight_smile: For my feeling the description for what the program should do is not very clear, I more or less guessed the intend, hope it is correct.

And a short note to your code: It makes not that much sense to pass all parameters as references -- in (&cumulus, &n, 2) n is a primitive type implementing the copy trait, so you can pass it by value. You could also pass cumulus as value, when you do not need it any more in main (it is moved).

4

OK, I think this is the actual exercise -- I was not aware of it :slight_smile:

The last code example is with use of a hash map:

Actually, my current feeling is, that the solution with the hash map is nice to get the total number of matching pairs, but is not that useful to get all the index positions?

5

I tried it again without hash. I think the problem has been solved. Thanks for your help.

fn main() {
    let cumulus: Vec<i32> = vec![3,1,4,1,5,9, // 5
                       2,6,5,3,5,8,9,7,9,3, // 15
                       2,3,8,4,6,2,6,4,3,3, // 25
                       8,3,2,7,9,5,0,2,8,8, // 35
                       4,1,9,7,1,6,9,3,9,9, // 45
                       3,7,5,1,0,5,8,2,0,9, // 55
                       7,4,9,4,4,5,9,2,3,0, // 65
                       7,8,1,6,4,0,6,2,8,6, // 75
                       2,0,8,9,9,8,6,2,8,0, // 85
                       3,4,8,2,5,3,4,2,1,1, // 95
                       7,0,6,7,9];
    let n:i32 = 17;
    let a = find_num_combine(&cumulus, &n, 2).expect("Error");
    println!("{:?}", a);
}

fn find_num_combine<T>(mass_vec: &Vec<T>, target: &T, parts: usize) -> Result<Vec<Vec<usize>>, String>
    where T: Sub<Output=T> + Copy + Eq + Hash
{
    let empty_or_good_return = |result: Vec<Vec<usize>>| {
        match result.len() {
            0 => Err("Can not find the combination".to_string()),
            _ => Ok(result)
        } };

    if parts >= 3 {
        // let mut result:Vec<Vec<usize>> = Vec::new();
        todo!();
        // empty_or_return(result)
    } else if parts == 2 {
        let mut result: Vec<Vec<usize>> = Vec::new();
        let mut sul: Vec<(T, usize)> = Vec::new();
        mass_vec
            .iter()
            .enumerate()
            .for_each(|(left_index, value)| {
                sul.iter().for_each(|(k,right_index)| {
                    if *target - *value == *k {
                        result.push(vec!(left_index ,*right_index));
                    } } );
                sul.push((*value, left_index));
            }); empty_or_good_return(result)
    } else if parts == 1 { empty_or_good_return(
        mass_vec
            .iter()
            .enumerate()
            .filter(|&(_, value)| *value == *target)
            .map(|(index, _)| vec![index])
            .collect())
    } else { Err("At least parts >= 1".to_string()) }
}

It prints

[[11, 5], [12, 11], [14, 11], [18, 5], [18, 12], [18, 14], [26, 5], [26, 12], [26, 14], [30, 11], [30, 18], [30, 26], [34, 5], [34, 12], [34, 14], [34, 30], [35, 5], [35, 12], [35, 14], [35, 30], [38, 11], [38, 18], [38, 26], [38, 34], [38, 35], [42, 11], [42, 18], [42, 26], [42, 34], [42, 35], [44, 11], [44, 18], [44, 26], [44, 34], [44, 35], [45, 11], [45, 18], [45, 26], [45, 34], [45, 35], [52, 5], [52, 12], [52, 14], [52, 30], [52, 38], [52, 42], [52, 44], [52, 45], [55, 11], [55, 18], [55, 26], [55, 34], [55, 35], [55, 52], [58, 11], [58, 18], [58, 26], [58, 34], [58, 35], [58, 52], [62, 11], [62, 18], [62, 26], [62, 34], [62, 35], [62, 52], [67, 5], [67, 12], [67, 14], [67, 30], [67, 38], [67, 42], [67, 44], [67, 45], [67, 55], [67, 58], [67, 62], [74, 5], [74, 12], [74, 14], [74, 30], [74, 38], [74, 42], [74, 44], [74, 45], [74, 55], [74, 58], [74, 62], [78, 5], [78, 12], [78, 14], [78, 30], [78, 38], [78, 42], [78, 44], [78, 45], [78, 55], [78, 58], [78, 62], [79, 11], [79, 18], [79, 26], [79, 34], [79, 35], [79, 52], [79, 67], [79, 74], [79, 78], [80, 11], [80, 18], [80, 26], [80, 34], [80, 35], [80, 52], [80, 67], [80, 74], [80, 78], [81, 5], [81, 12], [81, 14], [81, 30], [81, 38], [81, 42], [81, 44], [81, 45], [81, 55], [81, 58], [81, 62], [81, 79], [81, 80], [84, 5], [84, 12], [84, 14], [84, 30], [84, 38], [84, 42], [84, 44], [84, 45], [84, 55], [84, 58], [84, 62], [84, 79], [84, 80], [88, 5], [88, 12], [88, 14], [88, 30], [88, 38], [88, 42], [88, 44], [88, 45], [88, 55], [88, 58], [88, 62], [88, 79], [88, 80], [100, 11], [100, 18], [100, 26], [100, 34], [100, 35], [100, 52], [100, 67], [100, 74], [100, 78], [100, 81], [100, 84], [100, 88]]
6

Not fully solved. I have still no real idea about your initial algorithm. What was your basic idea? My feeling is, that using a hash map makes sense to get a O(n) solution. But you are actually iterating over the initial vector, and over the hash map, so it is more a O(n^2) solution. Was it just a homework task, suggesting using a hash map and generics as well? Personally, I start most of the time without generics, and make the generic solution at the end. For a hashmap solution, I would assume that it is possible, when the value of the map is not just a count, but a vector with all the index position. But OK, if you are satisfied with your double iteration solution without a hash map, then it is fine.

7

It was an idea that I suddenly got today.
I thought many algorithms are like people to choose the solution and let the computer to check. So, I want a simple version of program that it can let the computer find out all the solutions, and I decide which one to use. I thought this idea can be used in many places.
I just learned few things about rust. Trying to exercise, especially on hashmap and iterator. I found something I can not handle with hashmap. I decided to write a post asking for help. Looking for solution or some better methods.