CodeIQ MAGAZINECodeIQ MAGAZINE

Ozyさん出題「コード美人」問題の解説と解答コード公開~正統派美人、ビジュアル系美人、カワイイ系美人、自称系美人、数学だ系美人、美白系美人など面白解答多数

2014.03.03 Category:CodeIQ問題解説・リーダーボード Tag: , ,

  • 47
  • このエントリーをはてなブックマークに追加

Ozyさんの「コード美人」問題の解説と解答コードのご紹介です。問題が問題なだけあって、提出されたコードはかなり面白いです。

正統派美人、ビジュアル系美人、カワイイ系美人、自称系美人、数学だ系美人、短さの美、個性派美人、美白系美人、オンリーワン美人などなど。

Ozyさんの寄稿記事にてお楽しみください!
by CodeIQ運営事務局

Ozyです。

今回は、「あなたの考える、最も美しいコードを書いてください。」なんて、少し挑発的な問題を出題しました。まず、ご参加いただいた244名もの方々に感謝いたします。どうもありがとうございました。ご参加いただいたすべての方が正解というわけではありませんでしたので、最初に簡単な解説をしておこうと思います。

問題

問題文は以下のようなものでした。

【問題】
1, 3, 9, 27, 81, …のように、1からはじまり3ずつ掛け合わせていく数列があります。
さらに、これらの中からいくつかを足し合わせたものを、小さい順に並べると、次のようになります。

1, 3, 4, 9, 10, 12, 13, 27, ...
(4=1+3, 10=1+9, 12=3+9, 13=1+3+9)

このような数列の、最初から100個分を出力するプログラムを、美しく書いてください。

【出力形式】
標準出力に改行区切りで出力してください。つまり、

1
3
4
9
10
12
13
27
.
.
.

のように、100行分出力をしてくださいということです。改行コードは、LFまたはCR+LFでお願いします。

【注意】
評価は出力が正しいかどうかのみで判定します
コードが美しいかどうかは主観的なものですので、特にルールはありません。「これが美しいコードだ!」と、自分で思えるものを送ってください。出題者のハートを打ち抜いた美しいコードは、解答者のニックネームと共に、後日CodeIQ MAGAZINEで紹介されます。

【言語】
コードの実行テストは、ideone.comで行いますので、ここで実行できるコードはすべて使用可能です。言語一覧はこちら

上記以外の言語を使用する場合は、処理系の情報を必ず明記してください。

【ideone.comを利用する際の注意】
コードのコンパイル・実行を行うとき、プライバシー設定にご注意ください。
Publicで実行すると、他の人からもあなたのコードを見ることができるようになってしまいます。
Secretを選択するようにしておきましょう。

【解答方法】
テキストファイルに、以下の情報を記入し、アップロードしてください。

(1)ソースコード(必須)

(2)言語の種類・処理系の情報(必須)
ideone.comで実行できる場合は言語の種類のみで結構です

(3)コードの説明やコードに対する熱いメッセージ(任意)

※(1)の中にコメントとして(2)、(3)を記入してください(そのようにしていただけると、採点作業がたいへん捗りますので、ご協力お願いします)。

(これは過去問題です。すでに解答受付は終了していますのでご注意ください)

解説

基本的な考え方

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]

このリストは、3^3が出現するまでを表していますが、この続きは簡単に生成することができます。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文字以上もあるワンライナーは、きっと美しくありません。

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

出題・採点を終えて

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

それではまた。

お知らせ

この春にOzyさん著の元祖ショートコーディングの本がこの度復刊となりました!

復刊を記念しまして、この「コード美人」問題に挑戦した方の中から抽選で『ショートコーディング 職人達の技法』を3名さまにプレゼントします!

当選者はCodeIQ運営事務局よりCodeIQに登録しているメールアドレス宛に連絡をいたします。

実際の本の郵送は、本の生産の都合上、3月20日(木)以降となります。

※本の中身については、Ozyさんからの寄稿記事をご覧ください。

記事:祝!元祖コードゴルフ本が復刻! #codegolf #c

  • 47
  • このエントリーをはてなブックマークに追加

■関連記事

【コードゴルフ】Ozyさん出題「シンプル・ライフゲーム」問題解説と解答コード公開!... はじめに まずは問題のおさらいです。 【ライフゲーム】 ライフゲームでは、格子状のフィールドの各マス目(セル)に対して、「生」と「死」の2つの状態を初期値として与え、次のルールによって世代変化します。   各セルについて、   「生」の状態の場合 ・周囲の8セルのうち、「生...
世界初!?Opal製Hubotプラグインで解答する「RubyでHubot!?」問題解説 #Ruby ... はじめに 2015年7月3日~2015年7月20日の期間、「RubyでHubot!?」というRuby/Opal/JavaScript複合問題を出題し、5名の方が挑戦してくださいました。 環境構築が必要なことに加え、ネット上に直接的な情報が皆無(おそらくこの問題の解答が世界初のOpal製Hubot...
総勢986名の方が挑戦!ホリエモンからの挑戦状【解説編】 #C++ #Ruby #Python #J... 問題のおさらい まずは、問題についてのおさらいです。今回の問題は以下のような内容でした。 こんにちは。堀江貴文です。 今回は、エンジニアのみなさんにぜひ解いていただきたい問題をCodeIQと一緒に考えてみました。ちょっと考え方に工夫が必要な問題になっていますので、ぜひ挑戦してみてください。 ...
割とあるサンプルコード書く機会 。第2回Rubictionary問題結果発表です! #rubicti... はじめに 出題者のtbpgrです。 当記事では「第2回 Rubictionary」問題の優秀解答発表を行います。 記事の構成は以下のようになります。 出題意図 問題文 サンプルコード紹介 選択問題の出題ミスのお詫び 出題意図 ※出題意図の内容は、第1回 Rubictionary問題結果...
割とあるサンプルコード書く機会。第1回Rubictionary問題結果発表です! #rubictio... はじめに 出題者のtbpgrです。 当記事では「第1回 Rubictionary」問題の優秀解答発表を行います。 記事の構成は以下のようになります。 出題意図 問題文 サンプルコード紹介 出題意図 昨今、 サンプルコードによるコミュケーションやドキュメンテーションの重要度が増しています...
書籍発刊記念問題(プレゼント付)!「わんにゃんキャッスル」解説 #プログラミング #ruby... 問題のおさらい ■ 設問内容 わんにゃん勢力MAPがあります。 彼らは自分たちの権威を誇示するために、できるだけ大きな城を建てようと考えました。 城は、MAPの自勢力上で、正方形の区画になっている部分に建てることができます。 にゃんこ群は3×3の城を建てることができます。わんこ群は、複数の候...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

CodeIQ(コードアイキュー)とは、自分の実力を知りたいITエンジニア向けの、実務スキル評価サービスです。

CodeIQご利用にあたって
関連サイト
codeiq

リクルートグループサイトへ