[briansteffens]

Wow this is cool and you did this really fast!

So you did kind of a functional style where each row represents an instruction being run with a full copy of the state of the VM at that point in time. Then each subsequent row is based on the state of the previous one. Am I reading that right? (I'm not familiar with Brainfk)

[SonOfLilit]

Yes. Had to store state somewhere, spreadsheets find "one row per thing" to be most natural, and in my case the "thing" I'm working with is state, so one row per state transition it is.

The more interesting hackery is in the parenthesis parser...

[briansteffens]

Yeah I don't follow the parenthesis parser. Plan to do a write-up of some kind on how it works?

[SonOfLilit]

The basic algorithm is "parentheses counting": walk the string starting from an opening bracket, counting +1 per `[` and -1 per `]`; when you reach 0 you're at the matching closing bracket.

First, lets split the code to one char per row:

    =MID($A$1,D3,1)

(D3,D4,... are simply 1,2,3,...)

Now, lets parse `[` as 1, `]` as -1, anything else as 0:

    =IF(E3="[",1,if(E3="]",-1,0))

Now, we will need one column per character in the code, where in the i'th column the first row is the i'th character's value and each row we go down accumulates the value of the next character.

    =G2+OFFSET($F2,G$1,0)
    =G3+OFFSET($F3,G$1,0)
    ...

(Column F is the 1,0,-1s. Row 1 is 0,1,2,3..., this time horizontally, which we use to translate horizontal motion into vertical motion)

Now for the i'th row of the "] match" column, lets find the index of the first 0 in the i'th column, and add `i-1` to get an index from the beginning of the code instead of from the opening bracket:

    =MATCH(0,offset($G$3,0,D3-1,18,1),0)+D3-1
    =MATCH(0,offset($G$3,0,D4-1,18,1),0)+D4-1
    ...

And all that's left is reverse-search this table to find the matching opening brackets to every closing bracket, and while we're at it lets clean up all irrelevant rows to the empty string:

    =IF(F3=1,C3,IF(F3=-1,MATCH(D3,$B$3:$B$20,0),""))

(D3 is the index of the closing bracket, $B$3:$B$20 is interestingly the column we're currently in - Sheets does not complain as long as there is no actual circular referencing going on)

Voila! Column B now contains for every bracket its matching bracket's index in the code, and for anything else, "".

[doubleplusgood]

Oh, that's pretty clever. Thanks for the explanation!

[briansteffens]

Awesome, nice work.