Cellular Automata with Vim Macros

It struck me while taking a break from a heavy refactoring session and browsing /r/cellular_automata that Wolfram-style cellular automata are really just glorified string substitutions. Suddenly I felt a tickling deep in my hindbrain. An idea was forming. Can you implement a Wolfram-style cellular automata, like Rule-30, entirely within Vim using only “normal” features like macros and substitutions?

In an effort to rid myself of the crushing weight of that question (and because it was Friday), I descended into the depths and came back with an answer. Yes, you can.

What is Rule 30?

Before we stick our hands into a big pile of Vim, let’s take a look at what we’re trying to accomplish. Wolfram-style cellular automata are a family of one-dimensional cellular automata where a cell’s state in the next generation is determined by its current state and the state of its immediate neighbors.

Rule 30, a specific type of Wolfram-style cellular automata, derives it’s rules from the binary representation of the number thirty, 00011110:

■■■	■■□	■□■	■□□	□■■	□■□	□□■	□□□
□	□	□	■	■	■	■	□

As you can hopefully infer from the diagram above, an “on” cell with two “on” neighbors will turn off in the next generation. Similarly, an “off” cell with an “on” leftmost neighbor will turn on, and so on.

When computing the next generation, every cell with two neighbors is considered before any modifications are made. Let’s solidify our understanding by considering how the next generation of a longer initial sequence would be computed:

□□■□□ 

Looking at each cell and its imediate neighbors, we can use the rules described above to come up with the next generation of our sequence. The first three cells are □□■, which map to ■ in the next generation. The next three cells, □■□, map to ■. And finally, the last three cells, ■□□, map to ■.

This means the next generation of our initial sequence of cells (□□■□□) is ■■■. Notice that the next generation of our automata is two cells shorter than the previous generation. A simple way of avoiding this problem is to prepend and append “off” cells to the initial generation before computing the subsequent generation. If we had done that, we’d have ended up with □■■■□ as our next generation, rather than ■■■.

We can repeatedly apply this operation on successive generations to create many interesting patterns, balancing on the edge of chaos and order.

The Seeds of a Plan

Coming into this project, I had a high-level plan of attack for accomplishing what I was after. I knew I wouldn’t be able to process every iteration of the cellular automata in one pass. I’d have to break the process down into pieces.

My main strategy was to break each generation, represented as a line of on/off characters, into a paragraph of three-character lines, one for each grouping of neighbors. From there I could encode the cellular automata’s rules into substitution commands, and roll the resulting paragraph of one-character lines back up into a single line.

This current-line substitution was the foundation of my solution:

:.s/^\(..*\)\(\(..\).\)$/\1\3\r\2/ 

The idea behind this substitution is to use capture groups to replace a line with everything up until the last character of the line (\1\3), followed by a newline (\r), and the last three characters of the original line (\2). As an aside, I learned that you should use \r instead of \n when using newlines in substitutions.

Executed on a line with the text, □□■□□, we’d get the following result:

□□□■□□ □□□ 

Repeatedly applying this substitution would give us the following paragraph of lines:

□□□ □□■ □■□ ■□□ □□□ 

From here, we can translate our eight Rule 30 rules into global substitutions:

:%s/^■■■$/□/g :%s/^■■□$/□/g :%s/^■□■$/□/g :%s/^■□□$/■/g :%s/^□■■$/■/g :%s/^□■□$/■/g :%s/^□□■$/■/g :%s/^□□□$/□/g 

Running those substitutions on our paragraph gives us a new paragraph made up of single character lines. Each of these characters is a cell in our next generation:

□ ■ ■ ■ □ 

Next we just need to roll that paragraph back up into a single line. J is the tool for joining lines in Vim, but J insists on separating newly concatenated lines with a space. It turns out you can join lines directly with the gJ command:

□■■■□ 

And just like that we have our next generation.

Implementing Our Plan

The outline of our plan includes lots of hand waving, like “repeatedly applying this substitution,” which just won’t cut it for a fully automated cellular automata generation machine.

