Learn to Code via Tutorials on Repl.it

← Back to all posts
Becoming a better problem solver in BrainF**k part 4: the FINALE
vityavv (46)

See all 4 tutorials

https://repl.it/talk/learn/Becoming-a-better-problem-solver-in-BrainFk-part-4-the-FINALE/22886
https://repl.it/talk/learn/Becoming-a-better-problem-solver-through-BrainFk-part-3-Example-problems-MORE-TRICKS/22733
https://repl.it/talk/learn/Becoming-a-better-problem-solver-through-BrainFk-Part-2-Why-How/22588
https://repl.it/talk/learn/Becoming-a-better-problem-solver-through-BrainFk-part-1-What-is-BrainFk/22526

Throughout the last 3 tutorials, you've learned how to use BrainF**k, learned some tricks, and looked at a few example problems. This is probably going to be the final tutorial in the series.

First, let's go through our last practice problem, which was "for each character in the input, write that character the amount of times equal to that character's ascii value." The solution to this problem combines two tricks from the previous tutorial. For each character of input, duplicate the input, and use one as a counter, counting off how many times the other duplicate is printed. The solution looks like this:

, take input
[ start loop for each input
  [>+>+<<-] copy input into next two cells
  > get to the first copy
  [ start a loop on that
    >. print from the second copy
    <- subtract from the first copy
  ]
  > go to the second copy and
  [-] zero it so that the cell is ready for the next input (you can also just go forward to skip past the used up cells)
  , take input (since all of the cells are zero(comma) you don't have to go back to the first cell)
]

With that out of the way, let's get to the final thing you don't know how to do: make decisions! For all of our previous practice problems, we've used [ and ] as just loops. However, if you look back to the first tutorial, you'll remember that both were described as "if ... then ...`. That means that they can be used as if statements.

Let's start with the following challenge: given any input, replace every exclamation point with a period. First, let's write out our logic, keeping in mind what BrainF**k can do:

1. loop over the input
  1. If the input is an exclamation point,
    1. Change it to a period
  2. Output it

The only problem with that is that both [ and ] only do something if the value is/isn't zero. So, we have to rewrite our flow once again:

1. Loop over input
  1. Subtract the value of an exclamation point
  2. If the result is zero,
    1. Add the value of |0 - !| (their difference)
  3. Add the value of an exclamation point

Let's try writing that in BrainF**k:

, input
[ loop
  >+++[<----------->-]< subtract 33
  what do we use here? [ or ]?

Looks like we ran into a few problems. Our control flow says "if the result is zero," and for that we'd use [. However, [ skips to the matching ], so if the value is zero, it executes everything outside of the [...], but if the value is non-zero, it executes everything inside the [...] and outside it. So, we have to rewrite our logic again.

1. Loop over input
  1. Subtract the value of the exclamation point
  2. If the result is non-zero 
    1. Subtract the value of |0 - !|
  3. Add the value of |0 - !|
  4. Add the value of the exclamation point

So, you see here, if the input is zero it only subtracts the difference, but if the difference is non-zero, they cancel each-other out. Let's write this in BrainF**k

, input
[ loop
  >+++[<----------->-] subtract exclamation point
  <[ if nonzero
    --------------- subtract 15 (difference between zero and exclamation point)
    > go forward into empty cell so that the following end bracket doesn't go back to the beginning (making it not a loop)
  ]
  +++++++++++++++ add 15
  >+++[<+++++++++++>-] add back the value of the exclamation point
  <. print what you get
  [-] zero it to prepare for next input
  , input
]

Oops! Looks like we have a problem! If the value is nonzero, we have to go forward to an empty cell in order to exit the code inside the brackets without it looping. So, we'd have to go back before subtracting 15. However, if it is zero, going backwards would go off the tape! So, we have to use another trick. If you recall tutorial 2, one of the tricks was [<], which would go left through the tape until it found an empty space. We can extend the trick as such: at the beginning, we go forward one so that there's always an empty cell at the beginning. Then, before subtracting 15, we go all the way back to the beginning (which is empty, stopping the [<] loop). Finally, we go forward one, to get back to the input. Here's what the program looks like!

> make the first cell empty
, input
[ loop
  >+++[<----------->-] subtract exclamation point
  <[ if nonzero
    --------------- subtract 15 (difference between zero and exclamation point)
    > go forward into empty cell so that the following end bracket doesn't go back to the beginning (making it not a loop)
  ]
  <[<]> go back to the first cell (we have a less than sign outside of the loop because if we start on the empty cell after the input we can find our way back but if we start on the input we go straight to the beginning and don't do the loop)(comma) and then go to the next cell (input)
  +++++++++++++++ add 15
  >+++[<+++++++++++>-] add back the value of the exclamation point
  <. print what you get
  [-] zero it to prepare for next input
  , input
]

Voila! It works! Now, you know everything you need to become a master BrainF**ker. By looking at these tricks, hopefully you've become a better problem solver, looking at how you can work around constraints to solve difficult challenges. The attached repl is one that I made while doing a challenge on a site called codegolf.stackexchange.com, which has a bunch of different programming challenges. I encourage you to look at those and see how you can approach them in different ways. Finally, your last challenge problem:

Build a BrainF**k interpreter in BrainF**k

Footnote: most brainf**k interpreters make cells overflow instead of going negative, so for example doing - on an empty cell makes it 255 (8-bit cell).

Commentshotnewtop
vityavv (46)

Feel free to share some interesting problems or solutions you find!