合成数列の和アドベントカレンダー sed 編

ルール

• 入力として正の整数 N を与えたら 4 から始まる合成数の数列の 1 番目から N 番目までの合計を出力してください
• N は最大で 100 とします

sedとは

今回使う sed とは、名前を"stream editor"に由来する、古くからUNIX系のシステムで使われているテキスト処理ツールです。

…というのは表向きの顔。
今回の問題を解けることからも分かる通り、ただのテキスト処理に留まらず、強力でプログラマブルな機能を有するツールなのです。
それがなぜ「テキスト処理」のくくりに入っているのか。その理由は大分昔にさかのぼります。以下に参考資料の一部をあげます。

時の為政者が、プログラミングツールによる作業の効率化を弾圧した暗黒の時代、賢人「速・欸都(su・eidu)」がプログラマブルな能力を隠し、あくまでテキスト処理ツールだと、エディターに過ぎないとして「流編者」を開発し、弾圧を避けつつも世に広めました。sedの名前は、オリジナルのツール名の英語訳と、開発者のアルファベットをかけたものになっています。
そして人々は彼とこのツールに感謝し、後発のプログラミング言語ではなく、敢えて sed で ( 或いは各種ツール群もまじえて ) 処理をこなすという「謝流(シェリゥ)芸」を嗜むという習慣を生み出しました。
そう、これが当に、現代に受け継がれる「シェル芸」のルーツなのです。
※出典: 「虐げられし技術と腹背の開発者」( 民明書房刊 )

今回、そのような歴史あるツールで挑戦できるというのは、非常に光栄なことです。

…。

…。ポエム終わり。
一応念のためですが、この由来の話は適当にでっち上げたものなので信用しないでくださいね。

出力例

Win10+WSL/Ubuntu16.04/GNU sed 4.2.2 で試しました。が、同じGNU sedなら他の環境でも同じように動くと思います。

1要素だけ

$ sed -rf sum_cnum_seq.sed <<< 1
4

複数要素

$ cat input.dat
2
4
10
100
$ sed -rf sum_cnum_seq.sed input.dat
10
27
112
7059

ソース

sum_cnum_seq.sed

# 数値以外は対象外
/^[1-9][0-9]*$/!d
# ホールドスペースの初期化 ( 数字は後で削除されるので無害 )
h
# 数値を同じ文字数のXに変える
:Ln2x
 s/$/  9z8z7z6z5z4z3z2z1z0/
 s/^(.)(.* .*) [^ ]*\1([^ ]*)$/\2\3/
 s/X/XXXXXXXXXX/g
 y/z/X/
 /^ /!b Ln2x
# 余分な文字を削除し、Xのみの文字列にする
s/[^X]//g
# 合成数の加算(加算する数値分の文字数のYをホールドスペースに追加していく)
s/^/YYY  /
:Ladd
 # 偶数は無条件で加算対象
 s/ /Y/
 H
 # 加算回数上限に達したらループ脱出
 T; s/XX/X/; T Lpost
 # 3以上の奇数による試し割り
 s/^YY/YYY /
 :Ltry
  /^(Y+) \1+ /! {
   s/ YY/YY /
   /^(Y+) \1{4}/b Ltry
   b Ladd
  }
 # 合成数のみ加算
 H
 T; s/XX/X/; t Ladd
:Lpost
# ホールドスペースに追加していったデータを取り出し、Yのみにする
x
s/[^Y]//g
# Yのみの文字列から文字数を表す数字へ変換
:Ly2n
 s/YYYYYYYYYY/z/g
 s/$/ YYYYYYYYY9YYYYYYYY8YYYYYYY7YYYYYY6YYYYY5YYYY4YYY3YY2Y10/
 s/(Y*)([0-9]*) .*\1([0-9]).*$/\3\2/
 T; s/z/Y/g; t Ly2n
# 最終結果が出力される

解説

sedの機能

「sedとは」の由来の説明は思いっきりでっち上げですが、とは言え sed がプログラマブルなツールであることは確かです。

• 文字列操作が可能なパターンスペースと、バックアップ的にデータを保持できるホールドスペースという、十分な記憶域
• :によるラベル定義と、b,t等のラベルへのジャンプ、それに条件判定を組み合わせた条件分岐やループ
• そしてなにより正規表現による強力なマッチングと文字列置換

sed で使用できる正規表現は、POSIX.2 Basic-RE と Extended-RE の2種類で、Perl,Rubyといった言語で使えるものより機能的にはやや見劣りします。が、それでも十分な機能を持っています。
※sedビルド時の設定によっては、PCRE(Perl互換正規表現)も使えるようなのですが…

今回は、後方参照(back-reference)を利用するために Extended-RE を選択しており、sed 実行時に -rオプション ( 或いは-E ) で指定します。

全体の流れ

