Here's a hint: The states in your state machine are not associated with the binary codes representing the key inputs, they're associated with the number of correct numbers entered so far. You start out in an initial, or "reset" state, in which no valid keys have been entered so far, and then proceed to states representing 1 valid key entered, 2 valid keys entered, etc. until you get to the final state with 5 valid keys entered. In the last state, the output is 1; in all others it's 0.

In each state, if the next valid key is entered, you proceed to the next state; otherwise, you go back to the initial state.

There are two sides to this problem: the algorithmic and the engineering.

**Algorithmic:**

How do you determine the amount of each type of coins to give back as a change, such that the total amount of coins is minimized?

In this case, there is very simple algorithm: start by giving back the highest value coins. Once the remaining amount of change gets below the value of the highest value coins, start giving back the second highest. Keep this process until you gave back the whole amount of change required.

**Engineering:**

In the most general case of a vending machine, you would implement in HW the above algorithm. However, due to the simplifications provided in the problem's description you can do the following:

- Calculate yourself the required change for each item
- Implement a simple state machine which returns the amount of coins which you've just calculated based on the type of item bought.

The input to your state machine will be the type of the item.

There will be three outputs: one for each type of coin you can give back for change.

The purpose of the state machine is to assert the outputs some predefined number of times based on the input.

You do not necessarily have to latch the input - once you got the input, your state machine will transition to one of the two states corresponding to each type of item. From now on, you no longer need the input signal.

**One possible implementation:**

This implementation is one of the possible implementations, but not the only one.

You got just three coins types which you can use for the change. The amount of each coin type you need to give back to the buyer is determined by which kind of product did he buy.

You could use three different counters (one for each type of coins). Once you get the input from the buyer you load the initial amount of coins to each counter. While not all the counters are zeroed, on each clock cycle you assert the output corresponding to the one of non-zero counters and reduce the count of this particular counter by 1.

This is not the best approach in terms of gate count, but it will work.

## Best Answer

This isn't really a sequence detection problem. All you need to do is remember the previous state of each input (two DFFs). The rest is combinatorial logic on those bits combined with the current value of each input (four 2-input gates).

Solution:Explanation: