The parking machine implementation

Question

I am interesting in the topic of finite automata, so I started over by implementing a parking machine from this video: Computers Without Memory - Computerphile to understand conceptions. Didn't do much of an error checking - have made a minimal working version.

Short description of the task, but for better understanding watch the video:

1. You have the parking machine which is implemented by the finite automaton.
2. The parking lot costs 25 pence. The machine takes only 5, 10, 20 pence coins. Thus, any combination of these coins can be used to pay for parking.
3. After a sum of coins has reached 25 pence, the ticket is issued.
4. The machine gobble up all extra money above the 25 pence, like 20 + 20 pence = the ticket only, no change are given.

Questions:

• What do you think about my approach?
• Is it optimal, extendable, suitable for real world applications or this technique has limiting factors and an another should be used?
• How would you implement this machine? It will be good to see another solutions.

It is possible to do this by such way: Explicit state transition table, may be I will do this also. My target is to implement something more serious like a regex engine in the future, but I should read some books/articles before.

#!/usr/bin/python3

def get_coin(current_sum, *functions):
    print(f"Current sum = {current_sum} pence")
    coin = int(input("Insert coin\n"))
    if coin == 5:
        functions[0]()
    elif coin == 10:
        functions[1]()
    elif coin == 20:
        functions[2]()
    else:
        error(current_sum, functions)

def error(current_sum, functions):
    print("Error: only 5, 10, 20 pence coins are allowed\n")
    get_coin(current_sum, *functions)

def zero_pence():
    get_coin("0", five_pence, ten_pence, twenty_pence)

def five_pence():
    get_coin("5", ten_pence, fifteen_pence, twenty_five_pence)

def ten_pence():
    get_coin("10", fifteen_pence, twenty_pence, give_ticket)

def fifteen_pence():
    get_coin("15", twenty_pence, twenty_five_pence, give_ticket)

def twenty_pence():
    get_coin("20", twenty_five_pence, give_ticket, give_ticket)

def twenty_five_pence():
    input("Current sum = 25 pence, press the 'return' button to pay")
    give_ticket()

def give_ticket():
    print("""\nTake your ticket:

Date: 1 November 2019
Start time: \t20:21
End time: \t22:21\n
""")

def parking_machine():
    prompt = """\n\tThe parking machine.

Information:
1. The machine takes 5, 10, 20 coins.
2. The machine doesn't give a change.
3. The parking costs 25 pence.

Press 's' button to start inserting of coins.

"""
    prompt = '#' * 80 + prompt + '#' * 80 + '\n'

    while True:
        button = input(prompt)
        if button == 's':
            zero_pence()

parking_machine()

Answer 1

Not a finite state machine

The state machine in the posted code has infinite states. This is caused by the recursive calls of get_coin and error. Consider for example these states:

• zero-pence with nothing entered yet
• zero-pence, after zero-pence and an invalid input
• zero-pence, after zero-pence and an invalid input twice
• ...

And so on. You can see these are different states, because the content of the stack is different.

There are theoretically infinite zero-pence, five-pence, etc, states. Practically there are finite, because after enough invalid inputs, the stack will eventually overflow.

There should be precisely one zero-pence, five-pence, etc, states.

This is easy to fix by replacing the error function with a loop inside get_coin.

There are too many states

Even after making the states finite, there will still be more states than required by the exercise.

Why, again, because of the stack. For example, there are two ways to reach 10 pence:

• 0 -> 5 -> 5
• 0 -> 10

At this point, the machine should be in the 10 pence state, but these two states are not the same, because the stack stores two different histories.

If you want truly identical ten-pence, fifteen-pence, etc, states, you have to eliminate history, you have to eliminate stack, you have to eliminate function calls.

This is easy to fix by implementing state transitions in a loop, instead of through function calls.

Don't use varargs if you don't need it

The get_coin function takes a variable number of functions as arguments. But in fact it will only ever use 3, and in fact it's only ever called with 3. Therefore, it would be more natural to give those parameters dedicated, descriptive names.

Why convert input to int?

The get_coin function converts input to int, but doesn't actually perform any numeric operations with it.

Use a more portable shebang

Not all systems have Python 3 installed in /usr/bin/python3. A more robust, portable shebang would be:

#!/usr/bin/env python3

Answer 2

Given a state machine p which has initial state s and final state f, then it can only accept 0, 5, 10, 20 as inputs. This can be represented graphically as such:

Therefore, the machine must continue to run until the sum of the coins entered exceeds or equals 25. Therefore, the Python code can be written to be more faithful to the state machine as:

states = {
  "s": {0: "s", 5: "q1", 10: "q2", 20: "q4"},
  "q1": {0: "q1", 5: "q2", 10: "q3", 20: "f"},
  "q2": {0: "q2", 5: "q3", 10: "q4", 20: "f"},
  "q3": {0: "q3", 5: "q4", 10: "f", 20: "f"},
  "q4": {0: "q4", 5: "f", 10: "f", 20: "f"},
  "f": {0: "f"}
}

current_state = "s"

prompt = """\tThe parking machine.

Information:
1. The machine takes 5, 10, 20 coins.
2. The machine doesn't give a change.
3. The parking costs 25 pence.
"""
prompt = '#' * 80 + prompt + '#' * 80 + '\n'
print(prompt)

