おじい研究所

主にプログラミングの話題です

コード美人【解説】

本稿は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さん

オンリーワン美人

マイナーな言語ばかりというわけではなさそうですね。

KAZAMAI_NaruToさん:SQL

tailsさん:Bash, sed

ゆうふーるさん:Pascal

ももんちょさん:Kuin

grails使いさん:Groovy

Azicoreさん:GolfScript

pocketberserkerさん:F#

electrolysisさん:D

Mi_Sawaさん:Anko C++

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文字以上もあるワンライナーは、きっと美しくありません。

こうしたから美しい、なんてことは何一つ決まっていなくて、何かあるとすれば、さまざまな要因の調和ということでしょうね。自分の理解の程度、問題の種類、扱う言語、その時のコーディングルール、総合的に見て、無理をしないコーディングを心掛ければ、それほどひどいコードにはならないはずです。いつも少しだけ背伸びして、いろんな人のコードを読んで、確かに良いと思えるものを素直に受け入れる。そんなコード美人でありたいものです。

出題・採点を終えて

結構な方が、「これは美しくないコードです」みたいなコメントを入れてらっしゃったのですが、全くそんなことはなくて、変数名だとか、空白文字、改行も非常に読みやすいように考えられているものが多かったです。通常の採点と比較すると、圧倒的に読みやすいコードの割合が高くて、たくさんお気遣いいただいたのだなぁと感じております。何らかの組織に所属していると、決して美しいとは思えないようなコーディングスタイルを強要され、嫌な思いをすることもたくさんあると思いますが、だからと言って自分の美学をなくしてしまう必要はないわけですから、自信を持ってやってほしいですね。美しさと共に、愛を感じた採点でした。


こっちは古い版