19
\$\begingroup\$

You should write a 100-byte long brainfuck (BF) program.

One character will removed from it in every possible way the resulting 100 new (99-byte long) programs. E.g. for the program ++.>. the 5 subprograms are +.>., +.>., ++>., ++.. and ++.> .

Your score will be the number of unique outputs the 100 programs generate. Higher score is better.

Details

  • Your programs will be terminated after outputting the first character.
  • Invalid or non-terminating programs and programs generating empty outputs are not counted towards the score.
  • The BF cells are 8 bit wrapping ones. (255+1=0, 0-1=255)
  • Your program is given no input. If you use , in the code it set's the current cell to 0.
  • There are no cells on the left side of the starting position. E.g. <. is invalid but .< is valid as the execution is terminated at .. The tape is unbounded in the other direction.
  • Programs with unbalanced brackets ([ and ]) are invalid.
  • Your original program can be shorter than 100 bytes as it's easy to extend it to 100 bytes without changing the score.
  • Your original program doesn't have to be valid BF code.

You can use this python3 program (ideone link) to determine the score of your answer. (For long-running programs you may need to modify the maxstep variable.)

Example

(For simplicity this program is shorter than 100 bytes.)

Solution: ++,+[-]+><.-,-.

Score: 3

Explanation:

Subprogram     => Output

