日々之迷歩

世の中わからんことだらけ

ITが複雑で難しくなっていく様に翻弄される日々です

AtCoder Beginner Contest をbashとTukubaiで解く

シェルスクリプトマガジンでシェル女子の連載をされているちょまど氏が「AtCoder Beginner Contest」に参戦されたというTLがTwitterで流れてきた。

C言語やJava、PHP、Ruby、Haskell、JavaScriptなどのプログラミング言語を使って4つのお題を解く内容らしい。ルールなどは下記のリンクで。なお参戦期間は終了している。

- AtCoder Beginner Contest 029 | AtCoder

プログラマの端くれであるし、シェル芸人の端くれでいるつもりなので、bashで解いてみよう。反則な気もするがTukubaiコマンドも便利なので解禁で。 ちなみにTukubaiコマンドとは、ユニケージ開発手法で利用されているコマンド群のこと。これがあるとCUIでのオペレーションやテキストデータの操作が格段に便利になること請け合い。

Open usp Tukubaiコマンドマニュアル

環境

いつものように回答は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が付かない月の時期にカキを食うとアタルというのがあったな・・・

まあこれはgrepwc -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標準のseqtrが遅い。

高速化のため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などのシェルでデータ処理する時のポイントは、他のプログラミング言語のようにデータを変数で持たせてゴニョゴニョするという発想をしない方がいい気がする。

  • パイプを活用してストリーム処理
  • 一時ファイルを活用

シェルプログラミングの参考文献

シェルスクリプト高速開発手法入門

gihyo.jp

https://uec.usp-lab.com/JOURNAL/CGI/JOURNAL.CGI?POMPA=LIST

www.atmarkit.co.jp