[Prepare for PBA] pba_book: blockchain from scratch (c1_state_machine)

[chungquantin]

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
• Rust state machine (Substrate minimal version): https://github.com/shawntabrizi/rust-state-machine

Answer

p1_switches.rs

//! 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

//! 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

//! 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<Key>,
}

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

//! 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<User, u64>;

/// 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

//! 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<Bill>,
	/// The next serial number to use when a bill is created.
	next_serial: u64,
}

impl State {
	pub fn new() -> Self {
		State { bills: HashSet::<Bill>::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<Bill> for State {
	fn from_iter<I: IntoIterator<Item = Bill>>(iter: I) -> Self {
		let mut state = State::new();

		for i in iter {
			state.add_bill(i)
		}
		state
	}
}

impl<const N: usize> 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<Bill>, receives: Vec<Bill> },
}

/// 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

//! 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<Position> {
	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<Position> {
	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<Position> {
		let row = pos.0 as i16;
		let col = pos.1 as i16;
		let mut moves = HashSet::default();
		let chess_moves: Vec<Position> = 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<Position, ChessPiece>,
	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<ChessPiece> {
		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);
	}
}