Subscribed unsubscribe Subscribe Subscribe

ジャバ・ザ・ハットリの日記

日本→シンガポール→ベルリンへと家族と共に流れ着き、ベルリンのスタートアップで働くソフトウェアエンジニアの日記

天才プログラマーと自分との実力差をカンタンに測定する方法

Ruby プログラミング リファクタリング 英語

天才プログラマーと自分との実力差をカンタンに測定する方法を発見しましたよ、という話。

結論から言うと、いろんなところで過去に開催されたプログラミングコンテストの入賞者の結果を見て、その問題を同じ条件で解いてみること。

あるウェブサイトに2015年に開催されたプログラミング・コンテストの結果が載っていた。(本記事の末尾にそのプログラミング問題の日本語訳を載せた)

入賞者は1位の人が15分、2位が22分、3位が24分、となっていた。
f:id:tango_ruby:20160905222541p:plain:W300
プログラミングの問題をザッと眺めていたら、実装すべきアルゴリズムがパッと思いついた。「これはひょっとして1位の人は超えられなくても3位入賞ぐらいはいけそうじゃね?」などと考えてしまった。

それでそのウェブサイトが用意しているエディタを使って、コードを書きだした。
15分経過:「あれ?もう15分も経った?まー1位にはなれなくてもトップ集団には入るわ」
20分経過:「うーん。もう20分か。3位内にはなれなくてもまだまだトップ集団には入れる。。。はず」
30分経過:最初に考えたアルゴリズムに欠陥があることを発見する。
40分経過:「なんか最初の目論見とはかなり違う。。。これ完成するのか?」
1時間経過:「それなりのはできたしもう提出してまえ!なんかイヤになってきた」と、自暴自棄気味にウェブサイトのSubmitボタンを押すとB判定が出た。

B判定の理由は一般的なケースでは正しい答えが返ってくるが、特殊なケースにおいては対応できていないのと、計算量にまだ改良の余地があるとのこと。

ヘコんだ。

1時間かけてB判定の私と15分で完璧にスキが無く、計算量が最小限で済むコードを実装した人との差は歴然だった。
問題を読んだだけでは分からなかったが、実際に手を動かしてコードを書いた後では1位の人がどれほどすごいかが分かった。たった15分で完璧に実装してしまうのは天才的。この問題を読んでパッと思いついただけの解法にはきっとヌケがある。そこをしっかり埋めるのが難しい。誰でも時間をかければできる。しかし15分というのはもう天才の技としか言いようがない。

天才プログラマーとの実力差を見せつけられて、実はかなりヘコんだ。それでもこれは挑戦してとても良かったと考えている。
その世界でトップクラスの人と自分との差を把握することは、どんな職業においても重要だと思う。

例えばサッカー選手の場合、その選手がどこのリーグのどんなレベルの選手であったとしても世界最高峰との差異が把握できている選手とできていない選手とではその後の成長性が変わってくる。メッシやC・ロナウドらと対戦した経験があって、ハッキリとそれらの最高峰の選手と自分がどう違うのかを分かっている選手なら、その差異を意識して自分なりの方向性を考え、日々のトレーニングを積むことができる。
ただサッカー選手はその職業から世界最高峰との差を把握するにはやはりバルセロナやイギリスのリーグのチームに入って、真剣試合で対戦する必要がある。サッカー選手の真の実力なんてテレビで眺めているだけとか、たとえ対戦しても親善試合ではきっと分からないからだ。

それに引き換えソフトウェアエンジニアやプログラマーにとってはトップとの実力差の測定はとてもカンタン。ただプログラミングコンテストのページを開けて、その問題をやってみればいいだけ。トップクラスの人がやっていることと条件はほとんど変わらない。

しかもその差異はかなりの精度で数値化もしくはO記法などで数式化される。

こんなカンタンに世界のトップクラスとの差異が測定できる職業ってあまり無いのじゃないだろうか。

ということでご興味があればやってみてはいかがでしょうか?

私がやってみたのはこのサイトのコンテスト。
Argon 2015 challenge - Codility
プログラミング言語は以下の16言語に対応しており、なにかのプログラミング知識を持つ人なら誰でも参加できるようになっている。

C、C++、C#、Go、Java、JavaScript、Lua、Objective-C、Pascal、PHP、Perl、Python、Ruby、Scala、Swift、VB.NET