この数値の処理が絡む問題を文字列処理で解くと言われると、さっぱり想像もつかないかも知れません。
しかし、数値は文字列の長さとして扱うことができます。
しかも、素数/合成数は正規表現で判定できるというのは一般に良く知られた事実です。

ということで、全体の流れです。

• 入力数値を、同じ長さを持った文字列に変換する
• 文字列の長さを減らしてカウントダウンとしつつ、加算する数に相当する文字列を、長さを増やしながらホールドスペースへ追加していく
• 合成数の判定は正規表現で行う
• 最後、ホールドスペースにたまった文字列を、その長さを見て、数字に変換する

数字⇔文字列変換

まずは数字と文字列の変換ですが、ここでは後方参照を用いた文字列置換を活用しています。

最初の数字→文字列変換では、9z8z7z6z5z4z3z2z1z0 を末尾に追加しているのが仕込みです。
この後、先頭桁の数字に応じて、後方参照で、良い感じに長さを区切ることができるのです。例えば先頭が7なら、正規表現の \1 によって、9z8z7の7の所までが削除される部分としてマッチし、以降のz6z5z4z3z2z1z0という7文字のzが残されます。
この仕組みで、数字に応じた長さの文字列を作り出せるのです。
※残った余分な数字は後で一括で削除。

例として、23が入力の場合、次のように変換されます。

• 末尾に追加
  23→23 9z8z7z6z5z4z3z2z1z0
• 正規表現で先頭桁の2の部分まで間が削除される
  23 9z8z7z6z5z4z3z2z1z0→3 z1z0
• zをXに変換
  3 z1z0→`3 X1X0
• まだ先頭に数字の桁が残っているので、最初(Ln2xのラベル)に戻る
  
• また末尾に追加
  3 X1X0→3 X1X0 9z8z7z6z5z4z3z2z1z0
• 正規表現で3の部分まで間を削除
  3 X1X0 9z8z7z6z5z4z3z2z1z0→X1X0 z2z1z0
• Xを10倍にした上でzをXに変換
  X1X0 z2z1z0→XXXXXXXXXX1XXXXXXXXXX0 X2X1X0
• 先頭の数字の桁がなくなったので、余分な文字を消して変換完了
  XXXXXXXXXX1XXXXXXXXXX0 X2X1X0→XXXXXXXXXXXXXXXXXXXXXXX

最後の、文字列(Yのみ)から数字への変換も、10文字ずつまとめるようないわば余り付き割り算に相当する処理を行う以外は、ほとんど似たようなことをやっています。
つまり、端数として余ったYの塊を、仕込みで追加したYYYYYYYYY9YYYYYYYY8YYYYYYY7YYYYYY6YYYYY5YYYY4YYY3YY2Y10とマッチさせ、丁度Yの文字数と合っているところの数字の桁を選び出すということです。
例えば7文字のYYYYYYYの塊が残った場合、YYYYYYYYY9YYYYYYY8に続くYYYYYYY が後方参照\1に引っかかりますから、その次の 7 を残せば丁度数字に変換できているということです。

なお、9 の方を先に持ってきているのには理由があります。
それは、正規表現のマッチングが最長マッチであるということです。
※Perl等なら最短マッチ表現も使えるのですが
つまり、合致するパターンが複数あったとしても一番長く、文字列の後方まで行ったものが採用されますので、短いパターンほど後に持ってこないとまずくなるのです。

合成数の判定と加算

さて、合成数を正規表現で判断する方法についてです。

Yだけで構成された文字列の場合、単純に、後方参照(back reference)を利用して^(YY+)\1+$という正規表現にマッチすれば文字数が合成数と分かります。
これは、2文字以上の塊 ( 括弧でキャプチャした内容 ) が丁度複数回繰り返すかどうか、そうなるような塊の取り方があるかどうかを見ていることになります。

しかし、今回この判定方法は見送りました。なぜなら、sed では非常に時間がかかってしまうためです。代わりに、試し割りに相当するループを実装しました。コード上Ltryラベルから始まる処理です。

合成数かどうかを判断する正規表現は^(YY+) \1+です ( )と+の後に空白があることに注意 )。マッチを試す前に、先頭のY複数文字を切り離しておくことで、またその文字数を2ずつ増やしていくことでループとしています。
先ほど示した ^(YY+)\1+$と比べると、括弧でキャプチャした文字数が1通りに決まるのが大きな違いです。

また、試し割りの数がある程度大きくなったところでループを打ち切るための判定も行います。ループの初回に3の試し割りを済ませている以上、合成数であれば最低でもキャプチャした塊が4個 ( キャプチャした分を合わせて5個 ) 以上あるはずですから、それだけの塊がとれなければ素数だということになります。

メモ

この問題はずんだ問題の番外編です。

また、このソースを流用してシクシク素数アドベントカレンダー sed 編も組んでますので、よければそちらもどうぞ。