読者です 読者をやめる 読者になる 読者になる

paiza開発日誌

paiza(https://paiza.jp ギノ株式会社)の開発者が開発の事、プログラミングネタ、ITエンジニアの転職などについて書いています。

【コードゴルフ】初心者でもわかるRubyショートコード解説

f:id:paiza:20151026221935j:plain
今回は、2015年9月1日(火)より10月6日(火)まで開催しておりました、paizaと松江Ruby会議07とのコラボイベント「POH6+松江Ruby会議07協賛 回文作成プログラミングコンテスト」の結果レポートと模範解答コード、上位コードについてお届けします。

paiza.jp

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+問題文

最強の復活の回文

paiza.jp

現在あなたがプレイしているゲームには、復活の回文機能が備わっています。 (※回文:「え、つまがまつえ?」「たけやぶやけた」のような、上から読んでも下から読んでも同じ言葉になる文字列。ただし今回は、文字列の意味は問いません)

復活の回文とは、ゲームを中断する際に表示される回文の文字列を、ゲーム再開時に入力することにより、前回の終了時と同じ状態からゲームを再開することのできる機能です。逆に言うと、復活の回文さえ手に入れば、自分が望む状態からゲームを開始することもできます。

ゲームを解析したところ、復活の回文の作り方がわかりました。 どうやら、あらかじめある一定の長さの単語が N 個用意してあり、 その中からゲームを中断した時の状態に従って、いくつかの単語を選んで回文が作られているようです。さらに、レベル最強の復活の回文は、その N 個の単語からいくつかを連結することで作られる最長の回文の中で、アルファベット順の昇順でソートした際に、最も早く出てくるものであるということがわかりました。

これからその N 個の単語のリストが与えられますので、最長の回文の中で、アルファベット順の昇順で最も早く出てくるものを出力するプログラムを作成してください。回文は必ず作れるということが保証されています。

https://paiza.jp/poh/joshibato/matsue-ruby

■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種類がダウンロードできます!是非お気軽にご登録下さい!
f:id:paiza:20151014153402j:plain
f:id:paiza:20151014153444j:plain
f:id:paiza:20151014153458j:plain



paizaではスキルのあるエンジニアがきちんと評価されるようにし、技術を追い続ける事が仕事につながるようにする事で、日本のITエンジニアの地位向上を図っていければと考えています。特にpaizaではWebサービス提供企業などでもとめられる、システム開発力や、テストケースを想定できるかの力(テストコードを書く力)などが問われる問題を出題しています。

テストの結果によりS・A・B・C・D・Eの6段階でランクが分かります。自分のプログラミングスキルを客観的に知りたいという方は是非チャレンジしてみてください。

http://paiza.jp

プログラミング入門講座|paizaラーニング

PHP入門編Ruby入門編Python入門編Java入門編JavaScript入門編C言語入門編C#入門編アルゴリズム入門編