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.

Improve this question
\$\endgroup\$
4
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ Commented Jun 8, 2017 at 14:10
  • \$\begingroup\$ For n=3 assuming 2-way unbounded tape, we get <[] as well. \$\endgroup\$ Commented Jan 13, 2018 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\$ Commented Jan 15, 2018 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\$ Commented Jun 20, 2018 at 7:14

2 Answers 2

Reset to default
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!

Improve this answer
\$\endgroup\$
7
  • \$\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\$ Commented Jun 6, 2017 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\$ Commented Jun 6, 2017 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\$ Commented Jun 7, 2017 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\$ Commented Jun 7, 2017 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\$ Commented Jun 8, 2017 at 6:34
2
\$\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

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Also add [] for another length-2 testcase. \$\endgroup\$ Commented Jun 6, 2017 at 16:44

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.