22
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I suggest adding a clause that says "And runs in a reasonable amount of time" to prevent brute-force. \$\endgroup\$ – user34736 May 4 '15 at 9:06
  • \$\begingroup\$ @Reticality that's implied in "valid only if you ran your program on all the test cases" \$\endgroup\$ – edc65 May 4 '15 at 9:33
7
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ Great solution! I believe the score is optimal (based on my bruteforce calculation) and based on your description I think your algorithm always gives the best solutions. \$\endgroup\$ – randomra May 7 '15 at 9:57
  • \$\begingroup\$ @randomra I think its likely that it is, but I was only brute forced up to about +/-100 so I wasn't ready to say that it was necessarily the best, but now that I think about it I can't see how it could be done any better. \$\endgroup\$ – KSab May 7 '15 at 15:11
  • \$\begingroup\$ +1 very nice. How can I try it? What pyton? (I'm not a pythonist, I just have accidentaly a python 3.4 installed on my laptop). \$\endgroup\$ – edc65 May 7 '15 at 15:38
  • \$\begingroup\$ @edc65 I added code to test it; also this is using Python 2.7, so things like the print statements won't work with Python 3 \$\endgroup\$ – KSab May 7 '15 at 15:51
  • \$\begingroup\$ For what it's worth, I can confirm that this result is optimal: i tried a brute force solution (a BFS indeed), verifying up to a length of 450 (and still running). Same results yours. \$\endgroup\$ – edc65 May 8 '15 at 11:01
12
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Are you sure about your score for 2^31? My score for 2^30 is 131099, and 185369 for 2^31-1. \$\endgroup\$ – edc65 May 6 '15 at 13:58
  • \$\begingroup\$ @edc65 I must have typed it in wrong. I thought it seemed a bit low... Anyway, thanks for noticing, and giving some competition. Now it's time to see if I can do better :) \$\endgroup\$ – Geobits May 6 '15 at 14:04
4
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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)+"-";
}
\$\endgroup\$
  • 1
    \$\begingroup\$ ok, if we're golfing the 398710 solutions, game on! someone will come through with cjam or pyth and beat us both, though :( \$\endgroup\$ – Sparr May 6 '15 at 4:38
1
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.