6
\$\begingroup\$

Your task is to write a program that, given a number n, returns a list of all valid, halting Smallfuck programs of length n, in any order.

Actually, we're using a variation of Smallfuck called F2, which is just Smallfuck with a right-unbounded tape. For the purposes of this challenge, a program that moves left from the start of the tape is considered invalid, as is one with unbalanced brackets.

Scoring

Since solving this for every n is impossible (as it would require you to solve the halting problem), your submission's score will be the lowest n for which it returns an incorrect answer.

Each submission must be, at most, 1000 bytes (though you are encouraged to provide an ungolfed version as well). In the event of a tie, the earlier answer wins.

Test Cases

n = 1:

+ >

n = 2:

++ +> >+ >< >> []

n = 3:

+++ ++> +>+ +>< +>> >++ >+< >+> ><+ ><> >>+ >>< >>> >[] [+] [<] [>] []+ []>

n = 4:

++++ +++> ++>+ ++>< ++>> +>++ +>+< +>+> +><+ +><> +>>+ +>>< +>>> >+++ >++< >++> >+<+ >+<> >+>+ >+>< >+>> ><++ ><+> ><>+ ><>< ><>> >>++ >>+< >>+> >><+ >><< >><> >>>+ >>>< >>>> [][] ++[] +>[] ><[] >>[] [++] [+<] [+>] [<+] [<<] [<>] [>+] [><] [>>] []++ []+> []>+ []>< []>> +[+] +[>] >[+] >[<] >[>] >[]+ >[]< >[]> [+]+ [+]> [<]+ [<]> [>]+ [>]> [[]]

Please inform me if there are any more that I have forgotten to add.

\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Dennis Jun 8 '17 at 14:10
  • \$\begingroup\$ For n=3 assuming 2-way unbounded tape, we get <[] as well. \$\endgroup\$ – user75200 Jan 13 '18 at 18:03
  • \$\begingroup\$ @user75200 "For the purposes of this challenge, a program that moves left from the start of the tape is considered invalid." \$\endgroup\$ – Esolanging Fruit Jan 15 '18 at 0:42
  • \$\begingroup\$ This challenge is effectively just "write a Smallfuck implementation and find all programs that halt after at least G steps, where G is the largest constant you can fit under 1000 bytes." \$\endgroup\$ – Esolanging Fruit Jun 20 '18 at 7:14
6
\$\begingroup\$

Java (OpenJDK 8), Score: ???

This clocks in at 980 bytes, since I had so much to work with I decided to make it a little more readable. Basically I'm generating all the possible programs for length n and iterating them n^x times for some x. x is currently 3 but it can be modified arbitrarily to any size, limited only by the limitation of the JVM's precission. This will work for arbitrarily large input values if x is increased, but I have it set to 3 for tio.

import java.util.*;
public class Main{
    public static void main(String[] args){
        int i = new Scanner(System.in).nextInt();
        int x = 3;
        l:for(int j=0;j<Math.pow(5, i);j++){
            try {
                String s="";
                for(int k=j;s.length()<i;k/=5)
                    s="+<>][".charAt(k%5)+s;
                Stack<Integer>y=new Stack<Integer>();
                Map<Integer,Integer>f=new HashMap<>(),b=new HashMap<>();
                for(int m=0; m<s.length();m++){
                    char c=s.charAt(m);
                    if(c=='[')y.push(m);
                    if(c==']'){int n=y.pop();f.put(n, m);b.put(m, n);}
                }
                if(y.size()>0)
                    continue;
                boolean[] t= new boolean[s.length()];
                int l=0,n=0;
                for(long m=0;l<s.length()&m<Math.pow(i,x);l++,m++){
                    switch(s.charAt(l)){
                    case'+':t[n]=!t[n];break;
                    case'>':n++;break;
                    case'<':n--; if(n < 0)continue l;break;
                    case'[':if(!t[n])l=f.get(l);break;
                    case']':l=b.get(l)-1;break;
                    }
                }
                if(l>=s.length()){
                    System.out.println(s);
                }
            } catch(Exception e){continue;}
        }
    }
}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ My guess is that the first program that breaks this will be some sort of counting-in-binary program. I'm not sure exactly how long that would be, though. \$\endgroup\$ – user62131 Jun 6 '17 at 18:30
  • \$\begingroup\$ I did the same thing in Python, but just had no way of proving anything. It amused me how difficult the proof felt compared to the actual code. \$\endgroup\$ – nmjcman101 Jun 6 '17 at 19:08
  • \$\begingroup\$ >>>>>>>>+[[<]+>>>>>>>>+[+<<<<<<<[+>]]<+] is a program that SHOULD do binary counting (I don't know if that part works correctly), is 40 characters long (40*40=1600), and takes 4451 steps to run. I don't think it's the minimum program that takes longer than n*n steps to run, just an example. \$\endgroup\$ – nmjcman101 Jun 7 '17 at 12:34
  • \$\begingroup\$ @nmjcman101 Thanks for the input, I've updated the code to do n*n*n but set a variable x to allow it to arbitrarily be increased. I'm not sure what the score would be at x=3,4,5... and I don't know how I would begin calculating it, so I'm just going to leave it unknown \$\endgroup\$ – PunPun1000 Jun 7 '17 at 13:05
  • \$\begingroup\$ @PunPun1000 per the halting problem, there is no x such that this algorithm can determine if an arbitrary F2 program halts - indeed, we could then just convert any problem to F2 and solve the halting problem with your algorithm. \$\endgroup\$ – Sanchises Jun 8 '17 at 6:34
1
\$\begingroup\$

Braingolf, Score: 3

1-?"++ +> >+ >< >> []":"+ >"|&@

Start things off nice and easy, hardcodes the correct answer for 1 and 2, outputs + > if n = 1, and ++ +> >+ >< >> [] otherwise

\$\endgroup\$
  • \$\begingroup\$ Also add [] for another length-2 testcase. \$\endgroup\$ – Esolanging Fruit Jun 6 '17 at 16:44

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.