11
\$\begingroup\$

Your friend is trying to break into a vault that has a peculiar locking system: it requires a certain number of gentle knocks in a particular spot. Your friend discovered the number (which is in the range 1...99999) and possesses a gadget that produces the required knocks. However, the gadget is a Brainfuck interpreter! So your friend needs to feed it a Brainfuck program, which, obviously, should be as short as possible (the gadget's I/O is slow).

Your task is to help him! Write a program or a subroutine, in any language, that accepts as input a number N, and outputs a Brainfuck program, which takes no input and outputs a string of printable ASCII characters (excluding the space character - codes in the range 33...126) of length N.

Example: for input 10, the output might be

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

(but I am sure it can be shortened!)

Your score will be the sum of lengths of your outputs for the following values of N (they are random numbers):

55
68
15
28
841
838
522
846
4898
9004
9363
3810
13230
67175
37231
44701

Oh, and you will be transmitting your code (the generator program) to your friend by Twitter. So make sure it's 140 characters or less!


P.S. The Brainfuck language has many variants. Let's assume the tape is infinite in both directions (or "circular and large enough"), and the cells have 32-bit int capacity (finite and able to hold numbers up to 99999). Also, no wrapping: when a cell overflows, the machine self-destructs!

\$\endgroup\$
  • 1
    \$\begingroup\$ "following values of N (they are random numbers)" reminded me of xkcd.com/221 \$\endgroup\$ – cirpis Mar 17 '15 at 9:40
  • \$\begingroup\$ Just for reference, the space character (character code 32) is usually included in the printable ASCII range. It doesn't really make a difference for the challenge since you've defined the range explicitly though. \$\endgroup\$ – Martin Ender Mar 17 '15 at 11:51
  • 3
    \$\begingroup\$ Can we assume cells in brainfuck to be arbitrary width integers? If not, how and when do they wrap? \$\endgroup\$ – orlp Mar 17 '15 at 14:23
  • 1
    \$\begingroup\$ It would be nice to assume at least being able to contain 67175 + a few. \$\endgroup\$ – orlp Mar 17 '15 at 14:49
  • \$\begingroup\$ @anatolyg I realized that later. Sorry. \$\endgroup\$ – Esolanging Fruit Nov 28 '16 at 15:07
3
\$\begingroup\$

Python 2, score: 1021

I've just realized that this contest is pretty old but still, since I came up with a better solution than those posted, I posted it as well.

Here's a 102 byte python script that does the job:

n=input()
s='>'
while n:
    s+='>'+'+'*(n%5+1);n/=5
print s+'[->[-<+++++>]<<]<+++++++[>+++++<-]>>[-<.>]'

The idea is to use base 5 encoding for N (best base at least for the current inputs, which do not seem very "random" by the way, looks like they were arbitrarily chosen by OP), and to write a generic Brainfuck algorithm to decode a number of arbitrary length (the number is encoded with each digit increased by one in order to detect the end of conversion). I chose to print character 35 #, character 36 $ is equivalent.

You may run the following bash script to get the score:

i=0
while read p; do
  i=$((i+`echo $p | python convert.py | wc -m`))
done
echo $i

With a more advanced program that replaces encoding with multiplication for small numbers and chooses the best base for encoding each number, I can reach 958 Brainfuck characters, but Python is far too verbose (and I'm a pretty bad/lazy golfer) in order to get the converter into 144 bytes!

\$\endgroup\$
  • \$\begingroup\$ This is a great idea! Maybe I'll use it once to improve this answer (wrote a script in Python to get score less than 950, but I don't know any golfing language to make it short enough). \$\endgroup\$ – anatolyg Oct 8 '15 at 17:21
8
\$\begingroup\$

BrainF***, score: 193,313

It's not under 140 characters (it's 147, so close!!), so this can't win, but I thought it was cool.

Prints 43 plus signs, then N periods. Not very optimal.

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

If anyone can help shorten this I would love it.

\$\endgroup\$
  • \$\begingroup\$ I guess with Brainfuck it would be enough to make a "subroutine" that receives its input on the tape - no need to read from "standard input device". \$\endgroup\$ – anatolyg Mar 18 '15 at 21:06
  • \$\begingroup\$ @anatolyg That makes it much easier - probably about 80 or 90 characters. Should I change it? \$\endgroup\$ – mdc32 Mar 18 '15 at 23:20
5
\$\begingroup\$

J, Total score = 1481

(For my previous entry and explanation check revision history.)

