# Generate all halting Smallfuck programs of length n

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.

• Comments are not for extended discussion; this conversation has been moved to chat. – Dennis Jun 8 '17 at 14:10
• For n=3 assuming 2-way unbounded tape, we get <[] as well. – user75200 Jan 13 '18 at 18:03
• @user75200 "For the purposes of this challenge, a program that moves left from the start of the tape is considered invalid." – Esolanging Fruit Jan 15 '18 at 0:42
• 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." – Esolanging Fruit Jun 20 '18 at 7:14

# 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!

• 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. – user62131 Jun 6 '17 at 18:30
• 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. – nmjcman101 Jun 6 '17 at 19:08
• >>>>>>>>+[[<]+>>>>>>>>+[+<<<<<<<[+>]]<+] 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. – nmjcman101 Jun 7 '17 at 12:34
• @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 – PunPun1000 Jun 7 '17 at 13:05
• @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. – Sanchises Jun 8 '17 at 6:34

# Braingolf, Score: 3

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


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

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