Code Golf: конечный автомат!

Конечный автомат

Детерминированная машина конечного состояния – это простая вычислительная модель, широко используемая как введение в теорию автоматов в базовых курсах CS. Это простая модель, эквивалентная регулярному выражению, которая определяет определенную входную строку Accepted или Rejected . Оставляя некоторые формальности в стороне , пробег конечного автомата состоит из:

  1. алфавит , набор символов.
  2. состояний , которые обычно визуализируются как круги. Одно из состояний должно быть начальным состоянием . Некоторые из государств могут принимать , обычно визуализируются как двойные круги.
  3. переходы , обычно визуализируемые как направленные арки между состояниями, являются направленными связями между состояниями, связанными с буквой алфавита.
  4. строка ввода , список символов алфавита .

Запуск на машине начинается в начальном состоянии. Каждая буква входной строки считывается; Если есть переход между текущим состоянием и другим состоянием, соответствующим букве, текущее состояние изменяется на новое состояние. После чтения последней буквы, если текущее состояние является принимающим, входная строка принимается. Если последнее состояние не было принимающим, или буква не имела соответствующей дуги из состояния во время прогона, входная строка отклоняется.

Примечание. Это краткое описание не является полным формальным определением FSM; Прекрасная статья Википедии – отличное введение в тему.

пример

Например, следующая машина сообщает, имеет ли двоичное число, читаемое слева направо, четное число 0 с:

http://en.wikipedia.org/wiki/Finite-state_machine

  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. Обратите внимание, что требования к выходной мощности были ослаблены для ввода пустой строки.

добавление

Выходной формат

Следуя популярному требованию, следующий вывод также допустим для пустой строки ввода:

 ACCEPT 

или

 REJECT 

Без первого состояния, записанного в предыдущей строке.

Названия состояний

Допустимые имена состояний – это английская буква, за которой следует любое количество букв и цифр, подобно именам переменных, например State1 , state0 , STATE_0 .

Формат ввода

Как и большинство гольф-кодов, вы можете предположить, что ваш вход правильный.

Резюме ответов:

  • Cobol – 4078 символов
  • Python – 171 символ , 568 символов , 203 символа , 218 символов , 269 ​​символов
  • sed – 137 символов
  • рубин – 145 символов , 183 символа
  • Haskell – 192 символа , 189 символов
  • LISP – 725 символов
  • Perl – 184 символов
  • Баш – 184 символа
  • Rexx – 205 символов
  • Lua – 356 символов
  • F # – 420 символов
  • C # – 356 символов
  • Mixal – 898 символов

Решение sed 137 является самым коротким, 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 

поэтому, если у него нет разъяснений, щедрость идет на рубиновый раствор.

20 Solutions collect form web for “Code Golf: конечный автомат!”

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

Сценарий тестирования

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

Python 2.7+, 201 192 187 181 179 175 171 символ

PS. После того, как проблема была ослаблена (нет необходимости выводить строку состояния на пустой вход), вот новый код, который заметно короче. Если вы находитесь на версии <2.7, то нет понимания dict , поэтому вместо {c+o:s for o,c,s in i[1:-1]} try 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] 

Я хочу извиниться перед тем, как кто-то похлопывает меня за это: поведение кода немного отличается от первоначального обсуждения вопросов-комментариев. Это моя иллюстрация для обсуждения.

PS. в то время как мне нравится разрешение ACCEPT / REJECT в той же строке с конечным состоянием, оно может меня переместиться в уединение (например, представьте, что результаты должны анализироваться глупым скриптом, который заботится только о том, чтобы последняя строка принималась или отклонялась) путем добавления '\n'+ (5 символов) до последней print по цене +5 символов.

Пример вывода:

 # 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 

Сегодня я чувствую ретро, ​​мой язык выбора для этой задачи – 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. 

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 

Это должно обрабатывать входы без переходов правильно … надеюсь, что он полностью соответствует спецификации сейчас …

Адам предоставил справочную реализацию. Я не видел этого, прежде чем я сделал свой, но логика схожа:

