Existem muitos formalismos, portanto, embora você possa encontrar outras fontes úteis, espero especificar isso com clareza suficiente para que não sejam necessárias.
Um RM consiste em uma máquina de estados finitos e um número finito de registros nomeados, cada um dos quais contém um número inteiro não negativo. Para facilitar a entrada de texto, esta tarefa requer que os estados também sejam nomeados.
Existem três tipos de estado: incremento e decremento, que referenciam um registro específico; e terminar. Um estado de incremento incrementa seu registro e passa o controle para seu sucessor. Um estado de decréscimo possui dois sucessores: se seu registro é diferente de zero, ele o diminui e passa o controle para o primeiro sucessor; caso contrário (ou seja, o registro é zero), ele simplesmente passa o controle para o segundo sucessor.
Para "gentileza" como linguagem de programação, os estados de terminação levam uma string codificada para imprimir (para que você possa indicar uma terminação excepcional).
A entrada é de stdin. O formato de entrada consiste em uma linha por estado, seguida pelo conteúdo inicial do registro. A primeira linha é o estado inicial. O BNF para as linhas de estado é:
line ::= inc_line
| dec_line
inc_line ::= label ' : ' reg_name ' + ' state_name
dec_line ::= label ' : ' reg_name ' - ' state_name ' ' state_name
state_name ::= label
| '"' message '"'
label ::= identifier
reg_name ::= identifier
Há alguma flexibilidade na definição de identificador e mensagem. Seu programa deve aceitar uma sequência alfanumérica não vazia como identificador, mas pode aceitar sequências mais genéricas, se você preferir (por exemplo, se o seu idioma suportar identificadores com sublinhados e for mais fácil trabalhar com ele). Da mesma forma, para a mensagem, você deve aceitar uma sequência não-vazia de alfanuméricos e espaços, mas pode aceitar sequências mais complexas que permitam novas linhas de escape e aspas duplas, se desejar.
A linha final de entrada, que fornece os valores iniciais do registro, é uma lista separada por espaços das atribuições identifier = int, que devem estar não vazias. Não é necessário que ele inicialize todos os registros nomeados no programa: qualquer um que não seja inicializado será assumido como 0.
Seu programa deve ler a entrada e simular o RM. Quando atingir um estado final, deve emitir a mensagem, uma nova linha e, em seguida, os valores de todos os registros (em qualquer formato conveniente, legível por humanos, e em qualquer ordem).
Nota: formalmente os registradores devem conter números inteiros ilimitados. No entanto, você pode, se desejar, assumir que o valor de nenhum registro excederá 2 ^ 30.
Alguns exemplos simples
a + = b, a = 0s0 : a - s1 "Ok"
s1 : b + s0
a=3 b=4
Resultados esperados:
Ok
a=0 b=7
b + = a, t = 0
init : t - init d0
d0 : a - d1 a0
d1 : b + d2
d2 : t + d0
a0 : t - a1 "Ok"
a1 : a + a0
a=3 b=4
Resultados esperados:
Ok
a=3 b=7 t=0
Casos de teste para máquinas mais difíceis de analisar
s0 : t - s0 s1
s1 : t + "t is 1"
t=17
Resultados esperados:
t is 1
t=1
e
s0 : t - "t is nonzero" "t is zero"
t=1
Resultados esperados:
t is nonzero
t=0
Um exemplo mais complicado
Retirado do desafio de código de problema Josephus do DailyWTF. A entrada é n (número de soldados) ek (avanço) e a saída em r é a posição (indexada a zero) da pessoa que sobrevive.
init0 : k - init1 init3
init1 : r + init2
init2 : t + init0
init3 : t - init4 init5
init4 : k + init3
init5 : r - init6 "ERROR k is 0"
init6 : i + init7
init7 : n - loop0 "ERROR n is 0"
loop0 : n - loop1 "Ok"
loop1 : i + loop2
loop2 : k - loop3 loop5
loop3 : r + loop4
loop4 : t + loop2
loop5 : t - loop6 loop7
loop6 : k + loop5
loop7 : i - loop8 loopa
loop8 : r - loop9 loopc
loop9 : t + loop7
loopa : t - loopb loop7
loopb : i + loopa
loopc : t - loopd loopf
loopd : i + loope
loope : r + loopc
loopf : i + loop0
n=40 k=3
Resultados esperados:
Ok
i=40 k=3 n=0 r=27 t=0
Esse programa como uma imagem, para aqueles que pensam visualmente e acham útil entender a sintaxe:
Se você gostou deste golfe, dê uma olhada na sequência .
fonte
Respostas:
Perl, 166
Corra com
perl -M5.010 file
.Tudo começou muito diferente, mas receio que tenha convergido com a solução Ruby em muitas áreas no final. Parece que a vantagem de Ruby é "sem sigilos" e "melhor integração de expressões regulares" de Perl.
Um pouco de detalhes das entranhas, se você não lê Perl:
@p=<>
: leia a descrição completa da máquina para@p
/=/,$_{$`}=$' for split$",pop@p
: para cada (for
) atribuição (split$"
) na última linha de descrição da máquina (@p
), localize o sinal de igual (/=/
) e atribua valor$'
à%_
chave de hask$`
$o='\w+'
: o estado inicial seria o primeiro a corresponder à expressão regular do Perl "caracteres da palavra"until/"/
: loop até atingirmos um estado de término:map{($r,$o,$,,$b)=$'=~/".*?"|\S+/g if/^$o :/}@p
: loop na descrição da máquina@p
: quando estamos na linha que corresponde ao estado atual (if/^$o :/
), tokenize (/".*?"|\S+/g
) o resto da linha$'
com variáveis($r,$o,$,,$b)
. Truque: a mesma variável$o
se usada inicialmente para o nome do rótulo e posteriormente para o operador. Assim que o rótulo corresponde, o operador o substitui e, como um rótulo não pode (razoavelmente) ser nomeado + ou -, nunca corresponde novamente.$_=$o=($_{$r}+=','cmp$o)<0?do{$_{$r}=0;$b}:$,
:- ajuste o registro de destino para
$_{$r}
cima ou para baixo (ASCII magic:','cmp'+'
é 1','cmp'-'
e -1);- se o resultado for negativo (
<0?
, só pode acontecer para -)- permaneça em 0 (
$_{$r}=0
) e retorne o segundo rótulo$b
;- caso contrário, retorne o primeiro rótulo (possivelmente único)
$,
$,
vez de,$a
portanto, pode ser colado no próximo tokenuntil
sem espaço em branco no meio.say for eval,%_
: relatório de despejo (eval
) e conteúdo dos registros em%_
fonte
/^$o :/
. Somente o sinal de intercalação é suficiente para garantir que você esteja apenas visualizando rótulos.$'
. É um caractere no regex, seriam três$c,
para contabilizar de fora. Como alternativa, alguns maiores ainda mudam para a regex de tokenização.Python + C, 466 caracteres
Apenas por diversão, um programa python que compila o programa RM para C, compila e executa o C.
fonte
main
', 'if
' etc.Haskell, 444 caracteres
Cara, isso foi difícil! O manuseio adequado das mensagens com espaços custa mais de 70 caracteres. A formatação de saída para ser mais "legível por humanos" e corresponder aos exemplos custa outros 25.
fonte
where
em uma única linha separada por ponto e vírgula pode economizar 6 caracteres. E eu acho que você pode salvar alguns caracteres na definição deq
, alterando o detalhado if-then-else para um protetor de padrão."-"
na definição deq
e use um sublinhado.q[_,_,r,_,s,z]d|maybe t(==0)$lookup r d=n z d|t=n s$r%(-1)$d
. Mas de qualquer maneira, este programa é extremamente bom.lex
o Prelude. Por exemplo, algo comof[]=[];f s=lex s>>= \(t,r)->t:f r
dividirá uma linha em tokens enquanto manipula as strings entre aspas corretamente.Ruby 1.9,
214212211198195192181175173175fonte
Delphi, 646
O Delphi não oferece muito em relação à divisão de strings e outras coisas. Felizmente, temos coleções genéricas, o que ajuda um pouco, mas ainda é uma solução bastante ampla:
Aqui a versão recuada e comentada:
fonte
PHP,
446441402398395389371370366 caracteresUngolfed
Changelog
446 -> 441 : Suporta seqüências de caracteres para o primeiro estado e alguma leve compressão
441 -> 402 : Instruções if / else e de atribuição compactadas, tanto quanto possível
402 -> 398 : Os nomes das funções podem ser usados como constantes e podem ser usados como strings
398 -> 395 : Utiliza operadores de curto-circuito
395 -> 389 : Não há necessidade da outra parte
389 -> 371 : Não há necessidade de usar array_key_exists ()
371 -> 370 : Espaço desnecessário removido
370 -> 366 : Removidos dois espaços desnecessários o foreach
fonte
Groovy, 338
fonte
.sort()
)println
- ah bem!Clojure (344 caracteres)
Com algumas quebras de linha para "legibilidade":
fonte
Postscript () ()
(852)(718)Para reais desta vez. Executa todos os casos de teste. Ele ainda exige que o programa RM siga imediatamente no fluxo do programa.
Edit: Mais fatoração, nomes de procedimentos reduzidos.
Recuado e comentado com o programa anexado.
fonte
regline
? Você não pode economizar muito chamando-as de coisas assimR
?AWK - 447
Esta é a saída para o primeiro teste:
fonte
Stax ,
115100 bytesExecute e depure
fonte