f10=.('>++++++++++<';'')rplc~;@([:(<@('+++++[>+++++++<-]>>+',;@((<'[>++++++++++')#~#)),[<@(']',~'<-','<.>'#~],[,])"0 #-i.@# )10#.inv])

This function generates nested BF loops based on the base10 digits of the input number. Checking all reasonable bases and choosing the smallest BF code would improve the score with a small amount.

BF programs for the test set:

   f10 every 55 68 15 28 841 838 522 846 4898 9004 9363 3810 13230 67175 37231 44701
+++++[>+++++++<-]>>+[>++++++++++[-<<.....>>]<-<.....>]                                                                                     
+++++[>+++++++<-]>>+[>++++++++++[-<<......>>]<-<........>]                                                                                 
+++++[>+++++++<-]>>+[>++++++++++[-<<.>>]<-<.....>]                                                                                         
+++++[>+++++++<-]>>+[>++++++++++[-<<..>>]<-<........>]                                                                                     
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[-<<<........>>>]<-<<....>>]<-<.>]                                                             
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[-<<<........>>>]<-<<...>>]<-<........>]                                                       
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[-<<<.....>>>]<-<<..>>]<-<..>]                                                                 
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[-<<<........>>>]<-<<....>>]<-<......>]                                                        
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[>++++++++++[-<<<<....>>>>]<-<<<........>>>]<-<<.........>>]<-<........>]                      
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[>++++++++++[-<<<<.........>>>>]<-<<<>>>]<-<<>>]<-<....>]                                      
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[>++++++++++[-<<<<.........>>>>]<-<<<...>>>]<-<<......>>]<-<...>]                              
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[>++++++++++[-<<<<...>>>>]<-<<<........>>>]<-<<.>>]<-<>]                                       
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[>++++++++++[>++++++++++[-<<<<<.>>>>>]<-<<<<...>>>>]<-<<<..>>>]<-<<...>>]<-<>]                 
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[>++++++++++[>++++++++++[-<<<<<......>>>>>]<-<<<<.......>>>>]<-<<<.>>>]<-<<.......>>]<-<.....>]
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[>++++++++++[>++++++++++[-<<<<<...>>>>>]<-<<<<.......>>>>]<-<<<..>>>]<-<<...>>]<-<.>]          
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[>++++++++++[>++++++++++[-<<<<<....>>>>>]<-<<<<....>>>>]<-<<<.......>>>]<-<<>>]<-<.>]          

Computing score on the test set:

   +/#@> f10 each 55 68 15 28 841 838 522 846 4898 9004 9363 3810 13230 67175 37231 44701
1481
\$\endgroup\$
3
\$\begingroup\$

Pyth, 1702

Reconstruct numbers using factors of N + x.

+holN+]++">>"*"+"Q"<<"mjk(">>"j">"m*"+"kP+Qd"<[[->[->+>+<<]>>[-<<+>>]<<<]>[-]>[-<<+>>]<<<]>"*"-"d"<<")50"++++++[>++++++<-]>>[<.>-]"
\$\endgroup\$
  • \$\begingroup\$ For 2 this outputs ++. now which doesn't print anything in BF. \$\endgroup\$ – randomra Mar 17 '15 at 17:00
  • \$\begingroup\$ @randomra Good catch, this happened while updating, I'll fix it, give me a few. \$\endgroup\$ – orlp Mar 17 '15 at 17:09
  • \$\begingroup\$ @randomra Should be fixed, made the score slightly higher (of course). \$\endgroup\$ – orlp Mar 17 '15 at 17:38
3
\$\begingroup\$

CJam, 52 74 108 bytes, total = 1304 1244 1210

ri5b_,1>{(_3<{\(@5*+}*\+}*W%)\{T+_2>:T5*-_0>"-+"=\z*}%\T+'+*a+W%{"[->+++++<]>"\}*">x[>x<-]<[->>.<<]"'x/'+6**

A test script (slow in the online interpreter):

q~]
{
_[0:T;
5b_,1>{(_3<{\(@5*+}*\+}*W%)\{T+_2>:T5*-_0>"-+"=\z*}%\T+'+*a+W%{"[->+++++<]>"\}*">x[>x<-]<[->>.<<]"'x/'+6**
]s
_[L:RL@0\
"-+><.]"['('){+\_{)}0?@\}{@\+\_{)}0?}{R1$c+:R;}]:`"]a"{{_aa+1$4G#%{:~~1}{;0}?}g}`+a+er:~:~
];R,@=!"Error."N+*o
}%s,
\$\endgroup\$
  • \$\begingroup\$ I didn't see the part about self-destruction. But it will never overflow anyway. \$\endgroup\$ – jimmy23013 Mar 18 '15 at 10:14
  • \$\begingroup\$ How does it work? \$\endgroup\$ – anatolyg Mar 18 '15 at 10:38
  • \$\begingroup\$ @anatolyg The first version simply generate the number in base 5. Later versions added a special case for the first two digits and also used decrement. \$\endgroup\$ – jimmy23013 Mar 18 '15 at 11:10
  • \$\begingroup\$ @user23013 Oh, sorry, haven't seen the spec changes. (Updated my answer accordingly.) \$\endgroup\$ – randomra Mar 18 '15 at 11:23
2
\$\begingroup\$

Befunge-98, N + 41, total = 193281

&>'+\:v
v^-1,\_
' >1-:v
>v^,+'_
,'    :
>ff3++^
>2f*+v
^>/9+:,
>'>,61v
, v*6+<
^/2,:<@
v >+2+,
>'<,']^

I know it's bad, but I felt like writing some Befunge today. The best part of Befunge is that the programs are even less understandible than the actual golf languages, especially when they reuse code :D

Uses a similar algorithm to Martin Büttner's CJam answer:

(N +'s)>+++++++++++++++++++++++++++++++++<[->.<]
\$\endgroup\$
1
\$\begingroup\$

CJam, 40 + N, Total: 193265

'+33*'>'+l~*"[<.>-]"

Just to get this started, here is the baseline solution. It generates the following code:

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

where _ is N copies of +.

Run the generator here.

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

Befunge-93 - 24 + N, total = 193009

&>">>]-<]-<++++>[++++>[+++"v
v  ,,,,,,,,,,,,,,,,,,,,,,, <
>:v
,v_@
"1
.-
"
^<

This uses a prefix of +++[>++++[>++++<-]<-]>> to set the first tape index to '0' with 24 characters. The Befunge program is very basic and outputs that along with N '.' characters.

\$\endgroup\$
  • \$\begingroup\$ Now that I see this I don't know why I was thinking my loop would be any better... \$\endgroup\$ – Martin Ender Mar 17 '15 at 17:02

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.