Изменить: это код Python 2.6. Я не пытался минимизировать длину; Я просто попытался сделать его концептуально простым.

 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" 

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()] 

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 не нужен в версии для гольфа! Помимо этого, отдых – это все стандартные техники гольфа Haskell.

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 (изменение начального состояния и вводной строки). Он был вдохновлен, но не основан на решении sed . Он может быть сокращен на 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" 

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<'_']) 

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 

Освободите Кнут!

Хаскелл – 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"} 

EDIT: неправильно выполняет вывод для отказа от отказа.

Линейная версия и руководство переменной:

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

Я получил технику s<"[" из решения MtnViewMark; остальное – мой собственный дизайн. Известные характеристики:

  • Входные данные оставлены как нежелательные в таблице переходов. Это нормально, пока вход не содержит двух пробелов; но обратите внимание, что формат правила перехода, возможно, недружелюбен к переходу на космический персонаж.
  • Выполнение входной строки и поиск таблицы переходов – одна и та же функция.
  • Оба случая REJECT обрабатываются одним и тем же проходом.

Общий Лисп – 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 платит тяжелое наказание в требуемой обработке ввода, поэтому я не думаю, что есть много шансов на выигрыш этого решения 🙂

Рубин – 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

Rexx 205 символов

(Этот ответ прошел несколько изменений, поскольку я изначально просто разместил код для общего интереса, а затем решил фактически опубликовать реальное решение)

Вот версия Rexx, чтобы дать людям вкус к менее известному lanugage. Rexx http://en.wikipedia.org/wiki/REXX – это интерпретируемый язык, используемый в операционной системе IBM VM / CMS для мэйнфреймов, а затем в IBM OS / 2 (и я считаю, что был вариант Amiga). Это очень выразительный язык и потрясающий общий / «скриптовый» язык.

 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 .

Обработка неправильного сценария перехода с его уникальным выходом, а также тестирование для прописных букв немного дороже.

Код из некоторых старых редакций ниже для людей, заинтересованных в синтаксисе Rexx, которые не соответствуют требованиям выходных требований на 100%, но являются функциональными (весь код в этом ответе работает с образцами, вставленными ниже, но код выше обрабатывает другие требуемые углы ):

Старая короткая версия:

 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 

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 

bash – 186 185 184 символов

  объявить -А
 читать sx
 в то время как читать fm t && [$ m]; выполнить [$ f $ m] = $ t; done
 for ((i = 0; i - $ {# f}; i ++)) do b = "$ s $ {f: i: 1}"; s = $ {a [$ b]}; echo $ b - \ > $ s; done
 ["$ s" = "$ {s,}"] && echo REJECT || echo ACCEPT 

Обратите внимание, что на самом деле это требует bash. POSIX sh не имеет ассоциативных массивов или C-стиля для синтаксиса (и, вероятно, не имеет всех используемых расширений параметров, хотя я еще не проверял).

Изменить: альтернативно, для той же длины,

  объявить -А
 читать sx
 в то время как читать fm t && [$ m]; выполнить [$ f $ m] = $ t; done
 while [$ f]; do b = "$ s $ {f: i: 1}"; f = $ {f: 1}; s = $ {a [$ b]}; echo $ b - \> $ s ;сделанный
 ["$ s" = "$ {s,}"] && echo REJECT || echo ACCEPT 

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]] за 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]] 

Луа – 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') 

проверить запущенную версию на старой версии кодека

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] 

33 линии для не-гольф F #. Я немного обновлюсь после игры в гольф.

 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" 

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")); } } в 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")); } } 

В моем последнем обновлении я смог сохранить 22 символа, приняв практическое ограничение на количество входных строк (а именно 99,999). В худшем случае вам нужно довести до Int32 max 2,147,483,647, что добавит 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 
  • где в иерархии классов должны быть написаны методы экземпляра?
  • Почему аргументы за пределами аргумента не могут следовать аргументу по умолчанию?
  • Ориентация объектов на основе прототипа. Хороший, плохой, злой?
  • Unix: Получение Mouse-координаты над X, как Mathematica?
  • Почему я получил это ?
  • Извлечь поля структуры C
  • Python - лучший язык программирования в мире.