AtCoder Beginner Contest をbashとTukubaiで解く
シェルスクリプトマガジンでシェル女子の連載をされているちょまど氏が「AtCoder Beginner Contest」に参戦されたというTLがTwitterで流れてきた。
【再掲】数時間前にブログを書きました！
— ちょまど@MS入社して2ヶ月 (@chomado) September 20, 2015
昨日 (初心者向けのやつですが) 人生初競プロのコンテスト出て、すごい楽しかったから、記念に書きました！
提出したコードも載せてます
ーーーー
初めて競技プログラミングのコンテストに出た http://t.co/PyPF5Ue2pT
C言語やJava、PHP、Ruby、Haskell、JavaScriptなどのプログラミング言語を使って4つのお題を解く内容らしい。ルールなどは下記のリンクで。なお参戦期間は終了している。
- AtCoder Beginner Contest 029 | AtCoder
プログラマの端くれであるし、シェル芸人の端くれでいるつもりなので、bashで解いてみよう。反則な気もするがTukubaiコマンドも便利なので解禁で。 ちなみにTukubaiコマンドとは、ユニケージ開発手法で利用されているコマンド群のこと。これがあるとCUIでのオペレーションやテキストデータの操作が格段に便利になること請け合い。
環境
いつものように回答はMacで。
- OS X Yosemite
- GNU coreutils（gseq、gtr、gwcなど、頭にgを付けたコマンドになる）
- Open usp Tukubai
回答
問題は標準入力からデータを入れるらしい。回答は標準出力へ回答を吐き出せばいいのかな？と判断。では4つの問題を順次解いてみる。問題の詳しい内容はリンクから参照いただきたい。
A - 複数形
A: 複数形 - AtCoder Beginner Contest 029 | AtCoder
問題の趣旨は、入力された文字列の最後に's'をくっつけること。sed芸一発。
QA.bash
#!/bin/bash sed 's/$/s/'
$ echo dog | ./QA.bash
dogs
$ echo chokudai | ./QA.bash
chokudais
B - カキ
[http://abc029.contest.atcoder.jp/tasks/abc029_b:title]
文字'r'が含まれる行数を数える。ちなみにこの問題の題目がなぜ「カキ」なのか？と思ったが、rが付かない月の時期にカキを食うとアタルというのがあったな・・・
まあこれはgrepとwc -lの合わせ技でオケ。最後のtr -dコマンドは余計な空白を削除するため。
Mac標準wcコマンドだと、頭に余計な空白が出てしまう。GNU版wc -lコマンドか、Tukubaiのgyoコマンドだと余計な空白が出なくてスッキリ。
QB1.bash
#!/bin/bash grep 'r' | wc -l | tr -d ' '
QB2.bash
#!/bin/bash grep 'r' | gwc -l
QB3.bash
#!/bin/bash grep 'r' | gyo
$ cat <<EOF | ./QB1.bash
> january
> february
> march
> april
> may
> june
> july
> august
> september
> october
> november
> december
> EOF
8
$ cat <<EOF | ./QB1.bash
> rrrrrrrrrr
> srrrrrrrrr
> rsr
> ssr
> rrs
> srsrrrrrr
> rssrrrrrr
> sss
> rrr
> srr
> rsrrrrrrrr
> ssrrrrrrrr
> EOF
11
・・・と、ここまで書いたところで、grep -cオプションを思い出してしまい・・・あらま簡単。
QB4.bash
#!/bin/bash grep -c 'r'
C - Brute-force Attack
C: Brute-force Attack - AtCoder Beginner Contest 029 | AtCoder
abcの3文字を使って長さN文字の組み合わせを出す。ポイントは「組み合わせ全列挙」。再起呼び出しとか多重ループとか使うことになると思うが・・・さてどうするか？ここでTukubaiの必殺loopxコマンド登場。
使い方は下記の通り。データが入ったファイルを指定すると、組み合わせ全列挙してくれる。今回の問題は、最後の例のように、一行ごとにabcが書かれたファイルをN回指定してやればよさそう。
$ cat alpha
a
b
c
$ cat num
1
2
$ loopx alpha num
a 1
a 2
b 1
b 2
c 1
c 2
$ loopx alpha alpha
a a
a b
a c
b a
b b
b c
c a
c b
c c
あとは指定した回数だけファイル名を呼び出すにはどうするか？これはyesコマンドとheadコマンドの組み合わせでオケ。
$ yes alpha | head -n 2 | tr '\n' ' '
alpha alpha
$ yes alpha | head -n 10 | tr '\n' ' '
alpha alpha alpha alpha alpha alpha alpha alpha alpha alpha
ということで回答。abcのデータが入った一時ファイルを作成。一時ファイルのファイル名を、指定した回数だけ列挙してloopxコマンドで組み合わせ全列挙。最後に空白を削除。
QC.bash
#!/bin/bash tmp=/tmp/tmp-$$ read n cat <<EOF > $tmp-strings a b c EOF loopx $(yes $tmp-strings | head -n $n | tr '\n' ' ') | tr -d ' ' rm -f $tmp-*
$ echo 2 | ./QC.bash
aa
ab
ac
ba
bb
bc
ca
cb
cc
別解追加
後で思いついた回答。bashのブレース展開を使ってもよかった。こんな感じ。
$ echo {a..c}
a b c
$ echo {a..c}{a..c}
aa ab ac ba bb bc ca cb cc
つまり{a..c}を必要な文字数だけ繰り返してやれば良さそう。必要な分だけ繰り返して表示はyesコマンドとheadコマンドの組み合わせで。
$ yes '{a..c}' | head -n 2
{a..c}
{a..c}
後は実行したいコマンド文字列を作ってしまえばいい。
$ yes '{a..c}' | head -n 2 | tr -d '\n' | sed 's/^/echo /'
echo {a..c}{a..c}
ということで回答はこちら。
QC1.bash
#!/bin/bash read n yes '{a..c}' | head -n $n | tr -d '\n' | sed 's/^/echo /' | bash | tr ' ' '\n'
$ echo 2 | ./QC1.bash aa ab ac ba bb bc ca cb cc
D - 1
D: 1 - AtCoder Beginner Contest 029 | AtCoder
最後は'1'の文字を探し出して数え上げ。この辺はシェル芸の得意領域かな？tr -dcは指定した文字以外を全て削除（改行なども）。
$ seq 12
1
2
3
4
5
6
7
8
9
10
11
12
$ seq 12 | tr -dc '1'
11111
あとは1が並んでいる文字列の長さをwc -cでカウントすればオケ。ということで回答。
QD.bash
#!/bin/bash read n seq $n | tr -dc '1' | wc -c | tr -d ' '
$ echo 12 | ./QD.bash
5
$ echo 345 | ./QD.bash
175
しかしながら、入力が999999999だと、ものすごく時間がかかってしまいアウト・・・Mac標準のseqとtrが遅い。
高速化のためGNUコマンドに切り替えても、20秒くらいかかってしまった。
QD1.bash
#!/bin/bash read n gseq $n | gtr -dc '1' | gwc -c
$ time echo 999999999 | ./QD.bash
900000000
real 0m20.109s
user 0m23.945s
sys 0m8.986s
ポイント
bashなどのシェルでデータ処理する時のポイントは、他のプログラミング言語のようにデータを変数で持たせてゴニョゴニョするという発想をしない方がいい気がする。
- パイプを活用してストリーム処理
- 一時ファイルを活用