while (current_state != "f"):
  try:
      current_state = states[current_state][int(input("Insert coin: "))]
  except (ValueError, KeyError):
      print("Error: only 5, 10, 20 pence coins are allowed\n")

print("""\nTake your ticket:

Date: 1 November 2019
Start time: \t20:21
End time: \t22:21\n
""")

This removes all issues with recursion and stack overflows as there is no history (it is impossible to determine if state q1 was reached by accepting state 0 or 5, or any combination of those.

Answer 3

• For the first question: Your implementation is really good.

• For the second question: Yes, I believe this is suitable for real world applications, though it won't work without knowing mechanical engineering.

• For the third question: I've added my implementation at the bottom of the answer!

Here's how we can improve your current code:

Let's analyze the functions get_coin, give_ticket, and parking_machine as all others are just really simple functions.

get_coin

You don't have to use the function error! Instead, use:

while coin not in [5, 10, 20]:
    print("Error: only 5, 10, 20 pence coins are allowed\n")
    coin = int(input("Insert coin\n"))

If you want, you can replace

if coin == 5:
    functions[0]()
elif coin == 10:
    functions[1]()
elif coin == 20:
    functions[2]()

with

functions[int(coin >= 10) + int(coin >= 20)]()

Though it impacts the readability of that part. If I were you, I'd use a comment to explain what that part does!

give_ticket

Instead of

    print("""\nTake your ticket:

Date: 1 November 2019
Start time: \t20:21
End time: \t22:21\n
""")

I'd rather use

    print(
    """
        Take your ticket:

        Date: 1 November 2019
        Start time: \t20:21
        End time: \t22:21\n
    """)

With the space. I think it looks like a ticket only then!

Anyway, if you don't want the space, just use textwrap.dedent

def give_ticket():
    print(textwrap.dedent("""
        Take your ticket:

        Date: 1 November 2019
        Start time: \t20:21
        End time: \t22:21\n
    """))

This would remove the leading space in every line.

parking_machine

Same as the last one, except you have to print The parking machine. separately as it requires \t which textwrap.dedent would remove. Also, I'd add seperate = '#' * 80 and use it instead

Also, I'd rather add an option to quit as the only way to quit this program would be to close it.

General

Always have a if __name__ == '__main__' guard over your main code which will prevent it from running while imported from another module.

So,

parking_machine()

Should be

if __name__ == '__main__':
    parking_machine()

---

This is what the final code would look like:

import textwrap

def get_coin(current_sum, *functions):
    print(f"Current sum = {current_sum} pence")
    coin = int(input("Insert coin\n"))

    while coin not in [5, 10, 20]:
        print("Error: only 5, 10, 20 pence coins are allowed\n")
        coin = int(input("Insert coin\n"))

    functions[int(coin >= 10) + int(coin >= 20)]()

def zero_pence():
    get_coin("0", five_pence, ten_pence, twenty_pence)

def five_pence():
    get_coin("5", ten_pence, fifteen_pence, twenty_five_pence)

def ten_pence():
    get_coin("10", fifteen_pence, twenty_pence, give_ticket)

def fifteen_pence():
    get_coin("15", twenty_pence, twenty_five_pence, give_ticket)

def twenty_pence():
    get_coin("20", twenty_five_pence, give_ticket, give_ticket)

def twenty_five_pence():
    input("Current sum = 25 pence, press the 'return' button to pay: ")
    give_ticket()

def give_ticket():
    print(textwrap.dedent("""

        Take your ticket:

        Date: 1 November 2019
        Start time:  20:21
        End time:    22:21

    """))

def parking_machine():
    prompt = textwrap.dedent(
    """

        Information:
        1. The machine takes 5, 10, 20 coins.
        2. The machine doesn't give a change.
        3. The parking costs 25 pence.

        Press 's' button to start inserting of coins or 'q' to quit.

    """)

    prompt = '\n\tThe parking machine.' + prompt

    seperate = '#' * 80 + '\n'

    prompt = seperate + prompt + seperate

    while True:
        button = input(prompt)

        if button == 's':
            zero_pence()

        if button == 'q':
            print('Thanks for using this machine!')
            quit()

if __name__ == '__main__':
    parking_machine()

I'll make sure to add more ideas when I get them!

Hope this helps!

EDIT:

Here's how I'd implement it if I completely based inputs and outputs off of your program.

import textwrap

def give_ticket():
    print("""

        Take your ticket:

        Date: 1 November 2019
        Start time:  20:21
        End time:    22:21

    """)

def parking_machine():
    prompt = textwrap.dedent(f"""
    {'#' * 80}

    The parking machine.

        Information:
        1. The machine takes 5, 10, 20 coins.
        2. The machine doesn't give a change.
        3. The parking costs 25 pence.

        Press 's' button to start inserting of coins or 'q' to quit.

    {'#' * 80}
    """)

    while True:
        button = input(prompt)

        if button == 's':
            current_sum = 0

            while current_sum < 25:
                print(f"Current sum = {current_sum} pence")

                while True:
                    coin = int(input("Insert coin\n"))

                    if coin not in [5, 10, 20]:
                        print("Error: only 5, 10, 20 pence coins are allowed\n")
                    else:
                        current_sum += coin
                        break

            if current_sum == 25:
                input("Current sum = 25 pence, press the 'return' button to pay: ")

            give_ticket()

        if button == 'q':
            print('Thanks for using this machine!')
            quit()

if __name__ == '__main__':
    parking_machine()