Expresa un número
En los años 60, los franceses inventaron el programa de televisión "Des Chiffres et des Lettres" (Dígitos y letras). El objetivo de la parte Dígitos del espectáculo era acercarse lo más posible a un determinado número objetivo de 3 dígitos, utilizando algunos números seleccionados al azar. Los concursantes podrían usar los siguientes operadores:
- concatenación (1 y 2 es 12)
- suma (1 + 2 es 3)
- resta (5 - 3 = 2)
- división (8/2 = 4); la división solo está permitida si el resultado es un número natural
- multiplicación (2 * 3 = 6)
- paréntesis, para anular la precedencia regular de las operaciones: 2 * (3 + 4) = 14
Cada número dado solo se puede usar una vez o en absoluto.
Por ejemplo, el número objetivo 728 puede coincidir exactamente con los números: 6, 10, 25, 75, 5 y 50 con la siguiente expresión:
75 * 10 - ( ( 6 + 5 ) * ( 50 / 25 ) ) = 750 - ( 11 * 2 ) = 750 - 22 = 728
En este desafío de código, se le da la tarea de encontrar una expresión lo más cerca posible de un determinado número objetivo. Como vivimos en el siglo XXI, introduciremos números objetivo más grandes y más números para trabajar que en los años 60.
Reglas
- Operadores permitidos: concatenación, +, -, /, *, (y)
- El operador de concatenación no tiene símbolo. Solo concatena los números.
- No hay "concatenación inversa". 69 es 69 y no se puede dividir en un 6 y un 9.
- El número objetivo es un entero positivo y tiene un máximo de 18 dígitos.
- Hay al menos dos números para trabajar y un máximo de 99 números. Estos números también son enteros positivos con un máximo de 18 dígitos.
- Es posible (en realidad, muy probablemente) que el número objetivo no se pueda expresar en términos de números y operadores. El objetivo es acercarse lo más posible.
- El programa debe finalizar en un tiempo razonable (unos minutos en una PC de escritorio moderna).
- Se aplican lagunas estándar.
- Es posible que su programa no esté optimizado para el conjunto de pruebas en la sección "puntaje" de este rompecabezas. Me reservo el derecho de cambiar el conjunto de prueba si sospecho que alguien está violando esta regla.
- Esto no es un codegolf.
Entrada
La entrada consiste en una matriz de números que pueden formatearse de cualquier manera conveniente. El primer número es el número objetivo. El resto de los números son los números con los que debe trabajar para formar el número objetivo.
Salida
Los requisitos para la salida son:
- Debe ser una cadena que consta de:
- cualquier subconjunto de los números de entrada (excepto el número objetivo)
- cualquier número de operadores
- Prefiero que la salida sea una sola línea sin espacios, pero si debe hacerlo, puede agregar espacios y nuevas líneas como mejor le parezca. Serán ignorados en el programa de control.
- La salida debe ser una expresión matemática válida.
Ejemplos
Para facilitar la lectura, todos estos ejemplos tienen una solución exacta y cada número de entrada se usa exactamente una vez.
Entrada: 1515483, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
Salida:111*111*(111+11+1)
Entrada: 153135, 1, 2, 3, 4, 5, 6, 7, 8, 9
Salida:123*(456+789)
Entrada: 8888888888, 9, 9, 9, 99, 99, 99, 999, 999, 999, 9999, 9999, 9999, 99999, 99999, 99999, 1
Salida:9*99*999*9999-9999999-999999-99999-99999-99999-9999-999-9-1
Entrada: 207901, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0
Salida:1+2*(3+4)*(5+6)*(7+8)*90
Entrada: 34943, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0
Salida: 1+2*(3+4*(5+6*(7+8*90)))
Pero también la salida válida es:34957-6-8
Puntuación
La puntuación de penalización de un programa es la suma de los errores relativos de las expresiones para el conjunto de pruebas a continuación.
Por ejemplo, si el valor objetivo es 125 y su expresión da 120, su puntaje de penalización es abs (1 - 120/125) = 0,04.
El programa con la puntuación más baja (error relativo total más bajo) gana. Si dos programas terminan por igual, la primera presentación gana.
Finalmente, el conjunto de pruebas (8 casos):
14142, 10, 11, 12, 13, 14, 15
48077691, 6, 9, 66, 69, 666, 669, 696, 699, 966, 969, 996, 999
333723173, 3, 3, 3, 33, 333, 3333, 33333, 333333, 3333333, 33333333, 333333333
589637567, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
8067171096, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199
78649377055, 0, 2, 6, 12, 20, 30, 42, 56, 72, 90, 110, 132, 156, 182, 210, 240, 272, 306, 342, 380, 420, 462, 506, 552, 600, 650, 702, 756, 812, 870, 930, 992
792787123866, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169
2423473942768, 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000, 100000, 2000000, 5000000, 10000000, 20000000, 50000000
Rompecabezas similares anteriores
Después de crear este rompecabezas y publicarlo en el sandbox, noté algo similar (¡pero no lo mismo!) En dos rompecabezas anteriores: aquí (sin soluciones) y aquí . Este acertijo es algo diferente, porque introduce el operador de concatenación, no busco ni encuentro exactamente y me gusta ver estrategias para acercarme a la solución sin fuerza bruta. Creo que es un reto.
fuente
Respuestas:
C ++ 17, puntaje .0086
Este programa tiene un puntaje de penalización no determinista debido a las carreras de subprocesos, por lo que estoy declarando en base a un promedio de tres carreras, cada una de las cuales manejó el conjunto de pruebas en menos de un minuto:
Aquí está el programa; La explicación se proporciona en los comentarios. Puede definir
CONCAT_NONE
reglas tradicionales de cuenta regresiva que no permitan la concatenación, oCONCAT_DIGITS
permitir la concatenación de los valores de entrada, pero no de ningún resultado intermedio. Por defecto, sin ninguna definida, se utilizan las reglas más liberales.Compilé esto usando GCC 6.2, usando
g++ -std=c++17 -fopenmp -march=native -O3
(junto con algunas opciones de depuración y advertencia).fuente
Python 2.7. Puntuación: 1,67039106
Entonces, decidí echarle un vistazo yo mismo. Nada muy elegante. Este programa clasifica los números en orden inverso (de mayor a menor) e intenta todos los operadores secuencialmente en los números. Increíblemente rápido, pero un rendimiento que merece ser reemplazado.
Aquí está el programa:
La salida para todos los casos de prueba es:
fuente