Los números de paréntesis proporcionan una manera simple de expresar enteros grandes utilizando solo el corchete izquierdo, el espacio y el corchete derecho ( [ ]).
Un número de paréntesis se define como una cadena de uno o más pares de paréntesis coincidentes [...]llamados fragmentos , cada uno separado de sus vecinos por cero o más espacios.
El número de espacios entre cada fragmento define la hiperoperación entre ellos. Sin espacios significa suma, 1 espacio significa multiplicación, 2 espacios significa exponenciación, 3 espacios significa tetración , y así sucesivamente. Las hiperoperaciones de orden superior tienen prioridad, por lo que la tetración ocurre antes de la exponenciación, la exponenciación ocurre antes de la multiplicación, etc. También son asociativas a la derecha, por lo que a^b^cse calcula como a^(b^c). (Pero a^b*ctodavía está (a^b)*c).
Cada fragmento puede estar vacío ( []) o contener otro número de paréntesis. Los fragmentos vacíos tienen el valor 0. Los fragmentos no vacíos tienen el valor de su número de soporte contenido más 1.
Ejemplos: ( ^^es tetración, ^^^es pentación )
[[]]tiene valor 1 porque es 0 ([]) incrementado en 1[[[]]]tiene valor 2 pero también lo tiene[[]][[]]ya que[[]]se agregan los dos ( )[[[]]] [[[[]]] [[[[]]]]][[[]]]tiene valor 20 = (2 * ((2 ^ 3) +1)) + 2[[[]]] [[[[]]]]tiene valor 65536 = 2 ^^^ 3 = 2 ^^ (2 ^^ 2) = 2 ^^ 4 == 2 ^ (2 ^ (2 ^ 2))[[[[]]]] [[[]]] [[]]tiene valor 7625597484987 = 3 ^^^ (2 ^^^ 1) = 3 ^^^ 2 = 3 ^^ 3 = 3 ^ (3 ^ 3)
En números de paréntesis válidos:
- Nunca habrá espacios iniciales o finales.
- Siempre habrá al menos un par de paréntesis coincidentes.
- Todos los corchetes izquierdos tendrán un corchete derecho a juego.
- Un espacio nunca aparecerá directamente a la derecha
[ni a la izquierda de]. - El valor siempre es un entero no negativo.
Desafío
Tenga en cuenta que puede haber muchas formas para un número de paréntesis que den el mismo valor. [[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]y [[[]]] [[[[]]]]ambos representan 16, pero el último es mucho más corto.
Su desafío es escribir un algoritmo que intente encontrar la representación de número de soporte más corta de un valor dado. Por ejemplo, creo que la forma más corta de representar 16 es con 17 caracteres como [[[]]] [[[[]]]].
Puntuación (actualizada)
Sea S el conjunto de enteros del 1 al 256 (inclusive), así como los siguientes diez valores:
8191 13071 524287 2147483647 1449565302 1746268229 126528612 778085967 1553783038 997599288
(Los primeros 4 son primos de Mersenne, el resto son aleatorios).
La presentación que genera el conjunto más corto de números de paréntesis para todo en S ganará. Su puntaje es la suma de las longitudes de sus números de paréntesis para todos los valores en S (más pequeño es mejor).
Con su código, envíe una lista de sus números de paréntesis para todos los S , el orden exacto no es muy importante. p.ej:
1=[[]]
2=[[[]]]
3=[[[[]]]]
...
2147483647=[...]
...
(Sé que este no es el método de puntuación óptimo, pero no estoy configurado para ejecutar un montón de pruebas heurísticas aleatorias en cada envío. Lo sentimos :()
Reglas
- Es posible que no codificar los números de soporte, además de las soluciones incrementales triviales (
[], [[]], [[[]]], ...). Su programa realmente debe estar buscando representaciones óptimamente cortas. (Aunque los resultados pueden ser subóptimos). - Su algoritmo debería funcionar para todos los enteros no negativos por debajo de 2,147,483,648 (2 ^ 31). El usuario no puede centrarse específicamente en los valores de S .
- Para cualquier entrada en particular, su algoritmo debe ejecutarse como máximo 10 minutos en una computadora moderna decente (~ procesador de 2.5Ghz, ~ 6GB de RAM).
- En la (aparentemente) rara posibilidad de empate, gana la presentación más votada.
- Si copia otra solución o la revisa sin atribución, será descalificado.
fuente
Respuestas:
Python 11455b
Esta solución adopta un enfoque codicioso para encontrar formas de desglosar los números primos, en lugar de un enfoque exhaustivo. Necesito 9875b para 1-256 en comparación con 8181 para la solución probablemente óptima de Martin en ese espacio.
Una tabla más grande de resultados de multiplicación y exponenciación produce ligeras mejoras en los casos de prueba más grandes. La solución a continuación tomó aproximadamente 7 minutos. Aumentar el tiempo de ejecución más allá de 30 minutos tiene un impacto mínimo en la salida.
Yo, como Martin, tuve un problema de precedencia. Mi solución para restringir la selección de operaciones puede no ser óptima.
Salida:
fuente
Mathematica
Nota: Este algoritmo nunca podrá acercarse a los números de prueba más grandes. Necesitaría un enfoque sustancialmente diferente, por lo que lo dejaré como está para que otros verifiquen sus números más bajos. Puede considerar este envío inválido.
Aquí hay un comienzo para los primeros 256 números (los otros se agregaron después de que comencé, y probablemente necesito encontrar una solución separada para esos)
La longitud total de los primeros 256 números es de 7963 caracteres. No sé si esto es óptimo.
Ignorando la adición, los resultados para 8191 y 13071 se encontraron en unos segundos y 524387 en un par de minutos como
a 164 personajes juntos.
Aquí está el código:
Utilicé una búsqueda exhaustiva hasta la exponenciación. No hay operaciones de tetración ni de orden superior. Acabo de probar las operaciones de orden superior de forma manual, y solo hay unas pocas combinaciones que realmente producen números por debajo de 2 31 , por lo que simplemente codifiqué las que funcionan.
Editar: mi solución anterior no se preocupó por la precedencia, solo reunió todo.
Ahora creo que mi nuevo código soluciona eso,pero ninguno de los primeros 256 números ha cambiado, ni 8191 (que era válido antes, lo verifiqué) ... y es demasiado tarde para decir en este momento si mi código realmente lo arregló . Mañana volveré a echar un vistazo y también agregaré una explicación, porque ahora, con la comprobación de precedencia, es un poco complicado (aunque espero que reduzca el tiempo de búsqueda).Editar: Ok, hubo algunos errores como se esperaba. Creo que lo arreglé ahora, aumentando la longitud total de 1 - 256 a 7963 . No estoy seguro de que esto sea óptimo por más tiempo, porque podría ser posible encontrar soluciones más cortas de partes subóptimas si permiten operaciones de orden superior. Seguirá una explicación cuando logre limpiar un poco el código.
fuente
Python 9219b
Esta es mi segunda entrada. Comencé desde cero y probé una nueva disposición de los datos, incluido el uso del paquete blist para listas ordenadas y dictados, y algunos enfoques nuevos para encontrar grandes soluciones. Creo que tengo un óptimo 1-256. El aumento del tiempo de ejecución de 30 a 4 m acortó los grandes casos de prueba en aproximadamente 30 bytes.
Salida:
7944b para 1-256
1275b para los casos grandes
fuente