Hide
Problem I
Brainfuck
Brainfuck is an esoteric programming language that operates on a two-way infinite one-dimensional array of $8$-bit memory cells, each initialised to $0$. A pointer points to one of these memory cells.
![\includegraphics[width=.3\textwidth ]{img/tape.pdf}](/problems/brainfuck/file/statement/en/img-0002.png)
Brainfuck uses the following commands:
>
Move the pointer one memory cell to the right.
<
Move the pointer one memory cell to the left.
+
Increment the memory cell at the pointer modulo $2^8$.
-
Decrement the memory cell at the pointer modulo $2^8$.
.
Output the character signified by the memory cell at the pointer using ASCII encoding.
[
Jump past the matching ] if the memory cell at the pointer is $0$.
]
Jump back to the matching [ if the memory cell at the pointer is not $0$.
A Brainfuck program is executed one character at a time, beginning with the first character and ending with the last. Execution proceeds to the next character in reading order, except for jumps resulting from [ and ].
All characters different from <>+-.[] are ignored. They can be used to format or comment Brainfuck source code that is not already self-explanatory.
Input
The input is a well-formed Brainfuck program. It is guaranteed that the program
-
contains at most $1000$ lines, each of which uses at most $80$ characters,
-
performs at most $10^7$ operations,
-
outputs only characters that are either in the printable ASCII range $32$ to $126$ or the value $10$ (the ASCII code for Line feed), which should generate a new line (typically encoded as \n in modern programming languages),
-
outputs Line feed as its final character,
-
consists of properly nested brackets,
-
does not contain a comma (,).
Output
The output generated by the Brainfuck program.
Notes and Acknowledgements
Brainfuck was created in 1993 by Urban Müller, inspired by Corrado Böhm’s minimal language $\mathcal P”$ from 1964. Müller’s Brainfuck also supports an input operation called ,, which reads a single value from standard input. This operation is not part of the set of operations considered in the present task, mainly because it would complicate the problem statement and input specification.
Some of the inputs for this task are based on Brainfuck programs by Daniel B. Cristofani, released under a Creative Commons license.
| Sample Input 1 | Sample Output 1 |
|---|---|
++++++++[
>++++[
>++>+++>+++>+<<<<-
]
>+>+>->>+[<]<-
]
>>.>---.+++++++..+++.
>>.<-.<.+++.------.
--------.>>+.>++.
|
Hello World! |
| Sample Input 2 | Sample Output 2 |
|---|---|
+[+] Wrap around in first cell +++++ ++++ [ Repeat 9 times: >+++++ ++++ inc cell 1 by 9 <-] > cell 1 is now 81 --. output "O" (= 81 minus 2) ----. output "K" < +++++ +++++ . Line feed - [ Also check cell to the left < +++++ ++++ >-] < --. ----. "OK" > +++++ +++++ . Line feed |
OK OK |
| Sample Input 3 | Sample Output 3 |
|---|---|
++++[>+++++<-]>[<++++>-]+<+[
>[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+
>>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<]
<<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-
]
|
0 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 441 484 529 576 625 676 729 784 841 900 961 1024 1089 1156 1225 1296 1369 1444 1521 1600 1681 1764 1849 1936 2025 2116 2209 2304 2401 2500 2601 2704 2809 2916 3025 3136 3249 3364 3481 3600 3721 3844 3969 4096 4225 4356 4489 4624 4761 4900 5041 5184 5329 5476 5625 5776 5929 6084 6241 6400 |
| Sample Input 4 | Sample Output 4 |
|---|---|
Print i with 2^i != 0 + #0 := 1 >++++++[ >++++++++<- ]>- #2 = 47 << [ while #0 != 0 [>++<-] #1 := 2 * #0 >[<+>-] #0 := #1 >+. inc #2 and print it << ] [-]++++++++++. Line feed |
01234567 |
| Sample Input 5 | Sample Output 5 |
|---|---|
++++[>+++++<
-]>+++[[>+>+<<
-]>++++++[<+
>-]+++++++++[<
++++++++++>-
]>[<+>-]<-]+
++>+++++++++
[<+++++++++>
-]>++++++[<+
+++++++>-]<-
-[>+>+<<-]>>
[<<+>>-]<-->
>++++[<+++++
+++>-]++++++
++++>+++++++++
[>+++++++++++<
-]>[[>+>+>+<<<-]
>[<+>-]>>[[>+>+<
<-]>>[<<+>>-]<[<->
-[<->-[<->-[<->-[<
->-[<->-[<->-[<->-[<
->-[<<<+>---------->
->[-]]]]]]]]]]]<]<<[>>
++++++++++++[<++++<+++
+>>-]<<[.[-]>]<<]>[<++++
++[>++++++++<-]>.[-]]<<<
<<.<<<<<.[<]>>>>>>>>>.<<<<
<..>>>>>>>>.>>>>>>>.[>]>[>
+>+<<-]>[<+>-]>[-[[-]+++++++
++[<+++++++++++++>-]<--.[-]>
]]<<<<<.[<]>>>>>>>>>.>>>>>>>>>
.[>]<<.<<<<<.<<<..[<]>>>>>>.[>
]<<.[<]>>>>>>>>>.>.[>]<<.[<]>>>>
.>>>>>>>>>>>>.>>>.[>]<<.[<]>.[>]
<<<<<<.<<<<<<<<<<<..[>]<<<.>.[>]>[
>+>+>+<<<-]>[<+>-]>>[[>+>+<<-]>>[<
<+>>-]<[<->-[<->-[<->-[<->-[<->-[<->
-[<->-[<->-[<->-[<<<+>---------->->[
-]]]]]]]]]]]<]<<[>>++++++++++++[<++++<
++++>>-]<<[.[-]>]<<]>[<++++++[>+++++++
+<-]>.[-]]<<<<<.<<<<<.[<]>>>>>>>>>.<<<
<<..>>>>>>>>.>>>>>>>.[>]>[>+>+<<-]>[<+
>-]>[-[[-]+++++++++[<+++++++++++++>-]<
--.[-]>]]<<<<<.[<]>>>>>>>>>.>>>>>>>>>.
[>]<<.<<<<<.<<<..[<]>>>>>>.[>]<<<<.>>>
.<<<<.<.<<<<<<<<<<.>>>>>>.[>]<<.[<]>>>
>>>>>>.>.>>>>>>>>>.[>]<<.<<<<<<<.[<]>>
>>>>>>>.[<]>.>>>>>>>>>.[>]<<.<<<<.<<<<
<<<<<<<<<.[>]<<<<<<<<<.[>]<<.[<]>>>>>>
>>.[>]<<<<<<.[<]>>>>>..[>]<<.<<<<<<<<<
<<<.[<]>>>>.[>]<<.<<<<.[<]>>>>>>.>>>.<
<<<<<.>>>>>>>.>>>>>>>>>>.[>]<<<.>.>>>-
[>+>+>+<<<-]>[<+>-]>>[[>+>+<<-]>>[<<+>
>-]<[<->-[<->-[<->-[<->-[<->-[<->-[<->
-[<->-[<->-[<<<+>---------->->[-]]]]]]
]]]]]<]<<[>>++++++++++++[<++++<++++>>-
]<<[.[-]>]<<]>[<++++++[>++++++++<-]>.[
-]]<<[>+>+<<-]>[<+>-]+>[<->[-]]<[-<<<[
<]>>>>>>>>>>.<.[>]<<.[<]>>>>>>>>>>>.<<
.<<<.[>]<<<<<<<<<<.[>]>>]<<<<.<<<<<.[<
]>>>>>>>>>.<<<<<..>>>>>>>>.>>>>>>>.[>]
>[>+>+<<-]>[<+>-]+>[<->-[<+>[-]]]<[+++
+++++[>+++++++++++++<-]>--.[-]<]<<<<.[
<]>>>>>>>>>.>>>>>>>>>.[>]<<.<<<<<.<<<.
.[<]>>>>>>.[>]<<.[<]>>>>>>>>>.>.[>]<<.
[<]>>>>.>>>>>>>>>>>>.>>>.[>]<<.[<]>.[>
]<<<<<<.<<<<<<<<<<<..[>]<<<<.>>>..>>]
|
99 bottles of beer on the wall, 99 bottles of beer. Take one down and pass it around, 98 bottles of beer on the wall. 98 bottles of beer on the wall, 98 bottles of beer. Take one down and pass it around, 97 bottles of beer on the wall. 97 bottles of beer on the wall, 97 bottles of beer. Take one down and pass it around, 96 bottles of beer on the wall. 96 bottles of beer on the wall, 96 bottles of beer. Take one down and pass it around, 95 bottles of beer on the wall. 95 bottles of beer on the wall, 95 bottles of beer. Take one down and pass it around, 94 bottles of beer on the wall. 94 bottles of beer on the wall, 94 bottles of beer. Take one down and pass it around, 93 bottles of beer on the wall. 93 bottles of beer on the wall, 93 bottles of beer. Take one down and pass it around, 92 bottles of beer on the wall. 92 bottles of beer on the wall, 92 bottles of beer. Take one down and pass it around, 91 bottles of beer on the wall. 91 bottles of beer on the wall, 91 bottles of beer. Take one down and pass it around, 90 bottles of beer on the wall. 90 bottles of beer on the wall, 90 bottles of beer. Take one down and pass it around, 89 bottles of beer on the wall. 89 bottles of beer on the wall, 89 bottles of beer. Take one down and pass it around, 88 bottles of beer on the wall. 88 bottles of beer on the wall, 88 bottles of beer. Take one down and pass it around, 87 bottles of beer on the wall. 87 bottles of beer on the wall, 87 bottles of beer. Take one down and pass it around, 86 bottles of beer on the wall. 86 bottles of beer on the wall, 86 bottles of beer. Take one down and pass it around, 85 bottles of beer on the wall. 85 bottles of beer on the wall, 85 bottles of beer. Take one down and pass it around, 84 bottles of beer on the wall. 84 bottles of beer on the wall, 84 bottles of beer. Take one down and pass it around, 83 bottles of beer on the wall. 83 bottles of beer on the wall, 83 bottles of beer. Take one down and pass it around, 82 bottles of beer on the wall. 82 bottles of beer on the wall, 82 bottles of beer. Take one down and pass it around, 81 bottles of beer on the wall. 81 bottles of beer on the wall, 81 bottles of beer. Take one down and pass it around, 80 bottles of beer on the wall. 80 bottles of beer on the wall, 80 bottles of beer. Take one down and pass it around, 79 bottles of beer on the wall. 79 bottles of beer on the wall, 79 bottles of beer. Take one down and pass it around, 78 bottles of beer on the wall. 78 bottles of beer on the wall, 78 bottles of beer. Take one down and pass it around, 77 bottles of beer on the wall. 77 bottles of beer on the wall, 77 bottles of beer. Take one down and pass it around, 76 bottles of beer on the wall. 76 bottles of beer on the wall, 76 bottles of beer. Take one down and pass it around, 75 bottles of beer on the wall. 75 bottles of beer on the wall, 75 bottles of beer. Take one down and pass it around, 74 bottles of beer on the wall. 74 bottles of beer on the wall, 74 bottles of beer. Take one down and pass it around, 73 bottles of beer on the wall. 73 bottles of beer on the wall, 73 bottles of beer. Take one down and pass it around, 72 bottles of beer on the wall. 72 bottles of beer on the wall, 72 bottles of beer. Take one down and pass it around, 71 bottles of beer on the wall. 71 bottles of beer on the wall, 71 bottles of beer. Take one down and pass it around, 70 bottles of beer on the wall. 70 bottles of beer on the wall, 70 bottles of beer. Take one down and pass it around, 69 bottles of beer on the wall. 69 bottles of beer on the wall, 69 bottles of beer. Take one down and pass it around, 68 bottles of beer on the wall. 68 bottles of beer on the wall, 68 bottles of beer. Take one down and pass it around, 67 bottles of beer on the wall. 67 bottles of beer on the wall, 67 bottles of beer. Take one down and pass it around, 66 bottles of beer on the wall. 66 bottles of beer on the wall, 66 bottles of beer. Take one down and pass it around, 65 bottles of beer on the wall. 65 bottles of beer on the wall, 65 bottles of beer. Take one down and pass it around, 64 bottles of beer on the wall. 64 bottles of beer on the wall, 64 bottles of beer. Take one down and pass it around, 63 bottles of beer on the wall. 63 bottles of beer on the wall, 63 bottles of beer. Take one down and pass it around, 62 bottles of beer on the wall. 62 bottles of beer on the wall, 62 bottles of beer. Take one down and pass it around, 61 bottles of beer on the wall. 61 bottles of beer on the wall, 61 bottles of beer. Take one down and pass it around, 60 bottles of beer on the wall. 60 bottles of beer on the wall, 60 bottles of beer. Take one down and pass it around, 59 bottles of beer on the wall. 59 bottles of beer on the wall, 59 bottles of beer. Take one down and pass it around, 58 bottles of beer on the wall. 58 bottles of beer on the wall, 58 bottles of beer. Take one down and pass it around, 57 bottles of beer on the wall. 57 bottles of beer on the wall, 57 bottles of beer. Take one down and pass it around, 56 bottles of beer on the wall. 56 bottles of beer on the wall, 56 bottles of beer. Take one down and pass it around, 55 bottles of beer on the wall. 55 bottles of beer on the wall, 55 bottles of beer. Take one down and pass it around, 54 bottles of beer on the wall. 54 bottles of beer on the wall, 54 bottles of beer. Take one down and pass it around, 53 bottles of beer on the wall. 53 bottles of beer on the wall, 53 bottles of beer. Take one down and pass it around, 52 bottles of beer on the wall. 52 bottles of beer on the wall, 52 bottles of beer. Take one down and pass it around, 51 bottles of beer on the wall. 51 bottles of beer on the wall, 51 bottles of beer. Take one down and pass it around, 50 bottles of beer on the wall. 50 bottles of beer on the wall, 50 bottles of beer. Take one down and pass it around, 49 bottles of beer on the wall. 49 bottles of beer on the wall, 49 bottles of beer. Take one down and pass it around, 48 bottles of beer on the wall. 48 bottles of beer on the wall, 48 bottles of beer. Take one down and pass it around, 47 bottles of beer on the wall. 47 bottles of beer on the wall, 47 bottles of beer. Take one down and pass it around, 46 bottles of beer on the wall. 46 bottles of beer on the wall, 46 bottles of beer. Take one down and pass it around, 45 bottles of beer on the wall. 45 bottles of beer on the wall, 45 bottles of beer. Take one down and pass it around, 44 bottles of beer on the wall. 44 bottles of beer on the wall, 44 bottles of beer. Take one down and pass it around, 43 bottles of beer on the wall. 43 bottles of beer on the wall, 43 bottles of beer. Take one down and pass it around, 42 bottles of beer on the wall. 42 bottles of beer on the wall, 42 bottles of beer. Take one down and pass it around, 41 bottles of beer on the wall. 41 bottles of beer on the wall, 41 bottles of beer. Take one down and pass it around, 40 bottles of beer on the wall. 40 bottles of beer on the wall, 40 bottles of beer. Take one down and pass it around, 39 bottles of beer on the wall. 39 bottles of beer on the wall, 39 bottles of beer. Take one down and pass it around, 38 bottles of beer on the wall. 38 bottles of beer on the wall, 38 bottles of beer. Take one down and pass it around, 37 bottles of beer on the wall. 37 bottles of beer on the wall, 37 bottles of beer. Take one down and pass it around, 36 bottles of beer on the wall. 36 bottles of beer on the wall, 36 bottles of beer. Take one down and pass it around, 35 bottles of beer on the wall. 35 bottles of beer on the wall, 35 bottles of beer. Take one down and pass it around, 34 bottles of beer on the wall. 34 bottles of beer on the wall, 34 bottles of beer. Take one down and pass it around, 33 bottles of beer on the wall. 33 bottles of beer on the wall, 33 bottles of beer. Take one down and pass it around, 32 bottles of beer on the wall. 32 bottles of beer on the wall, 32 bottles of beer. Take one down and pass it around, 31 bottles of beer on the wall. 31 bottles of beer on the wall, 31 bottles of beer. Take one down and pass it around, 30 bottles of beer on the wall. 30 bottles of beer on the wall, 30 bottles of beer. Take one down and pass it around, 29 bottles of beer on the wall. 29 bottles of beer on the wall, 29 bottles of beer. Take one down and pass it around, 28 bottles of beer on the wall. 28 bottles of beer on the wall, 28 bottles of beer. Take one down and pass it around, 27 bottles of beer on the wall. 27 bottles of beer on the wall, 27 bottles of beer. Take one down and pass it around, 26 bottles of beer on the wall. 26 bottles of beer on the wall, 26 bottles of beer. Take one down and pass it around, 25 bottles of beer on the wall. 25 bottles of beer on the wall, 25 bottles of beer. Take one down and pass it around, 24 bottles of beer on the wall. 24 bottles of beer on the wall, 24 bottles of beer. Take one down and pass it around, 23 bottles of beer on the wall. 23 bottles of beer on the wall, 23 bottles of beer. Take one down and pass it around, 22 bottles of beer on the wall. 22 bottles of beer on the wall, 22 bottles of beer. Take one down and pass it around, 21 bottles of beer on the wall. 21 bottles of beer on the wall, 21 bottles of beer. Take one down and pass it around, 20 bottles of beer on the wall. 20 bottles of beer on the wall, 20 bottles of beer. Take one down and pass it around, 19 bottles of beer on the wall. 19 bottles of beer on the wall, 19 bottles of beer. Take one down and pass it around, 18 bottles of beer on the wall. 18 bottles of beer on the wall, 18 bottles of beer. Take one down and pass it around, 17 bottles of beer on the wall. 17 bottles of beer on the wall, 17 bottles of beer. Take one down and pass it around, 16 bottles of beer on the wall. 16 bottles of beer on the wall, 16 bottles of beer. Take one down and pass it around, 15 bottles of beer on the wall. 15 bottles of beer on the wall, 15 bottles of beer. Take one down and pass it around, 14 bottles of beer on the wall. 14 bottles of beer on the wall, 14 bottles of beer. Take one down and pass it around, 13 bottles of beer on the wall. 13 bottles of beer on the wall, 13 bottles of beer. Take one down and pass it around, 12 bottles of beer on the wall. 12 bottles of beer on the wall, 12 bottles of beer. Take one down and pass it around, 11 bottles of beer on the wall. 11 bottles of beer on the wall, 11 bottles of beer. Take one down and pass it around, 10 bottles of beer on the wall. 10 bottles of beer on the wall, 10 bottles of beer. Take one down and pass it around, 9 bottles of beer on the wall. 9 bottles of beer on the wall, 9 bottles of beer. Take one down and pass it around, 8 bottles of beer on the wall. 8 bottles of beer on the wall, 8 bottles of beer. Take one down and pass it around, 7 bottles of beer on the wall. 7 bottles of beer on the wall, 7 bottles of beer. Take one down and pass it around, 6 bottles of beer on the wall. 6 bottles of beer on the wall, 6 bottles of beer. Take one down and pass it around, 5 bottles of beer on the wall. 5 bottles of beer on the wall, 5 bottles of beer. Take one down and pass it around, 4 bottles of beer on the wall. 4 bottles of beer on the wall, 4 bottles of beer. Take one down and pass it around, 3 bottles of beer on the wall. 3 bottles of beer on the wall, 3 bottles of beer. Take one down and pass it around, 2 bottles of beer on the wall. 2 bottles of beer on the wall, 2 bottles of beer. Take one down and pass it around, 1 bottle of beer on the wall. 1 bottle of beer on the wall, 1 bottle of beer. Take one down and pass it around, no more bottles of beer on the wall. |