+,+[-]+><.-,-. => 1
+,+[-]+><.-,-. => 1
+++[-]+><.-,-. => 1
++,[-]+><.-,-. => 1
++,+-]+><.-,-. => None
++,+[]+><.-,-. => None
++,+[-+><.-,-. => None
++,+[-]><.-,-. => 0
++,+[-]+<.-,-. => None
++,+[-]+>.-,-. => 0
++,+[-]+><-,-. => 255
++,+[-]+><.,-. => 1
++,+[-]+><.--. => 1
++,+[-]+><.-,. => 1
++,+[-]+><.-,- => 1

Unique outputs are [0, 1, 255]    
Score is 3 for ++,+[-]+><.-,-. (length = 15)

In case of a tie the winner is the one with the shorter code. (Your program can be shorter than 100 bytes as stated in the Details section.) If the codes are equal length the winner is the earlier poster.

Bonus puzzle: without the bolded restriction can you find a program with score 100?

\$\endgroup\$
  • \$\begingroup\$ I solved the bonus puzzle; the answer is (censored). \$\endgroup\$ – AJMansfield Mar 30 '15 at 16:05
  • \$\begingroup\$ @AJMansfield Could you edit your comment so others could think about the puzzle too? E.g change your solution to a pastebin.com link which contains the answer. \$\endgroup\$ – randomra Mar 30 '15 at 16:08
  • 3
    \$\begingroup\$ Hmm. I wrote a genetic optimizer for this question to try to find micro-improvements to existing answers, but it's not too successful so far. They're getting stuck at 79 and 43 respectively. Ah well—it was worth a shot! \$\endgroup\$ – wchargin Mar 31 '15 at 3:58
13
\$\begingroup\$

Score: 35 41 69 78 79 83

(Remove the newline.)

-->+>->+>->+>->+>->+>->+>->+>->+>->+>->+>->+>->+>-
>+>->+>->+>->+>->+>->+>->+>->+>++[>[-<+++>]<<++]>.

Try it online!

I'm not sure exactly why it works...

Score: 79

X->>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>
+>+>+>+>+>+>+>+>+>+>+>+[>[-<+>>+<]+>[-<+>]<<<+]>>.

Try it online!

It was supposed to sum 2*mem[i]*i and add the number of cells (+const) where the addresses are counted from the right to the left. The multiplier 2 and number of cells can make removing + and > having different parity.

It indeed worked like that in the 69 points version. But the latest version broke that and got something else by coincidence. It calculates sum(mem[i]*i+i+1) and removing + and > does almost the same, except for the sum(i) which has a difference of the number of cells, which is also the number of different output for either removing + and >.

For the bonus:

+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.+.

\$\endgroup\$
  • \$\begingroup\$ Note: if you test this with the provided scorer program make sure to increase the maxstep value (in def evaluate(r,maxstep=20000):) as some subprograms run for a long time. \$\endgroup\$ – randomra Mar 30 '15 at 17:05
  • 1
    \$\begingroup\$ Score can actually be increased to 79 by replacing ->+>+> ... with ->,>+> ... \$\endgroup\$ – BrainSteel Mar 30 '15 at 17:52
  • \$\begingroup\$ @BrainSteel I just changed it to a no-op. \$\endgroup\$ – jimmy23013 Mar 30 '15 at 18:32
9
\$\begingroup\$

Score: 37 43

+>-,->,+-><->-[>---+-+<[--->>+><,+>>>++<><<<+<[>--]]><><+-+>+<<+<><+++<[[<[---->-<-]>++>],>,]<,]<+-.

EDIT: Now my program allows some square brackets. Not going to win any prizes with it, but that's what I get for making some weighted RNGs do the busy work for me.

This was generated by a program I wrote in C.

For every Nth character removed, here are the outputs:

N = 0 => 158
N = 1 => 158
N = 2 => 158
N = 3 => 187
N = 4 => 129
N = 5 => 100
N = 6 => 158
N = 7 => 13
N = 8 => 1
N = 9 => 211
N = 10 => 129
N = 11 => 1
N = 12 => 57
N = 13 => 255
N = 14 => Mismatched Braces
N = 15 => 59
N = 16 => 11
N = 17 => 11
N = 18 => 11
N = 19 => 117
N = 20 => 11
N = 21 => 117
N = 22 => 166
N = 23 => Mismatched Braces
N = 24 => 206
N = 25 => 206
N = 26 => 206
N = 27 => 147
N = 28 => 147
N = 29 => 158
N = 30 => 148
N = 31 => 188
N = 32 => 51
N = 33 => 17
N = 34 => 84
N = 35 => 84
N = 36 => 84
N = 37 => 158
N = 38 => 158
N = 39 => 94
N = 40 => 46
N = 41 => 94
N = 42 => 94
N = 43 => 94
N = 44 => 17
N = 45 => 196
N = 46 => Mismatched Braces
N = 47 => 149
N = 48 => No Termination
N = 49 => No Termination
N = 50 => Mismatched Braces
N = 51 => Mismatched Braces
N = 52 => 45
N = 53 => 77
N = 54 => 45
N = 55 => 77
N = 56 => 50
N = 57 => 209
N = 58 => 50
N = 59 => 251
N = 60 => 249
N = 61 => 99
N = 62 => 99
N = 63 => 117
N = 64 => 89
N = 65 => 207
N = 66 => 89
N = 67 => 115
N = 68 => 115
N = 69 => 115
N = 70 => 95
N = 71 => Mismatched Braces
N = 72 => Mismatched Braces
N = 73 => 104
N = 74 => Mismatched Braces
N = 75 => No Termination
N = 76 => No Termination
N = 77 => No Termination
N = 78 => No Termination
N = 79 => Left Overflow
N = 80 => 3
N = 81 => 2
N = 82 => No Termination
N = 83 => Mismatched Braces
N = 84 => No Termination
N = 85 => 133
N = 86 => 133
N = 87 => 0
N = 88 => Mismatched Braces
N = 89 => 158
N = 90 => 0
N = 91 => 4
N = 92 => Mismatched Braces
N = 93 => 0
N = 94 => 158
N = 95 => Mismatched Braces
N = 96 => 0
N = 97 => 157
N = 98 => 159
N = 99 => None

There are a total of 37 unique outputs, which are (in numerical order):

0, 1, 2, 3, 4, 11, 13, 17, 45, 46, 50, 51, 57, 59, 77, 84, 89, 94, 95, 99,
100, 104, 115, 117, 129, 133, 147, 148, 149, 157, 158, 159, 166, 187, 188, 
196, 206, 207, 209, 211, 249, 251, 255

I am 90% 100% certain this solution is not optimal, but proving that may be exceedingly difficult. There are a few things that are clear. Having no . symbols until the last character seems to be the way to go, and square brackets ([]) seem to be rather useless. I did a little bit of thinking here, which I'd like to outline:

Let L be the length of the code in bytes (in the challenge, 100), and n be the number of unique outputs of the sub programs.

For L=3, there are several optimal solutions of the form +-., where n=2 (in this case, the outputs are 1 and 255 for +. and -., respectively.) This puts the best ratio for L = 3 at n/L = 66.67%. Note that this ratio cannot be beaten for at least L<10.

For L=10, the solutions are simple enough to bruteforce it. Here are all the best solutions, at n = 6:

++>-->+<+. => 6
++>-->+<+. => 6
+++>->+<+. => 6
--->->+<+. => 6
++>---><+. => 6
+++>--><+. => 6
-->++>-<-. => 6
+++>+>-<-. => 6
--->+>-<-. => 6
-->+++><-. => 6
--->++><-. => 6

Which yields a score ratio of n/L = 60%.

As L->infinity, it is clear that the ratio must approach 0, since there only 255 possible outputs for a potentially infinite L.

The ratio does NOT, however, decrease uniformly. It is not possible to construct a solution for n=6, L=9, so the best possible ratio for L=9 is 5/9 = 55.56% < 60%.

This begs the question, how quickly, and in what matter, does the ratio descend? For L = 100, and at 10^9 checks/second, it would take several orders of magnitude longer than the lifetime of the universe to bruteforce an optimal solution. Is there an elegant way to go about this? I very much doubt that it is down to 37% for L = 100.

The ratio actually increases, up to L=100. View other answers to confirm.

I'd love to hear your evaluations of the above. I could be was atrociously wrong, after all.

\$\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.