miauのブログ

はてなダイアリー「miauの避難所」をはてなブログに移行しました

天下一プログラマーコンテストの予選例題やってみた

なんか見かけてちょっとやってみたら、妙なところで勉強になったのでネタにしてみる。

以下の文字列はUTF-8を文字エンコーディング形式とする16進数のバイト列である。 UTF-8エンコーディングされた文字列として解析した場合、この文字列の【文字数】を答えなさい。
e4bba5e4b88be381aee69687e5ad97e58897e381af5554462d38e38292e69687e5ad97
e382a8e383b3e382b3e383bce38387e382a3e383b3e382b0e5bda2e5bc8fe381a8e381
99e3828b3136e980b2e695b0e381aee38390e382a4e38388e58897e381a7e38182e3828be38082

やってみた

まあ一回やるだけならバイナリエディタに貼り付けて終わりだろうし、プログラムでまじめにやるなら pack() して〜とかやるところだけど、

※補足
なお、UTF-8では1バイト目の上位ビットを見ることで、その文字が何バイトの文字かがわかる。
2進数表記した場合以下のようになる。

  • 1バイト目の上位ビットが「0」 1バイトの文字
  • 1バイト目の上位ビットが「110」 2バイトの文字
  • 1バイト目の上位ビットが「1110」 3バイトの文字

これを読んでぱっと /[0-7].|[cd].{3}|e.{5}/ みたいな正規表現が思いついたので、自分だったらこんな感じで書くかなと。(※途中に改行が入ることは考慮してません。)

perl -pe "$_ = s/[0-7].|[cd].{3}|e.{5}//g"

誰も Code Golf しろとは言ってないけど、短く書けって課題だとこう書くかな。

perl -pe"$_=s/\d.|e.{5}|.{4}//g"

実はハマってた

ちなみに、もともとは、

perl -e "print scalar('e4bba5..e38082' =~ m/[0-7].|[cd].{3}|e.{5}/g)"

こんな感じでやろうとしてて、答えが 1 になってハマったりもしてた。perldoc -f scalar した感じだと、カンマ演算子っぽい動作になっちゃってるそうで、それを回避しつつ一時変数を使わずに処理するには、

perl -e "print scalar @{[ 'e4bba5..e38082' =~ m/[0-7].|[cd].{3}|e.{5}/g ]}"

こう書くことになりそう?あまりきれいじゃないし、-n や -p オプションを使えば破壊的な置換ができることに気づいたので不採用。

他の解法

で、はてブ経由でもっとよさげな解法を発見。

8〜b で始まってたら先頭の文字じゃないことが確定するから、それをばっさり落として文字数をカウントしていると。そういえば UTF-8 ってそういうもんだった。

こちらは本文で正攻法の解法&コメント欄で [89ab] を除外する方法を正規表現一発でやってる形と。

perl で最短っぽい書き方をすると、こんな?自分の解答よりも、こっちのほうがずいぶんシンプル。

perl -pe"$_=s/..([8-b].)*//g"

ちゃんと仕様把握してると楽ができるっていい見本だな。精進せねば。

      • -

念のため補足。Windows なのでダブルクォートで囲ってます。*nix な方はシングルクォートに書き換えてください。

・・・この注意書きを毎回書くの面倒だから、誰か Windows でも *nix でも気にせず動かせて、可読性もそんなに損なわれない記法を考えてほしいなぁ。(一時期考えてたんだけど、結局挫折した。)