Back
Close

BrainFuck part 2 - Working with arrays

DPAmar
2,404 views

Get item by index

Well, wait, this is the most important operation ! Why is it presented after useless things like moves, shifts, etc... ?

The reason is, there is no direct memory access in BF. We cannot say "I want value of memory cell X" and therefore accessing Array[X], generally done in any language by getting memory value of memory address of Array + X * size of Array items, cannot be done this way in BF.

Instead, we will use moves, shifts, etc... to get item #i from an array. The process will be:

  • have in memory 0, 0, Array, 0, target index, 0
  • during the process, it will be 0, ArrayA, 0, ArrayB, 0, target index with Array=ArrayA + ArrayB
  • while target index is not null
    • go to the first element of ArrayB
    • move it to the left (last element of array A)
    • then decrease target Index
    • Memory will by
      • before first pass 0, ArrayA, 0, X, ArrayB, 0, target index
      • after moving X 0, ArrayA, X, 0, ArrayB, 0, target index
      • after index decrease 0, ArrayA, X, 0, ArrayB, 0, target index-1
  • get first element of ArrayB
    • move it to the end of ArrayA first (otherwise we cannot move along ArrayB if this value is going to be null)
    • move it after ArrayB, twice
    • move back one of the copy at the end of ArrayA
    • Memory will by
      • before first pass 0, ArrayA, 0, target, ArrayB, 0, 0, 0
      • after first move pass 0, ArrayA, target, 0, ArrayB, 0, 0, 0
      • after second move pass 0, ArrayA, 0, 0, ArrayB, 0, target, target
      • after last move pass 0, ArrayA, target, 0, ArrayB, 0, target, 0
  • and finally, move ArrayA back to its initial location

Let's start

  • Memory: 0, 0, Array, 0, target index, 0
  • Cursor: on target index
  • Input: any

Process

  • invariant: memory is 0, ArrayA, 0, ArrayB, 0, index, 0 with Array = ArrayA + ArrayB and target is ArrayB[index]
  • while index is not null
    • go to ArrayB first element
    • move to the left
    • go back to target index and decrease
  • loop
  • index = 0: target is ArrayB[0]
  • go to ArrayB first element
  • move to the left
  • copy twice after ArrayB
  • go to second copy
  • move it back after ArrayA
  • move ArrayA back to its initial location

Code

[                               while index is not null
  <<[<]>                        go to ArrayB first element
  [-<+>]                        move to the left
  >[>]>-                        go back to target index and decrease
]                               loop
<<[<]>                          go to ArrayB first element
[-<+>]                          move to the left
<[->>[>]>+>+<<<[<]<]            copy twice after ArrayB
>>[>]>>[-<<<[<]<+>>[>]>>]       go to second copy and move it back after ArrayA
<<<[<]<[[->+<]<]>               move ArrayA back to its initial location
>[>]>                           go to the result value

Minified version

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

Final state

  • Memory: 0, 0, Array, 0, Array[target index], 0
  • Cursor: on result
  • Input: unchanged
  • Output: unchanged

Test program

This program first reads exactly 10 chars from input, then any number of digits.

For each digit, it prints the Array[digit] value

>>,>,>,>,>,>,>,>,>,>,>>,              read exactly 10 chars then first index to process
[                                     while there is an index to process
  <++++++++[->------<]>               convert decimal digit into a value (subtract 48)
  [<<[<]>[-<+>]>[>]>-]<<[<]>[-<+>]<   get Nth item
  [->>[>]>+>+<<<[<]<]>>[>]>>[-<<<[<    ** part 2 **
  ]<+>>[>]>>]<<<[<]<[[->+<]<]>>[>]>    ** part 3 **
.,]                                   print result; read next index and loop

Example with an input abcfiknru!17046382599999 : ouput is brainfuck!!!!!

Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.
Go to tech.io
codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD
Online Participants