O StickStack é uma linguagem de programação muito simples, baseada em pilha, com apenas duas instruções:

• | empurra o comprimento da pilha para a pilha
• -exibe os dois principais elementos da pilha e diminui a diferença ( second topmost - topmost)

Detalhes do idioma

• A pilha está vazia no início do programa.
• Todas as instruções são executadas seqüencialmente da esquerda para a direita.
• Se houver menos de 2 números na pilha, a -instrução é ilegal.
• No final da execução, a pilha deve conter exatamente um número .

Qualquer número inteiro pode ser gerado por um programa StickStack. Por exemplo:

|||--||-- 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 avaliar seu código StickStack, você pode usar este avaliador online (CJam) . (Obrigado por @Martin pelo código.)

A tarefa

Você deve escrever um programa ou função que tenha fornecido um número inteiro como saída ou retorne uma string que representa um programa StickStack que gera o número fornecido.

Pontuação

• Sua pontuação principal é a duração total dos programas StickStack para os casos de teste abaixo. Menor pontuação é melhor.
• Seu envio é válido apenas se você executou seu programa em todos os casos de teste e contou sua pontuação.
• Sua pontuação secundária (desempate) é a duração do seu programa ou função de geração.

Casos de teste de entrada

(Cada número é um caso de teste diferente.)

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

Seu programa deve funcionar para quaisquer números inteiros (que seu tipo de dados possa manipular) e não apenas para os casos de teste fornecidos. As soluções para os números de teste não devem ser codificadas no seu programa. Se houver dúvida de codificação, os números de teste serão alterados.

Python 2 - 5188

Bastante eficiente em termos de tempo e parece (provavelmente) a solução ideal. Eu observei que um padrão como

|||||-|||-|-|-|------ (uma solução ideal para 25)

pode ser delineado como

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

onde cada valor total no final é a soma de (o valor de cada nível multiplicado pelo número de '|'). Então, por exemplo acima, nós temos -1*1 + 2*1 - 3*1 + 4*2 - 5*1 + 6*4 = 25. Usando isso, escrevi esta solução que produz resultados semelhantes a outras respostas e em uma quantidade trivial de tempo.

Acredito que esta é a solução ideal, pois testo todas as alturas ideais possíveis (na verdade, testo muito mais que o necessário) e tenho certeza de que a solução sempre envolve no máximo uma camada com dois '|' s além do último (eu posso garanta isso para números positivos, mas não 100% certo de 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))

Aqui está o código que eu usei para testá-lo

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

Java, 5208 5240 5306 6152

Essa é uma função recursiva que se aproxima do alvo, com casos básicos para quando chega a 5 (o que geralmente é apenas uma etapa).

Basicamente, você pode obter (a*b)+(a/2)para (a+b)*2varas com um padrão simples. Se afor ímpar, o resultado será negativo, o que leva a uma lógica estranha.

Isso leva um minuto ou mais para 2 ³¹ -1, com uma duração de 185.367 como resultado. Porém, ele funciona quase instantaneamente em todos os casos de teste. Ele pontua 4*(sqrt|n|)em média. O caso de teste individual mais longo é o 9730que resulta em uma pilha de 397 pés:

|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||-|||||||||||||||||||||-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|--------------------------------------------------------------------------------------------------|-

Atualizar:

Foi encontrada uma maneira mais curta de adicionar / subtrair do padrão básico. De volta à liderança (por enquanto)!

Com um chicote de fios e casos de teste:

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);
    }
}

Golf (mais) no improvável evento de um empate exato.

JavaScript (ES6) 5296 6572

Editar Como eu disse na minha explicação, não sou bom em resolver equações inteiras. Meu palpite sobre o valor de b não foi tão bom, então ampliei o intervalo de valores para tentar. E (uau) eu estou liderando agora.

Editar 2 Correção de bug, mesmos resultados. Eu tenho uma ideia, mas não posso dizer nada.

