What's the problem with my solution?

Exercism
1

I’m studying Rust by Exercism → Rust → Exercises. I’m stuck on “Two Bucket”, but I don’t know what’s wrong with my Breadth First Search algorithm solution for the exercise. The solution I found seems correct, but I don’t pass the tests. Can anyone help?

use std::collections::{HashMap, LinkedList};

#[derive(Copy, Clone, PartialEq, Eq, Debug)]
pub enum Bucket {
One,
Two,
}

#[derive(PartialEq, Eq, Debug)]
pub struct BucketStats {
pub moves: u8,
pub goal_bucket: Bucket,
pub other_bucket: u8,
}

// It’s a Breadth First Search algorithm implementation
pub fn solve(
capacity_1: u8,
capacity_2: u8,
goal: u8,
start_bucket: &Bucket,
) → Option {

let initial = match *start_bucket {
    Bucket::One => NodeState::new(capacity_1, 0),
    Bucket::Two => NodeState::new(0, capacity_2),
};

let mut visited = HashMap::new();
let mut queue = LinkedList::new();
visited.insert(NodeState::ZERO_STATE, 0);
visited.insert(initial, 1);
queue.push_front(initial);

while let Some(current) = queue.pop_back() {
    let moves = *visited.get(&current).unwrap();

    if current.bucket_1 == goal || current.bucket_2 == goal {
        let (target, other) = if current.bucket_1 == goal {
            (Bucket::One, current.bucket_2)
        } else {
            (Bucket::Two, current.bucket_1)
        };
        return Some(BucketStats {
            moves: moves,
            goal_bucket: target,
            other_bucket: other,
        });
    }
    
    current.sucessors(capacity_1, capacity_2)
    .iter()
    .cloned()
    .for_each(|s| {
        if !visited.contains_key(&s) {
            visited.insert(s, moves + 1);
            queue.push_front(s);
        }
    });
}
None

}

#[derive(Copy, Clone, Eq, PartialEq, Hash, Debug)]
struct NodeState {
bucket_1: u8,
bucket_2: u8,
}

impl NodeState {

pub const ZERO_STATE: NodeState = NodeState::new(0, 0); 

pub const fn new(bucket_1: u8, bucket_2: u8) -> Self {
    NodeState {
        bucket_1: bucket_1,
        bucket_2: bucket_2,
    }
}

pub fn sucessors(&self, capacity_1: u8, capacity_2: u8) -> Vec<NodeState> {
    let mut container = Vec::new();
    let buck1 = self.bucket_1;
    let buck2 = self.bucket_2;
    if buck1 < capacity_1 {
        container.push( NodeState::new(capacity_1, buck2) );
    }
    if buck2 < capacity_2 {
        container.push( NodeState::new(buck1, capacity_2) );
    }
    if buck1 > 0 {
        container.push( NodeState::new(0, buck2) );
    }
    if buck2 > 0 {
        container.push( NodeState::new(buck1, 0) );
    }
    if buck1 > 0 && buck2 < capacity_2 {
        let remainder = capacity_2 - buck2;
        if buck1 > remainder {
            container.push( NodeState::new(buck1 - remainder, capacity_2) );
        } else {
            container.push( NodeState::new(0, buck1 + buck2) );
        }
    }
    if buck2 > 0 && buck1 < capacity_1 {
        let remainder = capacity_1 - buck1;
        if buck2 > remainder {
            container.push( NodeState::new(capacity_1, buck2 - remainder) );
        } else {
            container.push( NodeState::new(buck1 + buck2, 0) );
        }
    }
    container
}

}

2

What’s the error message being returned?

3

A common logical error is the following disallowed sequence: fill starting bucket, empty starting bucket, fill second bucket.

Do you guard against that?

4

There are 3 tests that get errors:

thread ‘measure_using_bucket_one_of_size_3_and_bucket_two_of_size_5_start_with_bucket_two’ panicked at tests/two-bucket.rs:23:5:
assertion left == right failed
left: Some(BucketStats { moves: 6, goal_bucket: One, other_bucket: 5 })
right: Some(BucketStats { moves: 8, goal_bucket: Two, other_bucket: 3 })

thread ‘with_the_same_buckets_but_a_different_goal_then_it_is_possible’ panicked at tests/two-bucket.rs:92:5:
assertion left == right failed
left: Some(BucketStats { moves: 4, goal_bucket: Two, other_bucket: 6 })
right: Some(BucketStats { moves: 10, goal_bucket: Two, other_bucket: 0 })

thread ‘measure_using_bucket_one_of_size_7_and_bucket_two_of_size_11_start_with_bucket_two’ panicked at tests/two-bucket.rs:47:5:
assertion left == right failed
left: Some(BucketStats { moves: 16, goal_bucket: One, other_bucket: 11 })
right: Some(BucketStats { moves: 18, goal_bucket: Two, other_bucket: 7 })

5

I started to “solve function” by adding zero state (0, 0) and first state (0, capacity_2) or (capacity_1, 0). I can’t go to a previously visited state. So I think this situation doesn’t occur. But just to be sure, I’ll check.

6

This doesn’t prevent you from returning to an invalid state.

1: (0, 0)
2: (cap_one, 0)  # fill starting bucket
3: (cap_one, cap_two)  # fill other bucket
4: (0, cap_two)  # empty starting bucket -- INVALID STATE!!
7

You’re absolutely right. This change makes all tests pass. Thanks, IsaacG!