Hay 40 formas en que se puede organizar una ruta Hamiltoniana dirigida en una cuadrícula de 3 × 3:
este gráfico (¡ gracias Sp3000! ) Muestra solo las 20 rutas no dirigidas. Atraviese cada línea de color en ambas direcciones para los 40 caminos dirigidos.
Reto
Usando solo ASCII imprimible , escriba una cuadrícula de caracteres de 3 × 3, como:
ABC
DEF
GHI
Cuando cada una de las 40 rutas dirigidas se lee de esta cuadrícula como 40 programas de una línea y 9 caracteres, el objetivo es que cada programa genere un número entero único del 1 al 40. Hacer esto para las 40 rutas parece difícil e improbable, así que solo necesitas hacer que funcione para tantos caminos como puedas.
El envío cuyos 40 programas de ruta generen los números más distintos del 1 al 40 será el ganador. Tiebreaker va a la presentación anterior.
Los programas de ruta que producen errores o no generan un número entero de 1 a 40 o generan un número entero que otro programa de ruta ya cubierto no se cuenta. Específicamente:
- Los programas que producen errores al compilar, ejecutar o salir no se cuentan. Las advertencias están bien.
- Los programas que no generan un número entero de 1 a 40 o que emiten algo ligeramente mal formado como
-35
o35 36
no se cuentan. - Los programas que requieren la entrada del usuario para producir la salida no se cuentan.
- Los programas que nunca terminan no se cuentan.
- De ahora en adelante , los programas que no son deterministas no se cuentan.
- De lo contrario, no se cuentan los programas válidos que generan un número entero de 1 a 40 que otro programa válido ya ha generado. (El primer programa se contó.)
- Solo los programas que generan representaciones enteras de números del 1 al 40 (inclusive) se cuentan para su total. Se espera que los números para estar en el habitual
1
,2
, ...,39
,40
formato, a menos que no es la norma para su idioma. (Una nueva línea final en la salida está bien). - No importa qué números generan sus programas y en qué orden están. Solo importa el número de enteros distintos de los programas válidos.
Todos los programas de ruta deben ejecutarse en el mismo idioma. Sin embargo, los "programas" pueden ser funciones (sin argumentos necesarios) o comandos REPL , así como programas completos, que imprimen o devuelven su entero objetivo. Puede mezclar y combinar funciones, comandos REPL y programas completos.
Sus 9 caracteres ASCII imprimibles no necesitan ser distintos.
Ejemplo
Si tu cuadrícula de 3 × 3 fuera
ABC
DEF
GHI
y sus 40 programas y salidas se veían así
ABCFEDGHI -> 26
ABCFIHEDG -> 90
ABCFIHGDE -> 2
ABEDGHIFC -> syntax error
ADEBCFIHG -> prints 40 but then errors
ADGHEBCFI -> 6
ADGHIFCBE -> 6
ADGHIFEBC -> 6
CBADEFIHG -> runtime error
CBADGHEFI -> 3
CBADGHIFE -> 4
CFEBADGHI -> -32
CFIHEBADG -> 38.0
CFIHGDABE -> "36"
EDABCFIHG -> 33
EFCBADGHI -> no output
EHGDABCFI -> compilation error
EHIFCBADG -> 8
GDABCFEHI -> 22
GHEDABCFI -> 41
IHGDEFCBA -> 0
GDEHIFCBA -> '9'
EDGHIFCBA -> +10
CFIHGDEBA -> 11
GHIFCBEDA -> error
IFCBEHGDA -> error
EBCFIHGDA -> prints 23 but then loops infinitely
CBEFIHGDA -> randomly prints either 24 or 44
GHIFEDABC -> error
IFEHGDABC -> 30
EFIHGDABC -> 39
IHGDABEFC -> 7
GDABEHIFC -> 29
EBADGHIFC -> -1
GHIFCBADE -> 26
IHGDABCFE -> 1
IFCBADGHE -> error
GDABCFIHE -> no output
IHEFCBADG -> no output
IFCBADEHG -> "quack"
su puntaje sería 14, porque hay 14 enteros distintos de 1 a 40 de salida válida, a saber 26 2 6 3 4 33 8 22 11 30 39 7 29 1
.
fuente
123654789
Respuestas:
PARI / GP - 24
PARI / GP ignora los espacios entre dígitos, de modo que
1 8 2
, por ejemplo, se trata como182
. Lo mismo podría funcionar para Perl al reemplazar los espacios con guiones bajos. No he agotado todo el espacio de búsqueda, por lo que puede haber mejores candidatos.Un programa puede ser alimentado a gp como
gp -q -f program.gp
, o interactivamente en la respuesta.Salida
Todos menos 4 valores están dentro del rango requerido, con 12 entradas duplicadas.
Actualizar
He terminado de procesar, hay seis 23 distintos, y solo uno 24 (como se lee por filas):
El programa que utilicé para el crujido está debajo. PARI / GP tiene capacidades limitadas de procesamiento de cadenas, así que trata principalmente con matrices de caracteres (aka
Vecsmall
). Los operadores probados son+
,-
,*
,\
(div piso),%
,;
(separador de expresión, esencialmente descartes todo antes de ella), y(espacio, como se describe anteriormente). El operador exponente
^
también podría agregarse, pero se vuelve demasiado lento para probar exhaustivamente.fuente
Deadfish , 18
Este fue realmente el primer idioma que probé antes de considerar operadores infix. Lo estoy publicando ahora por la pura hilaridad de la idea de que Deadfish podría ser útil para algo.
Para aquellos que no conocen Deadfish,
i
es incremental,s
es cuadrado yo
se emite, con el acumulador comenzando en 0 (también hay una cuarta instrucciónd
para la disminución que no se usa aquí). El hecho de que no tengamos impresión automática y necesitemos usarloo
es un gran inconveniente, pero sorprendentemente a Deadfish no le va demasiado mal aquí, considerando todo. Resulta que la ubicación óptima del operador de salida está en el medio.fuente
Python REPL y muchos más,
2223Observación clave: si colorea la cuadrícula como un tablero de ajedrez, la ruta alterna los colores de la cuadrícula a medida que avanza y comienza y termina en el mismo color.
Todavía fuerza bruta para mejorar.Intentar con+*%
(e incluso**
para los idiomas donde^
hay exponenciación) no mostró nada mejor, desafortunadamente. También intenté incluir operadores bit a bit y solo^
(xor) pareció ayudar levemente, pero la búsqueda tardó demasiado, así que me di por vencido.fuente
6+7*5%6%4
,6+7*4%6%5
y6+8*4%6%5
(de izquierda a derecha, de arriba a abajo), y nada más.+
y-
en las esquinas / centro? Dado que son operadores unarios y binarios, eso debería dar como resultado todas las expresiones válidas. Es poco probable que resulte en una mejor solución, pero al menos expande el espacio de búsqueda. Hmm, en realidad, podría ser un problema porque podrías terminar con secuencias de operadores.J, 15
Esto genera solo números válidos, pero muchos son duplicados. Los valores únicos son
17 11 16 28 31 23 13 10 21 33 18 24 22 29 27
. Definitivamente puede hacerlo mejor cambiando los operadores y los enteros involucrados.fuente
Yes
.> <>, 36 *
Si tienes la suerte!
Dado que el desafío no requiere que el código sea determinista, solo tenemos que demostrar que es posible (incluso si es improbable) devolver 36 números y hemos terminado.Fue bueno mientras duró, supongo.(Para aquellos que no están familiarizados con> <>, se puede encontrar una gran introducción aquí )
Decidí usar la instrucción "x" en> <>, que cambia la dirección de los punteros de instrucción a arriba, abajo, izquierda o derecha al azar. Dado que nuestro código solo será una línea, eso significa que solo podemos ver los casos cuando va hacia la derecha o hacia la izquierda, ya que si el puntero sube o baja, simplemente volverá a presionar la instrucción "x".
La instrucción "n" muestra el número en la parte superior de la pila y lo imprime. Sin embargo, si la pila está vacía y no hay nada que resaltar, se genera un error.
La instrucción "l" simplemente empuja la longitud de la pila sobre la pila (y por suerte para nosotros, no envía un error si la pila está vacía), por ejemplo, si la pila estuviera vacía y se llamaría "l", se empujaría 0 a la pila. Si ahora volviéramos a llamar "l", entonces, dado que la pila tiene un elemento (0), empujaría 1 a la parte superior de la pila y ahora eso significaría que habría dos cosas en la pila y eso significaría que si volviéramos a llamar a "l", empujaríamos 2 a la pila, etc. De modo que podemos usar "l" para empujar un número arbitrario a la pila mediante el método mostrado anteriormente.
Los ";" La instrucción termina el programa.
La idea de usar "x" es que, por ejemplo, si solo hubiera una "x" en el código (donde A, B, C, D son algunas instrucciones):
El programa ejecutaría A, luego B y luego C, y al llegar a "x" tendríamos dos posibilidades: el código continúa yendo hacia la derecha y toca ";" y sale o va a la izquierda y ejecuta C, luego B, luego A y luego D, y solo luego sale. Entonces, si nuestro código contiene una "x", el programa gana dos flujos de programa posibles de los cuales podemos elegir el programa más adecuado.
Si hay dos o más "x" es, entonces ganamos un número infinito de posibles flujos de programa.
Nuestro código tiene cinco "x" es, además cada uno de ellos está en una "celda inicial" de las rutas de Hamilton, lo que significa que cada programa comenzará con una "x", y cada programa tendrá la estructura:
Donde A, B, C, D pertenecen a {; , n, l, l} Esto significa que solo hay 12 programas únicos. Además, dado que siempre comenzamos con una "x", podemos ver el caso cuando el programa sale a la izquierda, por lo que los programas simétricos también pueden considerarse iguales. Hasta la simetría, solo hay 6 programas posibles diferentes. Solo 4 de ellos ocurren en los programas generados como caminos hamiltonianos:
Veamos el primer programa "xnxlxlx; x" si vamos directamente al primer paso, presionamos el comando de impresión que generará un error ya que no tenemos nada en la pila. Si vamos a la izquierda, presionamos el comando de finalización del programa. Por lo tanto, no podemos generar ningún número de estos programas.
El segundo programa, "xlxnxlx; x", es mucho más esperanzador, ya que al ir a la derecha al principio se pone un cero en la pila, si luego vamos a la izquierda en la próxima "x", nuestra pila gana un uno, luego yendo a la derecha nuevamente tenemos un 2 que luego podemos imprimir y continuar yendo a la derecha para finalizar el programa. Podemos observar que en realidad podemos imprimir cualquier número par , ya que en la parte "xlx" al principio podemos alcanzar un número de tamaño arbitrario yendo a la derecha, luego a la izquierda y a la derecha nuevamente una cierta cantidad de veces.
De manera similar, se puede ver que el tercer programa xnxlx; xlx puede generar cualquier número impar , yendo a la izquierda al principio y luego repitiendo la rutina "xlx" solo esta vez yendo a la izquierda, luego a la derecha y luego a la izquierda.
Y el cuarto programa es esencialmente el mismo que el segundo programa y puede generar cualquier número par .
Entonces, para los programas requeridos tenemos:
Son 4 programas que no pueden generar números, 20 que pueden generar cualquier número par, 16 que pueden generar cualquier número impar. Dado que hay exactamente 20 números pares y al menos 16 números impares en el rango de 1 a 40, entonces con una cierta probabilidad existe la posibilidad de que haya 36 números diferentes en el rango de 1 a 40 producidos por este bloque de código.
fuente
GolfScript, 8
Actualmente la solución de mayor puntuación. :PAGSFue agradable mientras duró.Programas
fuente
0)1#2#3(4
en 15. Hermosa simetría también.CJam, 14
Debajo de los programas de trabajo:
Los valores generados son: [1, 3, 4, 11, 13, 14, 20, 21, 22, 23, 24, 30, 31, 33]
fuente
dc (20)
32 salidas, 20 de ellas distintas (marcadas con un
$
)2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 14, 15, 16, 20, 22, 24, 25, 32, 34, 40
fuente