StickStack es un lenguaje de programación basado en pila muy simple con solo dos instrucciones:
|
empuja la longitud de la pila sobre la pila-
saca los dos elementos superiores de la pila y hace retroceder su diferencia (second topmost - topmost
)
Detalles del idioma
- La pila está vacía al inicio del programa.
- Todas las instrucciones se ejecutan secuencialmente de izquierda a derecha.
- Si hay menos de 2 números en la pila, la
-
instrucción es ilegal. - Al final de la ejecución, la pila debe contener exactamente un número .
Cualquier número entero puede ser generado por un programa StickStack. Por ejemplo:
|||--||-- generates the number 2 through the following stack states:
[]
[0]
[0, 1]
[0, 1, 2]
[0, -1]
[1]
[1, 1]
[1, 1, 2]
[1, -1]
[2]
Para evaluar su código StickStack puede usar este evaluador en línea (CJam) . (Gracias por @Martin por el código).
La tarea
Debe escribir un programa o función que proporcione un número entero como salidas de entrada o devuelva una cadena que representa un programa StickStack que genera el número dado.
Tanteo
- Su puntaje principal es la duración total de los programas StickStack para los siguientes casos de prueba. Puntaje más bajo es mejor.
- Su envío es válido solo si ejecutó su programa en todos los casos de prueba y contó su puntaje.
- Su puntaje secundario (desempate) es la duración de su función o programa generador.
Casos de prueba de entrada
(Cada número es un caso de prueba diferente).
-8607 -6615 -6439 -4596 -4195 -1285 -72 12 254 1331 3366 3956 5075 5518 5971 7184 7639 8630 9201 9730
Su programa debería funcionar para cualquier número entero (que su tipo de datos pueda manejar) no solo para los casos de prueba dados. Las soluciones para los números de prueba no deben codificarse en su programa. Si habrá dudas sobre la codificación, se cambiarán los números de prueba.
fuente
Respuestas:
Python 2 - 5188
Muy eficiente en cuanto al tiempo, y parece ser (probablemente) la solución óptima. Observé que un patrón como
|||||-|||-|-|-|------
(una solución óptima para 25)se puede delinear como
donde cada valor total al final es la suma de (el valor de cada nivel multiplicado por el número de '|' s). Entonces, por ejemplo arriba, tenemos
-1*1 + 2*1 - 3*1 + 4*2 - 5*1 + 6*4 = 25
. Usando esto, escribí esta solución que produce resultados similares a otras respuestas, y en un tiempo trivial.Creo que esta es la solución óptima, ya que pruebo todas las alturas óptimas posibles (en realidad pruebo muchas más de las necesarias) y estoy bastante seguro de que la solución siempre involucra como máximo una capa con dos '|' además de la última (puedo garantice esto para números positivos pero no esté 100% seguro de los negativos).
Aquí está el código que usé para probarlo
fuente
Java, 5208
524053066152Esta es una función recursiva que se acerca al objetivo, con casos básicos para cuando se acerca a 5 (que a menudo es solo un paso).
Básicamente, se puede obtener
(a*b)+(a/2)
de(a+b)*2
palos con un patrón simple. Sia
es impar, el resultado será negativo, por lo que lleva a una lógica extraña.Esto toma aproximadamente un minuto para 2 31 -1, con una longitud de 185,367 como resultado. Sin embargo, funciona casi instantáneamente para todos los casos de prueba. Se puntúa
4*(sqrt|n|)
en promedio. El caso de prueba individual más largo es el9730
que da como resultado una pila de barras de 397 de longitud:Actualizar:
Encontró una forma más corta de sumar / restar del patrón básico. De vuelta a la cabeza (por ahora)!
Con un arnés y casos de prueba:
Jugará golf (más) en el improbable caso de un empate exacto.
fuente
JavaScript (ES6) 5296
6572Editar Como dije en mi explicación, no soy bueno resolviendo ecuaciones enteras. Mi suposición del valor b no fue tan buena, por lo que he ampliado el rango de valores para probar.
Y (wow) estoy liderando por ahora.Edit 2 Bug fix, mismos resultados. Tengo una idea, pero no puedo concretarla.
Bytes: ~ 460, bastante golfizado. Funciona en enteros de 32 bits, tiempo de ejecución cercano a 0.
El código es la función F (oculta en el fragmento) a continuación.
Ejecute el fragmento para probar (en FireFox).
Mostrar fragmento de código
Explicación
Números positivos, para empezar. Comience con una "base" (intente en CJam si lo desea, espacios permitidos)
Resumen: 1 barra, luego b * 2 barras, luego b * 2 guiones
Luego intente agregar uno o más '- |' en la división del medio Cada uno agrega un incremento fijo que es dos veces la base inicial y puede repetirse muchas veces. Entonces tenemos una fórmula, con b = base y r = factor de repetición incremental
¿Ver? El valor de los addes aumenta rápidamente y cada adición sigue siendo solo 2 caracteres. El incremento base da 4 caracteres más cada vez.
Dado v y nuestra fórmula v = b + r * 2 * b, necesitamos encontrar 2 ints by r. No soy un experto en este tipo de ecuaciones, pero b = int sqrt (v / 2) es una buena suposición inicial.
Luego tenemos una r y b que juntas dan un valor cercano a v. Alcanzamos v exactamente con incremento repetido (|| -) o decremento (| -).
Siga el mismo razonamiento para los números negativos, por desgracia, la fórmula es similar pero no igual.
fuente
JavaScript, 398710
94 bytes / caracteres de código
¡Se me ocurrió una solución! ... y luego leí la respuesta de Sparr y fue exactamente la misma.
Pensé que lo publicaría de todos modos, ya que js permite un poco menos de caracteres.
Aquí hay una versión no minificada del código:
fuente
Python, 398710 (71 bytes)
La solución más simple posible, creo. Utiliza 4 * n (+/- 1) caracteres de stickstack para representar n.
fuente