StickStack Numbers

Question

StickStack is a very simple stack-based programming language with only two instructions:

• | pushes the length of the stack onto the stack
• - pops the top two elements from the stack and pushes back their difference (second topmost - topmost)

Language details

• The stack is empty at the start of the program.
• All instructions are executed sequentially from left to right.
• If there are less than 2 numbers on the stack the - instruction is illegal.
• At the end of the execution the stack should contain exactly one number.

Any integer can be generated by a StickStack program. For example:

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

To evaluate your StickStack code you can use this online (CJam) evaluator. (Thanks for @Martin for the code.)

The task

You should write a program or function which given an integer number as input outputs or returns a string representing a StickStack program which outputs the given number.

Scoring

• Your primary score is the total length of the StickStack programs for the below given test cases. Lower score is better.
• Your submission is valid only if you ran your program on all the test cases and counted your score.
• Your secondary (tiebreaker) score is the length of your generating program or function.

Input test cases

(Each number is a different test case.)

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

Your program should work for any integers (which your data-type can handle) not just for the given test cases. The solutions for the test numbers should not be hardcoded into your program. If there will be doubt of hardcoding the test numbers will be changed.

Answer 1

Python 2 - 5188

Quite efficient time-wise, and seems to be (probably) the optimal solution. I observed that a pattern such as

|||||-|||-|-|-|------ (an optimal solution for 25)

can be delineated as

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

where each the total value at the end is the sum of (each level's value times the number of '|'s ). So for example above, we have -1*1 + 2*1 - 3*1 + 4*2 - 5*1 + 6*4 = 25. Using this I wrote this solution which produces similar output to other answers, and in a trivial amount of time.

I believe this is the optimal solution, as I test every possible optimal height (I actually test many more than necessary) and I'm pretty sure the solution always involves at most one layer with two '|'s besides the last (I can guarantee this for positive numbers but not 100% sure about negatives).

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

Here is the code I used to test it

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

Answer 2

Java, 5208 5240 5306 6152

This is a recursive function that edges closer to the target, with base cases for when it gets within 5 (which is often only one step).

Basically, you can get (a*b)+(a/2) for (a+b)*2 sticks with a simple pattern. If a is odd, the result will be negative, so that leads to some weird logic.

This takes a minute or so for 2³¹-1, with a length of 185,367 as the result. It works almost instantly for all test cases, though. It scores 4*(sqrt|n|) on average. The longest individual test case is 9730, which results in a 397-length stick stack:

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

Update:

Found a shorter way to add/subtract from the basic pattern. Back in the lead (for now)!

---

With a harness and test cases:

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

Will golf (more) in the unlikely event of an exact tie.

Answer 3

JavaScript (ES6) 5296 6572

Edit As I said in my explanation, I'm not good at solving integer equations. My guess of b value was not so good, so I have widened the range of values to try. And (wow) I'm leading by now.

Edit 2 Bug fix, same results. I have an idea, but cant't nail it down.

Bytes: ~460, quite golfed. It works on 32 bit integers, run time near 0.

The code is the F function (hidden in the snippet) below.
Run the snippet to test (in 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>

Explanation

Positive numbers, to begin with. Start with a "base" (try in CJam if you like, spaces allowed)

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

Summary: 1 stick, then b*2 sticks, then b*2 dashes

Then try adding one or more '-|' in the middle split. Each one add a fixed increment that is two time the starting base and can be repeated many times. So we have a formula, with b=base and r=increment repeat factor

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

See? The addes value increases quicky and each addition still is only 2 chars. The base increment gives 4 more chars each time.

Given v and our formula v=b+r*2*b, we need to find 2 ints b and r. I'not an expert in this kind of equation, but b=int sqrt(v/2) is a good starting guess.

Then we have an r and b that together give a value near v. We reach v exactly with repeated increment (||--) or decrement (|-).

Follow the same reasoning for negative numbers, alas the formula is similar but not equal.

Answer 4

Python, 398710 (71 bytes)

Simplest possible solution, I think. Uses 4*n (+/-1) characters of stickstack to represent n.

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

Answer 5

JavaScript, 398710

94 bytes/chars of code

I came up with a solution! ... and then read Sparr's answer and it was exactly the same.

Figured I would post it anyway, as js allows for slightly fewer chars.

Here's an unminified version of the code:

function p(a){
    s = "";
    if(a<=0){
        for(i=0; i<-2*a-1;i++)
            s="|"+s+"-";
        return "|"+s;
    }
    return "|"+p(0-a)+"-";
}