StickStack Numbers

22

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.

randomra
fuente
Sugiero agregar una cláusula que diga "Y se ejecuta en un tiempo razonable" para evitar la fuerza bruta.
@Reticalidad que está implícito en "válido solo si ejecutó su programa en todos los casos de prueba"
edc65

Respuestas:

7

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

 0  |
-1  |                  
+2   |                 -
-3    |               -
+4     | |           -
-5      - |         -
+6         | | | | -
-7          - - - -

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).

def solution(num):
    if num == 0:
        return '|'

    neg = num<0
    num = abs(num)
    high = int(num**0.5)

    def sub(high):
        counts = [1]*high
        total = num - (high+neg)/2

        if total%high == 0:
            counts[-1] += total/high
        else:
            counts[-1] += total/high
            if (total%high)%2==1 and not neg:
                counts[-1] += 1
                counts[-(total%high)-1] += 1
            elif (total%high)%2==0 and neg:
                counts[(total%high)-2] += 1
                counts[0] += 1
            else:
                counts[total%high-1] += 1

        string = ""
        for c in counts[::-1]:
            string = '|-'*(c-1)+'|'+string+'-'
        return '|'+string

    return min((sub(h) for h in range(2-neg,2*high+2,2)), key=lambda s: len(s))

Aquí está el código que usé para probarlo

string = "-8607 -6615 -6439 -4596 -4195 -1285 -72 12 254 1331 3366 3956 5075 5518 5971 7184 7639 8630 9201 9730"
total = 0

def string_to_binary(string):
    total = 0
    for i,char in enumerate(string[::-1]):
        total += (char=='|')*(2**i)
    return total

def stickstack(bits,length):
    stack = []
    for i in range(length):
        d,bits = divmod(bits,2**(length-i-1))
        if d == 1:
            stack.append(len(stack))
        else:
            stack[-2] -= stack[-1]
            stack = stack[:-1]
    return stack

for num in string.split():
    s = solution(int(num))
    print '%s:' % num
    print s
    result = stickstack(string_to_binary(s),len(s))
    print 'Result: %s' % result
    print 'Length: %s' % len(s)
    total += len(s)
    print

print 'Total length: %s' % total
KSab
fuente
2
¡Gran solución! Creo que la puntuación es óptima (según mi cálculo de fuerza bruta) y según su descripción, creo que su algoritmo siempre ofrece las mejores soluciones.
randomra
@randomra Creo que es probable que así sea, pero solo fui forzado hasta aproximadamente +/- 100, así que no estaba listo para decir que era necesariamente el mejor, pero ahora que lo pienso, no puedo ver cómo se podría hacer mejor.
KSab
+1 muy agradable. ¿Cómo puedo probarlo? Que pyton (No soy un pitonista, solo tengo accidentalmente un python 3.4 instalado en mi computadora portátil).
edc65
@ edc65 agregué código para probarlo; también esto está usando Python 2.7, por lo que cosas como las declaraciones de impresión no funcionarán con Python 3
KSab
Por lo que vale, puedo confirmar que este resultado es óptimo: probé una solución de fuerza bruta (un BFS de hecho), verificando hasta una longitud de 450 (y aún funcionando). Mismos resultados tuyos.
edc65
12

Java, 5208 5240 5306 6152

Esta 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)*2palos con un patrón simple. Si aes 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 el 9730que 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:

import static java.lang.Math.*;

public class StickStacker {

    public static void main(String[] args){
        StickStacker stacker = new StickStacker(); 
        int tests[] = {-8607,-6615,-6439,-4596,-4195,-1285,-72,12,254,1331,3366,3956,5075,5518,5971,7184,7639,8630,9201,9730};
        int sum = 0;
        for(int test : tests){
            String sticks = stacker.stickStack3(test);
            sum += sticks.length();
            System.out.println("In: " + test + "\t\tLength: " + sticks.length());
            System.out.println(sticks+"\n");
        }
        System.out.println("\n\nTotal: "+sum);          
    }

    String stickStack3(int n){return"|"+k(n);}
    String k(int n){
        String o="";
        int q=(int)sqrt(abs(n)),a,b,d=1,e=0,c=1<<30,
        z[]={232,170,42,10,2,0,12,210,52,844,212};
        a=n>0?q:-q;
        a-=n>0?a%2<1?0:1:a%2<0?0:-1;

        for(b=0;b<abs(a)+10;b++)
            if(abs(n-(a*b+a/2-(n>0?0:1)))<abs(a)&&abs(a)+b<c){
                    c=abs(a)+b;
                    d=a;e=b;
            }

        for(a=0;a++<e;)o+="-|";
        for(a=0;a++<abs(d);)o="|"+o+"-";

        c=n-(d*e+d/2-(n>0?0:1));
        if(c>0&&c<abs(d)){
            if(c%2==0)
                o=o.substring(0,c)+"-|"+o.substring(c);
            else
                o=o.substring(0,c+1)+"-|"+o.substring(c+1)+"|-";
            c=0;
        }else if(c<0&-c<abs(d)){
            if(c%2!=0)
                o=o.substring(0,-c)+"-|"+o.substring(-c);
            else
                o=o.substring(0,-c-1)+"-|"+o.substring(-c-1)+"|-";  
            c=0;
        }

        return n==0?"":n<6&&n>-6?
                Long.toBinaryString(z[n+5])
                .replaceAll("0","-")
                .replaceAll("1","|"):
                o+k(c);
    }
}

Jugará golf (más) en el improbable caso de un empate exacto.

Geobits
fuente
¿Estás seguro de tu puntaje de 2 ^ 31? Mi puntaje para 2 ^ 30 es 131099 y 185369 para 2 ^ 31-1.
edc65
@ edc65 Debo haberlo escrito mal. Pensé que parecía un poco bajo ... De todos modos, gracias por notarlo y dar algo de competencia. Ahora es el momento de ver si puedo hacerlo mejor :)
Geobits
4

JavaScript (ES6) 5296 6572

Editar 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).

Explicación

Números positivos, para empezar. Comience con una "base" (intente en CJam si lo desea, espacios permitidos)

| gives 0  
||| -- gives 1
||||| ---- gives 2
||||||| ------ gives 3 

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

v=b+r*2*b

b=1, r=0 to 3, inc=2
| || -- 1 
| || -| -- 3 
| || -| -| -- 5 
| || -| -| -| -- 7

b=3, r=0 to 3, inc=6
| |||||| ------ 3
| |||||| -| ------ 9
| |||||| -| -| ------ 15
| |||||| -| -| -| ------ 21

¿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.

edc65
fuente
1

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:

function p(a){
    s = "";
    if(a<=0){
        for(i=0; i<-2*a-1;i++)
            s="|"+s+"-";
        return "|"+s;
    }
    return "|"+p(0-a)+"-";
}
Nate Young
fuente
1
ok, si estamos jugando al golf con las soluciones 398710, ¡sigue jugando! Sin embargo, alguien vendrá con cjam o pyth y nos golpeará a los dos :(
Sparr
1

Python, 398710 (71 bytes)

La solución más simple posible, creo. Utiliza 4 * n (+/- 1) caracteres de stickstack para representar n.

def s(n):return'|'*(n*2+1)+'-'*n*2 if n>=0 else'|'*(n*-2)+'-'*(n*-2-1)
Sparr
fuente