62 case (_, l) => jumpLeft(prog, pc - 1, l) |
62 case (_, l) => jumpLeft(prog, pc - 1, l) |
63 } |
63 } |
64 } |
64 } |
65 |
65 |
66 // test cases |
66 // test cases |
67 //jumpRight("""--[..+>--],>,++""", 3, 0) // => 10 |
67 //jumpRight("""--[..+>--].>.++""", 3, 0) // => 10 |
68 //jumpLeft("""--[..+>--],>,++""", 8, 0) // => 3 |
68 //jumpLeft("""--[..+>--].>.++""", 8, 0) // => 3 |
69 //jumpRight("""--[..[+>]--],>,++""", 3, 0) // => 12 |
69 //jumpRight("""--[..[+>]--].>.++""", 3, 0) // => 12 |
70 //jumpRight("""--[..[[-]+>[.]]--],>,++""", 3, 0) // => 18 |
70 //jumpRight("""--[..[[-]+>[.]]--].>.++""", 3, 0) // => 18 |
71 //jumpRight("""--[..[[-]+>[.]]--,>,++""", 3, 0) // => 22 (outside) |
71 //jumpRight("""--[..[[-]+>[.]]--.>.++""", 3, 0) // => 22 (outside) |
72 //jumpLeft("""[******]***""", 7, 0) // => -1 (outside) |
72 //jumpLeft("""[******]***""", 7, 0) // => -1 (outside) |
73 |
73 |
74 // (4) Complete the compute function that interprets (runs) a brainf*** |
74 // (4) Complete the compute function that interprets (runs) a brainf***++ |
75 // program: the arguments are a program (represented as a string), a program |
75 // program: the arguments are a program (represented as a string), a program |
76 // counter, a memory counter and a brainf*** memory. It Returns the |
76 // counter, a memory counter and a brainf***++ memory. It Returns the |
77 // memory at the stage when the execution of the brainf*** program |
77 // memory at the stage when the execution of the brainf***++ program |
78 // finishes. The interpretation finishes once the program counter |
78 // finishes. The interpretation finishes once the program counter |
79 // pc is pointing to something outside the program string. |
79 // pc is pointing to something outside the program string. |
80 // If the pc points to a character inside the program, the pc, |
80 // If the pc points to a character inside the program, the pc, |
81 // memory pointer and memory need to be updated according to |
81 // memory pointer and memory need to be updated according to |
82 // rules of the brainf*** language. Then, recursively, the compute |
82 // rules of the brainf***++ language. Then, recursively, the compute |
83 // function continues with the command at the new program |
83 // function continues with the command at the new program |
84 // counter. |
84 // counter. |
85 // Implement the run function that calls compute with the program |
85 // Implement the run function that calls compute with the program |
86 // counter and memory counter set to 0. |
86 // counter and memory counter set to 0. |
87 |
87 |
91 case '>' => (pc + 1, mp + 1, mem) |
91 case '>' => (pc + 1, mp + 1, mem) |
92 case '<' => (pc + 1, mp - 1, mem) |
92 case '<' => (pc + 1, mp - 1, mem) |
93 case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1)) |
93 case '+' => (pc + 1, mp, write(mem, mp, sread(mem, mp) + 1)) |
94 case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1)) |
94 case '-' => (pc + 1, mp, write(mem, mp, sread(mem, mp) - 1)) |
95 case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) } |
95 case '.' => { print(sread(mem, mp).toChar); (pc + 1, mp, mem) } |
96 case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte)) |
96 //case ',' => (pc + 1, mp, write(mem, mp, Console.in.read().toByte)) |
97 //case ',' => (pc + 1, mp, write(mem, mp, scala.io.StdIn.readByte())) |
97 //case ',' => (pc + 1, mp, write(mem, mp, scala.io.StdIn.readByte())) |
98 case '[' => |
98 case '[' => |
99 if (sread(mem, mp) == 0) (jumpRight(prog, pc + 1, 0), mp, mem) else (pc + 1, mp, mem) |
99 if (sread(mem, mp) == 0) (jumpRight(prog, pc + 1, 0), mp, mem) else (pc + 1, mp, mem) |
100 case ']' => |
100 case ']' => |
101 if (sread(mem, mp) != 0) (jumpLeft(prog, pc - 1, 0), mp, mem) else (pc + 1, mp, mem) |
101 if (sread(mem, mp) != 0) (jumpLeft(prog, pc - 1, 0), mp, mem) else (pc + 1, mp, mem) |
102 |
102 |
103 // new commands |
103 // new commands |
104 case '@' => (pc + 1, mp, write(mem, sread(mem, mp), sread(mem, mp - 1))) |
104 case '@' => (pc + 1, mp, write(mem, sread(mem, mp), sread(mem, mp - 1))) |
105 case '*' => (pc + 1, mp, write(mem, mp, sread(mem, mp) * sread(mem, mp -1))) |
105 case '*' => (pc + 1, mp, write(mem, mp, sread(mem, mp) * sread(mem, mp -1))) |
106 case '#' => { println(s"$mp: ${sread(mem, mp)}"); (pc + 1, mp, mem) } |
106 case '#' => { println(s"${sread(mem, mp)}"); (pc + 1, mp, mem) } |
107 |
107 |
108 |
|
109 case _ => (pc + 1, mp, mem) |
108 case _ => (pc + 1, mp, mem) |
110 } |
109 } |
111 compute(prog, new_pc, new_mp, new_mem) |
110 compute(prog, new_pc, new_mp, new_mem) |
112 } |
111 } |
113 else mem |
112 else mem |
117 |
116 |
118 |
117 |
119 |
118 |
120 |
119 |
121 |
120 |
122 // some sample bf-programs collected from the Internet |
121 // some sample bf/bf++-programs collected from the Internet |
123 //===================================================== |
122 //========================================================== |
124 |
123 |
125 |
124 |
126 // first some contrived (small) programs |
125 // some contrived (small) programs |
|
126 //--------------------------------- |
127 |
127 |
128 // clears the 0-cell |
128 // clears the 0-cell |
129 //run("[-]", Map(0 -> 100)) // Map will be 0 -> 0 |
129 //run("[-]", Map(0 -> 100)) // Map will be 0 -> 0 |
130 |
130 |
131 // moves content of the 0-cell to 1-cell |
131 // moves content of the 0-cell to 1-cell |
132 //run("[->+<]", Map(0 -> 10)) // Map will be 0 -> 0, 1 -> 10 |
132 //run("[->+<]", Map(0 -> 10)) // Map will be 0 -> 0, 1 -> 10 |
133 |
133 |
134 |
134 |
135 // copies content of the 0-cell to 2-cell and 4-cell |
135 // copies content of the 0-cell to 2-cell and 4-cell |
136 //run("[>>+>>+<<<<-]", Map(0 -> 42)) |
136 //run("[>>+>>+<<<<-]", Map(0 -> 42)) // Map(0 -> 0, 2 -> 42, 4 -> 42) |
137 |
137 |
138 |
138 |
139 // prints out numbers 0 to 9 |
139 // prints out numbers 0 to 9 |
140 //run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") |
140 //run("""+++++[->++++++++++<]>--<+++[->>++++++++++<<]>>++<<----------[+>.>.<+<]""") |
141 |
141 |
|
142 // bf++ program calculating the cube-function, 10 * 10 * 10 = 1000 |
|
143 //run("""++++++++++#>+***#""") // Map(0 -> 10, 1 -> 1000) |
|
144 |
|
145 |
|
146 // bf++ program copies 3 from 0-cell to to cells 1, 4, 5, 6 and 7 |
|
147 // (note that because of how the program wprks cell 1 will contain 7) |
|
148 //run("""+++>+@+@+@+@+@""") // Map(0 -> 3, 1 -> 7, 4 -> 3, 5 -> 3, 6 -> 3, 7 -> 3) |
|
149 |
|
150 |
142 |
151 |
143 // some more "useful" programs |
152 // some more "useful" programs |
|
153 //----------------------------- |
144 |
154 |
145 // hello world program 1 |
155 // hello world program 1 |
146 //run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ |
156 //run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ |
147 // ..+++.>>.<-.<.+++.------.--------.>>+.>++.""") |
157 // ..+++.>>.<-.<.+++.------.--------.>>+.>++.""") |
148 |
158 |
174 // +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++ |
180 // +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++ |
175 // ++++++++++++++++++++++++++++++++++++++++++++.[-]<< |
181 // ++++++++++++++++++++++++++++++++++++++++++++.[-]<< |
176 // <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<< |
182 // <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<< |
177 // [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""") |
183 // [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""") |
178 |
184 |
179 /* |
|
180 //outputs the square numbers up to 10000 |
185 //outputs the square numbers up to 10000 |
181 run("""++++[>+++++<-]>[<+++++>-]+<+[ |
186 //run("""++++[>+++++<-]>[<+++++>-]+<+[>[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+ |
182 >[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+ |
187 // >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<] |
183 >>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<] |
188 // <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]""") |
184 <<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]""") |
189 |
185 |
190 |
186 |
191 // calculates 2 to the power of 6 |
187 //collatz numbers (needs a number to be typed in) |
|
188 run(""">,[[----------[ |
|
189 >>>[>>>>]+[[-]+<[->>>>++>>>>+[>>>>]++[->+<<<<<]]<<<] |
|
190 ++++++[>------<-]>--[>>[->>>>]+>+[<<<<]>-],<]>]>>>++>+>>[ |
|
191 <<[>>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<<]]<[>+<-]>] |
|
192 >[>[>>>>]+[[-]<[+[->>>>]>+<]>[<+>[<<<<]]+<<<<]>>>[->>>>]+>+[<<<<]] |
|
193 >[[>+>>[<<<<+>>>>-]>]<<<<[-]>[-<<<<]]>>>>>>> |
|
194 ]>>+[[-]++++++>>>>]<<<<[[<++++++++>-]<.[-]<[-]<[-]<]<,]""") |
|
195 |
|
196 |
|
197 // infinite collatz (never stops) |
|
198 run(""">>+>+<[[->>[>>]>>>[>>]+[<<]<<<[<<]>[>[>>]>>+>[>>]<+<[<<]<<<[< |
|
199 <]>-]>[>>]>>[<<<<[<<]>+>[>>]>>-]<<<<[<<]+>>]<<[+++++[>+++++++ |
|
200 +<-]>.<++++++[>--------<-]+<<]>>[>>]+[>>>>[<<+>+>-]<-[>+<-]+< |
|
201 [<<->>-[<<+>>[-]]]>>>[<<<+<<+>>>>>-]<<<[>>>+<<<-]<<[[-]>+>>-> |
|
202 [<+<[<<+>>-]<[>+<-]<[>+<-]>>>>-]<[>+<-]+<[->[>>]<<[->[<+++>-[ |
|
203 <+++>-[<+++>-[<[-]++>>[-]+>+<<-[<+++>-[<+++>-[<[-]+>>>+<<-[<+ |
|
204 ++>-[<+++>-]]]]]]]]]<[>+<-]+<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[< |
|
205 +>-[<+>-[<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-[<+>-]]]]]]]]]]]<[>+<- |
|
206 ]+>>]<<[<<]>]<[->>[->+>]<[-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<- |
|
207 >>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+>-[<->>+<-[<+> |
|
208 -[<->>+<-[<+>-[<->>+<-[<+>-]]]]]]]]]]]]]]]]]]]>[<+>-]<+<[<+++ |
|
209 +++++++>-]<]>>[<+>->>]<<[>+>+<<-]>[<+>-]+>[<->[-]]<[-<<-]<<[< |
|
210 <]]++++++[>+++++++<-]>++.------------.[-]>[>>]<<[+++++[>+++++ |
|
211 +++<-]>.<++++++[>--------<-]+<<]+<]>[<+>-]<]>>>[>>]<<[>[-]<-< |
|
212 <]++++++++++.[-]<<<[<<]>>>+<[->[<+>-[<+>-[<+>-[<+>-[<+>-[<+>- |
|
213 [<+>-[<+>-[<+>-[<[-]>>[-]+>+<<-]]]]]]]]]]<[>+<-]+>>]<<[<<]>>]""") |
|
214 |
|
215 // 2 to the power of 6 |
|
216 //(example from a C-to-BF compiler at https://github.com/elikaski/BF-it) |
192 //(example from a C-to-BF compiler at https://github.com/elikaski/BF-it) |
217 run(""">>[-]>[-]++>[-]++++++><<<>>>>[-]+><>[-]<<[-]>[>+<<+>-]>[<+>-] |
193 //run(""">>[-]>[-]++>[-]++++++><<<>>>>[-]+><>[-]<<[-]>[>+<<+>-]>[<+>-] |
218 <><[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-][-]><<>>[-]>[-]<<<[>>[-] |
194 // <><[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-][-]><<>>[-]>[-]<<<[>>[-] |
219 <[>+>+<<-]>[<+>-]+>[[-]<-<->>]<<<-]>>[<<+>>-]<<[[-]>[-]<<[>+> |
195 // <[>+>+<<-]>[<+>-]+>[[-]<-<->>]<<<-]>>[<<+>>-]<<[[-]>[-]<<[>+> |
220 +<<-]>>[<<+>>-][-]>[-]<<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-] |
196 // +<<-]>>[<<+>>-][-]>[-]<<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-] |
221 <<>>[-]>[-]<<<[>>>+<<<-]>>>[<<[<+>>+<-]>[<+>-]>-]<<<>[-]<<[-] |
197 // <<>>[-]>[-]<<<[>>>+<<<-]>>>[<<[<+>>+<-]>[<+>-]>-]<<<>[-]<<[-] |
222 >[>+<<+>-]>[<+>-]<><[-]>[-]<<<[>>+>+<<<-]>>>-[<<<+>>>-]<[-]>[-] |
198 // >[>+<<+>-]>[<+>-]<><[-]>[-]<<<[>>+>+<<<-]>>>-[<<<+>>>-]<[-]>[-] |
223 <<<[>>+>+<<<-]>>>[<<<+>>>-][-]><<>>[-]>[-]<<<[>>[-]<[>+>+<<-]> |
199 // <<<[>>+>+<<<-]>>>[<<<+>>>-][-]><<>>[-]>[-]<<<[>>[-]<[>+>+<<-]> |
224 [<+>-]+>[[-]<-<->>]<<<-]>>[<<+>>-]<<][-]>[-]<<[>+>+<<-]>>[<<+> |
200 // [<+>-]+>[[-]<-<->>]<<<-]>>[<<+>>-]<<][-]>[-]<<[>+>+<<-]>>[<<+> |
225 >-]<<<<<[-]>>>>[<<<<+>>>>-]<<<<><>[-]<<[-]>[>+<<+>-]>[<+>-]<> |
201 // >-]<<<<<[-]>>>>[<<<<+>>>>-]<<<<><>[-]<<[-]>[>+<<+>-]>[<+>-]<> |
226 <[-]>[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-]<<>>[-]>[-]>[-]>[-]>[-]> |
202 // <[-]>[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-]<<>>[-]>[-]>[-]>[-]>[-]> |
227 [-]>[-]>[-]>[-]>[-]<<<<<<<<<<>>++++++++++<<[->+>-[>+>>]>[+[-<+ |
203 // [-]>[-]>[-]>[-]>[-]<<<<<<<<<<>>++++++++++<<[->+>-[>+>>]>[+[-<+ |
228 >]>+>>]<<<<<<]>>[-]>>>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<< |
204 // >]>+>>]<<<<<<]>>[-]>>>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<< |
229 ]>[-]>>[>++++++[-<++++++++>]<.<<+>+>[-]]<[<[->-<]++++++[->++++ |
205 // ]>[-]>>[>++++++[-<++++++++>]<.<<+>+>[-]]<[<[->-<]++++++[->++++ |
230 ++++<]>.[-]]<<++++++[-<++++++++>]<.[-]<<[-<+>]<<><<<""") |
206 // ++++<]>.[-]]<<++++++[-<++++++++>]<.[-]<<[-<+>]<<><<<""") |
231 |
207 |
232 |
208 |
233 |
209 |
234 // a Mandelbrot set generator in brainf*** written by Erik Bosman |
210 // a Mandelbrot set generator in brainf*** written by Erik Bosman |
235 // (http://esoteric.sange.fi/brainfuck/utils/mandelbrot/) |
211 // (http://esoteric.sange.fi/brainfuck/utils/mandelbrot/) |
236 |
212 // |
237 run(load_bff("mandelbrot.bf")) |
213 //run(load_bff("mandelbrot.bf")) |
238 |
214 |
239 |
215 |
240 // a benchmark program (counts down from 'Z' to 'A') |
216 // a benchmark program (counts down from 'Z' to 'A') |
241 val b1 = """>++[<+++++++++++++>-]<[[>+>+<<-]>[<+>-]++++++++ |
217 // |
242 [>++++++++<-]>.[-]<<>++++++++++[>++++++++++[>++ |
218 //run(load_bff("benchmark.bf")) |
243 ++++++++[>++++++++++[>++++++++++[>++++++++++[>+ |
219 |
244 +++++++++[-]<-]<-]<-]<-]<-]<-]<-]++++++++++.""" |
220 // calculates the Collatz series for numbers from 1 to 30 |
245 |
221 // |
246 |
222 //run(load_bff("collatz.bf")) |
247 def time_needed[T](n: Int, code: => T) = { |
223 |
248 val start = System.nanoTime() |
224 } |
249 for (i <- 0 until n) code |
|
250 val end = System.nanoTime() |
|
251 (end - start)/(n * 1.0e9) |
|
252 } |
|
253 |
|
254 time_needed(1, run(b1)) |
|
255 */ |
|
256 |
|
257 } |
|
258 |
|
259 def time_needed[T](n: Int, code: => T) = { |
|
260 val start = System.nanoTime() |
|
261 for (i <- 0 until n) code |
|
262 val end = System.nanoTime() |
|
263 (end - start)/(n * 1.0e9) |
|
264 } |
|
265 |
|
266 import CW10a._ |
|
267 |
|
268 // draws the Sierpinski triangle |
|
269 run("""++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[ |
|
270 ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<< |
|
271 ]>.>+[>>]>+]""") |
|
272 |
|
273 |
|
274 println(run("""++++++++++>+***""")) |
|
275 |
|
276 println(run("""+++>+!+!+!+!+!""")) |
|
277 |
|
278 |
|
279 println(time_needed(2, run(load_bff("a.bf")))) |
|
280 |
|