Bytes: ~ 460, bastante jogado. Funciona em números inteiros de 32 bits, com tempo de execução próximo de 0.

O código é a função F (oculta no snippet) abaixo.
Execute o snippet para testar (no FireFox).

F=n=>{
  l=1e8;
  v=Math.sqrt(n>0?n:-n)/2|0;
  p='|';
  if (n)
    for(b=v>>2|1;b<=v+v+9;b++)
    [w=n>0?(n-b)/(2*b)|0:(-n-b)/(2*b-1)|0,w+1].map(r=>(
      t=2*r*b+b, d=n-t, n<0?t=r-t:0,
      q=n>0?'|'.repeat(2*b+1)+'-|'.repeat(r)+'-'.repeat(2*b)
      :'|'.repeat(2*b)+'-|'.repeat(r)+'-'.repeat(2*b-1),
      q+=t<n?'||--'.repeat(n-t):'|-'.repeat(t-n),
      m=q.length,m<l&&(l=m,p=q)
    ))
  return p
}

// Test --------------------------------------------

FreeTest=_=>{var n=IN.value|0,s=F(n)
  LEN.value=s.length,CK.value=Check(s),ST.innerHTML=s}
Check=t=>{var s=[],a,b;
  [...t].forEach(c=>c=='|'? s.push(s.length):(b=s.pop(),a=s.pop(),s.push(a-b)))
  return s.pop()}

ot=[];
tot=0;
[-8607,-6615,-6439,-4596,-4195,-1285,-72,
 12,254,1331,3366,3956,5075,5518,5971,7184,7639,8630,9201,9730]
.forEach(x=>{
  s=F(x), k=Check(s), l=s.length, tot+=l,
  ot.push(`<tr><td>${x}</td><td>${l}</td><td>${k}</td><td class='S'>${s}</td></tr>`)
})
ot.push(`<tr><th>Total:</th><th>${tot}</th></tr>`)
TOUT.innerHTML=ot.join("")

td.S { font-size: 8px; font-family: courier}
pre { font-size: 8px; }
input { width: 6em }

Free test: <input id="IN" value=1073741824>
<button onclick="FreeTest()">-></button>
Len:<input readonly id="LEN"> Check:<input readonly id="CK">
<pre id=ST></pre>
<table><thead>
<tr><th>Number</th><th>Len</th><th>Check</th><th>Sticks</th></tr>
</thead>
<tbody id=TOUT></tbody>  
</table>

Explicação

Números positivos, para começar. Comece com uma "base" (tente no CJam, se quiser, espaços permitidos)

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

Resumo: 1 stick, depois b * 2 sticks e, em seguida, b * 2 traços

Em seguida, tente adicionar um ou mais '- |' na divisão do meio. Cada um adiciona um incremento fixo que é duas vezes a base inicial e pode ser repetido várias vezes. Portanto, temos uma fórmula, com b = base er = incremento do fator de repetição

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

Vejo? O valor dos addes aumenta rapidamente e cada adição ainda tem apenas 2 caracteres. O incremento base fornece mais 4 caracteres por vez.

Dado v e nossa fórmula v = b + r * 2 * b, precisamos encontrar 2 ints b e r. Não sou especialista nesse tipo de equação, mas b = int sqrt (v / 2) é um bom palpite inicial.

Então temos um r e b que juntos dão um valor próximo de v. Atingimos v exatamente com incremento repetido (|| -) ou decremento (| -).

Siga o mesmo raciocínio para números negativos, infelizmente a fórmula é semelhante, mas não é igual.

JavaScript, 398710

94 bytes / caracteres de código

Eu vim com uma solução! ... e depois leia a resposta de Sparr e era exatamente a mesma.

Imaginei que eu publicaria de qualquer maneira, já que o js permite um pouco menos de caracteres.

Aqui está uma versão não minificada do 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)+"-";
}

Python, 398710 (71 bytes)

Solução mais simples possível, eu acho. Usa 4 * n (+/- 1) caracteres do stickstack para representar n.

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