今回は、2015年9月1日(火)より10月6日(火)まで開催しておりました、paizaと松江Ruby会議07とのコラボイベント「POH6+松江Ruby会議07協賛 回文作成プログラミングコンテスト」の結果レポートと模範解答コード、上位コードについてお届けします。
POH6+ 松江Ruby会議07協賛 回文作成プログラミングコンテストは、paizaがRuby(Rails)で開発されているという事もあり、親交のあった島根県庁様経由で松江Ruby会議さんを紹介され、イベントを共催する事になりました。
POHの併催イベントは、POHより難し目の問題を出すという位置づけにしておりますが、今回は開発メンバーが遊び心でランキングに「提出コードバイト数」を入れたため、結果的にコードゴルフ大会となり思わぬ盛り上がりを見せました。
最終的にはrubyでの提出8735提出、ruby以外での提出6724提出、合計15,459提出となりました!参加していただいたみなさんありがとうございました!!
■Rubyランキング
順位 | ニックネーム | 平均実行時間 | 提出コードバイト数 |
---|---|---|---|
1位 | n2 | 0.09 秒 | 67 バイト |
2位 | siman | 0.09 秒 | 78 バイト |
3位 | fine | 0.09 秒 | 84 バイト |
4位 | raii | 0.09 秒 | 89 バイト |
5位 | siman | 0.09 秒 | 93 バイト |
6位 | yzx | 0.09 秒 | 96 バイト |
7位 | satoru_net | 0.09 秒 | 105 バイト |
8位 | Leonardone | 0.09 秒 | 105 バイト |
9位 | e8l | 0.09 秒 | 112 バイト |
10位 | YSR | 0.09 秒 | 116 バイト |
11位 | nobyuki | 0.09 秒 | 116 バイト |
12位 | nex | 0.09 秒 | 120 バイト |
13位 | DarkKnight | 0.09 秒 | 123 バイト |
14位 | tsussy | 0.09 秒 | 125 バイト |
15位 | satoru_net | 0.09 秒 | 126 バイト |
16位 | Naoki_M | 0.09 秒 | 135 バイト |
17位 | kariya_mitsuru_min | 0.09 秒 | 136 バイト |
18位 | kasuka | 0.09 秒 | 136 バイト |
19位 | yoshi | 0.09 秒 | 141 バイト |
20位 | yuya | 0.09 秒 | 142 バイト |
21位 | raii | 0.09 秒 | 147 バイト |
22位 | kurat | 0.09 秒 | 147 バイト |
23位 | quarter_moon2 | 0.09 秒 | 148 バイト |
24位 | DoG | 0.09 秒 | 148 バイト |
25位 | sada | 0.09 秒 | 148 バイト |
26位 | ktam | 0.09 秒 | 150 バイト |
27位 | rinzu_ | 0.09 秒 | 151 バイト |
28位 | zakiyama | 0.09 秒 | 155 バイト |
29位 | Langur | 0.09 秒 | 161 バイト |
30位 | tatsushi_d | 0.09 秒 | 166 バイト |
31位 | ivica_osim | 0.09 秒 | 167 バイト |
32位 | agen | 0.09 秒 | 170 バイト |
33位 | ythk_ | 0.09 秒 | 174 バイト |
34位 | shohashimoto | 0.09 秒 | 176 バイト |
35位 | KHAIN | 0.09 秒 | 178 バイト |
36位 | tkc | 0.09 秒 | 187 バイト |
37位 | bizkita | 0.09 秒 | 188 バイト |
38位 | nao | 0.09 秒 | 194 バイト |
39位 | kasei_san | 0.09 秒 | 196 バイト |
40位 | pocari | 0.09 秒 | 196 バイト |
41位 | tnobuhito | 0.09 秒 | 200 バイト |
42位 | ktam1219 | 0.09 秒 | 210 バイト |
43位 | ythk | 0.09 秒 | 210 バイト |
44位 | ythk_ | 0.09 秒 | 210 バイト |
45位 | tjake | 0.09 秒 | 212 バイト |
46位 | mokemokechicken | 0.09 秒 | 217 バイト |
47位 | hheztdozbyehq | 0.09 秒 | 217 バイト |
48位 | cedretaber | 0.09 秒 | 218 バイト |
49位 | sag | 0.09 秒 | 220 バイト |
50位 | ryz310 | 0.09 秒 | 223 バイト |
※松江Ruby会議発表時のランキングと異なっていたため修正致しました(2015/11/13)
■その他の言語の1位
言語 | ニックネーム | 平均実行時間 | 提出コードバイト数 |
---|---|---|---|
Java | n2 | 0.08 秒 | 403 バイト |
PHP | satoru_net | 0.02 秒 | 150 バイト |
Python | satoru_net | 0.02 秒 | 116 バイト |
Perl | yzx | 0.01 秒 | 86 バイト |
C | satoru_net | 0.01 秒 | 156 バイト |
C++ | satoru_net | 0.01 秒 | 165 バイト |
C# | n2 | 0.02 秒 | 548 バイト |
JavaScript | satoru_net | 0.08 秒 | 189 バイト |
■POH6+問題文
最強の復活の回文
現在あなたがプレイしているゲームには、復活の回文機能が備わっています。 (※回文:「え、つまがまつえ?」「たけやぶやけた」のような、上から読んでも下から読んでも同じ言葉になる文字列。ただし今回は、文字列の意味は問いません)
復活の回文とは、ゲームを中断する際に表示される回文の文字列を、ゲーム再開時に入力することにより、前回の終了時と同じ状態からゲームを再開することのできる機能です。逆に言うと、復活の回文さえ手に入れば、自分が望む状態からゲームを開始することもできます。
ゲームを解析したところ、復活の回文の作り方がわかりました。 どうやら、あらかじめある一定の長さの単語が N 個用意してあり、 その中からゲームを中断した時の状態に従って、いくつかの単語を選んで回文が作られているようです。さらに、レベル最強の復活の回文は、その N 個の単語からいくつかを連結することで作られる最長の回文の中で、アルファベット順の昇順でソートした際に、最も早く出てくるものであるということがわかりました。
これからその N 個の単語のリストが与えられますので、最長の回文の中で、アルファベット順の昇順で最も早く出てくるものを出力するプログラムを作成してください。回文は必ず作れるということが保証されています。
■POH6+ Ruby上位コード
それではここから上位者のコードを公開いたします。今回は松江Ruby会議07でもコードの解説があり、その動画もすでにアップされておりますが、時間の都合上、省略せざるを得なかった部分もあったかと思います。そこで松江Ruby会議の皆さんにお願いをして、1~3位のコードを解説入りで公開したいと思います。
今回上位コードを解説を書いて頂いたのは松江Ruby会議(Matsue.rb)の本多 展幸さん、橋本 将さん、西田 雄也さんのお三方に解説頂きました!!ありがとうございます。
◆1位 n2さんのコード
実行時間:0.09 秒
提出コードのバイト数:67 バイト
$><<`sort`.gsub(/.* (.*)/){$1[z=$1.reverse]||$'[z]&&$1%$/=z+$/}+$/
解説(Matsue.rb提供)
# シェルのレベルで sort コマンドを実行 # Rubyで同等のことをやると、「ARGF.read.split.sort.join('\n')」になる sorted_words = `sort` # /.*\n(.*)/ という正規表現の先頭の「.*」は、一行目の単語数を表す文字列を除去するため s = sorted_words.gsub(/.*\n(.*)/) { |matched| r = $1.reverse # $1 は最後に成功したパターンマッチにおける、1番目の括弧の中の値を表す # $1[$1.reverse] は $1 == $1.reverse と実質同じで、自身が回文となる単語がどうかの確認となる # 上記が成り立つ場合は置き換えない # 自身が回文となる単語が存在する場合、正しい結果となるかは入力に依存する cond1 = $1[r] # $' は最後に成功したパターンマッチにおける、マッチした部分以降の文字列を表す # $'[r] は、確認中の単語以降に、反転すると一致する単語が存在するかどうかを判定しており、 # 対となる単語が存在するかどうか、また、存在する場合に辞書順で小さい方がどうかの両方の確認を兼ねている cond2 = $'[r] # $/ は、入力レコードの区切り文字を表す # $/ の左側に文字を連結していくのは、変数初期化の手間を省きつつ、最後に改行を出力するため # cond1 が成立せず、cond2が成立する場合(自身は回文では無いが対となる単語が存在する場合)、 # $/ の左側に反転した単語を連結し、回文の右半分の文字列を作成する # # 「$1%$/=r+$/」は、「$/=r+$/」実行後に $1 を戻り値として返すための書き方 # % は Kernel#sprintf であり、「$/=r+$/」の後で「sprintf($1, $/)」を実行するのと同じで、 # 結局 $1 を返すが、「($/=z+$/)&&$1」や「($/=z+$/;$1)」などと書くより短い # # cond1 も cond2 も成立しない場合は、nil.to_s(空文字)に置換して、単語を除外する # nil || nil && anything #=> nil # 最終行の解析時のみ、cond2 は空文字そのものになるが、結果は変わらない cond1 || (cond2 && ($1 % ($/=r+$/))) } print s + $/
◆2位 simanさんのコード
実行時間:0.09 秒
提出コードのバイト数:78 バイト
f=?z+$<.read;print *f.split.sort.select{|s|s<$*[0,0]=f[s]=f[s.reverse]||''}+$*
解説(Matsue.rb提供)
# 基本コンセプト # 入力をソートした結果を以下の3種類に分けて1.と2.を連結 # # 1. 回文の中心に来る単語(sssなど)を含まない左側 # 2. 回文の中心と右側(正しい結果となるかは入力依存) # 3. 不要なもの(自身が回文でなく、対の文字列も存在しないもの) # 数字が一桁の場合、回文となる単語扱いされてしまうのを防ぐ # 入力の単語には数字が含まれないため、単純にペアが無い単語として処理できる # ?z は "z"という文字と同じだが、1バイト少なくできる f = ?z + $<.read # print *<結果の配列>でそのまま続きで配列の中身を出力する(連結が不要) # selectした結果が 1.、$* が 2. # # print *f.split.sort.select{ |s| words = f.split.sort selected_words = f.split.sort.select{ |s| # f[s.reverse] で入力の文字列全体の部分文字列を取得して存在するかどうか確認 # (|| '' のため、存在しなければ空文字列。saの対になるasがないというような)孤立する単語もこれにより削除) w = f[s.reverse] || '' # 現在チェック中の単語を、反転した単語で上書きする # 反転した単語をチェックするフェーズでは、上記で上書きされているため、 # ペアとなる単語それぞれで二重にカウントしてしまうことを防ぐことができる f[s] = w # 本来 $* はスクリプトの引数(ARGVの別名) # ARGV はつねに [] なので、配列の初期化を省略するために、ここでは 2. の入れ物として使われている # # 自身が回文となる単語も unshift の対象となる # 「array[0,0] = enum」は「array.unshift(enum)」と同じ $*.unshift(w) # 反転した文字列が存在しない場合、 w が空文字のため偽となり、除外される # # 自身が回文となる単語も除外される # そのため、回文となる単語とペアとなる単語の組が同時に存在するケースでは、 # 回文となる単語が辞書順の最後に1度だけ存在するか、あるいは、存在しない場合のみ正しい結果となる s < w } # 配列を連結してから、各要素を print メソッドの引数として渡す print *(selected_words + $*)
◆3位 fineさんのコード
実行時間:0.09 秒
提出コードのバイト数:84 バイト
l="";n,*a=$<.sort;$><<a.select{|w|r=w.chop!.reverse;w==r||a.index(r+$/)&&l=r+l}*""+l
解説(Matsue.rb提供)
l="" # 文字列をソートして、不要な「単語数を表す文字」を破棄 # # a = ARGF.sort # a.shift n,*a = $<.sort print a.select{|w| # 反転した文字列を代入 r = w.chop!.reverse # (1) w == r # 自身が回文であれば、select に対して true が返るため、残る # # (2) a.index(r+$/) # 自身が回文では無く、かつ、反転した文字が存在しない場合、select に対して nil が返るため、除外される # 「$/」は split の区切り文字を表し、デフォルトでは「\n」 # 反転した文字列すでにチェック済みの文字列の場合、 String#chop! で改行文字を削っているため、結果が nil となり、除外される # # (3) l = r + l # 自身が回文では無く、かつ、反転した文字が存在する場合、回文の右半分の文字列に連結する # 右側から順番に、辞書順で昇順にソートした文字を反転したものを連結していく # また、select に対して文字列(真となる値)が返るため、残る w == r || (a.index(r+$/) && l = r + l) }.join('') + l
◆4位 raiiさんのコード
実行時間:0.09 秒
提出コードのバイト数:89 バイト
gets;i=$<.sort;print o=(i&i.map{|s|s!=r=s.chop!.reverse or$*<<r;s>r&&r})*"",*$*,o.reverse
◆5位 simanさんのコード
実行時間:0.09 秒
提出コードのバイト数:93 バイト
n,*f=$<.read.split.sort;n=m='';f.map{|s|f.index(r=s.reverse)&&(s<r&&n+=s;s>r||m=r+m)};$><<n+m
◆6位 yzxさんのコード
実行時間:0.09 秒
提出コードのバイト数:96 バイト
gets;$><<[(s=$<.read).split.sort.select{|x|s[x]="";x==(y=x.reverse)||s.match(y)&&$/=y+$/},$/]*""
◆7位 satoru_netさんのコード
実行時間:0.09 秒
提出コードのバイト数:105 バイト
gets;b="";$><<(a=(w=$<.read).split.sort.reject{|s|!w.index(r=s.reverse)||r<s||s==r&&b<<s}*"")+b+a.reverse
◆8位 Leonardoneさんのコード
実行時間:0.09 秒
提出コードのバイト数:105 バイト
gets;c="";w=$<.read.split.sort;s=w.select{|x|c+=x if x==y=x.reverse;x<y&&w.index(y)}*"";$><<s+c+s.reverse
◆9位 e8lさんのコード
実行時間:0.09 秒
提出コードのバイト数:112 バイト
a={};c=$<.sort.map{|e|a[r=e.chop!.reverse]?$*<<a.delete(r): a[e]=e;r}&a.keys;$><<(t=$*.sort*'')<<c[1]<<t.reverse
◆10位 YSRさんのコード
実行時間:0.09 秒
提出コードのバイト数:116 バイト
n=gets;w=ARGF.read.split.sort;c="";w.select!{|x|c+=x if(y=x.reverse)==x;x<y&&w.index(y)};s=w.join;puts s+c+s.reverse
■POH6+ 各言語の上位コード
◆【Java】n2さん
平均実行時間:0.08秒
提出コードバイト数:403 バイト
import java.util.*;class Main{public static void main(String[]w)throws Exception{byte[]b=new byte[20001];Arrays.sort(w=new String(b,0,System.in.read(b,1,20000)).split("\n"));String l="",c="",r="",s,z;for(int i=0,j,n=w.length;++i<n;)if(0<(j=Arrays.binarySearch(w,i+1,n,z=new StringBuilder(s=w[i]).reverse().toString()))){l+=s;r=z+r;/* uso */w[j]+="@";}else if(s.equals(c+z))c=s;System.out.print(l+c+r);}}
◆【PHP】satoru_netさん
平均実行時間:0.02 秒
提出コードバイト数:150 バイト
<?php $w=join($l[0]=$l=file('php://stdin',2));sort($l);foreach($l as$s)($s==$r=strrev($s))?$b.=$s:($s<$r&&strpos($w,$r))&&$a.=$s;echo$a.$b.strrev($a);
◆【Python】satoru_netさん
平均実行時間:0.02 秒
提出コードバイト数:116 バイト
a=b="""" w=map(raw_input,[a]*input()) for s in sorted(w): r=s[::-1] if s==r:b+=s if s<r in w:a+=s print a+b+a[::-1]
◆【Perl】yzxさん
平均実行時間:0.01 秒
提出コードバイト数:86 バイト
$/=<>;print grep{$t=~s/$_//;($r=reverse)eq$_||$t=~/$r/&&($\=$r.$\)}sort split/ /,$t=<>
◆【C】satoru_netさん
平均実行時間:0.01 秒
提出コードバイト数:156 バイト
#include <stdio.h> main(){system(""perl -e '<>;$w=join q{},@w=<>;map{chop;$r=reverse;/$r/?$b.=$_:$_ lt$r&&$w=~$r?$a.=$_:0}sort@w;print$a.$b.reverse$a'"");}
◆【C++】satoru_netさん
平均実行時間:0.01 秒
提出コードバイト数:165 バイト
#include<cstdlib> int main(){exit(system(""perl -e '<>;$w=join q{},@w=<>;map{chop;$r=reverse;/$r/?$b.=$_:$_ lt$r&&$w=~$r?$a.=$_:0}sort@w;print$a.$b.reverse$a'""));}
◆【C#】n2さん
平均実行時間:0.02 秒
提出コードバイト数:548 バイト
namespace System.Runtime.InteropServices{using Linq;class P{[DllImport("libc")]static extern string gets(IntPtr s);[DllImport("libc")]static extern int puts(string s);static void Main(){int i=0,n=0,j,k;var w=new string[1002];string l="",c="",r="",z;for(;(w[n]=gets(Marshal.AllocHGlobal(11)))!=null;n++);Array.Resize(ref w,n);for(Array.Sort(w,(x,y)=>{for(j=k=0;k<x.Length&&j==0;)j=x[k]-y[k++];return j;});++i<n;){z=String.Concat(w[i].Cast<char>().Reverse());for(j=n;i<--j;)if(z==w[j]){l+=w[i];r=z+r;w[j]="";j=0;}c=j<0||w[i]!=c+z?c:z;}puts(l+c+r);}}}
◆【JavaScript】satoru_netさん
平均実行時間:0.04 秒
提出コードバイト数:189 バイト
a=b=c="";l=require('fs').readFileSync("/dev/stdin","utf8").split("\n").sort(i=2);while(s=l[i++])~l.indexOf(r=s.split("").reverse().join(""))&&s<r?(a+=s,c=r+c):s==r?b+=s:0;console.log(a+b+c)
■まとめ
POH6+は最初から計画していたわけではありませんでしたが、期せずしてpaiza初のコードゴルフ大会となりました。コードゴルフをすると「コードの可読性は落ちるから嫌い」という方もいらっしゃるかと思いますが、やってみると思わぬ発見もあるので、たまにはいいのではないかと思いました。
paizaではこのほかにも色々な問題を用意していますので、ご興味がある方はぜひ覗いてみてくださいね!
paizaオンラインハッカソンのレポートは今回で終了ですが、次回開催の準備も進めておりますので是非次回も皆様のご参加をお待ちしております!
■おまけ
最後まで読んでいただきありがとうございました。paizaに会員登録すると、下記の壁紙3種類がダウンロードできます!是非お気軽にご登録下さい!
paizaは、技術を追い続けることが仕事につながり、スキルのある人がきちんと評価される場を作ることで、日本のITエンジニアの地位向上を目指したいと考えています。
自分のスキルを磨いていきたいと考えている方におすすめなのが「paizaラーニング」。オンラインでプログラミングしながらスキルアップできる入門学習コンテンツです。初心者でも楽しくプログラミングの基本を学ぶことができます。
そして、paizaでは、Webサービス開発企業などで求められるコーディング力や、テストケースを想定する力などが問われるプログラミングスキルチェック問題も提供しています。
スキルチェックに挑戦した人は、その結果によってS・A・B・C・D・Eの6段階のランクを取得できます。必要なスキルランクを取得すれば、書類選考なしで企業の求人に応募することも可能です。「自分のプログラミングスキルを客観的に知りたい」「スキルを使って転職したい」という方は、ぜひチャレンジしてみてください。