代码高尔夫：有限状态机！

Question

有限状态机

确定性有限状态机（deterministicfinitestatemachine）是一种简单的计算模型，在计算机科学基础课程中被广泛用作自动机理论的入门课程。它是一个简单的模型，相当于正则表达式，它确定某个输入字符串是接受还是拒绝。Leaving some formalities aside，有限状态机的运行由以下部分组成：

1. 字母表，一组字符。
2. 状态，通常显示为圆形。其中一个状态必须是开始状态。有些状态可能是接受的，通常被视为双圆圈。
3. 转换通常被视为状态之间的有向拱，是与字母表字母相关的状态之间的有向链接。
4. 输入字符串，一个包含字母字符的列表。

机器上的运行从启动状态开始。读取输入字符串的每个字母；如果当前状态与对应于该字母的另一个状态之间存在转换，则当前状态将更改为新状态。读取最后一个字母后，如果当前状态是接受状态，则接受输入字符串。如果最后一个状态不是接受状态，或者某个字母在运行期间没有来自某个状态的对应拱门，则拒绝输入字符串。

注意：这个简短的描述远不是FSM的完整、正式的定义；Wikipedia's fine article是对这个主题的一个很好的介绍。

示例

例如，下面的机器告诉从左到右读取的二进制数是否具有偶数0s：

1. 字母表是集合{0,1}。
2. 状态是S1和S2。
3. 跃迁是(S1, 0) -> S2、(S1, 1) -> S1、(S2, 0) -> S1和(S2, 1) -> S2。
4. 输入字符串是任何二进制数，包括空字符串。

规则：

用您选择的语言实现FSM。

输入

FSM应接受以下输入：

<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.

例如，前面提到的以1001010作为输入字符串的机器将被写为：

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

输出

FSM的运行，写为<State> <letter> -> <state>，然后是最终状态。示例输入的输出为：

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

对于空输入''：

S1
ACCEPT

注意：在您的注释之后，可以省略S1行（显示第一个状态），并且还可以接受以下输出：

ACCEPT

对于101：

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

对于'10X'：

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

奖品

250人的奖金将给予最短的解决方案。

参考实施

有一个参考Python实现here。注意，对空字符串输入的输出要求已经放宽。

附录

输出格式

根据流行的需求，空输入字符串也可以接受以下输出：

ACCEPT

或者

REJECT

没有写在前一行的第一个状态。

州名

有效的状态名是英文字母后跟任意数量的字母，_和数字，非常像变量名，例如State1，state0，STATE_0。

输入格式

像大多数代码专家一样，您可以假设您的输入是正确的。

答案摘要：

• Cobol-4078 characters
• Python-171 characters，568 characters，203 characters，218 characters，269 characters
• sed-137 characters
• 红宝石-145 characters，183 characters
• 哈斯克尔-192 characters，189 characters
• LISP-725 characters
• Perl-184 characters
• 重击-184 characters
• 雷克斯-205 characters
• 卢阿-356 characters
• F#-420 characters
• C#-356 characters
• Mixal-898 characters

^{} 137 solution是最短的，ruby 145是#2。目前，我无法使用sed解决方案：

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

都给了我：

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

所以算了吧如果有澄清的话，赏金会流向ruby解决方案。

Answer 1

Python2.7+，201 192 187 181 179 175171个字符

问题解决后（不需要在空输入上输出状态行），这里有一个新代码，它明显更短。如果您使用的是<；2.7版本，则不存在对dict的理解，因此请尝试{c+o:s for o,c,s in i[1:-1]}而不是dict((c+o,s)for o,c,s in i[1:-1])以+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]

其测试输出：

# 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

---

上一条目（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]

在有人责骂我之前，我要道歉：代码行为与最初的按问题说明注释讨论略有不同。这是我的说明供讨论。

注意：虽然我喜欢最终状态的同一行上的ACCEPT/REJECT解析，但它可以通过在最后一行上添加'\n'+（5个字符）以+5个字符的价格移动到单独的位置（例如，想象结果将由只关心最后一行是ACCEPT还是REJECT的愚蠢脚本解析）。

示例输出：

# 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

Answer 2

红宝石1.9.2-178 190 182 177 153 161 158 154145个字符

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

输出

所有输入以：

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

Answer 3

今天我感觉很复古，我选择的语言是IBM Enterprise Cobol-char count24624078（抱歉，从面向屏幕的设备粘贴，尾随空格是一个悲惨的副作用）：

 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.