問題
Vim は何でもできます。
何でもできるのですから当然 Vim で素数を列挙することもできます。
ただ列挙するだけだと面白みに欠けますから、
Vim で最少の手数で素数を少ない順に100個だけ列挙するときっとモテるに違いありません。
一体どうすればよいのでしょうか。
方法1: 素朴に列挙する
まずは素数を列挙してリストとして返す関数を作りましょう。
function ListPrimes()
let primes = [2]
let n = 3
while len(primes) < 100
if empty(filter(copy(primes), 'n % v:val == 0'))
call add(primes, n)
endif
let n += 2
endwhile
return primes
endfunction後はこの関数の結果を貼り付けて体裁を整えればOKです。
put =ListPrimes()
1 delete
wq全体としてはこんな感じですね:
:function ListPrimes()
let primes = [2]
let n = 3
while len(primes) < 100
if empty(filter(copy(primes), 'n % v:val == 0'))
call add(primes, n)
endif
let n += 2
endwhile
return primes
endfunction
:put =ListPrimes()
:1 delete
:wqさっそく VimGolf にこの回答を登録してみましょう:
$ vimgolf put 4d1c27940e3d7832db000010
Downloading Vimgolf challenge: 4d1c27940e3d7832db000010
Launching VimGolf session for challenge: 4d1c27940e3d7832db000010
...
Success! Your output matches. Your score: 256
Upload result to VimGolf? (yes / no)256手だそうです。美しい手数ではありますが、まあ素朴に解いただけなので面白味がありません。
ここからどんどん手数を減らしていきましょう。
方法2: 素朴に圧縮する
手数を減らすにはまず無駄を減らすことです。
まずインデントは不要です:
:function ListPrimes()
let primes = [2]
let n = 3
while len(primes) < 100
if empty(filter(copy(primes), 'n % v:val == 0'))
call add(primes, n)
endif
let n += 2
endwhile
return primes
endfunction
:put =ListPrimes()
:1 delete
:wq:function 等は :fu のように省略可能です。という訳で各コマンドも限界まで省略しましょう:
:fu! ListPrimes()
let primes = [2]
let n = 3
wh len(primes) < 100
if empty(filter(copy(primes), 'n % v:val == 0'))
cal add(primes, n)
en
let n += 2
endw
retu primes
endf
:pu =ListPrimes()
:1 d
:wqn += 2 等のスペースも当然不要ですね。詰めましょう。
:fu! ListPrimes()
let primes=[2]
let n=3
wh len(primes)<100
if empty(filter(copy(primes),'n%v:val==0'))
cal add(primes,n)
en
let n+=2
endw
retu primes
endf
:pu=ListPrimes()
:1d
:wq変数名も関数名も1文字で十分です。詰めましょう。
これで大分短くなったはずです:
:fu! L()
let p=[2]
let n=3
wh len(p)<100
if empty(filter(copy(p),'n%v:val==0'))
cal add(p,n)
en
let n+=2
endw
retu p
endf
:pu=L()
:1d
:wqでは VimGolf にこの回答を登録してみましょう:
$ vimgolf put 4d1c27940e3d7832db000010
Downloading Vimgolf challenge: 4d1c27940e3d7832db000010
Launching VimGolf session for challenge: 4d1c27940e3d7832db000010
...
Success! Your output matches. Your score: 137
Upload result to VimGolf? (yes / no)137手。半分近くに削減できましたが、まだまだですね。もっと減らせそうです。
方法3: より手数の少ない方法に書き換える
- 関数を使うのを止めましょう。関数を使うと分かり易くなりますが定義や戻り値を書くだけで手数が増えてしまいます。
empty(...)は...==[]と等価ですが後者の方が短いですね。cal add(p,n)はlet p+=[n]と等価ですが後者の方が短いですね。
:let p=[2]
:let n=3
:wh len(p)<100
if filter(copy(p),'n%v:val==0')==[]
let p+=[n]
en
let n+=2
endw
:pu=p
:1d
:wqでは VimGolf にこの回答を登録してみましょう:
$ vimgolf put 4d1c27940e3d7832db000010
Downloading Vimgolf challenge: 4d1c27940e3d7832db000010
Launching VimGolf session for challenge: 4d1c27940e3d7832db000010
...
Success! Your output matches. Your score: 115
Upload result to VimGolf? (yes / no)115手。あまり減らせていません。そろそろベースとなっているコードを一から考え直す時期のようです。
方法4: 関数的にする
これまでは100個の素数を p に蓄積するまでループし、ループ中に調査対象の数 n を更新していました。
しかしこの更新部分で9手も消費しています。予め上限が分かっているなら :for n in range(...) とすれば良いのでは?
:let p=[]
:for n in range(2,541)
if filter(copy(p),'n%v:val==0')==[]
let p+=[n]
en
endfo
:pu=p
:1d
:wqところでこの :for n in ... は各値が条件に合致するか調べて、合致するものだけを p に追加しています。
言い換えればこれは filter() そのものでは? そして filter() で書き直せるなら p も不要になります:
:pu=filter(range(2,541),'filter(range(2,v:val-1),v:val.''%v:val==0'')==[]')|1d
ZZついでなので :pu=...^M:1d を :pu=...|1d に、 :wq^M を ZZ に置き換えました(※ ^M は Ctrl-M を表します)。
ほとんどワンライナーです。これは大分イケてるんじゃないでしょうか。
$ vimgolf put 4d1c27940e3d7832db000010
Downloading Vimgolf challenge: 4d1c27940e3d7832db000010
Launching VimGolf session for challenge: 4d1c27940e3d7832db000010
...
Success! Your output matches. Your score: 81
Upload result to VimGolf? (yes / no)81手。最初の1/3程度になりました。しかしこれでもVim業界では中の下程度のスコアです。
まだ何か方法があるはずです。
方法5: 数値演算以外の方法を考える
まず気になるのは入れ子になった filter() です。
組み込み関数は名前を省略できませんし、中に書く式も長ったらしくなっています。
ところで、素数判定を行っている条件式を読み易く書き直すと
filter(range(2, n - 1), 'n % v:val == 0') == []なのですが、これは
「 2 以上 n 未満の各整数 v:val について、 n が全ての v:val で割り切れない」
ことを表しています。
ここは整数の演算を行う必要性があるのでしょうか。
整数の代わりに文字列を使うとしたらどうでしょう。
例えば 3 なら 'xxx' で、 5 なら xxxxx で表すとしましょう。
このエンコードを施せば、
- 正規表現
xx+で2以上の整数を表すことができ、 - 正規表現
(xx+)\1+で2以上の整数の倍数を表すことができます。
となると任意の整数が合成数かどうかは n =~ '\v^(xx+)\1+$' で表現できます。
エンコードは repeat(n, 'x') で簡単にできます。
ということは以下の手順で素数が列挙できるはずです。
:pu=filter(range(2,541),'repeat(''x'',v:val)!~''\v^(xx+)\1+$''')|1d
ZZここでは分かり易さのために整数を x の列にエンコードしましたが、
文字列リテラルを書くにはクォートが必須です。
実のところ Vim script では文字列と数値は相互に自動変換されますから、x にエンコードするのではなく 8 にエンコードするようにしましょう。
:pu=filter(range(2,541),'repeat(8,v:val)!~''\v^(88+)\1+$''')|1d
ZZこれなら大分イケるんじゃないでしょうか。
$ vimgolf put 4d1c27940e3d7832db000010
Downloading Vimgolf challenge: 4d1c27940e3d7832db000010
Launching VimGolf session for challenge: 4d1c27940e3d7832db000010
...
Success! Your output matches. Your score: 66
Upload result to VimGolf? (yes / no)66手。当初の1/4近くになりましたが、まだまだVim業界では中の中の下くらいの位置ですね……
方法6: 編集方法を変える
これまでは素数のリストを作ってそれをペーストする形で対応してきましたが、
考え方を変えればもっと短くできるかも知れません。
なので Vim script レベルでリストを使うところから疑ってみましょう。
データを溜めておくのにリストを使う必然性はありません。
何故ならバッファーに書き出す形でも同じことができるからです。
試しにこの方向で考えてみましょう。
まずエンコードした数値をバッファに書き出します:
:put =map(range(2, 541), 'repeat(8, v:val)')リストを使っていた時は filter() で素数を絞り込んでいましたが、
バッファー相手なら :global と :delete を組み合わせれば同じことができそうです。
エンコードした数値なら正規表現で素数判定ができますからね:
:global/\v^(88+)\1+$/deleteただこれだとバッファーの内容が以下のように悲しい感じになります:
88
888
88888
8888888
88888888888
...と言う訳でエンコードした数値をデコードすることを考えましょう。
行頭にカーソルがあると仮定すれば、これは以下の手順でできますね:
(※ ^R は Ctrl-R を、 ^[ は Ctrl-[ を表します):
C^R=len(@-)
^[インサートモード中で ^R= を押下すると任意の式を入力できます。
式を入力して <Enter> を押下すると式の評価結果がバッファーに挿入されます。
文字の長さは len() で数えることが出来て、C 等で1行より小さい範囲を削除した場合はそのテキストがレジスター - に格納されます。
レジスターは @{register_name} で参照できますから、len(@-) で元々あったテキストの文字数が得られるわけです。
これで全てのパーツが揃いました。全体としては以下の手順で素数が列挙できます:
:pu=map(range(2,541),'repeat(8,v:val)')|g/\v^(88+)\1+$/d
qaC^R=len(@-)
^[k0q99@addZZ試しにこれを VimGolf に投稿してみましょう:
$ vimgolf put 4d1c27940e3d7832db000010
Downloading Vimgolf challenge: 4d1c27940e3d7832db000010
Launching VimGolf session for challenge: 4d1c27940e3d7832db000010
...
Success! Your output matches. Your score: 83
Upload result to VimGolf? (yes / no)83手。
これまでの66手から少し増えてしまいましたが、
どうしても手数を食う filter() を除外できたことは大きいです。
この方針でもう少し詰めてみましょう。
方法7: map を reduce する
先程は filter() を別の方法で置き換えました。
同様に map() も別の方法で置き
換えられるのではないでしょうか?
数値をそのまま扱っていた時は処理が面倒でしたが、
エンコードすれば簡単な文字列処理に置き換えられるのでより短くできそうです。
:pu=map(range(2,541),'repeat(8,v:val)')これが行っていることは「2から541までの数値をエンコードした結果をペーストする」なので、
- エンコードした2を書き込む。
- その行をコピー・ペーストする。
- ペーストした行に1文字追加する(コピー元の数値+1のエンコード結果になる)。
- 2と3を540回ほど繰り返す。
とすればできます。これを Vim 語に翻訳すると以下の通りです:
Sxx^[qaYpAx^[q540@a明らかに map() を使っていた時より短くなりました。
全体の手順をまとめると以下の通りです:
Sxx^[qaYpAx^[q540@a:g/\v^(xx+)\1+$/d
qbC^R=len(@-)
^[k0q99@bZZこれは良い感じです。
$ vimgolf put 4d1c27940e3d7832db000010
Downloading Vimgolf challenge: 4d1c27940e3d7832db000010
Launching VimGolf session for challenge: 4d1c27940e3d7832db000010
...
Success! Your output matches. Your score: 58
Upload result to VimGolf? (yes / no)58手。66手から8手もの進歩です。やりましたね。
方法8: エンコード方法を変える
これまでは数値 n を長さが n の文字列にエンコードした上で文字列処理を行い素数を列挙してきました。
文字は何でも良かったので、 x や 8 を利用してきましたが、ここももう少し工夫のし甲斐がありそうです。
素数列挙の最初のステップが「2 から 541 の整数をペーストする」なのですが:
- 初期値を書き込む:
Sxx^[ - 「それをコピーして1文字追加する」を540回くらい繰り返す:
Sxx^[qaYpAx^[q540@a
この「1文字追加する」が曲者です。 Ax^[ で3手もかかっています。
これがインデントの調整なら >> や << の2手で済みます。
ということはエンコードに使う文字をタブ ^I に限定すれば良いのではないでしょうか?
さらに「コピーして1文字追加する」を「1文字追加してからコピーする」に変えると
初期値として書き込む文字数は2文字から1文字に減らせます。
つまりはこういうことです:
S^I^[qa>>Ypq540@a:g/\v^(^I^I+)\1+$/d
qb0C^R=len(@-)
^[kq99@bZZこれならどうでしょう:
$ vimgolf put 4d1c27940e3d7832db000010
Downloading Vimgolf challenge: 4d1c27940e3d7832db000010
Launching VimGolf session for challenge: 4d1c27940e3d7832db000010
...
Success! Your output matches. Your score: 56
Upload result to VimGolf? (yes / no)56手。最初のバージョンから22%程度のサイズに削減できました。
しかし……しかしこれでもVim業界では中の中のほんのり上程度のスコアです。
恐るべしVim業界。
方法9以降
さすがに疲れたのでこれ以上は皆さんの宿題とします。
補足
次回は Emacs 編です。
＃人気の記事
＃タグ
