ほげめも

CodeIQ: Q124 解説編

昨年 参加して解答を送ってみた CodeIQ の問題 ですが、 gihyo.jp 連載 に 解説記事 が出ていました。

私の解答を github.com にあげておいたので、興味のある方はご覧ください。

解答の解説

解答のスクリプト encode.sh は /bin/sh プログラミング的なみどころをあげると次のようになるでしょうか。

  1. 算術演算構文 $((expression))
  2. バイナリ入出力
    • od コマンド でバイナリ列を 1 バイト単位で読み込める形に変換する
    • printf コマンド で 1 バイトずつ変換してバイナリ列を書きだす
  3. 合流するパイプラインの作成

1. は特に難しいところもないので、今回は 2. と 3. について説明します。

バイト入出力

可能なかぎり外部コマンドは使わず実装するように頑張ってみたのですが、バイナリ列の入出力だけは /bin/sh のビルトイン機能だけでは苦しく、やむをえず od と printf に頼ることになりました。

まずバイト列の入力ですがこれは od コマンドを次のように使います。

$ cat plain.txt
漢字、カタカナ、ひらがなの入ったPNG。
$ od -v -An -tu1 plain.txt
 230 188 162 229 173 151 227 128 129 227 130 171 227 130 191 227
 130 171 227 131 138 227 128 129 227 129 178 227 130 137 227 129
 140 227 129 170 227 129 174 229 133 165 227 129 163 227 129 159
  80  78  71 227 128 130  10

このままでは 1 行につき 16 バイトと使いにくいので、さらにこれを p3split() 関数に通して次のような 1 行に 1 バイトに変換します。 while read a のような構文で読み込むのに適した形となります。

230
180
162
229
...

次にバイト列の出力ですが、これには printf コマンドの %b フォーマットを使います。 p3decode() では次のように使っています。

    printf %b $(printf '\\0%o' $c)

%b に 8 進数文字コード表記 \0nnn を渡すと、それをよくある echo コマンドのように解釈して出力してくれます。 POSIX の echo のマニュアル の APPLICATION USAGE にも、ポータビリティに問題のある echo よりも printf の %b を使うようにと書かれています。

合流するパイプライン

合流するパイプラインというのは、次の encode() で関数でやってる exec リダイレクトのようなことです。

encode() {
        test $# -lt 2 && abort "Usage: $0 plain.txt source.png >embedded.png"
        exec 8<&0 # ← dup2(0,8);
        od -v -An -tu1 "$1" | p3split | (
                exec 9<&0 <&8 8<&- # ← dup2(0,9); dup2(8,0); close(8);
                pngtopnm "$2" | pnmtoplainpnm | p3split | p3encode | pnmtopng
        )
}

/bin/sh のパイプ | には親プロセスの fd 1 と子プロセスの fd 0 をつなぐ機能しかないため、複数のプロセスからの出力を同時に扱いたければ、このように個々のパイプを閉じないように維持管理する必要があります。

さもなければあきらめてテンポラリファイルを作るか bashism に堕ちて <(command) といった構文を使うしかありません。なおこの手のことは whiptail コマンド を使うプログラムなどでは頻出します。

感想

今回の問題の受付期間は 2 週間ほどだったと思いますが、その間の挑戦者は 20 名でした。もうちょっと盛り上がればよかったなと思います。

正答率が低いのも残念でした。ただ 解説記事 によれば不備がある解答 1 件も正解にしたとありますが、それは私の解答のことかもしれません。画像に収まらない長さの文字列が来た場合のチェックはしてなかったので。

CodeIQ はまた面白そうな問題が出たら挑戦してみたいです。最近はコードゴルフ問題が流行ってるみたいですが、これは際限なく時間を吸い取られる危険な問題なので、いまのところ私は手を出してません。

なお伝統ある Ruby FizzBuzz ゴルフ (の亜種) が 今日締め切り のようですが、いったいどのような結果になるのか、ちょっと気になっています。解答は公表されないんでしょうか。

2013/01/14 00:56:00 JST