This is a reimplementation of a classic brainfuck program by Linus Åkesson. This is another one that spent a long time on my to-do list before I tackled it properly. I started with some desiderata. I wanted my program to be relatively fast and concise. (I generally try to get my programs under a kilobyte, but I didn't know if it would be possible for this one.) I wanted the interface to behave the same as the original, but I thought it important to have the grid wrap toroidally, although I figured that would cost me at least 200-300 commands. I also wanted the board size to appear in my code only once so it could be changed easily, and I wanted to let it go up to 100x100 or more with byte cells, which meant never putting both coordinates in the same cell. In my initial thinking about memory layout, I thought I might use as many as five brainfuck cells per Life cell: one for the cell value and another used to accumulate neighbor count and then adjust that first cell; one for a moving navigation rail of 1 cells, connecting each cell to the cells above and below, also used to handle horizontal wrapping; another to keep track of the size of the board, and to handle vertical wrapping; and one more to hold the ASCII values of cells for easy output. I quickly realized the ASCII cells also implicitly marked the size of the board, and that enough other cells would be empty during the vertical-wrapping step that four brainfuck cells per Life cell would be enough. My basic plan then was: -spread value from each v cell to the t cells to left and right, and (using the rail) to the t cells 11, 10, and 9 spaces left and right, then compute the new v values from the accumulated t values. (We assume a boardsize of 10, which again, I wanted to be easily modified.) -(It'd be nice to get the cell value out of the v cell and into its own corresponding t cell, at the same time as it's spread to the surrounding t cells, to free up the v cell. But it can't just be lumped in with all the other values, per the Life transition rule; it must be distinguishable. We could put 9 times the v cell into its own t cell, and 1 times the v cell into those other eight cells; then each v cell would be live in the next generation if its t cell were 3, 11, or 12. Or we could put 1 times the v cell in its own t cell, and twice that much in the other eight cells; then each cell lives on a 5, 6, or 7. That second one sounds more convenient. (Either one gives t values ranging from 0 to 17.)) -The way we handle the wrapping is that we have fake or shadow cells around all four edges of the grid (their corresponding ASCII cells hold the linefeeds and coordinate grid for when the board is printed). These always have 0 as their v cell value, as dead cells do. So the plan becomes: -spread value from nonzero v cells to adjacent t cells (including fakes; no special code needed) -move t values from horizontal fake cells into the opposite real t cells (and from the 4 double-fake corner cells to the opposite vertical fake cells) -move t values from the vertical fake cells into the opposite real t cells -recompute v values for all t values (fakes will now have t=0 resulting in v=0 again, no special code needed; and each real t cell will by now have its full value, including any value from across the edges of the board that was initially spread into its shadow cell(s)). -ASCII cells may as well track the v cells, so they're changed from "*" to "-" if the v cell was 1 when its value was removed and spread, and changed from "-" to "*" if the new computed v value is 1. Fake cells will thus never get their ASCII value ("linefeed" or "c" or whatever) changed, since they have v=0 both those times. -I noticed we don't need two separate rails of (roughly) the board width to spread v values 9*4, 10*4, and 11*4 brainfuck cells left and right (make that 11*4, 12*4, 13*4 counting the fakes); we can use one rail and spread values from its right end to spaces near its left, and vice versa. -We can use basically the same navigation rail to fix the horizontal fakes as for spreading the values initially; it's about the right length. To move it one rail length and stop to copy values is a matter of building a second rail (in the next row) one cell at a time, one cell for each cell removed from the first rail, and stopping when the first rail is used up. This would need the rail to be 11 1-cells long. -Fixing the vertical fakes needs a much longer rail, or maybe just a pair of marks, 12*10*4=480 brainfuck cells apart. Fortunately, the whole time the fakes are being adjusted, the v cells are empty and free for navigational use as we move values from t cell to t cell. The distance needed is close to the length of the ASCII part of the board, minus the length of the usual 1-row-long navigation rail. That's about what I had figured out before I started coding. I built a working version with data layout "v t r a v t r a" (value, temp, rail, ASCII). Then I noticed that storing all the ASCII values decreased by 9, to make it convenient to find the linefeeds at ends of rows, might be less cumbersome for fixing the horizontal fakes than using a rail. Then I started thinking it might be possible to lose the rail and the rail cells entirely, and rebuild the thing with layout "v t a v t a". During the spreading of values, that meant using a left-end marker in the just-cleared v cells, and a right-end marker in the not-yet-used t cells. That proved perfectly workable. I also rewrote the initialization code from its original clunky rail-based form to basically its current form. For a while I was thinking that the process of dragging several counters along while building the board might be less concise than leaving the counters at left and scanning the whole length of the ASCII board to add each new value; that would have taken O(boardsize^4) time instead of O(boardsize^3). But dragging the counters along turned out to be short enough as well as fast, so I didn't even bother writing the other version. Anyway. Of course I found a ton of other small improvements while tinkering with this further. >>>->+>+++++>(++++++++++)[[>>>+<<<-]>+++++>+>>+[<<+>>>>>+<<<-]<-]>>>>[ The first three lines build the (empty) board. We need to generate a lot of ASCII values (decremented by 9 to help with navigation). I'll use a technique I learned from Erik Bosman's quine, first setting a two-part code for each value: a and b, where the desired value is (17+0)*a+b+1. I could use either a or b to mark the extent of my list by making sure one or the other of them was always nonzero, but instead I'm using an explicit -1 stopper at the left. Then the code for the initial space (32-9=23) is "1 5" (17*(a=1)+(b=5)+1=23). The first line of code builds the first line of the board (" abcdefghij" or similar, and a linefeed). We use one down-counter to keep track of how much more line needs building, and one up-counter which is added to each value to make the progression. This also has the effect of moving our board size from the downcounter to the upcounter, and leaving it in the upcounter at the end of the row for further use. Again, I aim to have the initial value given to that downcounter be the ONLY place the board size appears in the program, for easy alteration, and I'm putting it in parentheses to mark it. So the progression over the course of this loop goes: a b d 0 0 0 u 0 0 0 0 ... a b 0 0 0 d u 0 0 0 0 ... a b 0 5 1 d u 0 0 0 0 ... a b 0 5 u+1 d 0 0 0 u 0 ... where 5 and u+1 are of course the next a and b ('a'=97-9-88; 17*(a=5)+(b=1+u)+1=87+u, and u is incremented before being added to b each time). I've shaped this loop to dump u pretty far to the right at the end of this line, in accord with the needs of the following loop. In case it's not obvious, the code for linefeed (10-9=1) is 0 0 (17*(a=0)+(b=0)+1), and that's one reason I chose this encoding; it will become useful later. So the end state is: ... 0 a b 0 a b 0 u where that last "a b" is "0 0" for the linefeed. Then we start the next loop at u; it generates most of the board. [>>>+>+<<<<-]+++>>+[<+>>>+>+<<<-]>>[>[[>>>+<<<-]<]<<++>+>>>>>>-]<- In this loop we again use a downcounter and an upcounter; the former upcounter now becomes a downcounter, tracking how many lines still need to be generated, and a new upcounter is used to generate the coordinate letters at the start of each line. However, we also use a third counter to control an inner loop which generates '-'s for the empty board. We will synthesize this counter from the other two counters at the start of each line; the inner loop drags all three counters along but only changes the inner-loop counter. So the progression at the start of this loop is: ... 0 a b 0 d 0 u 0 0 0 0 ... ... 0 a b 0 0 0 u d d 0 0 ... ... 0 a b 0 3 u 0 d i u 0 ... ending at i, which is now boardsize+1. The inner loop then makes this into: ... 0 a b 0 5 u+1 0 0 0 0 d i u 0 ... ... 0 a b 0 5 u+1 0 2 1 0 0 0 0 d i u 0 ... ... 0 a b 0 5 u+1 0 2 1 0 2 1 0 0 0 0 d i u 0 ... and so on. ('-'=45)-9=36; 17*(a=2)+(b=1)+1=36. The first iteration of the inner loop drops its "2 1" on top of the already built "3 u" to the left to produce the "5 1+u" that will generate a letter coordinate. When i is exhausted, we leave the inner loop and restart the outer loop to start another line. If the code for linefeed weren't "0 0" we would need to take two or three steps back to set it at this point. ]+++>+>[[-]<+<[>+++++++++++++++++<-]<+]>>[ When the outer loop has wrapped up, we still need to set up '>' (prompt for input) after the last linefeed. That's 62-9=53=(17*(a=3)+(b=1)+1). Then we have the loop that builds these almost-characters (still minus 9) from a and b. This loop continues back to our -1 stopper back in the fourth cell, but also note that it starts by wiping out u (board size). From now on we'll use the shape of the ASCII board to control all navigation, directly or indirectly, and won't need the size stored explicitly anywhere. Next we start the main loop, executed once per command. [+++++++++brainfuck.org-------->>>]+[-<<<]>>>[>>,----------[>]<]<<[ The first thing is to output the board. This is very straightforward; it just needs adjusting by 9 to be proper ASCII. Next we read a linefeed-terminated command. Like the classic program, this one identifies commands by their length. We consider three possibilities (not bothering to deal gracefully with invalid input): 0 0 0 v t a v t a v t a v t a ... 0 0 0 0 [0] 23 0 0 88 0 0 89 0 0 90 ... "" (linefeed as first character): advance one generation 0 0 0 0 0 23 0 [q] 88 0 0 89 0 0 90 ... "q": quit 0 0 0 0 0 23 0 y 88 0 [x] 89 0 0 90 ... "yx": toggle that cell In that first case, we skip the loop that just started. In the second and third cases we enter it. <<<[ Now this loop, we enter only in the case of a "toggle" command, so the "toggle" code is in here. If the command was "q" (or for that matter "k" or "7") we skip this loop, and for that matter we skip everything and exit the main loop so the program terminates. >--[<->>+>-<<-]<[[>>>]+>-[+>>+>-]+[<<<]<-]>++>[<+>-] So, the cell-toggle code. First we subtract 86 from x and y, which already had 10 subtracted from them. This should give them values from a=1 up. Next we start building a rail of 1s in the (empty) t column, leading to the cell we want to toggle. First, y times, we go to the end of the rail-so-far, then extend it as far as the next linefeed after that by searching for a 1 in the ASCII column, then come back to y via the a column (scanning for the 0 where the 88 normally is). Then we restore that 88 to its usual place. >[[>>>]+[<<<]>>>-]+[->>>]<-[++>]>[------<]>+++[<<<]> Next we add another x 1s to the rail in the t column, and then scan along (and clear) that column to get to the cell we want to toggle. We toggle the cell and scan back along the a column. ]< ]>[ Again, this is arranged so it will exit these loops and skip the following one on "toggle" or "quit", whereas on "advance" it will have skipped the previous outer loop and will enter this one. -[+>>>-]+>>>>>>[<+<<]>->>[ So we're advancing the board one generation. The first major step is to spread the value from each living v cell to its corresponding t cell and the 8 "neighboring" t cells, while removing it from that v cell and updating the matching a (ASCII) cell. I'm treating the board size as variable apart from its initial declaration, so these values are having to move a variable distance to reach the cells in rows above and below; I'll use a moving rail to indicate that distance. Note also that the space the values have to be moved across is all full of values we need to save, in all three cell types. How then to mark the ends of the rail? I mark its left end with a -1 in the most recently cleared v cell, to distinguish it from the 0s and 1s in v cells within the rail. I mark the rail's right end by artifically increasing all t cells in the rail by 1, so we can find the right end by scanning for the first 0 t cell (the leftmost t cell that's still empty and untouched, this step). So this line increments the t cells in the rail, sets the v cell to -1 at its left end, and then starts a loop at the leftmost nonzero ASCII cell. For each nonzero ASCII cell, we will spread values from the v cell 1 step right, rightward, and we spread values from the v cell 13 life cells right of that ASCII cell (assuming standard 10-wide board) leftward, and adjust both ends of the rail 1 life cell right. Note that the last three iterations will always find both v cells 0, a slight awkwardness. >[->+>+++>>++[>>>]+++<<<++<<<++[>>>]>>>]<<<[>[>>>]+>>>] If this v cell was 1, we clear it, increase its associated t cell by 1, change the matching ASCII value from '*'-9 (33) to '-'-9 (36) by adding three, increase the t cell to the right by 2, scan forward to the end of the rail, lengthen it and increase the three neighboring t cells on the next row by 2 (skipping the second outer loop). If the v cell was 0, we do very little of that, merely scanning to the end of the rail and lengthening it. Either way we end up just right of the rail. <<<<<<<[<<++<+[-<<<+]->++>>>++>>>++<<<<]<<<+[-<<<+]+>->>->> Now we check this v value near the right end of the rail; if it's 1 we increase the t cell to the left by 2, scan left to the -1 v cell marking the left end of the rail, and increment the three t cells in the row above by 2. Notice we don't clear the v cell; it will be used again and then cleared when the left end of the rail gets here. If the v cell was 0, we merely scan to the left end of the rail. Either way we are moving the -1 right by three brainfuck cells, reversing the artifical t increment at the left end of the rail, and leaving a 1 in the v cell that we're leaving behind (one behind the one whose value we just checked, cleared, and set to -1). This leaves a trail of v=1s roughly the length of the board, which will be used shortly. ]<<+<<+<<<+<<-[+<+<<-]+<+[ This next part moves values from the fake t cells at the bottom of the board to the real t cells at the top, and vice versa. This code works, and is more concise than other versions I've tried, but it still strikes me as an ugly mess and I'm still vaguely hoping to do better. We use the rail of v=1 to move values across most of the length of the board; there's an outer loop that moves this rail along; the first 13 times it will go to the left end of the rail and move, mostly, values from the top fake t cells to the bottom real t cells; the next, I think, 15 times it will, mostly, move values from the bottom fake t cells to the top real t cells. it looks at the v cells in its path, to the right of the rail, to decide which of these things to do; and it looks at the t cells in its path to decide how long to go on doing either of these things (it will also decrement them, thus wiping out the rail of artifically incremented t cells used in the last chunk of this program). So this line is setting up values to make that work. It zeroes the -1 v marker from the last section and extends the rail of incremented t cells back another whole row. Then it starts the loop at the the fake t cell at the right end of the second-to-last row of real cells. ->+>[-<-<<[<<<]>[>>[>>>]<<+<[<<<]>-]] Decrement t cell, increment the a cell just right of it (for a later purpose), check the next v cell. If nonzero, restore that a cell, go to the top of the rail, move value from top fake t cell into bottom real t cell. (Also handles the four double-fake corner cells, moving their values to the matching singly fake side cells.) <[<[<[<<<]>+>>[>>>]<<-]<[<<<]]>>>->>>[>>>]+> If we did the loop in the last line, this leaves us at the empty v cell just left of the rail and we skip this loop. If not, this leaves us at the incremented a cell; we move the value from the matching bottom fake t cell to its corresponding top real t cell, then move to the top of the rail; finally we shorten the rail at its top end, lengthen it at its bottom end, and look at the next t to see whether to continue this loop. (The last three iterations can't have any values to move.) ]>+[-<<[-]<]-[ When this loop ends, the rail of incremented t cells will have been cleared, but the '>' and all the 0 a cells between that and where the pointer is will have been incremented. Now we'll use those to cruise clear back to the start of the array, decrementing a cells and clearing our rail of v cells on the way. On getting back to the start, we set up a -1 there; note that most of the array's a cells are now at -1, or their ASCII character value minus 10; that '>' prompt is back to '>'-9 and the following 0 ASCII cells are back to 0. All the linefeeds in the array are now at 10-10=0 too, which makes it easier to find them for this next bit. We start a loop for fixing the horizontal fake t cells. [>>>]<[<<[<<<]>>>>>+>[>>>]<-]>>>[>[>>>]<<<<+>[<<<]>>-]> We scan to the end of the line; move the value from the right fake t cell to the left real t cell; move the value from the left fake t cell of the next line to the right real t cell of that line; and go to the next ASCII cell. This loop runs until we move (0) values near the '>' cell, then stops. All t values are gathered in the appropriate real t cells now. ]<<<<<<[---<-----[-[-[<->>+++<+++++++[-]]]]<+<+]> Now we go back to the '>', the only nonzero ASCII cell that's now at -9 below its usual value and not -10; our task here is to compute new v values on the basis of each t value, in accordance with the Life transition rule, and to adjust the ASCII cells accordingly. For each ASCII cell, we first decrement it by 3 (which would change '-' into '*', on the presumption that the cell will be live; then decrease the t cell and use some skip loops so that if it IS live (t value of 5, 6, or 7: i.e., 2 2s from neighboring v cells and one 1 from this v cell; or three 2s from neighboring v cells; or three 2s from neighboring v cells and one 1 from this v cell), we'll skip the inner part. The inner part basically cancels the outer part. It decrements v to counteract the increment of v that's about to happen outside the loop; it increases a by 3 to turn '*' back into '-'; it restores the t value to 0 or greater before zeroing it (safety measure to avoid being slow on implementations with large cells). After the inner skippable loop, we increment v and also increment a to bring it back to its usual -9. Thus, if the outer and inner parts are both done, the cell will be v=0 and a='-'-9 (or some border value if this was a fake cell) as appropriate for a dead cell; if only the outer part is done it will be v=1 and a='*'-9 as appropriate for a live cell. Either way t will be zeroed. Now we're done updating all v values and a values; we have advanced the automaton one step; and we've gotten back to the -1 at the far left and restored it to 0. ]>> ] The "if advancing the automaton was even what we wanted to do" loop ended at an empty v cell, two cells left of the leftmost nonzero a cell (holding a 32-9=23 representing a space). Or if the command was "toggle", that loop started on that same empty v cell, got skipped, and we're still there. Either way we move to the 23 and go back to the start of the main loop, to output it and take another command. Conversely, if the last command was "q", we've moved to an empty t cell one cell left of the 23, skipped the "if advance one step" loop, now we go to the empty v cell just right of the 23, exit the main loop and terminate the program. I'm not sure what new lessons to draw from this. Certainly the pairs-of-values text-generation technique I borrowed from Erik Bosman is a solidly useful thing. This program also reinforces and validates most of the lessons I learned from earlier programs. This one seems distinctively board-centric and like a strong example of letting your data layout do the work for you; it reminds me a little of quicksort in that respect.