Originally posted by **chungquantin** December 27, 2023
## Description
Required reading: https://polkadot-blockchain-academy.github.io/pba-book/blockchain-contracts/services-as-state-machines/page.html
What's intriguing is that the majority, if not all, of the systems we are concerned with can be conceptualized as state machines. A state machine isn't a tangible, touchable machine in the physical sense; rather, it's a model consisting of a defined set of states and a set of rules governing the transitions between those states. In visualizing this, imagine my state machine initiating from state one, and then an external trigger, perhaps akin to a specific action or transaction in blockchain terms, propels it into state two.
Therefore, our objective with the blockchain is to meticulously record the entire sequence of these transitions. By maintaining a comprehensive history of all transitions, we gain the ability to discern our current state in the system.
Below are the solutions for the exercise `c1_state_machine` in `pba_book`. Please use this as a reference if you get any blockers. I still recommend working through the problem set on your own so you can fully understand the concept of the state machine.
## Other learning materials
- Substrate state machine implementation (sp_state_machine): [sp-state-machine](https://docs.rs/sp-state-machine/latest/src/sp_state_machine/lib.rs.html#18-1963:~:text=pub%20struct%20StateMachine,Out%3E%2C%0A%09%09context%3A%20CallContext%2C%0A%09%7D)
- Rust state machine (Substrate minimal version): https://github.com/shawntabrizi/rust-state-machine
## Answer
### p1_switches.rs
```rust
//! We begin our hands on exploration of state machines with two very simple examples.
//! In these examples, we use actually switch boards as the state machine. The state is,
//! well, just the state of the switches.
use super::StateMachine;
/// This state machine models a single light switch.
/// The internal state, a bool, represents whether the switch is on or not.
pub struct LightSwitch;
/// We model this simple system as a state machine with a single transition - toggling the switch
/// Because there is only a single kind of transition, we can use a unit struct.
impl StateMachine for LightSwitch {
type State = bool;
type Transition = ();
fn next_state(starting_state: &bool, t: &()) -> bool {
!starting_state
}
}
/// This second state machine models two light switches with one weird property.
/// Whenever switch one is turned off, switch two also goes off.
pub struct WeirdSwitchMachine;
/// The state is now two switches instead of one so we use a struct.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct TwoSwitches {
first_switch: bool,
second_switch: bool,
}
/// Now there are two switches so we need a proper type for the transition.
pub enum Toggle {
FirstSwitch,
SecondSwitch,
}
/// We model this system as a state machine with two possible transitions
impl StateMachine for WeirdSwitchMachine {
type State = TwoSwitches;
type Transition = Toggle;
fn next_state(starting_state: &TwoSwitches, t: &Toggle) -> TwoSwitches {
let mut next_state = starting_state.clone();
match t {
Toggle::FirstSwitch => {
if starting_state.first_switch {
next_state.second_switch = false;
}
next_state.first_switch = !starting_state.first_switch;
},
Toggle::SecondSwitch => next_state.second_switch = !next_state.second_switch,
}
next_state
}
}
#[test]
fn sm_1_light_switch_toggles_off() {
assert!(!LightSwitch::next_state(&true, &()));
}
#[test]
fn sm_1_light_switch_toggles_on() {
assert!(LightSwitch::next_state(&false, &()));
}
#[test]
fn sm_1_two_switches_first_goes_on() {
let state = TwoSwitches { first_switch: false, second_switch: false };
assert_eq!(
WeirdSwitchMachine::next_state(&state, &Toggle::FirstSwitch),
TwoSwitches { first_switch: true, second_switch: false }
);
}
#[test]
fn sm_1_two_switches_first_goes_off_second_was_on() {
// This is the special case. We have to make sure the second one goes off with it.
let state = TwoSwitches { first_switch: true, second_switch: true };
assert_eq!(
WeirdSwitchMachine::next_state(&state, &Toggle::FirstSwitch),
TwoSwitches { first_switch: false, second_switch: false }
);
}
#[test]
fn sm_1_two_switches_first_goes_off_second_was_off() {
// This is adjacent to the special case. We have to make sure the second one stays off.
let state = TwoSwitches { first_switch: true, second_switch: false };
assert_eq!(
WeirdSwitchMachine::next_state(&state, &Toggle::FirstSwitch),
TwoSwitches { first_switch: false, second_switch: false }
);
}
#[test]
fn sm_1_two_switches_second_goes_on() {
let state = TwoSwitches { first_switch: false, second_switch: false };
assert_eq!(
WeirdSwitchMachine::next_state(&state, &Toggle::SecondSwitch),
TwoSwitches { first_switch: false, second_switch: true }
);
}
#[test]
fn sm_1_two_switches_second_goes_off() {
let state = TwoSwitches { first_switch: true, second_switch: true };
assert_eq!(
WeirdSwitchMachine::next_state(&state, &Toggle::SecondSwitch),
TwoSwitches { first_switch: true, second_switch: false }
);
}
```
## p2_laundry_machine.rs
```rust
//! When you wear clothes they get dirty. When you wash them they get wet. When you dry them,
//! they're ready to be worn again. Or course washing and wearing clothes takes its toll on the
//! clothes, and eventually they get tattered.
use super::StateMachine;
/// This state machine models the typical life cycle of clothes as they make their way through the
/// laundry cycle several times before ultimately becoming tattered.
pub struct ClothesMachine;
/// Models a piece of clothing throughout its lifecycle.
#[derive(PartialEq, Eq, Debug)]
pub enum ClothesState {
/// Clean clothes ready to be worn. With some given life left.
Clean(u64),
/// Dirty clothes. With some given life left.
Dirty(u64),
/// Wet clothes. With some given life left. The clothes are assumed to be wet because
/// they were just washed. And washing clothes is the only modeled way to get them wet.
Wet(u64),
/// Tattered clothes beyond their useful life. These clothes will always be tattered no matter
/// what is done with them.
Tattered,
}
/// Something you can do with clothes
pub enum ClothesAction {
/// Wearing clothes decreases their life by 1 and makes them dirty.
Wear,
/// Washing clothes decreases their life by 1, and makes them wet.
Wash,
/// This operation models a tumble drier. Drying clothes decreases their life by 1.
/// If the clothes were clean or wet to begin with they will be clean after drying.
/// If they were dirty to begin with, they will still be dirty after drying.
Dry,
}
impl StateMachine for ClothesMachine {
type State = ClothesState;
type Transition = ClothesAction;
fn next_state(starting_state: &ClothesState, t: &ClothesAction) -> ClothesState {
let given_life = match starting_state {
ClothesState::Clean(life) => life,
ClothesState::Dirty(life) => life,
ClothesState::Wet(life) => life,
ClothesState::Tattered => return ClothesState::Tattered,
};
let life_left = given_life - 1;
if life_left == 0 {
return ClothesState::Tattered;
}
match t {
ClothesAction::Wash => return ClothesState::Wet(life_left),
ClothesAction::Dry => {
let dummy_dirty = ClothesState::Dirty(*given_life);
if *starting_state == dummy_dirty {
return ClothesState::Dirty(life_left);
}
return ClothesState::Clean(life_left);
},
ClothesAction::Wear => return ClothesState::Dirty(life_left),
}
}
}
#[test]
fn sm_2_wear_clean_clothes() {
let start = ClothesState::Clean(4);
let end = ClothesMachine::next_state(&start, &ClothesAction::Wear);
let expected = ClothesState::Dirty(3);
assert_eq!(end, expected);
}
#[test]
fn sm_2_wear_dirty_clothes() {
let start = ClothesState::Dirty(4);
let end = ClothesMachine::next_state(&start, &ClothesAction::Wear);
let expected = ClothesState::Dirty(3);
assert_eq!(end, expected);
}
#[test]
fn sm_2_wear_wet_clothes() {
let start = ClothesState::Wet(4);
let end = ClothesMachine::next_state(&start, &ClothesAction::Wear);
let expected = ClothesState::Dirty(3);
assert_eq!(end, expected);
}
#[test]
fn sm_2_wear_tattered_clothes() {
let start = ClothesState::Tattered;
let end = ClothesMachine::next_state(&start, &ClothesAction::Wear);
let expected = ClothesState::Tattered;
assert_eq!(end, expected);
}
#[test]
fn sm_2_wear_clean_until_tattered() {
let start = ClothesState::Clean(1);
let end = ClothesMachine::next_state(&start, &ClothesAction::Wear);
let expected = ClothesState::Tattered;
assert_eq!(end, expected);
}
#[test]
fn sm_2_wear_wet_until_tattered() {
let start = ClothesState::Wet(1);
let end = ClothesMachine::next_state(&start, &ClothesAction::Wear);
let expected = ClothesState::Tattered;
assert_eq!(end, expected);
}
#[test]
fn sm_2_wear_dirty_until_tattered() {
let start = ClothesState::Dirty(1);
let end = ClothesMachine::next_state(&start, &ClothesAction::Wear);
let expected = ClothesState::Tattered;
assert_eq!(end, expected);
}
#[test]
fn sm_2_wash_clean_clothes() {
let start = ClothesState::Clean(4);
let end = ClothesMachine::next_state(&start, &ClothesAction::Wash);
let expected = ClothesState::Wet(3);
assert_eq!(end, expected);
}
#[test]
fn sm_2_wash_dirty_clothes() {
let start = ClothesState::Dirty(4);
let end = ClothesMachine::next_state(&start, &ClothesAction::Wash);
let expected = ClothesState::Wet(3);
assert_eq!(end, expected);
}
#[test]
fn sm_2_wash_wet_clothes() {
let start = ClothesState::Wet(4);
let end = ClothesMachine::next_state(&start, &ClothesAction::Wash);
let expected = ClothesState::Wet(3);
assert_eq!(end, expected);
}
#[test]
fn sm_2_wash_tattered_clothes() {
let start = ClothesState::Tattered;
let end = ClothesMachine::next_state(&start, &ClothesAction::Wash);
let expected = ClothesState::Tattered;
assert_eq!(end, expected);
}
#[test]
fn sm_2_wash_clean_until_tattered() {
let start = ClothesState::Clean(1);
let end = ClothesMachine::next_state(&start, &ClothesAction::Wash);
let expected = ClothesState::Tattered;
assert_eq!(end, expected);
}
#[test]
fn sm_2_wash_wet_until_tattered() {
let start = ClothesState::Wet(1);
let end = ClothesMachine::next_state(&start, &ClothesAction::Wash);
let expected = ClothesState::Tattered;
assert_eq!(end, expected);
}
#[test]
fn sm_2_wash_dirty_until_tattered() {
let start = ClothesState::Dirty(1);
let end = ClothesMachine::next_state(&start, &ClothesAction::Wash);
let expected = ClothesState::Tattered;
assert_eq!(end, expected);
}
#[test]
fn sm_2_dry_clean_clothes() {
let start = ClothesState::Clean(4);
let end = ClothesMachine::next_state(&start, &ClothesAction::Dry);
let expected = ClothesState::Clean(3);
assert_eq!(end, expected);
}
#[test]
fn sm_2_dry_dirty_clothes() {
let start = ClothesState::Dirty(4);
let end = ClothesMachine::next_state(&start, &ClothesAction::Dry);
let expected = ClothesState::Dirty(3);
assert_eq!(end, expected);
}
#[test]
fn sm_2_dry_wet_clothes() {
let start = ClothesState::Wet(4);
let end = ClothesMachine::next_state(&start, &ClothesAction::Dry);
let expected = ClothesState::Clean(3);
assert_eq!(end, expected);
}
#[test]
fn sm_2_dry_tattered_clothes() {
let start = ClothesState::Tattered;
let end = ClothesMachine::next_state(&start, &ClothesAction::Dry);
let expected = ClothesState::Tattered;
assert_eq!(end, expected);
}
#[test]
fn sm_2_dry_clean_until_tattered() {
let start = ClothesState::Clean(1);
let end = ClothesMachine::next_state(&start, &ClothesAction::Dry);
let expected = ClothesState::Tattered;
assert_eq!(end, expected);
}
#[test]
fn sm_2_dry_cwet_until_tattered() {
let start = ClothesState::Wet(1);
let end = ClothesMachine::next_state(&start, &ClothesAction::Dry);
let expected = ClothesState::Tattered;
assert_eq!(end, expected);
}
#[test]
fn sm_2_dry_dirty_until_tattered() {
let start = ClothesState::Dirty(1);
let end = ClothesMachine::next_state(&start, &ClothesAction::Dry);
let expected = ClothesState::Tattered;
assert_eq!(end, expected);
}
```
## p3_atm.rs
```rust
//! The automated teller machine gives you cash after you swipe your card and enter your pin.
//! The atm may fail to give you cash if it is empty or you haven't swiped your card, or you have
//! entered the wrong pin.
use super::StateMachine;
/// The keys on the ATM keypad
#[derive(Hash, Debug, PartialEq, Eq, Clone)]
pub enum Key {
One,
Two,
Three,
Four,
Enter,
}
/// Something you can do to the ATM
pub enum Action {
/// Swipe your card at the ATM. The attached value is the hash of the pin
/// that should be keyed in on the keypad next.
SwipeCard(u64),
/// Press a key on the keypad
PressKey(Key),
}
/// The various states of authentication possible with the ATM
#[derive(Debug, PartialEq, Eq, Clone)]
enum Auth {
/// No session has begun yet. Waiting for the user to swipe their card
Waiting,
/// The user has swiped their card, providing the enclosed PIN hash.
/// Waiting for the user to key in their pin
Authenticating(u64),
/// The user has authenticated. Waiting for them to key in the amount
/// of cash to withdraw
Authenticated,
}
/// The ATM. When a card is swiped, the ATM learns the correct pin's hash.
/// It waits for you to key in your pin. You can press as many numeric keys as
/// you like followed by enter. If the pin is incorrect, your card is returned
/// and the ATM automatically goes back to the main menu. If your pin is correct,
/// the ATM waits for you to key in an amount of money to withdraw. Withdraws
/// are bounded only by the cash in the machine (there is no account balance).
#[derive(Debug, PartialEq, Eq, Clone)]
pub struct Atm {
/// How much money is in the ATM
cash_inside: u64,
/// The machine's authentication status.
expected_pin_hash: Auth,
/// All the keys that have been pressed since the last `Enter`
keystroke_register: Vec,
}
impl StateMachine for Atm {
// Notice that we are using the same type for the state as we are using for the machine this
// time.
type State = Self;
type Transition = Action;
fn next_state(starting_state: &Self::State, t: &Self::Transition) -> Self::State {
let atm = starting_state;
let mut updated_atm = starting_state.clone();
let key_to_num = move |key: Key| match key {
Key::One => 1,
Key::Two => 2,
Key::Three => 3,
Key::Four => 4,
_ => panic!("no valid key num found"),
};
match t {
Action::SwipeCard(value) => {
updated_atm.expected_pin_hash = Auth::Authenticating(*value);
},
Action::PressKey(key) => {
if *key == Key::Enter {
let provided_pin_hash = crate::hash(&atm.keystroke_register);
match atm.expected_pin_hash {
Auth::Authenticated => {
let mut withdraw_amount = 0;
atm.keystroke_register.iter().enumerate().for_each(|(i, k)| {
withdraw_amount += key_to_num(k.clone())
* 10_u64.pow((atm.keystroke_register.len() - i) as u32 - 1);
});
if withdraw_amount <= atm.cash_inside {
updated_atm.cash_inside -= withdraw_amount;
}
updated_atm.expected_pin_hash = Auth::Waiting;
updated_atm.keystroke_register = vec![];
},
Auth::Authenticating(value) => {
if provided_pin_hash == value {
updated_atm.expected_pin_hash = Auth::Authenticated;
updated_atm.keystroke_register = vec![];
} else {
updated_atm.expected_pin_hash = Auth::Waiting;
updated_atm.keystroke_register = vec![];
}
},
_ => unimplemented!(),
}
} else if atm.expected_pin_hash != Auth::Waiting {
// add keystroke
updated_atm.keystroke_register.push(key.clone());
}
},
}
return updated_atm;
}
}
#[test]
fn sm_3_simple_swipe_card() {
let start =
Atm { cash_inside: 10, expected_pin_hash: Auth::Waiting, keystroke_register: Vec::new() };
let end = Atm::next_state(&start, &Action::SwipeCard(1234));
let expected = Atm {
cash_inside: 10,
expected_pin_hash: Auth::Authenticating(1234),
keystroke_register: Vec::new(),
};
assert_eq!(end, expected);
}
#[test]
fn sm_3_swipe_card_again_part_way_through() {
let start = Atm {
cash_inside: 10,
expected_pin_hash: Auth::Authenticating(1234),
keystroke_register: Vec::new(),
};
let end = Atm::next_state(&start, &Action::SwipeCard(1234));
let expected = Atm {
cash_inside: 10,
expected_pin_hash: Auth::Authenticating(1234),
keystroke_register: Vec::new(),
};
assert_eq!(end, expected);
let start = Atm {
cash_inside: 10,
expected_pin_hash: Auth::Authenticating(1234),
keystroke_register: vec![Key::One, Key::Three],
};
let end = Atm::next_state(&start, &Action::SwipeCard(1234));
let expected = Atm {
cash_inside: 10,
expected_pin_hash: Auth::Authenticating(1234),
keystroke_register: vec![Key::One, Key::Three],
};
assert_eq!(end, expected);
}
#[test]
fn sm_3_press_key_before_card_swipe() {
let start =
Atm { cash_inside: 10, expected_pin_hash: Auth::Waiting, keystroke_register: Vec::new() };
let end = Atm::next_state(&start, &Action::PressKey(Key::One));
let expected =
Atm { cash_inside: 10, expected_pin_hash: Auth::Waiting, keystroke_register: Vec::new() };
assert_eq!(end, expected);
}
#[test]
fn sm_3_enter_single_digit_of_pin() {
let start = Atm {
cash_inside: 10,
expected_pin_hash: Auth::Authenticating(1234),
keystroke_register: Vec::new(),
};
let end = Atm::next_state(&start, &Action::PressKey(Key::One));
let expected = Atm {
cash_inside: 10,
expected_pin_hash: Auth::Authenticating(1234),
keystroke_register: vec![Key::One],
};
assert_eq!(end, expected);
let start = Atm {
cash_inside: 10,
expected_pin_hash: Auth::Authenticating(1234),
keystroke_register: vec![Key::One],
};
let end1 = Atm::next_state(&start, &Action::PressKey(Key::Two));
let expected1 = Atm {
cash_inside: 10,
expected_pin_hash: Auth::Authenticating(1234),
keystroke_register: vec![Key::One, Key::Two],
};
assert_eq!(end1, expected1);
}
#[test]
fn sm_3_enter_wrong_pin() {
// Create hash of pin
let pin = vec![Key::One, Key::Two, Key::Three, Key::Four];
let pin_hash = crate::hash(&pin);
let start = Atm {
cash_inside: 10,
expected_pin_hash: Auth::Authenticating(pin_hash),
keystroke_register: vec![Key::Three, Key::Three, Key::Three, Key::Three],
};
let end = Atm::next_state(&start, &Action::PressKey(Key::Enter));
let expected =
Atm { cash_inside: 10, expected_pin_hash: Auth::Waiting, keystroke_register: Vec::new() };
assert_eq!(end, expected);
}
#[test]
fn sm_3_enter_correct_pin() {
// Create hash of pin
let pin = vec![Key::One, Key::Two, Key::Three, Key::Four];
let pin_hash = crate::hash(&pin);
let start = Atm {
cash_inside: 10,
expected_pin_hash: Auth::Authenticating(pin_hash),
keystroke_register: vec![Key::One, Key::Two, Key::Three, Key::Four],
};
let end = Atm::next_state(&start, &Action::PressKey(Key::Enter));
let expected = Atm {
cash_inside: 10,
expected_pin_hash: Auth::Authenticated,
keystroke_register: Vec::new(),
};
assert_eq!(end, expected);
}
#[test]
fn sm_3_enter_single_digit_of_withdraw_amount() {
let start = Atm {
cash_inside: 10,
expected_pin_hash: Auth::Authenticated,
keystroke_register: Vec::new(),
};
let end = Atm::next_state(&start, &Action::PressKey(Key::One));
let expected = Atm {
cash_inside: 10,
expected_pin_hash: Auth::Authenticated,
keystroke_register: vec![Key::One],
};
assert_eq!(end, expected);
let start = Atm {
cash_inside: 10,
expected_pin_hash: Auth::Authenticated,
keystroke_register: vec![Key::One],
};
let end1 = Atm::next_state(&start, &Action::PressKey(Key::Four));
let expected1 = Atm {
cash_inside: 10,
expected_pin_hash: Auth::Authenticated,
keystroke_register: vec![Key::One, Key::Four],
};
assert_eq!(end1, expected1);
}
#[test]
fn sm_3_try_to_withdraw_too_much() {
let start = Atm {
cash_inside: 10,
expected_pin_hash: Auth::Authenticated,
keystroke_register: vec![Key::One, Key::Four],
};
let end = Atm::next_state(&start, &Action::PressKey(Key::Enter));
let expected =
Atm { cash_inside: 10, expected_pin_hash: Auth::Waiting, keystroke_register: Vec::new() };
assert_eq!(end, expected);
}
#[test]
fn sm_3_withdraw_acceptable_amount() {
let start = Atm {
cash_inside: 10,
expected_pin_hash: Auth::Authenticated,
keystroke_register: vec![Key::One],
};
let end = Atm::next_state(&start, &Action::PressKey(Key::Enter));
let expected =
Atm { cash_inside: 9, expected_pin_hash: Auth::Waiting, keystroke_register: Vec::new() };
assert_eq!(end, expected);
}
```
## p4_accounted_currency.rs
```rust
//! The state machines we have written so far model individual devices that are typically used
//! by a single user at a time. State machines can also model multi user systems. Blockchains
//! strive to provide reliable public infrastructure. And the public is very much multiple users.
//!
//! In this module and the next we explore two common techniques at modeling multi-user state
//! machines. In this module we explore accounts, and in the next we explore UTXOs.
//!
//! In this module we design a state machine that tracks the currency balances of several users.
//! Each user is associated with an account balance and users are able to send money to other users.
use super::{StateMachine, User};
use std::collections::HashMap;
/// This state machine models a multi-user currency system. It tracks the balance of each
/// user and allows users to send funds to one another.
pub struct AccountedCurrency;
const MINIMUM_EXISTENTIAL_BALANCE: u64 = 1;
/// The main balances mapping.
///
/// Each entry maps a user id to their corresponding balance.
/// There exists an existential deposit of at least 1. That is
/// to say that an account gets removed from the map entirely
/// when its balance falls back to 0.
type Balances = HashMap;
/// The state transitions that users can make in an accounted currency system
pub enum AccountingTransaction {
/// Create some new money for the given minter in the given amount
Mint { minter: User, amount: u64 },
/// Destroy some money from the given account in the given amount
/// If the burn amount exceeds the account balance, burn the entire
/// amount and remove the account from storage
Burn { burner: User, amount: u64 },
/// Send some tokens from one account to another
Transfer { sender: User, receiver: User, amount: u64 },
}
impl AccountedCurrency {
fn mint(updated_balances: &mut Balances, minter: &User, amount: &u64) {
let get_minter_balance = updated_balances.get_mut(minter);
match get_minter_balance {
Some(balance) => {
*balance = balance.saturating_add(*amount);
},
None => {
if *amount >= MINIMUM_EXISTENTIAL_BALANCE {
updated_balances.insert(*minter, *amount);
}
},
}
}
fn burn(updated_balances: &mut Balances, burner: &User, amount: &u64) {
let get_burner_balance = updated_balances.get_mut(burner);
if let Some(cur_balance) = get_burner_balance {
*cur_balance = cur_balance.saturating_sub(*amount);
if *cur_balance < MINIMUM_EXISTENTIAL_BALANCE {
updated_balances.remove(burner);
}
};
}
}
/// We model this system as a state machine with three possible transitions
impl StateMachine for AccountedCurrency {
type State = Balances;
type Transition = AccountingTransaction;
fn next_state(starting_state: &Balances, t: &AccountingTransaction) -> Balances {
let mut updated_balances = starting_state.clone();
match t {
AccountingTransaction::Mint { minter, amount } => {
Self::mint(&mut updated_balances, minter, amount);
},
AccountingTransaction::Burn { burner, amount } => {
Self::burn(&mut updated_balances, burner, amount);
},
AccountingTransaction::Transfer { sender, receiver, amount } => {
let sender_balance = starting_state.get(sender).unwrap_or_else(|| &0);
if sender_balance >= amount {
Self::burn(&mut updated_balances, sender, amount);
Self::mint(&mut updated_balances, receiver, amount);
}
},
}
return updated_balances;
}
}
#[test]
fn sm_4_mint_creates_account() {
let start = HashMap::new();
let end = AccountedCurrency::next_state(
&start,
&AccountingTransaction::Mint { minter: User::Alice, amount: 100 },
);
let expected = HashMap::from([(User::Alice, 100)]);
assert_eq!(end, expected);
}
#[test]
fn sm_4_mint_creates_second_account() {
let start = HashMap::from([(User::Alice, 100)]);
let end = AccountedCurrency::next_state(
&start,
&AccountingTransaction::Mint { minter: User::Bob, amount: 50 },
);
let expected = HashMap::from([(User::Alice, 100), (User::Bob, 50)]);
assert_eq!(end, expected);
}
#[test]
fn sm_4_mint_increases_balance() {
let start = HashMap::from([(User::Alice, 100)]);
let end = AccountedCurrency::next_state(
&start,
&AccountingTransaction::Mint { minter: User::Alice, amount: 50 },
);
let expected = HashMap::from([(User::Alice, 150)]);
assert_eq!(end, expected);
}
#[test]
fn sm_4_empty_mint() {
let start = HashMap::new();
let end = AccountedCurrency::next_state(
&start,
&AccountingTransaction::Mint { minter: User::Alice, amount: 0 },
);
let expected = HashMap::new();
assert_eq!(end, expected);
}
#[test]
fn sm_4_simple_burn() {
let start = HashMap::from([(User::Alice, 100)]);
let end = AccountedCurrency::next_state(
&start,
&AccountingTransaction::Burn { burner: User::Alice, amount: 50 },
);
let expected = HashMap::from([(User::Alice, 50)]);
assert_eq!(end, expected);
}
#[test]
fn sm_4_burn_no_existential_deposit_left() {
let start = HashMap::from([(User::Alice, 100), (User::Bob, 50)]);
let end = AccountedCurrency::next_state(
&start,
&AccountingTransaction::Burn { burner: User::Bob, amount: 50 },
);
let expected = HashMap::from([(User::Alice, 100)]);
assert_eq!(end, expected);
}
#[test]
fn sm_4_non_registered_burner() {
let start = HashMap::from([(User::Alice, 100)]);
let end = AccountedCurrency::next_state(
&start,
&AccountingTransaction::Burn { burner: User::Bob, amount: 50 },
);
let expected = HashMap::from([(User::Alice, 100)]);
assert_eq!(end, expected);
}
#[test]
fn sm_4_burn_more_than_balance() {
let start = HashMap::from([(User::Alice, 100), (User::Bob, 50)]);
let end2 = AccountedCurrency::next_state(
&start,
&AccountingTransaction::Burn { burner: User::Bob, amount: 100 },
);
let expected2 = HashMap::from([(User::Alice, 100)]);
assert_eq!(end2, expected2);
}
#[test]
fn sm_4_empty_burn() {
let start = HashMap::from([(User::Alice, 100)]);
let end = AccountedCurrency::next_state(
&start,
&AccountingTransaction::Burn { burner: User::Alice, amount: 0 },
);
let expected = HashMap::from([(User::Alice, 100)]);
assert_eq!(end, expected);
}
#[test]
fn sm_4_burner_does_not_exist() {
let start = HashMap::from([(User::Alice, 100)]);
let end = AccountedCurrency::next_state(
&start,
&AccountingTransaction::Burn { burner: User::Bob, amount: 50 },
);
let expected = HashMap::from([(User::Alice, 100)]);
assert_eq!(end, expected);
}
#[test]
fn sm_4_simple_transfer() {
let start = HashMap::from([(User::Alice, 100), (User::Bob, 50)]);
let end = AccountedCurrency::next_state(
&start,
&AccountingTransaction::Transfer { sender: User::Alice, receiver: User::Bob, amount: 10 },
);
let expected = HashMap::from([(User::Alice, 90), (User::Bob, 60)]);
assert_eq!(end, expected);
let start = HashMap::from([(User::Alice, 90), (User::Bob, 60)]);
let end1 = AccountedCurrency::next_state(
&start,
&AccountingTransaction::Transfer { sender: User::Bob, receiver: User::Alice, amount: 50 },
);
let expected1 = HashMap::from([(User::Alice, 140), (User::Bob, 10)]);
assert_eq!(end1, expected1);
}
#[test]
fn sm_4_send_to_same_user() {
let start = HashMap::from([(User::Alice, 100), (User::Bob, 50)]);
let end = AccountedCurrency::next_state(
&start,
&AccountingTransaction::Transfer { sender: User::Bob, receiver: User::Bob, amount: 10 },
);
let expected = HashMap::from([(User::Alice, 100), (User::Bob, 50)]);
assert_eq!(end, expected);
}
#[test]
fn sm_4_insufficient_balance_transfer() {
let start = HashMap::from([(User::Alice, 100), (User::Bob, 50)]);
let end = AccountedCurrency::next_state(
&start,
&AccountingTransaction::Transfer { sender: User::Bob, receiver: User::Alice, amount: 60 },
);
let expected = HashMap::from([(User::Alice, 100), (User::Bob, 50)]);
assert_eq!(end, expected);
}
#[test]
fn sm_4_sender_not_registered() {
let start = HashMap::from([(User::Alice, 100), (User::Bob, 50)]);
let end = AccountedCurrency::next_state(
&start,
&AccountingTransaction::Transfer {
sender: User::Charlie,
receiver: User::Alice,
amount: 50,
},
);
let expected = HashMap::from([(User::Alice, 100), (User::Bob, 50)]);
assert_eq!(end, expected);
}
#[test]
fn sm_4_receiver_not_registered() {
let start = HashMap::from([(User::Alice, 100), (User::Bob, 50)]);
let end = AccountedCurrency::next_state(
&start,
&AccountingTransaction::Transfer {
sender: User::Alice,
receiver: User::Charlie,
amount: 50,
},
);
let expected = HashMap::from([(User::Alice, 50), (User::Bob, 50), (User::Charlie, 50)]);
assert_eq!(end, expected);
}
#[test]
fn sm_4_sender_to_empty_balance() {
let start = HashMap::from([(User::Alice, 100), (User::Bob, 50)]);
let end = AccountedCurrency::next_state(
&start,
&AccountingTransaction::Transfer { sender: User::Bob, receiver: User::Alice, amount: 50 },
);
let expected = HashMap::from([(User::Alice, 150)]);
assert_eq!(end, expected);
}
#[test]
fn sm_4_transfer() {
let start = HashMap::from([(User::Alice, 100), (User::Bob, 50)]);
let end = AccountedCurrency::next_state(
&start,
&AccountingTransaction::Transfer { sender: User::Bob, receiver: User::Charlie, amount: 50 },
);
let expected = HashMap::from([(User::Alice, 100), (User::Charlie, 50)]);
assert_eq!(end, expected);
}
```
### p5_digital_cash
```rust
//! In this module we design another multi-user currency system. This one is not based on
//! accounts, but rather, is modelled after a paper cash system. The system tracks individual
//! cash bills. Each bill has an amount and an owner, and can be spent in its entirety.
//! When a state transition spends bills, new bills are created in lesser or equal amount.
use anyhow::{Error, Result};
use super::{StateMachine, User};
use std::collections::{HashMap, HashSet};
/// This state machine models a multi-user currency system. It tracks a set of bills in
/// circulation, and updates that set when money is transferred.
pub struct DigitalCashSystem;
/// A single bill in the digital cash system. Each bill has an owner who is allowed to spent
/// it and an amount that it is worth. It also has serial number to ensure that each bill
/// is unique.
#[derive(Clone, Debug, Eq, PartialEq, Hash)]
pub struct Bill {
owner: User,
amount: u64,
serial: u64,
}
/// The State of a digital cash system. Primarily just the set of currently circulating bills.,
/// but also a counter for the next serial number.
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct State {
/// The set of currently circulating bills
bills: HashSet,
/// The next serial number to use when a bill is created.
next_serial: u64,
}
impl State {
pub fn new() -> Self {
State { bills: HashSet::::new(), next_serial: 0 }
}
pub fn set_serial(&mut self, serial: u64) {
self.next_serial = serial;
}
pub fn next_serial(&self) -> u64 {
self.next_serial
}
fn increment_serial(&mut self) {
self.next_serial += 1
}
fn add_bill(&mut self, elem: Bill) {
self.bills.insert(elem);
self.increment_serial()
}
}
impl FromIterator for State {
fn from_iter>(iter: I) -> Self {
let mut state = State::new();
for i in iter {
state.add_bill(i)
}
state
}
}
impl From<[Bill; N]> for State {
fn from(value: [Bill; N]) -> Self {
State::from_iter(value)
}
}
/// The state transitions that users can make in a digital cash system
pub enum CashTransaction {
/// Mint a single new bill owned by the minter
Mint { minter: User, amount: u64 },
/// Send some money from some users to other users. The money does not all need
/// to come from the same user, and it does not all need to go to the same user.
/// The total amount received must be less than or equal to the amount spent.
/// The discrepancy between the amount sent and received is destroyed. Therefore,
/// no dedicated burn transaction is required.
Transfer { spends: Vec, receives: Vec },
}
/// We model this system as a state machine with two possible transitions
impl StateMachine for DigitalCashSystem {
type State = State;
type Transition = CashTransaction;
fn next_state(starting_state: &Self::State, t: &Self::Transition) -> Self::State {
let mut new_state = starting_state.clone();
match t {
CashTransaction::Mint { minter, amount } => {
// using `add_bill` method to add a new bill with serial as `next_serial()`
let bill =
Bill { owner: *minter, amount: *amount, serial: starting_state.next_serial() };
new_state.add_bill(bill);
},
CashTransaction::Transfer { spends, receives } => {
// if `spends` is empty, we don't do anything
if spends.len() == 0 {
return new_state;
}
// if `receives` is empty, we remove the discrepancy from the new state
if receives.len() == 0 {
new_state.bills = HashSet::default();
return new_state;
}
// closure to handle the transfer
let process_transfer = |new_state: &mut State| -> Result<()> {
let (spend_id, receive_id) = ("spend", "receive");
let mut visited_serial: HashMap<(&'static str, u64), bool> = HashMap::default();
let mut total_spends: u64 = 0;
let mut total_receive: u64 = 0;
for s in spends {
// if the `spend` bill is not exist in the current state => ERROR
if !new_state.bills.contains(s) {
return Err(Error::msg("bill does not exist"));
}
// if the `spend` bill serial is duplicate current state => ERROR
if visited_serial.contains_key(&(spend_id, s.serial)) {
return Err(Error::msg("invalid serial key"));
}
// mark the current `spend` bill serial as visited so we can check with receive later
visited_serial.insert((spend_id, s.serial), true);
// remove the `spend` bill from the new bill list as it is processed already
new_state.bills.remove(s);
// increase the total spend amount
total_spends = total_spends.saturating_add(s.amount);
}
for r in receives {
// if there is a serial with invalid value => ERROR
if r.serial == u64::MAX {
return Err(Error::msg("invalid serial key"));
}
// if the `receive` bill is same as `spend` bill, identified by serial => ERROR
if visited_serial.contains_key(&(spend_id, r.serial))
|| visited_serial.contains_key(&(receive_id, r.serial))
{
return Err(Error::msg("invalid serial key"));
}
// mark the `receive` bill as visited
visited_serial.insert((receive_id, r.serial), true);
// if the current `receive` bill amount is larger than `total_spends` => ERROR
if r.amount > total_spends {
return Err(Error::msg("exceed spending amount"));
}
// increase the total_receive so we can check if the value is zero later
total_receive += r.amount;
// substract the total_spends with `receive` bill amount
total_spends = total_spends.saturating_sub(r.amount);
// add `receive` bill to the new state if it passes all checks
new_state.add_bill(r.clone());
}
// if total_receive is zero => ERROR
if total_receive == 0 {
return Err(Error::msg("output 0 value"));
}
Ok(())
};
match process_transfer(&mut new_state) {
Ok(_) => {
return new_state;
},
Err(err) => {
// for debugging
println!("{}", err.to_string());
},
}
},
}
starting_state.clone()
}
}
#[test]
fn sm_5_mint_new_cash() {
let start = State::new();
let end = DigitalCashSystem::next_state(
&start,
&CashTransaction::Mint { minter: User::Alice, amount: 20 },
);
let expected = State::from([Bill { owner: User::Alice, amount: 20, serial: 0 }]);
assert_eq!(end, expected);
}
#[test]
fn sm_5_overflow_receives_fails() {
let start = State::from([Bill { owner: User::Alice, amount: 42, serial: 0 }]);
let end = DigitalCashSystem::next_state(
&start,
&CashTransaction::Transfer {
spends: vec![Bill { owner: User::Alice, amount: 42, serial: 0 }],
receives: vec![
Bill { owner: User::Alice, amount: u64::MAX, serial: 1 },
Bill { owner: User::Alice, amount: 42, serial: 2 },
],
},
);
let expected = State::from([Bill { owner: User::Alice, amount: 42, serial: 0 }]);
assert_eq!(end, expected);
}
#[test]
fn sm_5_empty_spend_fails() {
let start = State::from([Bill { owner: User::Alice, amount: 20, serial: 0 }]);
let end = DigitalCashSystem::next_state(
&start,
&CashTransaction::Transfer {
spends: vec![],
receives: vec![Bill { owner: User::Alice, amount: 15, serial: 1 }],
},
);
let expected = State::from([Bill { owner: User::Alice, amount: 20, serial: 0 }]);
assert_eq!(end, expected);
}
#[test]
fn sm_5_empty_receive_fails() {
let start = State::from([Bill { owner: User::Alice, amount: 20, serial: 0 }]);
let end = DigitalCashSystem::next_state(
&start,
&CashTransaction::Transfer {
spends: vec![Bill { owner: User::Alice, amount: 20, serial: 0 }],
receives: vec![],
},
);
let mut expected = State::from([]);
expected.set_serial(1);
assert_eq!(end, expected);
}
#[test]
fn sm_5_output_value_0_fails() {
let start = State::from([Bill { owner: User::Alice, amount: 20, serial: 0 }]);
let end = DigitalCashSystem::next_state(
&start,
&CashTransaction::Transfer {
spends: vec![Bill { owner: User::Alice, amount: 20, serial: 0 }],
receives: vec![Bill { owner: User::Bob, amount: 0, serial: 1 }],
},
);
let expected = State::from([Bill { owner: User::Alice, amount: 20, serial: 0 }]);
assert_eq!(end, expected);
}
#[test]
fn sm_5_serial_number_already_seen_fails() {
let start = State::from([Bill { owner: User::Alice, amount: 20, serial: 0 }]);
let end = DigitalCashSystem::next_state(
&start,
&CashTransaction::Transfer {
spends: vec![Bill { owner: User::Alice, amount: 20, serial: 0 }],
receives: vec![Bill { owner: User::Alice, amount: 18, serial: 0 }],
},
);
let expected = State::from([Bill { owner: User::Alice, amount: 20, serial: 0 }]);
assert_eq!(end, expected);
}
#[test]
fn sm_5_spending_and_receiving_same_bill_fails() {
let start = State::from([Bill { owner: User::Alice, amount: 20, serial: 0 }]);
let end = DigitalCashSystem::next_state(
&start,
&CashTransaction::Transfer {
spends: vec![Bill { owner: User::Alice, amount: 20, serial: 0 }],
receives: vec![Bill { owner: User::Alice, amount: 20, serial: 0 }],
},
);
let expected = State::from([Bill { owner: User::Alice, amount: 20, serial: 0 }]);
assert_eq!(end, expected);
}
#[test]
fn sm_5_receiving_bill_with_incorrect_serial_fails() {
let start = State::from([Bill { owner: User::Alice, amount: 20, serial: 0 }]);
let end = DigitalCashSystem::next_state(
&start,
&CashTransaction::Transfer {
spends: vec![Bill { owner: User::Alice, amount: 20, serial: 0 }],
receives: vec![
Bill { owner: User::Alice, amount: 10, serial: u64::MAX },
Bill { owner: User::Bob, amount: 10, serial: 4000 },
],
},
);
let expected = State::from([Bill { owner: User::Alice, amount: 20, serial: 0 }]);
assert_eq!(end, expected);
}
#[test]
fn sm_5_spending_bill_with_incorrect_amount_fails() {
let start = State::from([Bill { owner: User::Alice, amount: 20, serial: 0 }]);
let end = DigitalCashSystem::next_state(
&start,
&CashTransaction::Transfer {
spends: vec![Bill { owner: User::Alice, amount: 40, serial: 0 }],
receives: vec![Bill { owner: User::Bob, amount: 40, serial: 1 }],
},
);
let expected = State::from([Bill { owner: User::Alice, amount: 20, serial: 0 }]);
assert_eq!(end, expected);
}
#[test]
fn sm_5_spending_same_bill_fails() {
let start = State::from([Bill { owner: User::Alice, amount: 40, serial: 0 }]);
let end = DigitalCashSystem::next_state(
&start,
&CashTransaction::Transfer {
spends: vec![
Bill { owner: User::Alice, amount: 40, serial: 0 },
Bill { owner: User::Alice, amount: 40, serial: 0 },
],
receives: vec![
Bill { owner: User::Bob, amount: 20, serial: 1 },
Bill { owner: User::Bob, amount: 20, serial: 2 },
Bill { owner: User::Alice, amount: 40, serial: 3 },
],
},
);
let expected = State::from([Bill { owner: User::Alice, amount: 40, serial: 0 }]);
assert_eq!(end, expected);
}
#[test]
fn sm_5_spending_more_than_bill_fails() {
let start = State::from([
Bill { owner: User::Alice, amount: 40, serial: 0 },
Bill { owner: User::Charlie, amount: 42, serial: 1 },
]);
let end = DigitalCashSystem::next_state(
&start,
&CashTransaction::Transfer {
spends: vec![
Bill { owner: User::Alice, amount: 40, serial: 0 },
Bill { owner: User::Charlie, amount: 42, serial: 1 },
],
receives: vec![
Bill { owner: User::Bob, amount: 20, serial: 2 },
Bill { owner: User::Bob, amount: 20, serial: 3 },
Bill { owner: User::Alice, amount: 52, serial: 4 },
],
},
);
let expected = State::from([
Bill { owner: User::Alice, amount: 40, serial: 0 },
Bill { owner: User::Charlie, amount: 42, serial: 1 },
]);
assert_eq!(end, expected);
}
#[test]
fn sm_5_spending_non_existent_bill_fails() {
let start = State::from([Bill { owner: User::Alice, amount: 32, serial: 0 }]);
let end = DigitalCashSystem::next_state(
&start,
&CashTransaction::Transfer {
spends: vec![Bill { owner: User::Bob, amount: 1000, serial: 32 }],
receives: vec![Bill { owner: User::Bob, amount: 1000, serial: 33 }],
},
);
let expected = State::from([Bill { owner: User::Alice, amount: 32, serial: 0 }]);
assert_eq!(end, expected);
}
#[test]
fn sm_5_spending_from_alice_to_all() {
let start = State::from([Bill { owner: User::Alice, amount: 42, serial: 0 }]);
let end = DigitalCashSystem::next_state(
&start,
&CashTransaction::Transfer {
spends: vec![Bill { owner: User::Alice, amount: 42, serial: 0 }],
receives: vec![
Bill { owner: User::Alice, amount: 10, serial: 1 },
Bill { owner: User::Bob, amount: 10, serial: 2 },
Bill { owner: User::Charlie, amount: 10, serial: 3 },
],
},
);
let mut expected = State::from([
Bill { owner: User::Alice, amount: 10, serial: 1 },
Bill { owner: User::Bob, amount: 10, serial: 2 },
Bill { owner: User::Charlie, amount: 10, serial: 3 },
]);
expected.set_serial(4);
assert_eq!(end, expected);
}
#[test]
fn sm_5_spending_from_bob_to_all() {
let start = State::from([Bill { owner: User::Bob, amount: 42, serial: 0 }]);
let end = DigitalCashSystem::next_state(
&start,
&CashTransaction::Transfer {
spends: vec![Bill { owner: User::Bob, amount: 42, serial: 0 }],
receives: vec![
Bill { owner: User::Alice, amount: 10, serial: 1 },
Bill { owner: User::Bob, amount: 10, serial: 2 },
Bill { owner: User::Charlie, amount: 22, serial: 3 },
],
},
);
let mut expected = State::from([
Bill { owner: User::Alice, amount: 10, serial: 1 },
Bill { owner: User::Bob, amount: 10, serial: 2 },
Bill { owner: User::Charlie, amount: 22, serial: 3 },
]);
expected.set_serial(4);
assert_eq!(end, expected);
}
#[test]
fn sm_5_spending_from_charlie_to_all() {
let mut start = State::from([
Bill { owner: User::Charlie, amount: 68, serial: 54 },
Bill { owner: User::Alice, amount: 4000, serial: 58 },
]);
start.set_serial(59);
let end = DigitalCashSystem::next_state(
&start,
&CashTransaction::Transfer {
spends: vec![Bill { owner: User::Charlie, amount: 68, serial: 54 }],
receives: vec![
Bill { owner: User::Alice, amount: 42, serial: 59 },
Bill { owner: User::Bob, amount: 5, serial: 60 },
Bill { owner: User::Charlie, amount: 5, serial: 61 },
],
},
);
let mut expected = State::from([
Bill { owner: User::Alice, amount: 4000, serial: 58 },
Bill { owner: User::Alice, amount: 42, serial: 59 },
Bill { owner: User::Bob, amount: 5, serial: 60 },
Bill { owner: User::Charlie, amount: 5, serial: 61 },
]);
expected.set_serial(62);
assert_eq!(end, expected);
}
```
### p6_open_ended.rs
```rust
//! Now is your chance to get creative. Choose a state machine that interests you and model it here.
//! Get as fancy as you like. The only constraint is that it should be simple enough that you can
//! realistically model it in an hour or two.
//!
//! Here are some ideas:
//! - Board games:
//! - Chess
//! - Checkers
//! - Tic tac toe
//! - Beaurocracies:
//! - Beauro of Motor Vehicles - maintains driving licenses and vehicle registrations.
//! - Public Utility Provider - Customers open accounts, consume the utility, pay their bill
//! periodically, maybe utility prices fluctuate
//! - Land ownership registry
//! - Tokenomics:
//! - Token Curated Registry
//! - Prediction Market
//! - There's a game where there's a prize to be split among players and the prize grows over
//! time. Any player can stop it at any point and take most of the prize for themselves.
//! - Social Systems:
//! - Social Graph
//! - Web of Trust
//! - Reputation System
use anyhow::{Error, Result};
use std::collections::{HashMap, HashSet};
use std::result::Result::Ok;
use std::vec;
use super::StateMachine;
type Row = i16;
type Col = i16;
type Position = (Row, Col);
#[derive(Clone, Eq, PartialEq, Debug)]
enum Color {
Black,
White,
}
const BOARD_MAX_SIZE: i16 = 8;
const BOARD_MIN_SIZE: i16 = 0;
impl Color {
fn get_other_color(self: &Self) -> Color {
return match self {
Color::Black => Color::White,
Color::White => Color::Black,
};
}
fn dir(self: &Self) -> i16 {
match self {
Color::White => -1,
Color::Black => 1,
}
}
}
#[derive(Clone, PartialEq, Eq, Debug)]
enum ChessPiece {
Pawn(Color),
Bishop(Color),
Knight(Color),
Rook(Color),
Queen(Color),
King(Color),
}
fn get_rook_moves((row, col): Position) -> Vec {
let mut rook_moves = vec![];
for i in BOARD_MIN_SIZE + 1..BOARD_MAX_SIZE {
rook_moves.append(&mut vec![(row + i, col), (row - i, col)]);
rook_moves.append(&mut vec![(row, col + i), (row, col - 1)]);
}
rook_moves
}
fn get_bishop_moves((row, col): Position) -> Vec {
let mut bishop_moves = vec![];
for i in BOARD_MIN_SIZE + 1..BOARD_MAX_SIZE {
bishop_moves.append(&mut vec![
(row + i, col + i),
(row + i, col - i),
(row - i, col + i),
(row - i, col - i),
]);
}
bishop_moves
}
impl ChessPiece {
pub fn get_color(self: &Self) -> Color {
match self {
ChessPiece::Pawn(color) => return color.clone(),
ChessPiece::Bishop(color) => return color.clone(),
ChessPiece::King(color) => return color.clone(),
ChessPiece::Knight(color) => return color.clone(),
ChessPiece::Queen(color) => return color.clone(),
ChessPiece::Rook(color) => return color.clone(),
};
}
pub fn get_moves(self: &Self, pos: Position) -> HashSet {
let row = pos.0 as i16;
let col = pos.1 as i16;
let mut moves = HashSet::default();
let chess_moves: Vec = match self {
ChessPiece::Bishop(_) => get_bishop_moves(pos),
ChessPiece::Rook(_) => get_rook_moves(pos),
ChessPiece::King(_) => {
vec![
(row + 1, col + 1),
(row + 1, col),
(row + 1, col - 1),
(row, col + 1),
(row, col - 1),
(row - 1, col + 1),
(row - 1, col),
(row - 1, col - 1),
]
},
ChessPiece::Knight(_) => {
vec![
(row + 2, col + 1),
(row + 2, col - 1),
(row - 2, col + 1),
(row - 2, col - 1),
(row + 1, col + 2),
(row + 1, col - 2),
(row - 1, col + 2),
(row - 1, col - 2),
]
},
ChessPiece::Pawn(color) => {
let d = color.dir();
vec![(row + d, col + 1), (row - d, col - 1)]
},
ChessPiece::Queen(_) => {
let rook_moves = get_rook_moves(pos);
let bishop_moves = get_bishop_moves(pos);
[rook_moves, bishop_moves].concat()
},
};
for (row, col) in chess_moves {
// chess moves out of the board
if row > BOARD_MAX_SIZE
|| col > BOARD_MAX_SIZE
|| row <= BOARD_MIN_SIZE
|| col <= BOARD_MIN_SIZE
{
continue;
}
moves.insert((row, col));
}
return moves;
}
}
#[derive(Clone, PartialEq, Eq, Debug)]
enum ChessGameStatus {
Finished(Color),
Running,
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct State {
/// Chess Board
/// Column
/// |
/// | 1 2 3 4 5 6 7 8
/// Row - - - - - - - - - -
/// 1 | R k B Q K B k R
/// 2 | P P P P P P P P
/// 3 |
/// 4 |
/// 5 |
/// 6 |
/// 7 | P P P P P P P P
/// 8 | R k B Q K B k R
board: HashMap,
side_color: Color,
status: ChessGameStatus,
moves: u64,
}
impl Default for State {
fn default() -> Self {
State {
moves: 0,
status: ChessGameStatus::Running,
side_color: Color::White,
board: HashMap::from([
((1, 1), ChessPiece::Rook(Color::Black)),
((1, 2), ChessPiece::Knight(Color::Black)),
((1, 3), ChessPiece::Bishop(Color::Black)),
((1, 4), ChessPiece::Queen(Color::Black)),
((1, 5), ChessPiece::King(Color::Black)),
((1, 6), ChessPiece::Bishop(Color::Black)),
((1, 7), ChessPiece::Knight(Color::Black)),
((1, 8), ChessPiece::Rook(Color::Black)),
((2, 1), ChessPiece::Pawn(Color::Black)),
((2, 2), ChessPiece::Pawn(Color::Black)),
((2, 3), ChessPiece::Pawn(Color::Black)),
((2, 4), ChessPiece::Pawn(Color::Black)),
((2, 5), ChessPiece::Pawn(Color::Black)),
((2, 6), ChessPiece::Pawn(Color::Black)),
((2, 7), ChessPiece::Pawn(Color::Black)),
((2, 8), ChessPiece::Pawn(Color::Black)),
((7, 1), ChessPiece::Pawn(Color::White)),
((7, 2), ChessPiece::Pawn(Color::White)),
((7, 3), ChessPiece::Pawn(Color::White)),
((7, 4), ChessPiece::Pawn(Color::White)),
((7, 5), ChessPiece::Pawn(Color::White)),
((7, 6), ChessPiece::Pawn(Color::White)),
((7, 7), ChessPiece::Pawn(Color::White)),
((7, 8), ChessPiece::Pawn(Color::White)),
((8, 1), ChessPiece::Rook(Color::White)),
((8, 2), ChessPiece::Knight(Color::White)),
((8, 3), ChessPiece::Bishop(Color::White)),
((8, 4), ChessPiece::Queen(Color::White)),
((8, 5), ChessPiece::King(Color::White)),
((8, 6), ChessPiece::Bishop(Color::White)),
((8, 7), ChessPiece::Knight(Color::White)),
((8, 8), ChessPiece::Rook(Color::White)),
]),
}
}
}
pub enum Transition {
#[allow(unused)]
Move { chess_piece: ChessPiece, from: Position, to: Position },
}
impl State {
fn incre_move(self: &mut Self) {
self.moves += 1;
}
fn board_move(self: &mut Self, from_pos: Position, to_pos: Position) -> Option {
let pos_element = self.board.get(&from_pos);
if let Some(element) = pos_element {
let option = self.board.insert(to_pos, element.clone());
if option.is_some() {
return option;
}
self.board.remove(&from_pos);
}
self.incre_move();
return None;
}
fn next_color(self: &mut Self, color: Color) {
self.side_color = color.get_other_color();
}
}
impl StateMachine for State {
type State = State;
type Transition = Transition;
fn human_name() -> String {
return String::from("Chess State Machine");
}
fn next_state(starting_state: &Self::State, t: &Self::Transition) -> Self::State {
let mut updated_state = starting_state.clone();
let process_state = |updated_state: &mut State| -> Result<()> {
match t {
Transition::Move { chess_piece, from, to } => {
let chess_piece_color = chess_piece.get_color();
let enemy_color = chess_piece_color.get_other_color();
if chess_piece_color != starting_state.side_color {
return Err(Error::msg("wrong side color"));
}
let get_chess_from_pos = starting_state.board.get(from);
if get_chess_from_pos.is_none() || get_chess_from_pos.unwrap() != chess_piece {
return Err(Error::msg("chess piece is not at `from` position"));
}
let possible_moves = chess_piece.get_moves(*from);
if !possible_moves.contains(to) {
return Err(Error::msg("invalid move"));
}
for possible_move in possible_moves {
if let Some(board_chess) = starting_state.board.get(&possible_move) {
if board_chess.get_color() == chess_piece_color {
// possible move lands on same side chess piece
return Err(Error::msg(
"position is occupied by other same side chess",
));
}
}
}
// this also covers a case of enemy chess piece is killed
if let Some(killed_chess_piece) = updated_state.board_move(*from, *to) {
if killed_chess_piece == ChessPiece::King(enemy_color) {
updated_state.status =
ChessGameStatus::Finished(chess_piece_color.clone());
}
}
updated_state.next_color(chess_piece_color);
},
};
Ok(())
};
match process_state(&mut updated_state) {
Ok(_) => {
return updated_state;
},
Err(err) => {
println!("{}", err.to_string());
return starting_state.clone();
},
};
}
}
mod test {
#[allow(unused)]
use super::*;
#[test]
fn test_wrong_side_color() {
let state = State::default();
let end = State::next_state(
&state,
&Transition::Move {
chess_piece: ChessPiece::Pawn(Color::Black),
from: (7, 1),
to: (7, 3),
},
);
let expected = State::default();
assert_eq!(end, expected);
}
#[test]
fn test_pawn_move_failed_invalid_move() {
let state = State::default();
let end = State::next_state(
&state,
&Transition::Move {
chess_piece: ChessPiece::Pawn(Color::White),
from: (7, 1),
to: (8, 8),
},
);
let expected = State::default();
assert_eq!(end, expected);
}
#[test]
fn test_success_move_pawn() {
let state = State::default();
let end = State::next_state(
&state,
&Transition::Move {
chess_piece: ChessPiece::Pawn(Color::White),
from: (7, 1),
to: (6, 2),
},
);
let mut expected = State::default();
expected.board_move((7, 1), (6, 2));
expected.next_color(Color::White);
assert_eq!(end, expected);
}
#[test]
fn test_invalid_bishop_move() {
let state = State::default();
let end = State::next_state(
&state,
&Transition::Move {
chess_piece: ChessPiece::Bishop(Color::White),
from: (8, 3),
to: (7, 3),
},
);
let expected = State::default();
assert_eq!(end, expected);
}
#[test]
fn test_success_move_bishop() {
let state = State::default();
let end = State::next_state(
&state,
&Transition::Move {
chess_piece: ChessPiece::Bishop(Color::White),
from: (8, 3),
to: (7, 4),
},
);
let mut expected = State::default();
expected.board_move((8, 3), (7, 4));
expected.next_color(Color::White);
assert_eq!(end, expected);
}
#[test]
fn test_invalid_king_move() {
let state = State::default();
let end = State::next_state(
&state,
&Transition::Move {
chess_piece: ChessPiece::King(Color::White),
from: (8, 5),
to: (8, 7),
},
);
let expected = State::default();
assert_eq!(end, expected);
}
#[test]
fn test_success_move_king() {
let state = State::default();
let end = State::next_state(
&state,
&Transition::Move {
chess_piece: ChessPiece::King(Color::White),
from: (8, 5),
to: (8, 4),
},
);
let mut expected = State::default();
expected.board_move((8, 5), (8, 4));
expected.next_color(Color::White);
assert_eq!(end, expected);
}
}
```
Discussed in https://github.com/orgs/lowlevelers/discussions/7