Placar
Aqui estão as pontuações brutas (ou seja, o dominó conta) para a apresentação do VisualMelon. Vou transformá-las nas pontuações normalizadas descritas abaixo, quando houver mais respostas. A solução existente agora pode resolver todos os circuitos no benchmark:
Author Circuit: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
VisualMelon 39 45 75 61 307 337 56 106 76 62 64 62 182 64 141 277 115 141 92 164 223 78 148 371 1482 232 107 782 4789 5035 1314 3213 200 172 1303 3732 97596 156889 857
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Legend:
I - invalid circuit
B - circuit too big
W - circuit computes wrong function
T - exceeded time limit
O desafio
Ele é possível construir portas lógicas simples dos dominós. Portanto, combinando essas funções, ou de outra forma, funções binárias arbitrárias podem ser computadas com dominós.
Mas é claro que todo mundo que brincou com dominós (exceto Robin Paul Weijers) experimentou a decepção ao ficar sem eles. Portanto, queremos usar nossos dominós da maneira mais eficiente possível, para que possamos fazer alguns cálculos realmente interessantes com o material que temos.
Observe que você não pode produzir uma saída diferente de zero a partir da entrada zero, por isso, precisamos adicionar uma "linha de energia", que se encaixa na sua configuração e da qual você pode extrair 1
s a qualquer momento.
Sua tarefa
Dada uma função booleana com M
entradas e N
saídas ( f: {0,1}^M --> {0,1}^N
para os matematicamente inclinados), produza um circuito dominó com o menor número possível de dominós que calcule essa função. Você estará usando os símbolos |
, -
, /
, \
para representar dominó em várias orientações.
Entrada
Você receberá informações por meio de argumentos da linha de comando:
[command for your solver] M N f
onde M
e N
são números inteiros positivos e f
é a tabela de verdade separada por vírgula em ordem canônica. Ou seja, f
conterá 2^M
valores de comprimento N
. Por exemplo, se M = N = 2
e o primeiro bit na saída for a função AND, enquanto o segundo bit for a função OR, f
lerá
00,01,01,11
Saída
Escreva para STDOUT uma grade ASCII representando a configuração do dominó. Sua configuração deve se encaixar na seguinte estrutura
/////.../////
????...????
I????...????O
I????...????O
.............
.............
I????...????O
I????...????O
I????...????O
- A linha superior consiste inteiramente
/
e o dominó mais à esquerda é garantido para ser derrubado no início - esta é a sua linha de energia. - A coluna mais à esquerda consiste em suas entradas. Cada um
I
pode ser um espaço ou um|
, de modo que exista exatamenteM
|
s. - A coluna mais à direita consiste em suas saídas. Cada um
O
pode ser um espaço ou um|
, de modo que exista exatamenteN
|
s. - Observe que há pelo menos um espaço em branco antes do primeiro
|
na entrada ou saída. - O
.
indica que a grade pode ser arbitrariamente grande. - Você pode preencher
?
da maneira que desejar.
Observe que a entrada inferior tem a variação mais rápida enquanto você avança na tabela verdade, enquanto a entrada superior é 0
a primeira metade das saídas e 1
a segunda metade.
Regras
Os dominós se propagam conforme especificado em Golfe para o dia do dominó . Em resumo, se representarmos as direções em queda como letras
Q W E
A D
Z X C
essas são todas as combinações únicas que podem se propagar (assim como suas rotações e reflexões):
D| -> DD D\ -> DE D/ -> DC
C| -> CD C/ -> CC
C -> C C -> C C -> C
| D - X / C
Todas as regras acima são aplicadas simultaneamente a cada etapa do tempo. Se duas dessas regras estiverem em conflito (por exemplo, um bloco é empurrado para duas direções opostas válidas ao mesmo tempo), o bloco afetado não cairá e será efetivamente bloqueado na posição pelo resto da simulação.
Restrições
M
eN
nunca excederá 6.- Seu solucionador deve produzir um circuito dentro de N * 2 M segundos .
- Seu solucionador não deve usar mais de 1 GB de memória . Esse é um limite flexível, pois monitorarei isso manualmente e matarei seu processo se ele exceder significativamente / continuamente esse limite.
- Nenhum circuito pode conter mais de 8.000.000 de células ou 1.000.000 de dominó .
- Seu envio deve ser determinístico . Você tem permissão para usar geradores de números pseudo-aleatórios, mas eles devem usar uma semente codificada (que você pode otimizar o quanto quiser).
Pontuação
Para cada circuito, D
seja o número total de dominós no seu circuito e B
o menor número de dominós com os quais este circuito foi resolvido (por você ou por qualquer outro participante). Então sua pontuação para este circuito é dada por 10,000 * B / D
arredondado para baixo. Se você não conseguiu resolver o circuito, sua pontuação é 0. Sua pontuação geral será a soma de um conjunto de benchmarks de casos de teste. Os circuitos que ainda não foram resolvidos por ninguém não serão incluídos na pontuação total.
Cada participante pode adicionar um caso de teste ao benchmark (e todos os outros envios serão reavaliados, incluindo o novo caso de teste).
O arquivo de benchmark pode ser encontrado no GitHub .
Exemplos
Aqui estão alguns exemplos resolvidos de maneira não ideal.
Constante 1
1 1
1,1
///////
/
| |||
Contagem de dominó: 12
OU portão
2 1
0,1,1,1
///////////
|||||/
|||||
|||||\
Contagem de dominó: 28
E portão
2 1
0,0,0,1
///////////////////
\-/
- -
|||||/|\ /|||/
/ -
- \-
\- \ -
|||||\ / \ /
|\ |||||
Contagem de dominó: 62
Trocar faixas
2 2
00,10,01,11
////////////
||||/ \||||
/\
\/
||||\ /||||
Contagem de dominó: 36
Notas Adicionais
As regras de propagação são tais, que as pistas diagonais podem cruzar usando um formato de diamante (veja o último exemplo), mesmo que uma caia antes da outra (ao contrário dos dominós reais).
Como ponto de partida, você pode usar os portões lógicos (não minimizados) nesta essência e tentar combinar o menor número possível deles. Para uma maneira simples (não ótima) de criar funções booleanas arbitrárias a partir das portas AND, OR e NOT, dê uma olhada nas Formas Normais Conjuntivas e Disjuntivas .
Existe um verificador neste repositório do GitHub para testar seu código, que também será usado para classificar todos os envios. Isso gera as pontuações brutas (contagens de dominó) e as salva em um arquivo a ser processado por um apontador separado (também nesse repositório) para obter as pontuações finais.
A documentação geral pode ser encontrada nos dois arquivos Ruby, mas são controller.rb
necessárias duas opções de linha de comando antes do arquivo de referência:
-v
fornece um pouco mais de saída, incluindo os circuitos reais produzidos pelo seu solucionador.-c
permite selecionar um subconjunto da referência que você deseja testar. Forneça os circuitos desejados como uma lista separada por vírgula de índices baseados em 1. Você também pode usar intervalos Ruby, para fazer algo assim-c 1..5,10,15..20
.
Por favor inclua na sua resposta:
- Seu código
- Um comando para (compilar e) executar seu código. Vou perguntar onde obter os compiladores / intérpretes necessários, se não os tiver.
- Uma tabela de verdade adicional com um nome, a ser adicionada como um caso de teste ao benchmark. (Isso é opcional, mas fortemente incentivado.)
Vou testar todos os envios no Windows 8.
fonte
Respostas:
Solução maciça, lenta e ineficiente
Confissão: escreveu esta solução há algum tempo, quando a pergunta ainda estava na caixa de areia, mas não é muito boa: você pode fazer melhor!
Editar: substituiu a solução chata por um método menos chato, mais flexível e geralmente melhor
Você executa o programa compilando
csc dominoPrinter.cs
e passando argumentos para o executável, por exemplo (o verificador principal de 4 bits):Explicação:
A "Impressora Domino" é um programa de três estágios:
Etapa 1 : O "solucionador" gera uma árvore de expressão de operações "ifnot" e "ou" binária com as entradas fornecidas e um "1" da linha de energia; existem 2 maneiras de fazer isso, dependendo do número de entradas:
Se houver menos de 4 entradas, o programa oferece uma solução com o menor número de operações
Se houver 4 ou mais entradas, o programa reduz bruta cada pedaço de 8 bits da saída e combina os resultados para obter a saída desejada. Os bits brutados se flexíveis: quanto mais brutados, menor a solução, mas maior o tempo de execução.
O "solucionador" é o que leva o tempo todo (ou pelo menos costumava ser) e também é a maior parte do código. Eu acredito que há uma solução bem documentado, rápido, não tão de memória com fome, e provavelmente ideal para este problema, mas onde estaria a diversão estar em pesquisá-lo?
A árvore de expressão (em bruto) para o verificador principal de 4 bits é
onde os números são os índices das entradas.
Etapa 2 : O "organizador" toma a árvore de expressão como entrada e monta um layout "esqueleto", que descreve precisamente um layout de dominó feito de um conjunto de células sobrepostas 4x5. Abaixo está o esqueleto do verificador primário bruto de 4 bits (você precisará alterar a
bruteBase
variável inteira na linha 473 para 4 (ou maior) para obter esse resultado).Essa saída é composta efetivamente de duas partes: o "avaliador" à direita, criado a partir da árvore de expressão do estágio 1, e o "painel de controle" à esquerda, que troca e divide as entradas para que elas cheguem ao lugares certos para o "avaliador" lidar.
Há uma margem considerável para compactar o layout neste momento, mas o programa atualmente faz muito pouco desse trabalho. O código para esse estágio é horrível, mas bem simples embaixo (veja o método "orifnot"). A saída é passada para o estágio 3.
Etapa 3 : A "impressora" obtém a saída do "organizador" e imprime as "células" sobrepostas 4x5 correspondentes, juntamente com a linha de energia. Abaixo está uma animação do verificador primário de 4 bits brutado, verificando se 5 é primo.
Codifique a falta de recuo para evitar ultrapassar o limite de caracteres SE 30k, que de outra forma seria :
Um caso de teste adicional:
Isso verifica se dois bits adjacentes (sem quebra) são ambos 1s (por exemplo, verdadeiro para 0110, mas falso para 0101 e 1001)
fonte
I
e cujas saídas especificar um novo layout de dominó