StickStack est un langage de programmation basé sur une pile très simple avec seulement deux instructions:

• | pousse la longueur de la pile sur la pile
• -sort les deux premiers éléments de la pile et repousse leur différence ( second topmost - topmost)

Détails sur la langue

• La pile est vide au début du programme.
• Toutes les instructions sont exécutées séquentiellement de gauche à droite.
• S'il y a moins de 2 nombres sur la pile, l' -instruction est illégale.
• À la fin de l'exécution, la pile doit contenir exactement un numéro .

Tout entier peut être généré par un programme StickStack. Par exemple:

|||--||-- 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]    

Pour évaluer votre code StickStack, vous pouvez utiliser cet évaluateur en ligne (CJam) . (Merci pour @Martin pour le code.)

La tâche

Vous devez écrire un programme ou une fonction qui a donné un nombre entier comme sorties d'entrée ou renvoie une chaîne représentant un programme StickStack qui sort le nombre donné.

Notation

• Votre score principal est la durée totale des programmes StickStack pour les cas de test donnés ci-dessous. Un score plus bas est meilleur.
• Votre soumission n'est valide que si vous avez exécuté votre programme sur tous les cas de test et compté votre score.
• Votre score secondaire (bris d'égalité) est la durée de votre programme ou fonction de génération.

Cas de test d'entrée

(Chaque numéro est un cas de test différent.)

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

Votre programme devrait fonctionner pour tous les entiers (que votre type de données peut gérer) et pas seulement pour les cas de test donnés. Les solutions pour les numéros de test ne doivent pas être codées en dur dans votre programme. En cas de doute sur le codage en dur, les numéros de test seront modifiés.

Python 2 - 5188

Assez efficace dans le temps, et semble être (probablement) la solution optimale. J'ai observé qu'un motif tel que

|||||-|||-|-|-|------ (une solution optimale pour 25)

peut être délimité comme

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

où chaque valeur totale à la fin est la somme de (la valeur de chaque niveau multipliée par le nombre de «|»). Ainsi, par exemple ci-dessus, nous avons -1*1 + 2*1 - 3*1 + 4*2 - 5*1 + 6*4 = 25. En utilisant cela, j'ai écrit cette solution qui produit une sortie similaire à d'autres réponses, et en un temps trivial.

Je crois que c'est la solution optimale, car je teste toutes les hauteurs optimales possibles (j'en teste beaucoup plus que nécessaire) et je suis presque sûr que la solution implique toujours au plus une couche avec deux '|' en plus de la dernière (je peux garantir cela pour les nombres positifs mais pas sûr à 100% des négatifs).

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

Voici le code que j'ai utilisé pour le tester

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

Il s'agit d'une fonction récursive qui se rapproche de la cible, avec des cas de base pour quand elle se rapproche de 5 (ce qui n'est souvent qu'une étape).

Fondamentalement, vous pouvez obtenir (a*b)+(a/2)des (a+b)*2bâtons avec un motif simple. Sia est impair, le résultat sera négatif, ce qui conduit à une logique étrange.

Cela prend environ une minute pour 2 ³¹ -1, avec pour résultat une longueur de 185 367. Cela fonctionne cependant presque instantanément pour tous les cas de test. Il marque 4*(sqrt|n|)en moyenne. Le cas de test individuel le plus long est 9730, ce qui donne une pile de bâtons de 397 longueurs:

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

Mise à jour:

Trouvé un moyen plus court pour ajouter / soustraire du modèle de base. De retour en tête (pour l'instant)!

Avec un harnais et des cas de test:

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

Jouera au golf (plus) dans le cas peu probable d'une égalité exacte.

JavaScript (ES6) 5296 6572

Modifier Comme je l'ai dit dans mon explication, je ne suis pas bon pour résoudre des équations entières. Ma supposition de la valeur b n'était pas si bonne, j'ai donc élargi la plage de valeurs pour essayer. Et (wow) je mène maintenant.

Edit 2 Correction de bogue, mêmes résultats. J'ai une idée, mais je ne peux pas la clouer.

Octets: ~ 460, assez golfé. Il fonctionne sur des entiers 32 bits, un temps d'exécution proche de 0.

Le code est la fonction F (masquée dans l'extrait) ci-dessous.
Exécutez l'extrait de code à tester (dans 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>

Explication

Des nombres positifs, pour commencer. Commencez avec une "base" (essayez dans CJam si vous le souhaitez, espaces autorisés)

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

Résumé: 1 bâton, puis b * 2 bâtons, puis b * 2 tirets

Essayez ensuite d'ajouter un ou plusieurs '- |' dans la fente du milieu. Chacun ajoute un incrément fixe qui est deux fois la base de départ et peut être répété plusieurs fois. Nous avons donc une formule, avec b = base et r = incrémenter le facteur de répétition

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

Voir? La valeur ajoutée augmente rapidement et chaque ajout ne fait toujours que 2 caractères. L'incrément de base donne 4 caractères supplémentaires à chaque fois.

Étant donné v et notre formule v = b + r * 2 * b, nous devons trouver 2 entiers b et r. Je ne suis pas un expert dans ce genre d'équation, mais b = int sqrt (v / 2) est une bonne supposition de départ.

Nous avons alors un r et un b qui donnent ensemble une valeur proche de v. Nous atteignons v exactement avec un incrément répété (|| -) ou un décrément (| -).

Suivez le même raisonnement pour les nombres négatifs, hélas la formule est similaire mais pas égale.

JavaScript, 398710

94 octets / caractères de code

J'ai trouvé une solution! ... puis j'ai lu la réponse de Sparr et c'était exactement la même chose.

Je pensais que je le publierais de toute façon, car js permet un peu moins de caractères.

Voici une version non réduite du code:

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

Je pense que la solution la plus simple possible. Utilise 4 * n (+/- 1) caractères de stickstack pour représenter n.

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