Menu
A system where particular inputs cause particular changes in state can be represented using finite state machines. This example describes the various states of a turnstile. Inserting a coin into a turnstile will unlock it, and after the turnstile has been pushed, it locks again.
PS. After the problem was relaxed (no need to output state line on empty input), here is new code that's notably shorter. If you are on version <2.7, there is no dict comprehension, so instead of {c+o:s for o,c,s in i[1:-1]} try dict((c+o,s)for o,c,s in i[1:-1]) for the price of +5.
import sys
i=map(str.split,sys.stdin)
s=i[0][0]
for c in''.join(i[-1]):
if s:o=s;s={c+o:s for o,c,s in i[1:-1]}.get(c+s,());print o,c,'->',s
print'ARCECJEEPCTT'[s>'Z'::2]
And its test output:
# for empty input
ACCEPT
# for input '1001010'
S1 1 -> S1
S1 0 -> s2
s2 0 -> S1
S1 1 -> S1
S1 0 -> s2
s2 1 -> s2
s2 0 -> S1
ACCEPT
# for input '101'
S1 1 -> S1
S1 0 -> s2
s2 1 -> s2
REJECT
# for input '10X'
S1 1 -> S1
S1 0 -> s2
s2 X -> ()
REJECT
# for input 'X10'
S1 X -> ()
REJECT
Previous entry (len 201):
import sys
i=list(sys.stdin)
s=i[0].split()[0]
t={}
for r in i[1:-1]:a,b,c=r.split();t[a,b]=c
try:
for c in i[-1]:print s,c.strip(),;s=t[s,c];print' ->',s
except:print('ACCEPT','REJECT')[s>'Z'or' '<c]
I want to apologize before someone slaps me for it: the code behavior is slightly different from the original spec - per question-comments discussion. This is my illustration for the discussion.
PS. while i like the resolution ACCEPT/REJECT on the same line with the final state, it can me moved to solitude (e.g. imagine results are to be parsed by stupid script that only cares about last line being accept or reject) by adding '\n'+ (5 chars) to the last print for the price of +5 chars.
Example output:
# for empty input
S1 ACCEPT
# for input '1001010'
S1 1 -> S1
S1 0 -> s2
s2 0 -> S1
S1 1 -> S1
S1 0 -> s2
s2 1 -> s2
s2 0 -> S1
S1 ACCEPT
# for input '101'
S1 1 -> S1
S1 0 -> s2
s2 1 -> s2
s2 REJECT
# for input '10X'
S1 1 -> S1
S1 0 -> s2
s2 X REJECT
# for input 'X10'
S1 X REJECT
I'm feeling retro today, my language of choice for this task is IBM Enterprise Cobol - char count 2462 4078 (Sorry, pasted from a screen oriented device, trailing spaces are a tragic side effect):
Identification Division.
Program-ID. FSM.
Environment Division.
Data Division.
Working-Storage Section.
01 FSM-Storage.
*> The current state
05 Start-State Pic X(2).
05 Next-State Pic X(2).
*> List of valid states
05 FSM-State-Cnt Pic 9.
05 FSM-States Occurs 9
Pic X(2).
*> List of valid transitions
05 FSM-Trans-Cnt Pic 999.
05 FSM-Trans Occurs 999.
10 Trans-Start Pic X(2).
10 Trans-Char Pic X.
10 Trans-End Pic X(2).
*> Input
05 In-Buff Pic X(72).
*> Some work fields
05 II Pic s9(8) binary.
05 JJ Pic s9(8) binary.
05 Wk-Start Pic X(2).
05 Wk-Char Pic X.
05 Wk-End Pic X(2).
05 Wk-Cnt Pic 999.
05 Pic X value ' '.
88 Valid-Input value 'V'.
05 Pic X value ' '.
88 Valid-State value 'V'.
05 Pic X value ' '.
88 End-Of-States value 'E'.
05 Pic X value ' '.
88 Trans-Not-Found value ' '.
88 Trans-Found value 'T'.
Linkage Section.
01 The-Char-Area.
05 The-Char Pic X.
88 End-Of-Input value x'13'.
05 The-Next-Char Pic X.
Procedure Division.
Perform Load-States
Perform Load-Transitions
Perform Load-Input
Perform Process-Input
Goback.
*> Run the machine...
Process-Input.
Move FSM-States (1) to Start-State
Set address of The-Char-Area to address of In-Buff
Perform until End-Of-Input
Perform Get-Next-State
Set address of The-Char-Area to address of The-Next-Char
Move Next-State to Start-State
End-Perform
If Start-State (1:1) is Alphabetic-Lower
Display 'REJECT'
Else
Display 'ACCEPT'
End-If
Exit.
*> Look up the first valid transition...
Get-Next-State.
Set Trans-Not-Found to true
Perform varying II from 1 by 1
until (II > FSM-State-Cnt)
or Trans-Found
If Start-State = Trans-Start (II)
and The-Char = Trans-Char (II)
Move Trans-End (II) to Next-State
Set Trans-Found to true
End-If
End-Perform
Display Start-State ' ' The-Char ' -> ' Next-State
Exit.
*> Read the states in...
Load-States.
Move low-values to In-Buff
Accept In-Buff from SYSIN
Move 0 to FSM-State-Cnt
Unstring In-Buff
delimited by ' '
into FSM-States (1) FSM-States (2) FSM-States (3)
FSM-States (4) FSM-States (5) FSM-States (6)
FSM-States (7) FSM-States (8) FSM-States (9)
count in FSM-State-Cnt
End-Unstring
Exit.
*> Read the transitions in...
Load-Transitions.
Move low-values to In-Buff
Accept In-Buff from SYSIN
Perform varying II from 1 by 1
until End-Of-States
Move 0 to Wk-Cnt
Unstring In-Buff
delimited by ' '
into Wk-Start Wk-Char Wk-End
count in Wk-Cnt
End-Unstring
If Wk-Cnt = 3
Add 1 to FSM-Trans-Cnt
Move Wk-Start to Trans-Start (FSM-Trans-Cnt)
Move Wk-Char to Trans-Char (FSM-Trans-Cnt)
Move Wk-End to Trans-End (FSM-Trans-Cnt)
Move low-values to In-Buff
Accept In-Buff from SYSIN
Else
Set End-Of-States to true
End-If
End-Perform
Exit.
*> Fix input so it has newlines...the joys of mainframes
Load-Input.
Perform varying II from length of In-Buff by -1
until Valid-Input
If In-Buff (II:1) = ' ' or In-Buff (II:1) = low-values
Move x'13' to In-Buff (II:1)
Else
Set Valid-Input to true
End-If
End-Perform
Exit.
End Program FSM.
This is using the -r flag (+3), for a total of 134+3=137 characters.
$!{H;D}
/:/!{G;s/(\S*)..(\S*)/\2 \1:/}
s/(.* .)(.*\n\1 (\S*))/\1 -> \3\n\3 \2/
/-/{P;D}
/^[A-Z].* :/cACCEPT
s/( .).*/\1/
/:/!P
cREJECT
This should handle inputs without transitions correctly... hopefully it fully complies with the spec now...
h={}
o=s=p
$<.map{|l|o,b,c=l.split;h[[o,b]]=c;s||=o}
o.chars{|c|puts s+' '+c+((s=h[[s,c]])?' -> '+s :'')}rescue 0
puts s&&s<'['?:ACCEPT: :REJECT
[
"S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2
1001010",
"S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2
101",
"S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2
",
"S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2
10X"
].each do |b|
puts "------"
puts "Input:"
puts b
puts
puts "Output:"
puts `echo "#{b}" | ruby fsm-golf.rb`
puts "------"
end
All input starts with:
S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2
Input: '1001010'
Output:
S1 1 -> S1
S1 0 -> s2
s2 0 -> S1
S1 1 -> S1
S1 0 -> s2
s2 1 -> s2
s2 0 -> S1
ACCEPT
Input: '101'
Output:
S1 1 -> S1
S1 0 -> s2
s2 1 -> s2
REJECT
Input: 'X10'
Output:
S1 X
REJECT
Input: ''
Output:
ACCEPT
Input: '10X'
Output:
S1 1 -> S1
S1 0 -> s2
s2 X
REJECT
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With