Solve Rusty Lake's beaker puzzle.

rusty-lake-beaker.rs

use std::cmp::min;
use std::collections::VecDeque;

const BEAKERS: usize = 3;

const INITIAL_STATE: State = State {
  beakers: [
      Beaker::new(10, 0),
      Beaker::new(5, 5),
      Beaker::new(6, 6),
  ]
};

fn end(state: &State) -> bool {
    state.beakers[0].volume == 8
}


#[derive(Hash, Debug, Eq, PartialEq, Clone)]
struct Beaker {
    capacity: u8,
    volume: u8,
}

impl Beaker {
    const fn new(capacity: u8, volume: u8) -> Beaker {
        Beaker { capacity, volume }
    }
}

#[derive(Hash, Debug, Eq, PartialEq, Clone)]
struct State {
    beakers: [Beaker; BEAKERS]
}

#[derive(Debug, Copy, Clone)]
struct Pour {
    from: usize,
    to: usize
}

impl Pour {
    fn iter() -> impl Iterator<Item=Pour> {
        struct PourIter {
            from: usize,
            to: usize,
        }

        impl Iterator for PourIter {
            type Item = Pour;
            fn next(&mut self) -> Option<Pour> {
                let result = Pour { from: self.from, to: self.to };
                self.to+=1;
                if self.to == BEAKERS {
                    self.to = 0;
                    self.from+=1;
                    if self.from == BEAKERS {
                        return None;
                    }
                }
                return Some(result);
            }
        }

        PourIter {
            from: 0, to: 1
        }
    }
}

fn is_valid_action(state: &State, Pour {from, to}: Pour) -> bool {
    if state.beakers[from].volume == 0 {
        return false;
    }
    if state.beakers[to].capacity == state.beakers[to].volume {
        return false;
    }
    return true;
}

fn do_action(state: &mut State, Pour {from, to}: Pour) {
    let remaining_capacity = state.beakers[to].capacity - state.beakers[to].volume;
    let remaining_water = state.beakers[from].volume;
    let to_pour = min(remaining_capacity, remaining_water);

    state.beakers[to].volume += to_pour;
    state.beakers[from].volume -= to_pour;
}

struct StateWithHistory {
    state: State,
    history: Vec<Pour>
}

impl StateWithHistory {
    fn progress(&self, pour: Pour) -> Option<StateWithHistory> {
        if is_valid_action(&self.state, pour) {
            Some(StateWithHistory {
                state: {
                    let mut state = self.state.clone();
                    do_action(&mut state, pour);
                    state
                },
                history: {
                    let mut history = self.history.clone();
                    history.push(pour);
                    history
                }
            })
        } else {
            None
        }
    }
}

fn main() {
    let mut queue = VecDeque::new();
    queue.push_back(StateWithHistory {
        state: INITIAL_STATE.clone(),
        history: Vec::new(),
    });

    while let Some(state_history) = queue.pop_front() {
        if end(&state_history.state) {
            println!("Initial state: {:?}", INITIAL_STATE);
            let mut intermediate_state = INITIAL_STATE;
            for pour in state_history.history {
                do_action(&mut intermediate_state, pour);
                println!("{} -> {}, {:?}", pour.from, pour.to, intermediate_state);
            }
            return;
        }

        for pour in Pour::iter() {
            if let Some(progress) = state_history.progress(pour) {
                queue.push_back(progress);
            }
        }
    }
}