5 ms·

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

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 9y ago
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 9y ago
  Yeah I don't follow the parenthesis parser. Plan to do a write-up of some kind on how it works?
  - SonOfLilit 9y ago
    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, "".
    - briansteffens 9y ago
      Awesome, nice work.
    - doubleplusgood 9y ago
      Oh, that's pretty clever. Thanks for the explanation!

SonOfLilit 9y ago

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 9y ago
Yeah I don't follow the parenthesis parser. Plan to do a write-up of some kind on how it works?
- SonOfLilit 9y ago
  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, "".
  - briansteffens 9y ago
    Awesome, nice work.
  - doubleplusgood 9y ago
    Oh, that's pretty clever. Thanks for the explanation!