Prime Numbers is among the hardest challenges in VimGolf. I've spent more time working on this challenge than any other. When I first saw it, I figured I'd have to brush up on my vimscript. As it turns out, you don't really need any at all.
"=r^I543)^MP:%no<S-Tab>~VEEkdYo@0D@.^O@.^MdZZ for 35.
That's the optimized version. It's tricky, but the basics behind it are relatively simple. The algorithm is the sieve of Eratosthenes. It uses
range() to set up a list of numbers, one per line, and
:%normal to run a macro on each line. Within the
:normal, it reads the number on the line, and recursively moves the cursor down that many lines, clearing each one (but not deleting them). Effectively, every number that's a multiple of the number on the line you started from is cleared. At the end, only the primes remain.
range(x)with one argument returns a list of the numbers in
[0,x). By typing it into the expression register's
"=command line, you can paste the numbers into the file, one per line. This is the only vimscript we'll use, and it's a common VimGolf trick anyway. (You could use an incrementing macro, but it's slightly slower than
range()when fully optimized.)
@0D@q: The macro to run from each line. The
"0register will be set beforehand to a macro that moves the cursor down some number of lines. We'll be in the first column, so
Dwill clear the line we get to.
@qmakes the macro recursively call itself until it hits the end of the file.
1so they don't get in the way.
:%normal: Runs its argument as a macro on each line.
~: Fails the
:normalon blank lines. This is normally the case flipping command, but it has useful macro failing properties. If the rest of the commands ran from blank lines, they would ruin the file.
:normaltreats failure different from other macros—it stops the current run of the macro, but it starts up again on the next. This means you can use a "failure test" to run commands conditionally... in this case, depending on whether the line is empty.
Y: Yanks the line the cursor is on. The line itself is a macro.
Yyanks the line with the newline (
^J) at the end, which is a normal mode command for moving the cursor down. The number on the line acts as a numeric argument to the newline at the end, and together they form a macro to move the cursor down the specified amount. This macro will be yanked into two registers,
"0, like any other yank. In the
"0untouched, so that's what we'll use.
@q: Run the recursive macro defined earlier. When it runs from the last line, it will fail, which is good, because you don't want your macros running forever. Note that the text
Prime Numbersthat we started the challenge with will still be there at first. This line acts as a "junk line". You need at least one line after the last prime, so the
^Jcommand doesn't land on a line you don't want to clear.
:v/./d: Every line that didn't contain a prime number is now blank. This command means "delete every line that doesn't contain a character". It destroys blank lines.
Just one last problem:
~ moves the cursor right a column, and
^J moves straight down, just like
j. You'd think we'd sometimes land on the second column when we run
D. This turns out not to be an issue though, because:
- from the number
2, the cursor can't go right anyway, and
- from every other number, the first
^Jwill land on a multiple of 2, which will already be blank. Once
Druns on the blank line, the cursor will stay on the first column until the end of the file.
Using command completion, a bunch of strokes were saved on
:normal starts with a nonletter, so there's no need for a space. The recursive macro is now defined as a
@. macro directly within the
:normal. The blank lines and the numbers above 2 are now removed by a slick key sequence that cleans as it goes.
Yo@0D@.: Both defines a macro in the
".register, and leaves a line full of junk. Both are useful. (This could also be
S^V^R"D@., which puts the number and newline directly into
o^X^LjD@., which "copies" the number above it using line completion. Stroke counts are the same.)
^O@.: If you want an
:normal, you have to prepend it with
^Vso it inserts literally.
^Ohas no such restriction, and it gives us one command in normal mode, which is all we need. You'd think we'd drop back to insert mode after the macro was done, but insert mode escaping is automatic at the end of
VEEkd: Deletes up to the next number we need. Does the right thing in several different contexts.
- Starting from
0, it deletes the lines with
1, leaving the cursor on
- On every subsequent line
:%normalhits, it deletes the line of junk created by the last
@.definition, and all the blank lines that might come after. This works because
earen't like the rest of the word family movements—they skip blank lines.
- When running from the junk after the last prime, the second
Ewill fail the macro, even though the cursor moved, and leave the editor in visual mode. When
:normalruns the next (blank) line,
Vfrom running, which would otherwise cancel visual mode. Since all the junk after the last prime ends up in a visual selection, you can delete it all in one stroke with
- Starting from
~ fails on blank lines, at the end of this macro, it's running from visual mode. It should try to flip the case of the visual selection. The reason it doesn't is there's bug in Vim.
Vim devs: Don't fix this. I like my 35.
I showed an alternate 38 in my write-up of It's a factor. Here are some more.
541O1^[s@-+>>@.^[:%no<S-Tab>@-^A^Dp@.^M:g/^I/d^MZZ for 38.
This 38 by @KersonHsiao also implements the sieve of Eratosthenes, but in a different way. Instead of starting with all the numbers, he decided to start with a bunch of
1s. He adds them up to their final values as he goes in the
:%normal. With that strategy, he can't clear the lines like I did; instead, he marks composite numbers by indenting their lines, and clearing the lines with tabs at the end.
C^I1^[qq^A>>Ypq540@q:g/\v^(^I^I+)\1+</d^M=(ZZ for 39.
Not the sieve of Eratosthenes this time. It starts by setting up the list of numbers, indented by tabs. If the number is 6, it will be indented by 6 tabs. Then a regex matches the tab sequences that can be split into 2 or more chunks of 2 or more tabs. The frowny removes the tabs at the end. There's a VimCast that does a great job describing this solution.
If you use the
factor program (included in GNU coreutils, and therefore available on lots of systems), you can save a couple strokes.
!!seq 541|factor^M:v/: \d*$/d^Mg&ZZ for 33.
This was mostly derived from work done by @federicogalassi. The
seq program makes a list of numbers, and
factor... factors them. Then you parse the output. The way
g& work together is especially elegant. The regex matches on lines that list only one factor, so
:v can remove lines with more.
g& uses that same regex to delete the factor listing itself on the remaining lines.
Read the manual
:help registers: You should really know this.
:help :normal: Less informative than I'd like. My article on tactical
:normalmay be more useful.
:help ~: Just to prove the manual never says anything about how commands can fail macros. You just have to figure it out yourself. I like to run tests, such as
@="~A". If the
~didn't fail in that position.
:help j: Just to show it's listed together with
:help e: Keep reading to the end of the section, and it talks about how
ecan skip blank lines.