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

有限状态机

确定性有限状态机是一种简单的计算模型，在基础CS课程中被广泛用作自动机理论的介绍。 它是一个简单的模型，相当于正则expression式，它决定了某个inputstring是Accepted还是Rejected 。 抛开一些手续 ，一个有限状态机的运行包括：

1. 字母表 ，一组字符。
2. 状态 ，通常可视化为圆形。 其中一个州必须是开始状态 。 一些州可能会接受 ，通常可视化为双圈。
3. 过渡 ，通常可视化为国家之间的定向拱，指向与字母表相关联的状态之间的链接。
4. inputstring ， 字母字符列表。

机器上的运行从起始状态开始。 inputstring的每个字母都被读取; 如果在当前状态和对应于该字母的另一个状态之间存在转换，则当前状态改变为新状态。 读完最后一个字母后，如果当前状态为接受状态，则接受inputstring。 如果最后一个状态不是接受状态，或者一个字母在运行过程中没有相应的状态，则inputstring将被拒绝。

注：这个短暂的破坏远非FSM的全面正式定义; 维基百科的精美文章是对这个主题的一个很好的介绍。

例

例如，下面的机器会告诉从二进制数字中，从左到右读取的偶数是否为0 ：

1. 字母表是集{0,1} 。
2. 状态是S1和S2。
3. (S1, 0) -> S2 ， (S1, 1) -> S1 ， (S2, 0) -> S1 ， (S2, 1) -> S2 。
4. inputstring是任何二进制数字，包括一个空string。

规则：

以您select的语言实施FSM。

input

FSM应接受以下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. 

例如，前面提到的将1001010作为inputstring的机器将被写为：

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

产量

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

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

对于空input'' ：

 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 

奖

最短的解决scheme将获得250分的奖金。

参考实现

这里有一个参考Python实现。 请注意，对于空stringinput，输出要求已放宽。

附录

输出格式

按照常见的要求，空inputstring也可以接受以下输出：

 ACCEPT 

要么

 REJECT 

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

州名

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

input格式

像大多数高尔夫代码一样，您可以假设您的input是正确的。

答案摘要：

• Cobol – 4078个字符
• Python – 171个字符 ， 568个字符 ， 203个字符 ， 218个字符 ， 269个字符
• sed – 137个字符
• ruby – 145个字符 ， 183个字符
• Haskell – 192个字符 ， 189个字符
• LISP – 725个字符
• Perl – 184个字符
• Bash – 184个字符
• Rexx – 205个字符
• Lua – 356个字符
• F＃ – 420个字符
• C＃ – 356个字符
• 混合 – 898个字符

sed 137解决scheme是最短的， ruby145是＃2。 目前，我无法使sed解决scheme工作：

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

都给了我：

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

所以除非有澄清的奖金去ruby解决scheme。

Answer 1

ruby1.9.2 – 178 190 182 177 153 161 158 154 145个字符

 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 

