Subscribed unsubscribe Subscribe Subscribe

@kyanny's blog

Write down what I learnt. Opinions are my own.

Re:Excel列名変換問題で第2回社内プログラミングコンテストを開催してみた(前編)

http://d.hatena.ne.jp/aereal+tech/20111104/1320351723 で知って時間計りながら書いた。問題1を解くのに57分もかかった。「問題1を解き終わるまで問題2は読まないこと」というルールがあったのでそれに従って解き終わってから問題2をみたらすでに実装済みだったのでテストケースだけ追加して両方合わせて1時間ちょいだったと思う。

https://gist.github.com/1366384

http://subtech.g.hatena.ne.jp/secondlife/20100224/1267018963 のようなものを作ればいいんだよなとすぐわかった。記事を探してコードを読むのはやめた (なので perldoc と問題が書いてあるページ以外は見ていない)

とりあえずアルファベットと数字の変換テーブルを作ってさてどうしようかなと少し考えて、「アルファベット -> 数字」よりも「数字 -> アルファベット」の変換のほうが楽に思えたので先にそれを実装した (number_to_alphabet, _number_to_alphabet_rec) 26 進数 (基数 26) だから 26 で割っていって商とあまりを変換して文字列連結すればいいと考えて繰り返しは再帰すればいいかとそのまま書き下した。これは30分以内で終わってたと思う。

実際欲しいものはこれの逆なので、できたコードを見ながら反対の仕事をするように書いていけばいいかなと思って実装しはじめた (alphabet_to_number, _alphabet_to_number_rec) 桁数に応じて掛ける数を調整するあたりがなかなかうまくいかなくて print デバッグを入れまくったりして時間がかかった。やりながらなんとなく、数学というか数についての体系的な基礎知識がないせいで無駄なことをやっていそうだなと思った。

例にあがってた XFD とかでちゃんと動いてるのを確認できたのでテストケースを書いて問題1を終えて問題2を読んだら前述のとおりもうやってあったのでテストケースを付け足して終了。途中で解けなかったらどうしようと不安になったりしたけどどうにか制限時間内に終えられてよかった。

なんで一発で alphabet_to_number を書けなかったんだろうと思い返してみると、変換テーブルを作った時点で「各桁ごとに個別に変換などを処理しておいて最後に足そう」と考えたので掛け算するあたりまで頭の中に入れて書き下せなかったのかなという気がする。考えのモードが inject 脳 (副作用あり) じゃなくて map 脳 (副作用なし) になっていたんだろうと自分では納得したけどこの表現が他の誰かに伝わる気がしない...

だいぶ長いし所要時間も長くてダメな感じだけど、「再帰で書こう」と思って迷わず再帰関数を書けたのは成長が見られて良かった。三年前くらいだったらたぶん再帰が書けなかった。再帰っぽいコードや考え方に一切触れてこなかったら三年経とうが五年経とうがずっと進歩しなかったと思うので、下手の横好きでも Lisp とか関数型言語とかを触ってきたのは無駄じゃなかったのかもしれない。