Seu desafio é interpretar um diagrama de circuitos, completo com portas lógicas.
Portas lógicas (na verdade, você não precisa saber o que elas fazem para completar esse desafio):
- e portão:
a
- ou portão:
o
- portão nand:
A
- nem portão:
O
- xor portão:
x
- portão xnor:
X
- não portão:
~
Cada portão, exceto o último, recebe duas entradas. As entradas são de um .
no canto superior esquerdo e inferior esquerdo do quadrado 3 por 3 centralizado no portão. Para não, a entrada está diretamente à sua esquerda. A saída é .
diretamente para a direita.
Os fios são representados por -|\/.=
-
entra em contato com dois fios, um à direita e outro à esquerda:c-c
|
entra em contato com dois fios, um acima e outro abaixo:c | c
/
e\
trabalhe da seguinte maneira:c c \ / c c
.
entra em contato com todos os fios ao redor:ccc c.c ccc
=
é especial; conecta fios adjacentes através dele:-=-
conecta os dois fios. Na sequência
\|/ -=- /|\
cada fio oposto está conectado um ao outro, mas não aos outros (é aqui que difere
.
).- Para que a corrente flua, dois fios devem ser conectados ao outro, portanto
|-
, a corrente não flui.
Exemplo de fiação:
.-.
= \
.--. .---=---
-. = .--
.--. .-------
a entrada é dividida em dois fios e depois dividida em três. Nesta divisão, o fio inferior move-se para o meio e a divisão para baixo do fio superior aparece na parte inferior. Em seguida, a parte superior dos três fios é movida para o meio.
Exemplo de fiação com portões:
--.
o..~..
--. o.---
a.---.
--.
Formato de entrada:
- cada fio de entrada será identificado com um dígito. No final (logo antes da nova linha), cada saída será rotulada com
:
(e o fio sempre entrará direto nela,-:
ou seja,.:
ou=:
) - a entrada sempre será válida; não haverá laços ou fios unidos sem um portão. Observe que pode haver fios com pontas soltas.
=
será usado somente quando necessário.
Formato de saída:
- cada entrada é referenciada com o número correspondente.
- uma expressão é emitida. Por exemplo, se os fios computarem a entrada 1 e a entrada 2, a saída será
1a2
. - quaisquer funções emitidas devem corresponder às portas lógicas no início.
- para não mostrar, coloque o
~
antes no local correto. para várias funções, use parênteses para mostrar a ordem de execução. Parênteses também podem ser usados quando há apenas uma única função. Por exemplo,
1-.~.-. A.~.-: . 2-. / x. 3-.
tem uma saída possível de
~((2x3)A(~1))
- várias saídas devem ser separadas por uma nova linha (ou equivalente)
Entrada de amostra:
1--.---.
x. \
2--. x.-=---------.
. .~. X.--.
3---. . a.----. /
O.~.-. \ /
. =
4-. / / .-:
X. .----:
5-.
Uma saída correspondente possível:
(~1)a(~(3O(4X5))
((1x2)x3)X((~1)a(~(3O(4X5))))
Respostas:
Python
24881567806706697657653Yay para gzip + exec!
Limitações e premissas
Assim, apenas 9 entradas são suportadas - vários dígitos não são manipulados corretamente. Como a especificação indica que as entradas são identificadas com um dígito , não um número , isso é permitido.
Entrada e saída
A entrada é recebida via entrada padrão e a saída é via saída padrão.
Teste
Entrada e saída de amostra:
Testado aqui: http://ideone.com/gP4CIq
O algoritmo
É basicamente um DFS bastante ingênuo das saídas. Para cada saída, ele começa do caractere à sua esquerda e rastreia o fio, ramificando (e adicionando à expressão) a cada porta. Quando atinge uma entrada, a adiciona à expressão e segue para o último ponto em que ramificou, pois podemos ter certeza de que a ramificação não é possível sem um portão. E, claro, todos os casos inválidos são descartados. Nada realmente especial para ele - e, portanto, provavelmente é mais do que poderia ter sido.
Notas
O tamanho provavelmente poderia ser reduzido um pouco com alguma reestruturação, mas eu gastei tempo suficiente nisso hoje. A versão de golfe manual foi a compactada.
A compactação gzip torna o golfe interessante, porque determinado cache (por exemplo
d=(-1,0,1)
) ocupa mais espaço do que permitir que o algoritmo de compactação cuide dele. No entanto, optei por jogar a versão manual o máximo possível, em vez de otimizar a compactação.Golfed manualmente (
909895840803):Totalmente não-destruído (2488):
fonte
0
como um dígito? Como sobre a encomenda trocados de modo a que2
vem antes1
, etc..isdigit()
, que é efetivamente equivalente ao regex[0-9]
, tanto quanto eu posso dizer. Isso está correto de acordo com suas especificações? O que você quer dizer com encomenda trocada? Da maneira como é implementado, ele seguirá primeiro no ramo ascendente de qualquer porta lógica, mas não há garantia de pedido de entradas.isdigit()
é consistente. Ordenação trocada significa algo como2
a primeira entrada e1
a segunda entrada (classificada verticalmente).Java:
15231512 caracteresEle fornece esta saída para a entrada de amostra:
Para diminuir seu tamanho:
r
, sem nenhuma extensão de arquivo no nome.Estou certo de que deve ser possível reduzi-lo mais, mas apenas um pouco.
O intérprete é implementado na forma de algum tipo de autômato celular. Ele verifica todos os valores de configuração do campo, repetindo-o quantas vezes forem necessárias até que nenhuma alteração seja detectada.
Aqui está uma versão não destruída:
fonte
try{}catch(Exception e){}
do que doisthrows Exception
. Provavelmente há outras coisas, mas não tenho idéia de como jogar golfe em Java.