一応、私なりの日本語訳をここに掲載した。「我こそは15分以内に解いて1位以上の成績を叩きだしてやるぜ!」とお考えの方はぜひ挑戦して、見事に成功したら教えていただきたい。こんな問題を15分足らずで解いてしまう人は一体どんな人なのか本当に興味がある。

Argon 2015 プログラミングコンテスト問題
 
あなたは次の休暇をポーランドで過ごそうと考えています。ポーランドは大国とは言えないかもしれませんが、北のバルト海から南のタトラ山脈まで様々な自然を楽しむことができる国です。海で泳いだり、山で山登りを楽しむことができます。ところがポーランドの気候はとても変化が激しく、休暇を過ごすにはその天候を考慮に入れる必要があります。
 
あなたの今年の夏の休暇は連続したN日分があります。あなたはそのN日分の中でどこからでも休暇を始めることができて、N日内のどこでも休暇を終えることができます。あなたの休暇の前半は海で、後半は山で過ごすことにします。山と海の休暇期間は正の整数とし、あなたは休暇期間を最大化したいと計画しています。
 
あなたにはN日分の天気予報があります。奇妙なことにその天気予報によると海に行くのにパーフェクトな日は山に行くには不可能な日になっています。逆も同じ。山にとって絶好の天気の日は、海では遊べません。当然ながらあなたの計画は海や山での休暇先を最良な天気の下で過ごしたいと考えています。したがって休暇の前半(海で過ごす休暇)の半分以上の日程は海で泳ぐのに適した天候で、後半(山で過ごす休暇)の半分以上の日程は登山に適した天候にしてください。
 
天気予報は0からはじまる配列Aで示されます。K (0 ≤ K < N), A[K]が0の時、それはK日目の天候が海に適した天候であることを示します。A[K]が1の時はK日目が登山の天候です。
 
次のメソッドを書いてください。
Rubyの場合: def solution(A)
Javaの場合: class Solution { public int solution(int[] A); }
JavaScriptの場合: function solution(A);
Objective-Cの場合: int solution(NSMutableArray *A);
Pythonの場合: def solution(A)

 
このメソッドに配列Aとして天気予報を入れると、あなたが取れる休暇の最大日数が返ってくるようにしてください。
 
例えば配列Aが以下のような場合。
 
A[0] = 1
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 0
A[5] = 0
A[6] = 1
A[7] = 1
 
あなたは8日の休暇があります。2日目、4日目、5日目が海に適した天気。その他が山になります。あなたは1日目(A[1])から休暇をスタートし、5日間を海で過ごします。A[2], A[4], A[5] の3日間が海に適した日になるので「半分以上の日程」という条件に合います。その後の2日間を山で過ごします。2日とも山に適した天候になります。すなわち7日間が上記の天候条件下で最大の休暇日数になります。したがって7を返します。
 
例えば配列Aが以下のような場合。
 
A[0] = 1
A[1] = 0
 
あなたは上記の条件に合う休暇を取ることができません。したがって0を返します。
 
計算量はO(n)となるようにしてください。

 
1時間かけて書いたコードがB判定を食らった後、「CODE COMPLETE」を読み返した。人間は決まった特定の人の輪の中だけを見ていると「オレってコード書くことに関してはまーまーイケてんじゃね?」などと考えてしまいがち。このプログラミングコンテストの試し参加はそういう傲慢な姿勢を正し、基礎に戻ってしっかり勉強することを気付かせてくれた。

オススメです。機会があればぜひ。

codility.com

あとGoogle codejamとやらが有名らしい。
Google Code Jam

<追記>
コメントで「15分がトップとかレベルが低いな」とかいただいて、「えええ???」となった。しかしいろいろ調べると競技プログラマーなる人達が居る、と。chokudaiさんという方がなぜそんなに速く問題が解けるのか、のタネあかしをこちらの動画で解説されている。なるほど。知らなかった。
ワンランク上に行くプロコン講座 - YouTube


CODE COMPLETE 第2版 上 完全なプログラミングを目指して

CODE COMPLETE 第2版 上 完全なプログラミングを目指して

tango-ruby.hatenablog.com

tango-ruby.hatenablog.com

tango-ruby.hatenablog.com

tango-ruby.hatenablog.com