We need a way of turning our very hands-on algorithm into a hands-off, fully automated solution. An elegant way of doing this is using Vim’s built-in macro system. Vim macros are ridiculously powerful while being ridiculously simple in concept. They’re just stored keystrokes. This means there’s nothing stopping a macro (stored in, say, the q register) from invoking itself recursively (@q). This opens the door for quite a few interesting possibilities.

In the hope of building a fully automated solution, let’s implement our cellular automata generator as a script of keystrokes that can be executed in “batch mode” with the -s flag. Once finished, we’ll be able to invoke our generator on a file containing a seed, or an initial sequence of cells, with the following command:

vim -s script seed 

We’ll start off our script by using setreg (instead of let) to define a macro b that will perform our first set of substitutions and build our paragraph of three-character lines:

:call setreg('b', ':.s/^\(..*\)\(\(..\).\)$/\1\3\r\2/|norm!``@b', 'l') 

The |norm!`` at the end of our substitution returns the cursor to it’s starting place after each replacement.

Next, let’s define a macro to perform each of our Rule 30 replacements. I built these as eight separate macros, rather than one macro that performed eight substitutions because any of these substitutions might not find what they’re looking for, which causes it’s active macro execution to fail. Breaking each substitution out into it’s own macro prevents its potential failure from affecting other rules:

:call setreg('1', ':%s/^■■■$/□/g', 'l') :call setreg('2', ':%s/^■■□$/□/g', 'l') :call setreg('3', ':%s/^■□■$/□/g', 'l') :call setreg('4', ':%s/^■□□$/■/g', 'l') :call setreg('5', ':%s/^□■■$/■/g', 'l') :call setreg('6', ':%s/^□■□$/■/g', 'l') :call setreg('7', ':%s/^□□■$/■/g', 'l') :call setreg('8', ':%s/^□□□$/□/g', 'l') 

Let’s write one more macro, c, to roll our paragraph of Rule 30 replacements back up into a single line:

:call setreg('c', '''aV}gJ', 'l') 

Now we’ll tie everything together with a macro, a, that copies the current line and pastes it below, performs our recursive line destructing, carries out our Rule 30 replacements, and then rolls everything back together, producing the next generation of our cells right below the previous generation:

:call setreg('a', 'yypma:.s/^.*$/ \0 /|norm!``@b@1@2@3@4@5@6@7@8@c', 'l') 

We can produce the next two generations of a given starting generation by calling a two times:

:norm 2@a 

□□■□□ □■■■□ ■■□□■ 

If we start with a bigger starting generation (fifty “off” cells on either side of a single “on” cell, in this case), we could go even further!

Fifty generations of Rule 30 generated entirely within Vim.

Final Thoughts

And with that, we can finally answer the question that has plagued us for so long. You can implement a Wolfram-style cellular automata, like Rule-30, entirely within Vim using only “normal” features like macros and substitutions. Rest easy, my tired brain.

Altogether our script looks like this, and produces fifty generations of a given seed:

:call setreg('a', 'yypma:.s/^.*$/□\0□/|norm!``@b@1@2@3@4@5@6@7@8@c', 'l') :call setreg('b', ':.s/^\(..*\)\(\(..\).\)$/\1\3\r\2/|norm!``@b', 'l') :call setreg('1', ':%s/^■■■$/□/g', 'l') :call setreg('2', ':%s/^■■□$/□/g', 'l') :call setreg('3', ':%s/^■□■$/□/g', 'l') :call setreg('4', ':%s/^■□□$/■/g', 'l') :call setreg('5', ':%s/^□■■$/■/g', 'l') :call setreg('6', ':%s/^□■□$/■/g', 'l') :call setreg('7', ':%s/^□□■$/■/g', 'l') :call setreg('8', ':%s/^□□□$/□/g', 'l') :call setreg('c', '''aV}gJ', 'l') :norm 50@a 

I’m no Vim expert by any stretch of the imagination, so if you think you can improve on this solution, either in terms of terseness or clarity, while staying in the bounds of only using normal Vim features (no Vimscript), please let me know!

As a closing remark, I want to be clear and say that this project served absolutely no purpose, and this is a terribly inefficient way of propagating cellular automata. That said, learned quite a lot about my text editor of choice, which I consider to be invaluable.

from Hacker News https://ift.tt/3bTe2Ng