Python – Code Golf: Finite-state machine!

code-golflanguage-agnosticpythonstate-machine

Finite state machine

A deterministic finite state machine is a simple computation model, widely used as an introduction to automata theory in basic CS courses. It is a simple model, equivalent to regular expression, which determines of a certain input string is Accepted or Rejected. Leaving some formalities aside, A run of a finite state machine is composed of:

alphabet, a set of characters.
states, usually visualized as circles. One of the states must be the start state. Some of the states might be accepting, usually visualized as double circles.
transitions, usually visualized as directed arches between states, are directed links between states associated with an alphabet letter.
input string, a list of alphabet characters.

A run on the machine begins at the starting state. Each letter of the input string is read; If there is a transition between the current state and another state which corresponds to the letter, the current state is changed to the new state. After the last letter was read, if the current state is an accepting state, the input string is accepted. If the last state was not an accepting state, or a letter had no corresponding arch from a state during the run, the input string is rejected.

Note: This short descruption is far from being a full, formal definition of a FSM; Wikipedia's fine article is a great introduction to the subject.

Example

For example, the following machine tells if a binary number, read from left to right, has an even number of 0s:

The alphabet is the set {0,1}.
The states are S1 and S2.
The transitions are (S1, 0) -> S2, (S1, 1) -> S1, (S2, 0) -> S1 and (S2, 1) -> S2.
The input string is any binary number, including an empty string.

The rules:

Implement a FSM in a language of your choice.

Input

The FSM should accept the following input:

<States>       List of state, separated by space mark.
               The first state in the list is the start state.
               Accepting states begin with a capital letter.
<transitions>  One or more lines. 
               Each line is a three-tuple:
               origin state, letter, destination state)
<input word>   Zero or more characters, followed by a newline.

For example, the aforementioned machine with 1001010 as an input string, would be written as:

S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2
1001010

Output

The FSM's run, written as <State> <letter> -> <state>, followed by the final state. The output for the example input would be:

S1 1 -> S1
S1 0 -> s2
s2 0 -> S1
S1 1 -> S1
S1 0 -> s2
s2 1 -> s2
s2 0 -> S1
ACCEPT

For the empty input '':

S1
ACCEPT

Note: Following your comments, the S1 line (showing the first state) might be omitted, and the following output is also acceptable:

ACCEPT

For 101:

S1 1 -> S1
S1 0 -> s2
s2 1 -> s2
REJECT

For '10X':

S1 1 -> S1
S1 0 -> s2
s2 X
REJECT

Prize

A 250 rep bounty will be given to the shortest solution.

Reference implementation

A reference Python implementation is available here. Note that output requirements have been relaxed for empty-string input.

Addendum

Output format

Following popular demand, the following output is also acceptable for empty input string:

ACCEPT

REJECT

Without the first state written in the previous line.

State names

Valid state names are an English letter followed by any number of letters, _ and digits, much like variable names, e.g. State1, state0, STATE_0.

Input format

Like most code golfs, you can assume your input is correct.

Summary of answers:

Cobol – 4078 characters
Python – 171 characters, 568 characters, 203 characters, 218 characters, 269 characters
sed – 137 characters
ruby – 145 characters, 183 characters
Haskell – 192 characters, 189 characters
LISP – 725 characters
Perl – 184 characters
Bash – 184 characters
Rexx – 205 characters
Lua – 356 characters
F# – 420 characters
C# – 356 characters
Mixal – 898 characters

The sed 137 solution is the shortest, ruby 145 is #2. Currently, I can't get the sed solution to work:

cat test.fsm | sed -r solution.sed
sed -r solution.sed test.fsm

both gave me:

sed: -e expression #1, char 12: unterminated `s' command

so unless It there are clarifications the bounty goes to the ruby solution.

Best Answer

Python 2.7+, 201 192 187 181 179 175 171 chars

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

GolfScript - 181 characters

Newlines are not necessary. Output is in standard output, although some errors are present in stderr.
\10 should be replaced by the corresponding ASCII character for the program to be 181 characters.

{):X!-{2B{" #"=}%X" ":f*+-1%}%:P;:>.{\!:F;>P{\(@{3&\(@.2$&F|:F;|}%\+}%\+F![f]P+:P
;}do;{"= "&},.,7^.R+:R;[>0="#"/f*]*\+}0"R@1(XBc_""~\10"{base}:B/3/~4*"nIOZTLSJR "
";:"*~;n%)n*~ 10R*+n*

Sample I/O:

$ cat inp
[          ]
[          ]
[          ]
[          ]
[ #    #  #]
[ ## ######]
[==========]
T2 Z6 I0 T7
$ cat inp|golfscript tetris.gs 2>/dev/null
[          ]
[          ]
[          ]
[#      ###]
[#     ### ]
[##### ####]
[==========]
10

Tetromino compression:
Pieces are stored as three base 8 digits. This is a simple binary representation, e.g.T=[7,2,0], S=[6,3,0], J=[2,2,3]. [1] is used for the I piece in compression, but this is explicitly set to [1,1,1,1] later (i.e. the 4* in the code). All of these arrays are concatenated into a single array, which is converted into an integer, and then a string (base 126 to minimize non-printable characters, length, and not encounter utf8). This string is very short: "R@1(XBc_".

Decompression is then straightforward. We first do a base 126 conversion followed by a base 8 conversion ("~\10"{base}/, i.e. iterate through "~\10" and do a base conversion for each element). The resulting array is split into groups of 3, the array for I is fixed (3/~4*). We then convert each element to base 2 and (after removing zeros) replace each binary digit with the character of that index in the string " #" (2base{" #"=}%...-1% - note that we need to reverse the array otherwise 2 would become "# " instead of " #").

Board/piece format, dropping pieces
The board is simply an array of strings, one for each line. No work is initially done on this, so we can generate it with n/( on the input. Pieces are also arrays of strings, padded with spaces to the left for their X position, but without trailing spaces. Pieces are dropped by prepending to the array, and continuously testing whether there is a collision.

Collision testing is done by iterating through all characters in the piece, and comparing against the character of the same position on the board. We want to regard #+= and #+# as collisions, so we test whether ((piecechar&3)&boardchar) is nonzero. While doing this iteration, we also update (a copy of) the board with ((piecechar&3)|boardchar), which correctly sets the value for pairs #+, +#, +[. We use this updated board if there is a collision after moving the piece down another row.

Removing filled rows is quite simple. We remove all rows for which "= "& return false. A filled row will have neither = or , so the conjunction will be a blank string, which equates to false. Then we count the number of rows that have been removed, add the count to the score and prepend that many "[ ... ]"s. We generate this compactly by taking the first row of the grid and replacing # with .

Bonus
Since we compute what the board would look like in each position of the piece as it falls, we can keep these on the stack instead of deleting them! For a total of three characters more, we can output all these positions (or two characters if we have the board states single spaced).

{):X!-{2B{" #"=}%X" ":f*+-1%}%:P;:>.{>[f]P+:P(!:F;{\(@{3&\(@.2$&F|:F;|}%\+}%\+F!}
do;{"= "&},.,7^.R+:R;[>0="#"/f*]*\+}0"R@1(XBc_""~\10"{base}:B/3/~4*"nIOZTLSJR "
";:"*~;n%)n*~ ]{n*n.}/10R*