Kata(題目)

輸入: String format binary number

輸出: Boolean

// Examples (Javascript)
multipleof3Regex.test('000') // should be true
multipleof3Regex.test('001') // should be false
multipleof3Regex.test('011') // should be true
multipleof3Regex.test('110') // should be true
multipleof3Regex.test(' abc ') // should be false

建立有限狀態機(FSM)

設s0, s1, s2三個狀態表示mod3 為0, 1, 2

binary字串中只會有1和／或0

如果在數值x的binary後面增加一個數位0，等同乘2，變成2x

如果新增數位1，等同乘2加1，變成2x+1，

表示從左到右逐個數位看，如果當前…

在狀態s0時

看到0，保持狀態s0

看到1，更新至狀態s1

在狀態s1時

看到0，更新至狀態s2

看到1，更新至狀態s0

在狀態s2時

看到0，更新至狀態s1

看到1，保持狀態s2

fsm visualization powered by ivanzuzak.info

#states
s0
s1
s2
#initial
s0
#accepting
s0
#alphabet
0
1
#transitions
s0:0>s0
s0:1>s1
s1:0>s2
s1:1>s0
s2:0>s1
s2:1>s2

起始狀態為s0，如果最終狀態回到s0就是3的倍數

例如12的binary是1100

從左到右的狀態變化為

s0s1s0s0s0，最終是s0所以是3的倍數

14的binary是1110，狀態變化為

s0s1s0s1s2，最終是s2，所以mod3為2

翻譯成regex就是

let multipleof3Regex = /^0{0,}(1(01{0,}0|11){0,}10{0,}){0,}$/

Reference

FSM & Regex