Kata

A Finite State Machine (FSM) is an abstract machine that can be in exactly one of a finite number of states at any given time. Simple examples are:

• vending machines, which dispense products when the proper combination of coins is deposited;
• elevators, whose sequence of stops is determined by the floors requested by riders;
• traffic lights, which change sequence when cars are waiting;
• combination locks, which require the input of combination numbers in the proper order.

In this Kata we are going to design our very own basic FSM class that takes in a string of instructions

instructions is a string input with the following format:

first; next_if_input_0, next_if_input_1; output\n
second; next_if_input_0, next_if_input_1; output\n
third; next_if_input_0, next_if_input_1; output

A basic example would be:

instructions = \
'''S1; S1, S2; 9
S2; S1, S3; 10
S3; S4, S3; 8
S4; S4, S1; 0'''

char instructions[] = "S1; S1, S2; 9\n"
                      "S2; S1, S3; 10\n"
                      "S3; S4, S3; 8\n"
                      "S4; S4, S1; 0";

const instructions = (
  'S1; S1, S2; 9\n' +
  'S2; S1, S3; 10\n'+
  'S3; S4, S3; 8\n' +
  'S4; S4, S1; 0' )

instructions = """
S1; S1, S2; 9
S2; S1, S3; 10
S3; S4, S3; 8
S4; S4, S1; 0"""

String instructions = "S1; S1, S2; 9\n" +
                      "S2; S1, S3; 10\n" +
                      "S3; S4, S3; 8\n" +
                      "S4; S4, S1; 0\n";

Where each line in the string describes a state in the FSM. Given in the example, if the current state was S1, if the input is 0 it would loop back to itself: S1 and if the input is 1 it would go to S2

The instructions are compiled into the FSM class, then the run_fsm() method will be called to simulate the compiled FSM.

Example:

# run_fsm takes in two arguments:

start = 'S1'
# where start is the name of the state that it starts from
sequence = [0, 1, 1, 0, 1]
# where sequence is a list of inputs
# inputs are only 1 or 0 (1 input variable) 
# to keep it simple with this Kata
final_state, final_state_value, path = run_fsm(start, sequence)
# run_fsm should return a tuple as:
final_state => name of final state
final_state_value => integer value of state output
path => list of states the FSM sequence went through

Fsm *fsm = compile(instructions);

const char *final_state;
const char *path[6];
int final_state_value = run_fsm(
  fsm,
  "S1",                     // name of the initial state
  (_Bool[]){0, 1, 1, 0, 1}, // input
  5,                        // input length
  &final_state,             // returned final state
  &path                     // returned path
); // returns the output from the final state

// runFSM takes two arguments:

start = 'S1'
// where start is the name of the state that it starts from

sequence = [0, 1, 1, 0, 1]
// where sequence is a list of inputs
// inputs are only 1 or 0 (1 input variable) 
// to keep it simple with this Kata

// Input / Output
runFSM(start, sequence)  --returns-->  [final_state, final_state_value, path]

// runFSM should return an array as:
final_state       //= name of final state
final_state_value //= integer value of state output
path              //= array of states the FSM sequence went through

# run_fsm takes in three arguments:

# fsm is your compiled FSM
fsm = FSM(instructions)

# start is the name of the state that it starts from
start = "S1"

# sequence is a list of inputs
sequence = [0, 1, 1, 0, 1]
# inputs are only 1 or 0 (1 input variable) 
# to keep it simple with this Kata

# run_fsm should return a tuple as:
final_state, final_state_value, path = run_fsm(fsm, start, sequence)
#=
  final_state => name of final state
  final_state_value => integer value of state output
  path => list of states the FSM sequence went through
=#

// runFSM takes in two arguments:

// fsm is your compiled FSM
FSM fsm = new FSM(instructions);

// start is the name of the state that it starts from
String start = "S1";

// sequence is a list of inputs
int[] sequence = new int[]{0, 1, 1, 0, 1};
// inputs are only 1 or 0 (1 input variable) 
// to keep it simple with this Kata

// runFSM should return a Result as:
Result result = fsm.runFSM(start, sequence);
// result.finalState => name of final state
// result.output => integer value of state output
// result.path => array of states the FSM sequence went through

From the given example, when run_fsm is executed the following should proceed below

instructions:
S1; S1, S2; 9
S2; S1, S3; 10
S3; S4, S3; 8
S4; S4, S1; 0

start: S1
sequence: 0, 1, 1, 0, 1

input 0: S1->S1
input 1: S1->S2
input 1: S2->S3
input 0: S3->S4
input 1: S4->S1

final state: S1
output: 9

In this Kata are many FSM examples in real life described in: https://en.wikipedia.org/wiki/Finite-state_machine

Good Luck!