コード美人【解説】
本稿はCodeIQで2014年2月6日～同年2月24日に出題された「コード美人」という問題の解説です。
コード美人【解説】
◆基本的な考え方
1, 3, 9, 27, 81, 243, 729, …と、3の累乗になっている数を、3進法で表します。
1: 00000001 3: 00000010 9: 00000100 27: 00001000 81: 00010000 243: 00100000 729: 01000000
これらの値をいくつか足し合わせても、3進数の各位は0か1しか現れません。つまり、2進数のように見えます。これを利用して、2進数を小さい順に並べ、それを3進数とみなし、3進→10進の変換を行えば、必要な数列が得られます。
たとえば、Rubyでコードを書くと次のようになります。
1.upto(100){|n| puts n.to_s(2).to_i(3) }
「1から100までの数を、2進表現にして、それを3進数とみなし、10進数に変換する」
基数変換がしやすい言語なら、この方法を用いて、簡潔でわかりやすいコードを書くことができます。もちろん、この方法が最も美しいかといえば、はっきりYESと言うことはできません。他の方法を考えてみましょう。
◆アルゴリズムのパターン
n進法の変換が容易な言語を使った場合は、前述のコードで十分かもしれませんが、それ以外にも、アルゴリズムにいくつかのパターンがあります。
とりあえず3進法で表してみる方法
1から順に3進法で表してみると、
1: 001 2: 002 3: 010 4: 011 5: 012 6: 020 7: 021 8: 022 9: 100 10: 101
のようになりますが、該当する値は前述の通り2進っぽく見えなければなりません。つまり、このような変換をしたときに、1か所でも2が出現したら、それは出力しないという考え方をすると、目的の数列が得られるということですね。2が含まれるかどうかを調べるだけですから、正規表現を使って書くこともできそうなアルゴリズムです。
2進っぽく3進数を生成する
まず、1のみが入ったリストを用意します
[1]
ここから1を取り出し、3倍したもの、3倍して1足したものを、リストの末尾に加えます。
[1] <- 取り出した値のリスト [3, 4] <- 追加する値のリスト
次に、リストの先頭にある3を取り出し、先程と同様に3倍したものと3倍して1足したものを、リストの末尾に加えます。
[1, 3] <- 取り出した値のリスト [4, 9, 10] <- 追加する値のリスト
これを繰り返すと、目的の数列が得られます。
[1, 3, 4] <- 取り出した値のリスト [9, 10, 12, 13] <- 追加する値のリスト
3倍するという操作は、3進表現したときの桁上りを意味します。また、1を足す操作しかしないことで、3進表現の中に2が現れないようにするのです。このような方法は、再帰的なコードを書きやすいですから、関数型言語等を用いれば非常に美しいコードになります。
まとめて足しちゃう
わかりやすいように、ある程度大きくなったリストで説明します。
[1, 3, 4, 9, 10, 12, 13, 27]
このリストは、33が出現するまでを表していますが、この続きは簡単に生成することができます。27を、その直前まで(1から13まで)のすべての値に足していけば、続きの数列が得られます。
[ 1, 3, 4, 9, 10, 12, 13, 27] [28, 30, 31, 36, 37, 39, 40]
全部足したら、27に3を1回かけたもの（81）を、リストの要素すべてに加えていけば、続きのリストが得られます。 これも再帰的に処理しやすいので、美しいコードが書けそうですね。
どの方法も、本質的には同じですが、言語の特性にうまくマッチする方法を選ぶことができれば、非常に美しいコードになるでしょう。
◆挑戦者の解答集
正統派美人
挑戦者244名、提出数283の大量のコードを見て、私が個人的に心惹かれたコードです。
antimon2さん
Haskellで書かれたコードです。 パッと見ただけで、fnの定義部分に自然に目が動きます。特別高度なテクニックを使っているわけでもなく、非常に素直なコードで、だからこそ非常にわかりやすい。関数型言語をよく知らない人間が見ても理解できそうな、すばらしいコードだと思いました。
-- define series series = let fn n | n < 2 = 1 | odd n = (+ 1) $ fn $ n - 1 | otherwise = (* 3) $ fn $ n `div` 2 construct_stream n = fn n : construct_stream (n + 1) in construct_stream 1 -- define output output stream n = let print_each = mapM_ print in print_each $ take n stream -- run main = output series 100
ほかにも良いコードはたくさんありましたが、見た瞬間私の心を打ち抜いた、このコードのみご紹介ということにさせていただきます。
おもしろ解答
採点作業は非常に大変だったのですが、ときどき現れるおもしろ解答に癒され、最後まで採点することができました。変わった言語での挑戦はある程度覚悟していましたが、変わったコードを書く方に限って、恐ろしいほどにドキュメント・コメントが良いんですよね。相手への気遣いが強く感じられます。そりゃそうですよね。変わった解答をするには、相応のスキルが必要です。高いスキルがあって余裕があるからこそ、おもしろいコードが書けるわけですし、それをするだけのエネルギーを持っているわけですから。
ビジュアル系美人
みけCATさん
Pietという、プログラミング言語での解答です。画像データの色によってプログラムが表現されています。普通に書くだけでも結構大変なのですが、写真の画像データに仕込む形で見た目も美しく仕上げてあります。これはスゴイ！
この画像をPietインタープリタで動かすと、正しい解が出力されます。
http://www.bertnase.de/npiet/からダウンロードできますので、興味のある方は是非チャレンジしてみてください。
カワイイ系美人
amamaさん
CodeIQに住みついている謎の電脳生物ですね。正直このキャラクターってちょっと【自主規制】だと思うんですが、AAにすると意外とカワイイ…気がしてきました（´Д｀;）
int co(char*);d(int i); char Code['IQ']="0000000",I,Q; #include <stdio.h> #include <stdlib.h> long int main (int i) {for(;i< 'e'; i++) {for (I=0;I <'o'-'d' ;I++)/**/ d(i) ;printf ("%d\n", co(Code)) ;}return 0,"Code", ("");} int co( char*e){ return strtol(e ,0,3);}int d(i) {Code[10- I]=(i>>I) %2?'1':'0' ;return 0;}/*思ったより短くなっ てしまったので感想書きます． 美しい ->絵画->AAだ！となってAAにしました．AAの題材 には 某サイトのキャラを選びました．初めは golf も考えたのですがやったことのない code でAAに挑戦しよう と思い 書きました． 言語は Cです．顔 だけ見て もそれなり にコードに 見える筈*/
自称系美人
変数・関数名に「美」に関係する名前をつけるタイプのコードはいくつかありましたが、その中でも比較的クオリティが高かったものを紹介します。
simanmanさん
なんて押しつけがましい美なのでしょう。
class Object def 美 @counter ||= 0 @counter += 1 end def し p @counter end def method_missing(name, *args) name.to_s.chars do |ch| if ['美','し'].include?(ch) send(ch.to_sym) end end end end 美しい美美しい美しい美美美美美しい美しい美美しい美しい美美美美美美美 美美美美美美美しい美しい美美しい美しい美美美美美しい美しい美美しい美 しい美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美 美美美美美美美美美しい美しい美美しい美しい美美美美美しい美しい美美し い美しい美美美美美美美美美美美美美美しい美しい美美しい美しい美美美美 美しい美しい美美しい美しい美美美美美美美美美美美美美美美美美美美美美 美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美 美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美 美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美し い美しい美美しい美しい美美美美美しい美しい美美しい美しい美美美美美美 美美美美美美美美しい美しい美美しい美しい美美美美美しい美しい美美しい 美しい美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美 美美美美美美美美美美しい美しい美美しい美しい美美美美美しい美しい美美 しい美しい美美美美美美美美美美美美美美しい美しい美美しい美しい美美美 美美しい美しい美美しい美しい美美美美美美美美美美美美美美美美美美美美 美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美 美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美 美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美 美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美 美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美 美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美 美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美 美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美 美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美 美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美 美美美美美しい美しい美美しい美しい美美美美美しい美しい美美しい美しい 美美美美美美美美美美美美美美しい美しい美美しい美しい美美美美美しい美 しい美美しい美しい美美美美美美美美美美美美美美美美美美美美美美美美美 美美美美美美美美美美美美美美美美しい美しい美美しい美しい美美美美美し い美しい美美しい美しい美美美美美美美美美美美美美美しい美しい美美しい 美しい美美美美美しい美しい美美しい美しい美美美美美美美美美美美美美美 美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美 美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美 美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美美 美美美美美美しい美しい美美しい美しい美美美美美しいいいいいいいいいい
hogeover30さん
IOCCCなんかでありそうなコードですね。
#define BijiN main #define Bijin a[ #define bijiN ] #define bIjin i #define BIJIN { #define bijin } #define BIjin for #define biJIN printf #define biJin ; #define BiJin , #define bijIN ( #define BIJin ) #define BIjIN 100 bIjin BiJin Bijin BIjIN bijiN biJin BijiN bijIN BIJin BIJIN BIjin bijIN biJin bIjin++<BIjIN biJin BIJin biJIN bijIN"%d\n" BiJin Bijin bIjin bijiN=bIjin%2?Bijin bIjin-1 bijiN+1:Bijin bIjin/2 bijiN*3 BIJin biJin bijin //i,a[];main(){for(;i++<100;)printf("%d\n",a[i]=i%2?a[i-1]+1:a[i/2]*3);}
数字だ系
数の問題なんだから数で表現！という美学のコードです。
KTazakikさん
大きな整数部分を16進数に変換して2文字ずつ区切るとASCIIコードが得られるので、それをコードとして復元している感じですね。
at_exit { lst = Array.new ObjectSpace.each_object(Bignum).each do |v| s = [v.to_s(16)].pack("H*") next unless s =~ /^B:(\d+):(.*)$/ lst.push([$1.to_i, $2]) end lst.sort!{|a,b| a<=>b} lst.each do |v| eval(v[1]) end } 2373316440976457250197918761860105244459294325385303762620305085053253870070907368572077419160528092491364 155537702111748977192310430882078850619243054765155014640320252081585639835766783353761046199169094798851534436 607569288858065828278660803295971603713646320948985194399297827967374839831543760925478916117332928938471012 343872110370846088544574445068496937
短さの美
notさん
スクリプト言語を使えばもっと短く書けますが、このCのコードはショートコーディングテクニックがぎっしり詰まっています（57バイト）。
i;main(j){for(;i=~i%3?i/3?:~!printf("%d\n",j):++j%982;);}
アルゴリズムとしては、1から順に3進表現し、「どこにも2が現れなければ表示する」という考え方を用いています。このアルゴリズムで素直にコードを書こうとすると、次のような2重ループになります。
#include <stdio.h> int main() { // 100番目の値が981であることを事前に調べておく // 普通に書く場合はカウンタ用の変数を用意する for(int n = 1; n <= 981; ++n){ int k = n; for(; k != 0; k /= 3){ if( k % 3 == 2 ) break; } // kが0ということは、 // 3進表現したときに2が一度も現れなかったということ if( k == 0 ) printf("%d\n", n); } return 0; }
ここからnotさんのコードに持っていくのがいかに大変か、是非挑戦してみてください。
個性派美人
変わった言語や、あまり他の人が使わなかった言語での挑戦者を晒しあげ…じゃなくて紹介します。個人的にはたいへん楽しませていただきました。ありがとうございます。
美白系美人
美白…いるとは予想していましたが、やはりいましたWhitespace（´ω｀）
NeoCatさん
simbelmynさん
オンリーワン美人
マイナーな言語ばかりというわけではなさそうですね。
ゆうふーるさん：Pascal
ももんちょさん：Kuin
grails使いさん：Groovy
Azicoreさん：GolfScript
pocketberserkerさん：F#
electrolysisさん：D
ytominoさん：Ada
manmanさん：VBA
kazkaz613さん：VB.NET
◆統計情報
参加者数244名
正解者数229名
使用言語
| 言語名 | 人数 |
|---|---|
| C/C++ | 67 |
| Ruby | 43 |
| Java | 30 |
| Python | 22 |
| JavaScript | 16 |
| Haskell | 9 |
| PHP | 9 |
| Perl | 8 |
| C# | 7 |
| Scala | 7 |
| R | 2 |
| Whitespace | 2 |
| Ada | 1 |
| Anko C++ | 1 |
| Bash | 1 |
| D | 1 |
| F# | 1 |
| GolfScript | 1 |
| Groovy | 1 |
| Kuin | 1 |
| Pascal | 1 |
| Piet | 1 |
| Sed | 1 |
| SQL | 1 |
| VB.NET | 1 |
| VBA | 1 |
◆最後に
美しさ
出題しておいて何も語らないというのも少しズルい気がしますので、最後に個人的な考えを記します。
そのコードに美しさが見えるとき、おそらくそれはコード自体が美しいというより、アルゴリズムの美しさが自然にコードで表現されているのだと思います。「再帰的なコードは美しい」とか、「コメントが必要ないコードが美しい」のような台詞はよく耳にするような気がしますが、それは単なる要因の一つに過ぎません。部分的・限定的な要因を、それがすべてであるように信仰すればするほど、表現されるコードは歪なものとなり、『美しい。思っているのは、自分だけ』ということになりかねません。
深さ優先探索を行うなら再帰的なコードを書く場合が多いでしょうし、幅優先探索を行う場合はwhile文を書くでしょう。扱うプログラミング言語にパワーが足りなければ、なぜそう書くのか、そう書くと何が良いのか、ということをコメントで書いたって良いでしょうし、言語にパワーがあれば、あえてコメントを書く必要もないでしょう。
「ワンライナーで書いた！」それが自然なコードであれば、美しいと思います。けれども、無理やり1行で書いた、100文字以上もあるワンライナーは、きっと美しくありません。
こうしたから美しい、なんてことは何一つ決まっていなくて、何かあるとすれば、さまざまな要因の調和ということでしょうね。自分の理解の程度、問題の種類、扱う言語、その時のコーディングルール、総合的に見て、無理をしないコーディングを心掛ければ、それほどひどいコードにはならないはずです。いつも少しだけ背伸びして、いろんな人のコードを読んで、確かに良いと思えるものを素直に受け入れる。そんなコード美人でありたいものです。
出題・採点を終えて
結構な方が、「これは美しくないコードです」みたいなコメントを入れてらっしゃったのですが、全くそんなことはなくて、変数名だとか、空白文字、改行も非常に読みやすいように考えられているものが多かったです。通常の採点と比較すると、圧倒的に読みやすいコードの割合が高くて、たくさんお気遣いいただいたのだなぁと感じております。何らかの組織に所属していると、決して美しいとは思えないようなコーディングスタイルを強要され、嫌な思いをすることもたくさんあると思いますが、だからと言って自分の美学をなくしてしまう必要はないわけですから、自信を持ってやってほしいですね。美しさと共に、愛を感じた採点でした。