testing脚本

 [ "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 

输出

所有input始于：

 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 2

Python 2.7+， 201 192 187 181 179 175 171个字符

PS。 问题放松之后（不需要在空input上输出状态行），这里是新代码显着缩短。 如果你的版本小于2.7，那么就没有词典理解 ，所以不要用{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] 

其testing结果如下：

 # 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] 

我想道歉之前有人给我一个这样的： 代码行为是有点不同于原来的规范，每个问题的意见讨论。 这是我的讨论插图。

PS。 虽然我喜欢与最终状态相同的分辨率ACCEPT / REJECT，但是我可以将其移动到独处（例如，想象结果将由愚蠢的脚本parsing，只关心最后一行被接受或拒绝）添加'\n'+ （5个字符）到+5个字符的价格的最后一个print 。

示例输出：

 # 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 3

我今天感觉复古了，我select这个任务的语言是IBM Enterprise Cobol – char count 2462 4078（对不起，从面向屏幕的设备粘贴，拖尾空间是一个不幸的副作用）：

  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. 

Answer 4

sed – 118 137个字符

这是使用-r标志（+3），总共134 + 3 = 137个字符。

 $!{H;D} /:/!{G;s/(\S*)..(\S*)/\2 \1:/} s/(.* .)(.*\n\1 (\S*))/\1 -> \3\n\3 \2/ /-/{P;D} /^[AZ].* :/cACCEPT s/( .).*/\1/ /:/!P cREJECT 

这应该处理投入没有过渡正确…希望它完全符合规范现在…

Answer 5

亚当提供了一个参考实现。 我没有看到它，但我的逻辑是类似的：

编辑：这是Python 2.6的代码。 我没有尽量减less长度; 我只是试图使它在概念上简单。

 import sys a = sys.stdin.read().split('\n') states = a[0].split() transitions = a[1:-2] input = a[-2] statelist = {} for state in states: statelist[state] = {} for start, char, end in [x.split() for x in transitions]: statelist[start][char] = end state = states[0] for char in input: if char not in statelist[state]: print state,char print "REJECT" exit() newstate = statelist[state][char] print state, char, '->', newstate state = newstate if state[0].upper() == state[0]: print "ACCEPT" else: print "REJECT" 

Answer 6

Python，218个字符

 import sys T=sys.stdin.read() P=T.split() S=P[0] n="\n" for L in P[-1]if T[-2]!=n else"": i=T.find(n+S+" "+L) if i<0:print S,L;S=n;break S=T[i:].split()[2];print S,L,"->",S print ("REJECT","ACCEPT")[S[0].isupper()] 

Answer 7

Haskell – 252 216 204 197 192个字符

 s%(c:d,t)=s++' ':c:maybe('\n':x)(\[u]->" -> "++u++'\n':u%(d,t))(lookup[s,[c]]t) s%_|s<"["="ACCEPT\n"|1<3=x x="REJECT\n" p(i:j)=(words i!!0)%(last j,map(splitAt 2.words)j) main=interact$p.lines 

符合输出规格。

Ungolf'd版本：

 type State = String type Transition = ((State, Char), State) run :: [Transition] -> State -> String -> [String] run ts s (c:cs) = maybe notFound found $ lookup (s,c) ts where notFound = stateText : ["REJECT"] found u = (stateText ++ " -> " ++ u) : run ts u cs stateText = s ++ " " ++ [c] run _ (s:_) "" | s >= 'A' && s <= 'Z' = ["ACCEPT"] | otherwise = ["REJECT"] prepAndRun :: [String] -> [String] prepAndRun (l0:ls) = run ts s0 input where s0 = head $ words l0 input = last ls ts = map (makeEntry . words) $ init ls makeEntry [s,(c:_),t] = ((s,c),t) main' = interact $ unlines . prepAndRun . lines 

一个很好的谜题是为什么在高尔夫版本中不需要init ！ 除此之外，rest都是标准的哈斯克尔高尔夫技巧。

Answer 8

Perl – 184个字符

（Count不包括所有可选的换行符。）

 ($s)=split' ',<>;$\=$/; while(<>){chomp;$r{$_[1].$_[0]}=$_[2]if split>2;$t=$_} $_=$t; 1 while$s&&s/(.)(.*)/print"$s $1",($s=$r{$1.$s})?" -> $s":"";$2/e; print$s=~/^[AZ]/?"ACCEPT":"REJECT" 

---

而且，这个155个字符的程序并没有实现中间输出，而是在整个FSM定义（改变开始状态和inputstring）上重复replace整个机器。 它受到了sed解决scheme的启发，但不是源于此。 通过将(?:...)转换为(...)并根据需要重新编号，可缩短2个字符。

 $/="";$_=<>; 1 while s/\A(\S+)(?: +\S+)*\n(.*\n)?\1 +(.) +(.+)\n(.*\n)?\3([^\n]*)\n\z/$4\n$2$1 $3 $4\n$5$6\n/s; print/\A[AZ].*\n\n\z/s?"ACCEPT\n":"REJECT\n" 

Answer 9

Python 3，Chars：203

输出格式似乎有点难以适应。

 import sys L=[i.split()for i in sys.stdin] N,P=L[0][0],print for c in L[-1]and L[-1][-1]: if N:O,N=N,{(i[0],i[1]):i[2]for i in L[1:-1]}.get((N,c),'');P(O,c,N and'-> '+N) P(('REJECT','ACCEPT')[''<N<'_']) 

Answer 10

MIXAL 898个字符

  ORIG 3910 A ALF ACCEP ALF T ORIG 3940 R ALF REJEC ALF T ORIG 3970 O CON 0 ALF -> ORIG 3000 S ENT6 0 T IN 0,6(19) INC6 14 JBUS *(19) LDA -14,6 JANZ T LDA -28,6(9) DECA 30 JAZ C DECA 1 JANZ B C LD2 0(10) ENT4 -28,6 ENT5 9 D JMP G ENT3 0 F INC3 14 LD1 0,3(10) DEC2 0,1 J2Z M INC2 0,1 DEC3 -28,6 J3NN U INC3 -28,6 JMP F M INC2 0,1 LD1 0,3(36) DECA 0,1 JAZ H INCA 0,1 JMP F H INCA 0,1 ST2 O(10) LD2 1,3(10) STA O(36) ST2 O+1(37) OUT O(18) JBUS *(18) JMP D HLT E LD1 0(10) DEC1 0,2 J1Z B U OUT R(18) JBUS *(18) HLT B OUT A(18) JBUS *(18) HLT G STJ K ST5 *+1(36) LDA 0,4 JAZ E DECA 30 JAZ I DECA 1 JANZ W INCA 1 I INCA 30 DEC5 45 J5NN J INC5 54 JMP K J INC4 1 ENT5 9 K JMP * W ST2 O(10) INCA 31 STA O(36) STZ O+1 OUT O(18) JBUS *(18) JMP B END S 

Deify Knuth！

Answer 11

哈斯克尔 – 189个字符

 main=interact$r.lines rf=gtz$last f where{(z:_):t=map words f;g _ s""|s<"["="ACCEPT\n";g([q,j,p]:_)s(i:k)|i:s==j++q=s++' ':i:" -> "++p++'\n':gtpk;g(_:y)si=gysi;g _ _ _="REJECT\n"} 

编辑：不正确实现无过渡拒绝的输出。

破线版本和variables指南：

 -- r: run FSM -- f: fsm definition as lines -- z: initial state -- g: loop function -- t: transition table -- s: current state -- i: current input -- k: rest of input -- q: transition table match state -- j: transition table match input -- p: transition table next state -- y: tail of transition table main=interact$r.lines; rf=gtz$last f where{ (z:_):t=map words f; g _ s""|s<"["="ACCEPT\n"; g([q,j,p]:_)s(i:k)|i:s==j++q=s++' ':i:" -> "++p++'\n':gtpk; g(_:y)si=gysi; g _ _ _="REJECT\n"} 

我从MtnViewMark的解决scheme中得到了这个技术。 其余的是我自己的devise。 显着的特点：

• input在转换表中保留为垃圾。 只要input不包含两个空格就可以了; 但要注意的是，转换规则的格式无论如何也是不太可能转换空间特征的。
• 逐步浏览inputstring并search转换表是相同的function。
• 这两个REJECT案件都由相同的延期处理。

Answer 12

Common Lisp – 725

 (defun split (string) (loop for i = 0 then (1+ j) as j = (position #\Space string :start i) collect (subseq string ij) while j)) (defun do-fsm () (let* ((lines (loop for l = (read-line *standard-input* nil) until (not l) collect (split l))) (cur (caar lines)) (transitions (subseq lines 1 (- (length lines) 1)))) (if (or (loop for c across (caar (last lines)) do (format t "~a ~a" cur c) when (not (loop for tr in transitions when (and (equal cur (car tr)) (equal c (char (cadr tr) 0))) return (progn (format t " -> ~a~%" (setq cur (caddr tr))) t) )) return t) (lower-case-p (char cur 0))) (format t "~%REJECT~%") (format t "ACCEPT~%")))) 

没有真正的尝试最小化代码 – Common Lisp在所需的input处理中付出了沉重的代价，所以我不认为这个解决scheme有很大的可能性:-)

Answer 13

ruby – 183

 h={} r=$<.read t=s=r.split[0] i=r[-1]==" "?"":r.split[-1] r.scan(/(\S+) (.) (.+)/){|a,b,c|h[[a,b]]=c} i.chars{|c|puts s+" #{c} -> #{s=h[[s,c]]}"} puts s&&s[/^[AZ]/]?"ACCEPT":"REJECT" 

真的，奇怪的输出规范。 这里是我的作品： http ： //ideone.com/cxweL

Answer 14

Rexx 205个字符

（这个答案经过了很less的编辑，因为我最初只是发布一些代码为一般的兴趣，然后决定实际上发布一个真正的解决scheme）

这是一个Rexx版本，让人们可以品尝到那些鲜为人知的蓝莓。 Rexx http://en.wikipedia.org/wiki/REXX是在IBM的VM / CMS大型机操作系统中使用的一种解释语言，后来在IBM OS / 2中（我相信有一个Amiga变体）。 这是一个非常有performance力的语言和一个惊人的通用/“脚本”语言。

 Parse pull i . d.='~' Do until l='';Parse pull ol dol;End Do j=1 to LENGTH(o) t=SUBSTR(o,j,1);p=it;i=dit If i=d. then Do;Say p;Leave;End Say p '->' i End Say WORD('ACCEPT REJECT',c2d(left(i,1))%32-1) 

这可以与Regina Rexx解释器一起运行。

使用其独特的输出处理不正确的转换场景并testing大写字体有点贵。

以下的一些较老的编辑代码，对于那些对Rexx语法感兴趣的人来说，那些不是100％符合输出要求，而是function性的（这个答案中的所有代码都适用于我粘贴的样本，但上面的代码处理了其他所需的angular落）：

较旧的短版本：

 Parse pull i . Do until l = ""; Parse pull old; tol = d; End Do j=1 to LENGTH(o); t=substr(o,j,1); Say it "->" tit; i=tit; End If LEFT(i,1)='S' then Say 'ACCEPT'; else say 'REJECT' 

更长的版本：

 Parse pull initial . /* Rexx has a powerful built in string parser, this takes the first word into initial */ Do until letter = "" /* This style of do loops is a bit unusual, note how it doesn't matter that letter isn't defined yet */ Parse pull origin letter destination /* Here we parse the inpt line into three words */ transition.origin.letter = destination /* Rexx has a very powerful notion of associative containers/dictionaries, many years pre-Python */ End /* Now we take the last line and iterate over the transitions */ Do i = 1 to LENGTH(origin) t = substr(origin, i, 1) /* This is the actual letter using Rexx's string functions */ Say initial t "->" transition.initial.t /* Say is like print */ initial = transition.initial.t /* Perform the transition */ End /* check for uppercase in the current state */ if left(initial, 1) = 'S' then Say 'ACCEPT'; else say 'REJECT' 

样品进/出：

 S1 s2 S1 0 s2 0 S1 0 -> s2 REJECT S1 s2 S1 0 s2 S1 1 S1 s2 0 S1 s2 1 s2 1001010 S1 1 -> S1 S1 0 -> s2 s2 0 -> S1 S1 1 -> S1 S1 0 -> s2 s2 1 -> s2 s2 0 -> S1 ACCEPT 

Answer 15

Lua，356

对于状态使用任何非空格字符，对于过渡字母使用任何非空格的一个字符。 虽然看起来不是最短的，但我会以任何方式发布。 可以保存25个字符的打印标签，而不是空格。

可读版本：

 i=io.read p=print S={} i():gsub("(%S+)",function (a) f=f or a S[a]={} end ) l=i"*a" for a,t,d in l:gmatch"(%S+) (%S) (%S+)"do S[a][t]=d end I=l:match"(%S+)%s$"or"" -- fixes empty input function F(a,i) t=I:sub(i,i) if t==""then p"ACCEPT" elseif S[a][t] then p(("%s %s -> %s"):format(a,t, S[a][t])) return F( S[a][t],i+1) else if t~=""then p(a.." "..t)end p'REJECT' end end F(f,1) 

高尔夫版本+输出。

 i=io.read p=print S={}i():gsub('(%S+)',function(a)f=f or a S[a]={}end)l=i'*a'for a,t,d in l:gmatch"(%S+) (%S) (%S+)"do S[a][t]=d end I=l:match'(%S+)%s$'or''function F(a,i)t=I:sub(i,i)if t==""and a:match'^%u'then p'ACCEPT'elseif S[a][t]then p(('%s %s -> %s'):format(a,t,S[a][t]))return F(S[a][t],i+1)else if t~=''then p(a.." "..t)end p'REJECT'end end F(f,1) -- input -- ABCABB ACC AAA BAABBB BCC CAACBB CCC AABCCBCBAX -- output -- AA -> A AA -> A AB -> B BC -> C CC -> C CB -> B BC -> C CB -> B BA -> A REJECT 

Answer 16

bash – 186 185 184个字符

 宣布 - 一个
读sx
同时阅读fm t && [$ m];做一个[$ f $ m] = $ t;完成
 for（（i = 0; i  -  $ {＃f}; i ++））do b =“$ s $ {f：i：1}”; s = $ {a [$ b]}; echo $ b  -  \ > $ s;完成
 [“$ s”=“$ {s，}”] && echo REJECT || echo ACCEPT 

请注意，这实际上需要bash – POSIX sh没有关联数组或C语法的语法（可能并没有使用所有的参数扩展，但我没有检查）。

编辑：或者，对于完全相同的长度，

 宣布 - 一个
读sx
同时阅读fm t && [$ m];做一个[$ f $ m] = $ t;完成
 while [$ f]; do b =“$ s $ {f：i：1}”; f = $ {f：1}; s = $ {a [$ b]}; echo $ b  -  \> $ s ;完成
 [“$ s”=“$ {s，}”] && echo REJECT || echo ACCEPT 

Answer 17

Python（2.6）〜269个字符。

可能还有改进的空间，提示欢迎。 我认为处理规格。

 import sys;a=sys.stdin.readlines();b=a[0].split() f=b[0];d=dict((x,{})for x in b);s='' for x,y,z in map(str.split,a[1:-1]):d[x][y]=z for g in a[-1]: try:s+=f+' '+g;f=d[f][g];s+=' -> '+f+'\n' except:s+='\n';break print s+("REJECT","ACCEPT")[ord(f[0])<90 and g in d[f]] 

Answer 18

Lua – 248 227

 r=... p=print M={} s=r:match('(%a%d)') for i,n,o in r:gmatch('(%a%d)%s(%d)%s(%a%d)')do M[i]=M[i]or{} M[i][n]=o end for c in r:match('%d%d+'):gmatch('(%d)')do z=s s=M[z][c] p(z,c,'->',s) end p(s==s:upper()and'ACCEPT'or'REJECT') 

检查键盘 旧版本上的运行版本

Answer 19

F＃420

对于不可改变的高尔夫不错，我想。 虽然我今天的课程做得不是很好。

 open System let f,p,a=Array.fold,printf,Map.add let l=Console.In.ReadToEnd().Split '\n' let e,s=l.Length,l.[0].Split ' ' let t,w=Map.ofList[for q in s->q,Map.empty],[|"ACCEPT";"REJECT"|] let m=f(fun t (r:String)->let s=r.Split ' 'in a s.[0](t.[s.[0]]|>a s.[1].[0]s.[2])t)t l.[1..e-2] try let r=l.[e-1].ToCharArray()|>f(fun s c->p"%s %c "sc;let n=m.[s].[c]in p"-> %s\n"n;n)s.[0]in p"%s"w.[int r.[0]/97]with|_->p"%s"w.[1] 

非高尔夫F＃33线。 打完高尔夫之后我会再次更新。

 open System let input = Console.In.ReadToEnd() //let input = "S1 s2\nS1 0 s2\nS1 1 S1\ns2 0 S1\ns2 1 s2\n1001010" let lines = input.Split '\n' let length = lines.Length let states = lines.[0].Split ' ' let stateMap = Map.ofList [for state in states -> (state, Map.empty)] let folder stateMap (line:String) = let s = line.Split ' ' stateMap |> Map.add s.[0] (stateMap.[s.[0]] |> Map.add s.[1].[0] s.[2]) let machine = Array.fold folder stateMap lines.[1 .. (length-2)] let stateMachine state char = printf "%s %c " state char let newState = machine.[state].[char] printfn "-> %s" newState newState try let result = lines.[length-1].ToCharArray() |> Array.fold stateMachine states.[0] if Char.IsUpper result.[0] then printf "ACCEPT" else printf "REJECT" with | _ -> printf "REJECT" 

Answer 20

C＃ – 453 375 353 345个字符

这不会赢（不是任何人都应该预料到的），但是写起来很有趣。 我保持领先的空间和换行符的可读性：

 using System; class P { static void Main() { string c,k=""; var t=new string[99999][]; int p=-1,n; while((c=Console.ReadLine())!="") t[++p]=c.Split(' '); c=t[0][0]; foreach(var d in t[p][0]){ k+=c+' '+d; for(n=1;n<p;n++) if(c==t[n][0]&&d==t[n][1][0]) { c=t[n][2]; k+=" -> "+c; break; } k+="\n"; if(n==p){ c="~"; break; } } Console.Write(k+(c[0]>'Z'?"REJECT":"ACCEPT")); } } 

在我上次的更新中，通过假定input行数（即99,999）的实际限制，我能够保存22个字符。 在最糟糕的情况下，你需要增加到2,147,483,647的Int32最大值，这将增加5个字符。 我的机器不喜欢这个数组的想法，虽然…

执行的一个例子：

 >FSM.exe S1 s2 S1 0 s2 S1 1 S1 s2 0 S1 s2 1 s2 1001010 S1 1 -> S1 S1 0 -> s2 s2 0 -> S1 S1 1 -> S1 S1 0 -> s2 s2 1 -> s2 s2 0 -> S1 ACCEPT