Marcador
Aquí están los puntajes brutos (es decir, el conteo de dominó) para el envío de VisualMelon Los convertiré en los puntajes normalizados que se describen a continuación, cuando lleguen más respuestas. La solución existente ahora puede resolver todos los circuitos en el punto de referencia:
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
El reto
Que es posible construir puertas lógicas simples de fichas de dominó. Por lo tanto, combinando estos o no, las funciones binarias arbitrarias se pueden calcular con fichas de dominó.
Pero, por supuesto, todos los que han jugado con dominó (excepto Robin Paul Weijers) han experimentado la decepción al quedarse sin ellos. Por lo tanto, queremos usar nuestras fichas de dominó de la manera más eficiente posible, para poder hacer algunos cálculos realmente interesantes con el material que tenemos.
Tenga en cuenta que no puede producir una salida distinta de cero a partir de la entrada cero per se, por lo que tendremos que agregar una "línea de alimentación", que se ubica a lo largo de su configuración, y de la que puede extraer 1
s en cualquier momento.
Tu tarea
Dada una función booleana con M
entradas y N
salidas ( f: {0,1}^M --> {0,1}^N
para los matemáticamente inclinados), produzca un circuito de dominó con la menor cantidad posible de dominó que calcule esa función. Que va a utilizar los símbolos |
, -
, /
, \
para representar al dominó en varias orientaciones.
Entrada
Se le dará entrada a través de argumentos de línea de comandos:
[command for your solver] M N f
donde M
y N
son enteros positivos y f
es la tabla de verdad separada por comas en orden canónico. Es decir, f
contendrá 2^M
valores de longitud N
. Por ejemplo, si M = N = 2
y el primer bit en la salida era la función AND, mientras que el segundo bit era la función OR, f
se leería
00,01,01,11
Salida
Escriba en STDOUT una cuadrícula ASCII que represente la configuración del dominó. Su configuración tiene que encajar en el siguiente marco
/////.../////
????...????
I????...????O
I????...????O
.............
.............
I????...????O
I????...????O
I????...????O
- La fila superior consta completamente de
/
, y se garantiza que el dominó más a la izquierda se derribará al principio: esta es su línea de alimentación. - La columna más a la izquierda consta de sus entradas. Cada uno
I
puede ser un espacio o un|
, de modo que hay exactamenteM
|
s. - La columna de la derecha consta de sus salidas. Cada uno
O
puede ser un espacio o un|
, de modo que hay exactamenteN
|
s. - Tenga en cuenta que hay al menos un espacio en blanco antes del primero
|
en la entrada o salida. - El
.
indican que la rejilla puede ser arbitrariamente grande. - Puede completarlo
?
de la forma que desee.
Tenga en cuenta que la entrada inferior es la que varía más rápidamente mientras recorre la tabla de verdad, mientras que la entrada superior es 0
para la primera mitad de las salidas y 1
para la segunda mitad.
Reglas
El dominó se propaga como se especifica en Golf para el Día del dominó . En resumen, si representamos las direcciones de caída como letras
Q W E
A D
Z X C
entonces estas son combinaciones únicas que pueden propagarse (así como sus rotaciones y reflexiones):
D| -> DD D\ -> DE D/ -> DC
C| -> CD C/ -> CC
C -> C C -> C C -> C
| D - X / C
Todas las reglas anteriores se aplican simultáneamente en cada paso de tiempo. Si dos de esas reglas están en conflicto (es decir, un mosaico se empuja en dos direcciones opuestas válidas al mismo tiempo), el mosaico afectado no caerá y se bloqueará efectivamente en su posición durante el resto de la simulación.
Restricciones
M
yN
nunca excederá de 6.- Su solucionador debe producir un circuito dentro de N * 2 M segundos .
- Su solucionador no debe usar más de 1 GB de memoria . Este es un límite suave, ya que lo monitorearé manualmente y eliminaré su proceso si excede este límite de manera significativa / continua.
- No se permite que ningún circuito contenga más de 8,000,000 de celdas o 1,000,000 de dominó .
- Su presentación debe ser determinista . Se le permite usar generadores de números pseudoaleatorios, pero deben usar una semilla codificada (que puede optimizar tanto como quiera).
Tanteo
Para cada circuito, indique el D
número total de fichas de dominó en su circuito y B
la cantidad más baja de fichas de dominó con las que este circuito ha sido resuelto (usted o cualquier otro participante). Entonces su puntaje para este circuito viene dado por 10,000 * B / D
redondeado hacia abajo. Si no resolvió el circuito, su puntaje es 0. Su puntaje general será la suma de un conjunto de casos de prueba de referencia. Los circuitos que aún no han sido resueltos por nadie no se incluirán en la puntuación total.
Cada participante puede agregar un caso de prueba al punto de referencia (y todas las demás presentaciones serán reevaluadas, incluido ese nuevo caso de prueba).
El archivo de referencia se puede encontrar en GitHub .
Ejemplos
Aquí hay algunos ejemplos no resueltos de manera óptima.
Constante 1
1 1
1,1
///////
/
| |||
Conteo de dominó: 12
O puerta
2 1
0,1,1,1
///////////
|||||/
|||||
|||||\
Conteo de dominó: 28
Y puerta
2 1
0,0,0,1
///////////////////
\-/
- -
|||||/|\ /|||/
/ -
- \-
\- \ -
|||||\ / \ /
|\ |||||
Conteo de dominó: 62
Intercambiar carriles
2 2
00,10,01,11
////////////
||||/ \||||
/\
\/
||||\ /||||
Conteo de dominó: 36
Notas adicionales
Las reglas de propagación son tales que los carriles diagonales pueden cruzarse usando una forma de diamante (ver el último ejemplo) incluso si uno cae antes que el otro (a diferencia de las fichas de dominó reales).
Como punto de partida, puede usar las puertas lógicas (no minimizadas) en esta esencia e intentar combinar la menor cantidad posible de estas. Para una forma simple (no óptima) de construir funciones booleanas arbitrarias desde las puertas AND, OR y NOT, eche un vistazo a las formas normales conjuntivas y disyuntivas .
Hay un verificador en este repositorio de GitHub para probar su código, que también se usará para calificar todas las presentaciones. Esto genera los puntajes brutos (conteos de dominó) y los guarda en un archivo para ser procesado por un anotador separado (también en ese repositorio) para obtener los puntajes finales.
Se puede encontrar documentación general dentro de los dos archivos Ruby, pero se controller.rb
necesitan dos cambios de línea de comando antes del archivo de referencia:
-v
le da más salida, incluidos los circuitos reales producidos por su solucionador.-c
le permite seleccionar un subconjunto del punto de referencia que desea probar. Proporcione los circuitos deseados como una lista separada por comas de índices basados en 1. También puede usar rangos de Ruby, por lo que podría hacer algo como-c 1..5,10,15..20
.
Por favor incluya en su respuesta:
- Tu codigo
- Un comando para (compilar y) ejecutar su código. Te preguntaré dónde obtener los compiladores / intérpretes necesarios si no los tengo.
- Una tabla de verdad adicional con un nombre, que se agregará como un caso de prueba al punto de referencia. (Esto es opcional, pero se recomienda encarecidamente).
Probaré todas las presentaciones en Windows 8.
fuente
Respuestas:
C # - Solución masiva, lenta e ineficiente
Confesión: escribí esta solución hace algún tiempo cuando la pregunta aún estaba en el sandbox, pero no es muy buena: ¡puedes hacerlo mejor!
Editar: reemplazó la resolución aburrida con un método menos aburrido, más flexible y generalmente mejor
Ejecutas el programa compilando
csc dominoPrinter.cs
y luego pasando argumentos al ejecutable, por ejemplo (el verificador principal de 4 bits):Explicación:
La "Impresora Domino" es un programa de 3 etapas:
Etapa 1 : el "solucionador" genera un árbol de expresión de "ifnot" y "u" operaciones binarias con las entradas dadas, y un "1" desde la línea de alimentación, hay 2 formas de hacerlo, dependiendo del número de entradas:
Si hay menos de 4 entradas, el programa presenta una solución de la menor cantidad de operaciones
Si hay 4 o más entradas, el programa elimina cada fragmento de salida de 8 bits y luego combina los resultados para obtener la salida deseada. Las partes brutas son flexibles: cuantas más partes brutas, menor es la solución, pero mayor es el tiempo de ejecución.
El "solucionador" es lo que lleva todo el tiempo (o al menos solía hacerlo), y también es la mayor parte del código. Creo que hay una solución bien documentada, rápida, que no requiere mucha memoria y que probablemente sea óptima para este problema, pero ¿dónde sería divertido buscarlo?
El árbol de expresión (bruto) para el verificador principal de 4 bits es
donde los números son los índices de las entradas.
Etapa 2 : el "organizador" toma el árbol de expresión como entrada y ensambla un diseño de "esqueleto", que describe con precisión un diseño de dominó hecho a partir de un conjunto de celdas superpuestas 4x5. A continuación se muestra el esqueleto para el verificador principal de 4 bits bruto (deberá cambiar la
bruteBase
variable entera en la línea 473 a 4 (o más grande) para obtener este resultado).Esta salida se compone efectivamente de dos partes, el "evaluador" a la derecha, que se crea a partir del árbol de expresión de la etapa 1, y el "panel de control" a la izquierda, que intercambia y divide las entradas para que lleguen al lugares correctos para el "evaluador" para manejar.
Hay un margen considerable para compactar el diseño en este punto, pero el programa actualmente hace muy poco ese trabajo. El código para esta etapa es horrible, pero bastante simple debajo (vea el método "orifnot"). La salida se pasa a la etapa 3.
Etapa 3 : la "impresora" toma la salida del "organizador" e imprime las "celdas" superpuestas 4x5 correspondientes junto con la línea de alimentación. A continuación se muestra una animación del verificador principal de 4 bits que verifica si 5 es primo.
Codifique la falta de sangría para evitar sobrepasar el límite de caracteres SE 30k que de otro modo :
Un caso de prueba adicional:
Esto verifica si dos bits adyacentes (sin envoltura) son ambos 1s (por ejemplo, verdadero para 0110, pero falso para 0101 y 1001)
fuente
I
y cuyas salidas especificar un nuevo diseño de dominó