My first experience with SM (State Machines) was about 4 years ago when I started reading the Ordering code for Shopee. And it was confusing as hell! Then I was put in charge of moving the code to our new system, which, over time, made me kinda love the approach. So it was inevitable for me to be in charge of the design for the new Ordering and Payment SM.
Recently, when I was brushing up my leetcode skill, I came across a simple Atoi question that made something in me tingle! it was time to put all those SM “practices” to test!
Problem 8
So the question reads as follows:
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function).
The algorithm for myAtoi(string s) is as follows:
Read in and ignore any leading whitespace.
Check if the next character (if not already at the end of the string) is '-' or '+'.
Read this character in if it is either. This determines if the final result is negative or positive respectively.
Assume the result is positive if neither is present.
Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32).
If no digits were read, then the integer is 0.
Change the sign as necessary (from step 2).
If the integer is out of the 32-bit signed integer range [-2^31, 2^31 - 1], then clamp the integer so that it remains in the range.
Specifically, integers less than -2^31 should be clamped to -2^31, and integers greater than 2^31 - 1 should be clamped to 2^31 - 1.
Return the integer as the final result.Ok, that was a lot of text. TL;DR: convert the string to int, and follow a bunch of rules. And those rulesets were the reason I was so keen to try and solve it using the SM approach.
Solution
So I started by defining the states. In my solution, I used 6 states to keep track of what has happened, and what can be done.
// 0 begininng // 1,2,3,4
// 1 signing // 0 3
// 2 whitespace // 1 3
// 3 digit
// 4 non-digit
// 5 dead!
type States int32
const (
begininng States = iota
signing
whitespace
digit
non_digit
dead
)Every operation starts from the beginning state, therefore, the initial state of the SM is 0. And since 0 is the first state, it can move to almost every state (apart from dead!). The dead state is the final state, which ends the SM and produces the result. And each state in between represents a possibility and is controlled by a ruleset.
Digit & Signing are the most basic functionality we need to provide. We know every time we see a digit we need to add it to the current value. Therefore, the functionality is the simplest to write. The only thing it needs to check is to validate the int32 range and move to the dead state if it’s out of range.
func (sm *StateMachine) toDigit(c byte) {
toInt := int(c - 48)
if sm.sign == 0 || sm.sign == isPositive {
if sm.currentValue > sm.upperLmt || sm.currentValue == sm.upperLmt && toInt >= sm.upperLmtMod {
sm.currentValue = sm.clampTop
sm.move(dead)
return
}
} else {
if sm.currentValue > sm.lowerLmt || sm.currentValue == sm.lowerLmt && toInt >= sm.lowerLmtMod {
sm.currentValue = sm.clampBtm
sm.move(dead)
return
}
}
sm.currentValue = sm.currentValue*10 + toInt
sm.move(digit)
}Signing on the other hand requires a simple validation. We know from the question that Sign is only valid either at the beginning or after whitespace. Therefore, the logic only requires a check for 2 states.
func (sm *StateMachine) toSign(c byte) {
if sm.currentState != begininng && sm.currentState != whitespace {
sm.move(dead)
return
}
if c == '+' {
sm.sign = isPositive
} else {
sm.sign = isNegative
}
sm.move(signing)
}That brings us to the whitespace state. Ruleset defines the whitespace to only be valid when it’s at the beginning. But since whitespace can occur after another whitespace, we need to validate 2 states
func (sm *StateMachine) toWhitespace(c byte) {
if sm.currentState != begininng && sm.currentState != whitespace {
sm.move(dead)
return
}
sm.move(whitespace)
}Non-Digits are simple as well since they straightaway kill the process
func (sm *StateMachine) toNonDigit(c byte) {
sm.move(dead)
}And then, the last thing to do is to run the SM
...
for i := 0; i < len(s); i++ {
c := s[i]
if c == '+' || c == '-' {
sm.toSign(c)
} else if c == ' ' {
sm.toWhitespace(c)
} else if int(c) < 48 || int(c) > 57 {
sm.toNonDigit(c)
} else {
sm.toDigit(c)
}
if sm.currentState == dead {
break
}
}
...Why not just if/else?
Even though no one in the interview expects you to solve this question with this approach in the 10~15 min time provided, I couldn’t resist the urge to solve it with SM. And tbh, my solution is far from perfect, but I’m still proud of doing it this way in sub 12 minutes! But the advantage this approach has is if the interviewer asks you to add more complicated logic, it’s pretty simple to add a new state and add the logic.