#codeiq

[kouchikennokaori-blog]

ディビジョン・ナインの解答内容

※tumblrでのコードの色付けとか良くわからなかったので, そのうち直したい.

=begin n 桁の場合における0 ~ 8までの余りの場合の数をそれぞれ配列の添え字に対応させている (n + 1)桁の数は n 桁の数の末尾に 1, 2, 3, 4 のいずれかを加えた数として考えている 以下略(面倒) =end fLine = gets fNoOfDigit = fLine.to_i fRemainder = Array.new(9, 0) fPreRemainder = fRemainder.dup fPreRemainder[0] = 1 fNoOfDigit.times do fRemainder.fill(0) fRemainder.length.times do |i| 4.times do |j| fRemainder[i] += fPreRemainder[i - j - 1] end end fPreRemainder.length.times do |i| fPreRemainder[i] = fRemainder[i] end end p fRemainder.first

[taskem1985]

【C++初級】Cちゃんをプラプラにしてあげて！

C/C++やったことないんやけど。教養として解いてみた。

34点。

①

ふーん。C/C++ではプロトタイプ宣言が必要なのね。

Ob-Cでこんなん確かあったな。

int func(void);

Cだとvoid省略不可、C++だと省略可とのこと。ほーん。https://ja.wikipedia.org/wiki/%E9%96%A2%E6%95%B0%E3%83%97%E3%83%AD%E3%83%88%E3%82%BF%E3%82%A4%E3%83%97 ②Cなら問題ないのに、C++だと

int func(){return;}

のreturnでコンパイルエラー出るらしい。return 0;みたくintを厳密に返してやらんといけないってこと？（真相は謎のままーーー） ③C++だと問題ないのに、Cだと

int main(){if(true){puts(”true”);}else{puts(”false”); }return 0;}

でコンパイルエラー出るらしい。んーわっかんねー（笑） 結論：プログラミングをもっと気軽に、効率よく、数値化して学べるサービス、ないかな。ちとこのサービスはやはり学習向けではない。。。

[taskem1985]

code IQやってみたよ。入会してみたよ。

Java初級とかいうランキング１位所要時間１０分の問題をとりあえず解いてみた。

全　問　不　正　解　☆

言い訳するとJavaなんてムカーシ本読んで学んだ気がするけど一切つかったことないのですが、

とりあえずショックだったので、正解になるまでやりました。調べながらで絶対３０分以上かかったよ。。。

①「Stringは似非プリミティブ型のようなもので、

プリミティブ型みたく文字列リテラルで簡単に生成できる。扱える。

String s = “あああ”みたく。

でもそうやって似非プリミティブとして作られた文字列リテラル同士しか==で比較できない。

つまり

String str1 = new String(“abc”);

String str2 = “abc”;

を==で比較するとfalseになってしまう。equals使えばOK」

②「疑似プリミティブは、以下のような処理を行なう。

1. 既存の文字列に同じものがないかどうか評価

2. もし既に存在していれば、既存のオブジェクトへの参照を代入

3. もし既存の文字列に等価なものが存在しなければ、新たに生成して、そのオブジェクトへの参照を代入

つまり、同じString型で疑似プリミティブ型宣言されたものが既にあれば、そのアドレスを代入してしまうということである。」

から、

オブジェクト指向におけるオブジェクトの「実体」ってなんなのか前々からモヤモヤっとしてたけど、

「メモリ上に生成された（多分16進数の）数列です」って言い切れると理解しました。

③文字リテラルって「プログラム実行時」に「スタック、ヒープとも違う特殊なメモリ内領域にデータ確保」するので「書き換え不可」、とか。

以上①〜③、Javaを切っかっけにオブジェクト指向が学べて良かったです。

ただ、（主にJavaを中心とした）プログラミングスキルの「評価」ができるだけで、わからない部分の解説が読めて「学習」できる感じのサービスではないと知り、学習利用には向いていないのかなと思いました。

参考：

https://javayuri.wordpress.com/2010/10/12/javaequals%E3%81%A8%E3%81%AE%E9%81%95%E3%81%84%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6/

http://mkubara.com/index.php/%E6%96%87%E5%AD%97%E5%88%97%E3%83%AA%E3%83%86%E3%83%A9%E3%83%AB

http://www7b.biglobe.ne.jp/~robe/cpphtml/ (なんとなく保存用)

[kobachiya]

ぶたさんドーナツ、私の胃の中に眠る。なーむー。 #html5j #codeiq

[jwhf]

CodeIQ: Q476: カードゲームの役を判定する

カードゲームの役の判定

概要

https://codeiq.jp/ace/nabetani_takenori/q476

6枚のカードを使って行うカードゲームがあります。その役を判定するプログラムを書いて下さい。 役は下表のとおりです。

役名 記号 意味 例 アンサー An 同一ランクの4枚組と、同一ランクの2枚組 ♥2, ♠2, ♦2, ♣2, ♠A, ♥A シンクダブルトリオ sDT 同一ランクの3枚組が、2組。 各3枚組は、スートの組み合わせが同一。 ♠10, ♥10, ♦10, ♠Q, ♥Q, ♦Q ダブルトリオ DT 同一ランクの3枚組が、2組。 sDT ではない。 ♠10, ♣10, ♦10, ♠Q, ♥Q, ♦Q シンクコントトリプルペア scTP 同一ランクの2枚組が、3組。 各2枚組はスートの組み合わせが同一。 3つのランクが連続している。 ♠9, ♥9, ♠10, ♥10, ♠J, ♥J コントトリプルペア cTP 同一ランクの2枚組が、3組。 3つのランクが連続している。 scTP ではない。 ♠9, ♣9, ♠10, ♥10, ♦J, ♥J シンクトリプルペア sTP 同一ランクの2枚組が、3組。 各2枚組はスートの組み合わせが同一。 scTP ではない。 ♠9, ♥9, ♠10, ♥10, ♠A, ♥A トリプルペア TP 同一ランクの2枚組が、3組。 scTP, sTP, cTP のいずれでもない。 ♠3, ♥3, ♦10, ♥10, ♠A, ♣A

役名が長いので、以下、上表の記号を使います。

ルールの詳細

カード

カードはいわゆる普通のトランプです。ランクは2〜10、J、Q、K、A の 13種類。スートは ♠、♥、♦、♣ の 4 種類です。都合、52種類のカードを使います。Joker は使いません。また、手札には全く同じカードは含まれません（つまり、手札に ♥A が2枚ある、というような状況は起こりません）。 手札は必ず6枚です。

ランクの連続

ランクは A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A のように並んでいると考えます。つまり、「A, 2, 3」や、「9, 10, J」、「J, Q, K」などは連続したランクですが、「2, 4, 6」、「7, 10, K」 などは連続したランクではありません。 なお、「K, A, 2」は連続したランクとはみなされません。通常のポーカーと同じです。

手札の順序

手札にあるカードの順序は役に影響しません。例えば手札が ♥J, ♦10, ♥2, ♥10, ♠2, ♣J の場合、役は TP となります。

入力

同梱の data.txt にデータがあります。 各データは改行で区切られています。各行は HJ,D10,H2,H10,S2,CJ のような形式をしています。見ての通り、各カードがコンマで区切られています。 各カードは HJ や D10 のような形式です。最初の文字がスートを表しています。スートは S, H, D, C のいずれかの文字で、それぞれ ♠, ♥, ♦, ♣ を表しています。 スートを除いた部分（つまり、 J や 10 ）がランクを表しており、ランクは A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K のいずれかの文字列で、見た通りのものを表しています。

出力

data.txt に含まれている手札に各役が何組あるか数えて下さい。 役がない手札を数える必要はありません。 解答の形式は answer.txt を参照して下さい。

補足

data.txt 内の入力文字列には変な形式のもの（いわゆる全角文字、無駄なスペース、コンマが足りない など）は含まれていません。

data.txt 内の手札には変な手札（枚数が足りない、多すぎる、 ♥3 が2枚ある、など）は含まれていません。

data.txt 内のデータは無作為抽出で作っているわけではないので、偏った分布になっています。

data.txt 内のデータには役がないものも含まれます。役がないものは数える必要がありません。

#-*- coding: utf8 -*- #S:SPADE #H:HEART #D:DIAMOND #C:CLOVER #rank={1:A,2:2,3:3,4:4,5:5,6:6,7:7,8:8,9:9,10:10,11:J,12:Q,13:K} #suit={1:S,2:H,3:D,4:C} #An: ex: H2,S2,D2,C2,SA,HA #sDT: ex: S10,H10,D10,SQ,HQ,DQ #DT: ex: S10,C10,D10,SQ,HQ,DQ #scTP: ex: S9,H9,S10,H10,SJ,HJ #cTP: ex: S9,C9,S10,H10,DJ,HJ #sTP: ex: S9,H9,S10,H10,SA,HA #TP: ex: S3,H3,D10,H10,SA,CA def chrrev(a): #マークと数字を入れ替える。また数値でソートできるように変換する:0AH,12H,13H,...20H,2JH,2QH,3KHの形。 for i in range(len(a)): if len(a[i])==2: #2文字の場合 if a[i][1] in ['J','Q']: #HJ->2JH,HQ->2QH a[i]= '2'+a[i][1]+a[i][0] elif a[i][1]=='K': #HK->2KH a[i]= '3'+a[i][1]+a[i][0] elif a[i][1]=='A': #HA->0AH a[i]= '0'+a[i][1]+a[i][0] else: #H2->12H a[i]= '1'+a[i][1]+a[i][0] else: #H10->20H:3文字になるパターンは数字が10の場合のみ。 a[i]='20'+a[i][0] return sorted(a) #ソートしてから返す def phands(a): a0=[] a1=[] rank={ '0A':1,'12':2,'13':3,'14':4,'15':5,'16':6,'17':7,'18':8,'19':9,'20':10,'2J':11,'2Q':12,'3K':13} for i in a: a0+=[rank[i[0]+i[1]]] #数字部分 a1+=i[2] #マーク部分 a0n=sorted(list(set(a0))) #rank: 1:13: 数字部分の積集合 a1n=sorted(list(set(a1))) #suit: S,H,D,C: マーク部分の積集合 if len(a0n)==2: #数字部分の積集合の要素が2の場合、An or sDT or DT if a0.count(a0n[0])==4 or a0.count(a0n[1])==4: #数字が4つある場合、An return 'An' elif len(a1n)==3: #マークが3つの場合、sDT return 'sDT' else: return 'DT' elif len(a0n)==3: #数字部分の積集合の要素が3の場合、scTP or cTP or sTP or TP or - for j in a0n: #数字のどれかが1つしかない場合はブタ、- if a0.count(j)==1: return '-' if a0n==[1,12,13] or a0n[2]-a0n[0]==2: #3つの数字が連続している場合、scTP or cTP if a1[0]==a1[2]==a1[4] and a1[1]==a1[3]==a1[5]: #マークが一致している場合、scTP: この比較のためにソートしている。 return 'scTP' else: return 'cTP' elif a1[0]==a1[2]==a1[4] and a1[1]==a1[3]==a1[5]: #3つの数字が連続していないがマークが一致している場合、sTP return 'sTP' else: return 'TP' else:#他は全部ブタ、- return '-' def gethands(filename): dictcount=[['An','sDT','DT','scTP','cTP','sTP','TP','-','error'], [0,0,0,0,0,0,0,0,0]] #f=open('answer1.txt, mode='w') for line in open(filename,'r'): lineedit=line.replace('\n','') a=lineedit.split(',') tmp=chrrev(a) ans=phands(tmp) #f.write(lineedit+': '+str(tmp)+': '+ans+'\n') for i in range(len(dictcount[0])): if dictcount[0][i]==ans: dictcount[1][i]+=1 break if i==8: dictcount[1][8]+=1 answer= '' for i in range(len(dictcount[0])- 2): answer+=dictcount[0][i]+':'+str(dictcount[1][i])+',' answer=answer[:-1] return answer if __name__=='__main__': print gethands('data.txt')

素直だけどちょっとした工夫の余地がある良問でした。 ↓出題者のblog

http://nabetani.hatenablog.com

[jwhf]

CodeIQ: Q377: Python：島の数をカウントしよう

# -*- coding: utf-8 -*- #Python 2.7.5 (v2.7.5:ab05e7dd2788, May 13 2013, 13:18:45) #CodeIQのPythonで島の数をカウントしようっていう問題。 #https://codeiq.jp/ace/joboffer_apli/q377 #最初に自分で考えたアルゴリズムが #アルゴリズムその1:import_island、island_count、__joinlist #です。これは隣接リストから積集合と和集合を使って島の数をカウントするんですが #白石と黒石の数が増えると極端にパフォーマンスが低下します。 #そこでインターネッツの力を借りて再度考えたアルゴリズムが #アルゴリズムその2:import_island2、island_count2、__check_replace #となっています。 #このアルゴリズム2はアルゴリズム1と違って石の数を全部走査すれば終わるので線形時間で終わります。 #パフォーマンス比較結果： #石の総数:100*100=10000、黒石の数:4987、島の数:703 #import_islandの実行時間:24秒227035 #import_island2の実行時間:0秒066305 #そもそもクラスの書き方に自信がないでござる。 #テキストファイルは自分で用意してください。 import math, datetime class IslandCount(object): def __init__(self,ff='sample_island1.txt'): self.ff=ff #白石0黒石1で描画したテキストファイル #石を描画する。白:0、黒:1。 def draw_island(self,c=[],m=0,n=0): list1=[] b='' for i in range(m*n): list1.append('0') for i in c: list1[i-1]='1' for i in range(m-1): list1.insert((i+1)*(n+1)-1,'\n') for i in range(len(list1)): b+=str(list1[i]) print b ''' アルゴリズムその1ここから ''' #txtファイルを読み込む場合に使用する。 def import_island(self,f=''): f=self.ff flist=[] sindex=[] j=0 flg=0 f=self.ff f=open(f).read() for i in f: j+=1 if i!='\n': flist.append(i) else: if flg==0: flg=1 clmns=j-1 lns=len(flist)/clmns for i, v in enumerate(flist): if v=='1': sindex.append(i+1) return self.island_count(sindex,lns,clmns) #島の数を返す。 def island_count(self,a=[],m=0,n=0): count=0 join_list2=[] new_list=[] flist=[] l=len(a) newlist2=[] #n=int(math.sqrt(m)) #黒石の1方向隣接リストを生成する。 #例:[1,2],[2,3],[2,8] for i in range(l-1): for j in range(l-1): if a[j+1]-a[i]==1 and a[i]%n!=0 or a[j+1]-a[i]==n: join_list2+=[[a[i],a[j+1]]] #黒石の隣接リストで結合できるものを結合する。 #例:[1,2,3,8] for i in range(len(join_list2)): for j in range(len(join_list2)): if join_list2[i][1]==join_list2[j][0]: join_list2[i]=join_list2[i]+join_list2[j][1:] for i in range(len(join_list2)): join_list2[i]=sorted(join_list2[i]) #結合した隣接リストから島リストを返す。 #例:[1,2,3,8],[7,8,9,10],[3,4,10]→[1,2,3,4,7,8,9,10] newlist2=self.__joinlist(join_list2) #島リストを結合する。 #[[6, 12], [7, 13]]→[6, 12, 7, 13] for i in newlist2: flist+=i #黒石の数-結合した島リストの要素数=黒石1つだけの孤島 #求めたい島の数=孤島+島リストの数(孤島ではない島の数) count=l-len(flist)+len(newlist2) '''描画が不要な場合は1行下ののコメント化してください。''' self.draw_island(a,m,n) return count #黒石の隣接リスト同士にて積集合が存在する場合、和集合を生成し重複を削除する。 def __joinlist(self,join_list2): newlist=[] flg=0 for i in range(len(join_list2)): for j in range(len(join_list2)): #自分自身以外で積集合が空でない場合 if i!=j and join_list2[j]!=[]: if len(set(join_list2[i])&set(join_list2[j]))>0: #和集合 flg=1 join_list2[i]=list(set(join_list2[i])|set(join_list2[j])) join_list2[j]=[] #重複を削除する。 for line in join_list2: if sorted(line) not in newlist and line!=[]: newlist.append(sorted(line)) #積集合がすべて空の場合、再帰を抜ける。 if flg==0: return newlist return self.__joinlist(newlist) ''' アルゴリズムその1ここまで ''' ''' アルゴリズムその2ここから ''' #txtファイルを読み込む場合に使用する。Part2 def import_island2(self,f=''): f=self.ff linescount=0 c=[] for line in open(f): b=[] columnscount=0 for char in line: if char.strip()!='': columnscount+=1 b+=[int(char.strip())] linescount+=1 c+=[b] return self.island_count2(c,linescount,columnscount) #島の数を返す。Part2 def island_count2(self,c,m,n): r=[0,0] for i in range(m): for j in range(n): if c[i][j] != -1: #c[i][j]==0の場合、r[0]+=1 #c[i][j]==1の場合、r[1]+=1 r[c[i][j]] += 1 #上で+1した後、c[i][j]の上下左右をチェックしていき同値の場合-1に置換する #即ち指定したc[i][j]と同じ島はカウントに+1後、すべて-1に置換され、次のチェックでカウントされない self.__check_replace(c,i,j,m,n) return r[1] #黒石の島の数を返す。白石はr[0] #チェックした要素と隣接する同値の要素を-1で再帰的に置換していく。 def __check_replace(self,c,i,j,m,n): k = c[i][j] c[i][j] = -1 #2行目以降で上の石が同じ場合、上の石に対して再帰 if i>0 and c[i-1][j]==k: self.__check_replace(c,i-1,j,m,n) #2列目以降で左の石が同じ場合、左の石に対して再帰 if j>0 and c[i][j-1]==k: self.__check_replace(c,i,j-1,m,n) #最終行より前の行で下の石が同じ場合、下の石に対して再帰 if i self.__check_replace(c,i+1,j,m,n) #最終列より前の列で右の石が同じ場合、右の石に対して再帰 if j self.__check_replace(c,i,j+1,m,n) ''' アルゴリズムその2ここまで ''' if __name__=='__main__': ''' a1:黒石のインデックス b1,c1:縦マスの数,横マスの数 f1-f4:黒石を1白石を0で記述したテキストファイル ''' a1=[6,7,12,13] b1,c1=6,6 f1='sample_island1.txt' a2=[6,11,12,17] b2,c2=6,6 f2='sample_island2.txt' a3=[1,2,3,4,7,8,9,10,12,13,24,25,29,30,31,35,36] b3,c3=6,6 f3='sample_island3.txt' a4=[1,2,3,4,7,8,9,10,12,13,24,25,29,30,31,35,36] b4,c4=7,7 f4='sample_island_100_100.txt' aaa=IslandCount(f1) #print '島の数:'+str(aaa.island_count(a1,b1,c1)) #黒石のインデックス数と石の総数から島の数を返す。 t1=datetime.datetime.now() print '島の数:'+str(aaa.import_island())+' #アルゴリズム1' #filenameで指定されたファイルから島の数を返す。1番目のアルゴリズム t2=datetime.datetime.now() print str(t2-t1)+'秒' t1=datetime.datetime.now() print '島の数:'+str(aaa.import_island2())+' #アルゴリズム2' #filenameで指定されたファイルから島の数を返す。2番目のアルゴリズム t2=datetime.datetime.now() print str(t2-t1)+'秒' print '===========================================================================================' bbb=IslandCount(f2) #print '島の数:'+str(bbb.island_count(a2,b2,c2)) t1=datetime.datetime.now() print '島の数:'+str(bbb.import_island())+' #アルゴリズム1' t2=datetime.datetime.now() print str(t2-t1)+'秒' t1=datetime.datetime.now() print '島の数:'+str(bbb.import_island2())+' #アルゴリズム2' t2=datetime.datetime.now() print str(t2-t1)+'秒' print '===========================================================================================' ccc=IslandCount(f3) #print '島の数:'+str(ccc.island_count(a3,b3,c3)) t1=datetime.datetime.now() print '島の数:'+str(ccc.import_island())+' #アルゴリズム1' t2=datetime.datetime.now() print str(t2-t1)+'秒' t1=datetime.datetime.now() print '島の数:'+str(ccc.import_island2())+' #アルゴリズム2' t2=datetime.datetime.now() print str(t2-t1)+'秒' print '===========================================================================================' ddd=IslandCount(f4) #print '島の数:'+str(ddd.island_count(a4,b4,c4)) t1=datetime.datetime.now() print '島の数:'+str(ddd.import_island())+' #アルゴリズム1' t2=datetime.datetime.now() print str(t2-t1)+'秒' t1=datetime.datetime.now() print '島の数:'+str(ddd.import_island2())+' #アルゴリズム2' t2=datetime.datetime.now() print str(t2-t1)+'秒' print '==========================================================================================='

[tnoda-clojure]

@cielavenir の CodeIQ 問題 (Restricted Words)

https://codeiq.jp/ace/cielavenir/q431

出題当初は解答指定言語に Clojure が含まれていなかったのでネタツイートしたら， 出題者の @cielavenir が何と対応してくださるということなので， 調子に乗って解いてみました．

指定言語に #clojure が含まれていないので 9/19 過ぎたら抗議はろーわーるどする。/挑戦者求む！Restricted Words by @cielavenir http://t.co/oLfv0hnoWd via @codeiq

— tnoda_ (@tnoda_) September 5, 2013

解答提出後，@cielavenir から私の解答について公開 ok の返事をもらいましたので，晒してみます．

問題と解答

オリジナルの問題は，

標準出力に Hello World と出力するプログラムを作成して下さい。

ただし、数値、文字及び文字列リテラルを解答に含めることはできません。

というものでした．これに加えて，独自に，

正規表現リテラル禁止

java.lang.String 禁止

clojure.lang.Symbol 禁止

clojure.lang.Keyword 禁止

という縛りを追加して作成した解答がこれです:

(let [m (frequencies [< / * < == + = - / + * / > * + + = < - > < = - = - / - + - < = - == / > = = < > * = = - / / - < / < = = / - / + - > + + + / = / / = = < = < + / = - * > + / < == == > * < < - - < + > < = + - / < / * < - < + < < - + < < + == + = + + / < - + / + = > > - + / = / * * + < / + = - / > > < = < = / * / < > < * - - > * < = + > = < > < < > < = - < - = * == + - < * + < * - < < = = - - + + == = - - / = + - / > * > < * + / / == * - = - - > + < = / < * * < < - > + = + - = + / + > > * * = = / < == * < - / + = > > > > = / = < * - < == > / > > / > = - == == * * < - - < + > + / - > = + < + == / / * - = > < = + * = - < / * - > / > * < + - > / + + - + == / = * - - + - / - - = / * > + < * < > / * = < = - < > * * = - > = - + < - > / * + * * + / + > * + - + = < == < - = < - < / > + / - = - / - + < - < + > - = = - * - > = / > / = + = = - * / = / - + == = / * - < * / / < / / + + - < * > / = < < * + > * - == / + > / + < - = + - == - - + - / < = = - + > - = = > + = - > = == = / - * + == = + = == - > > / > * - + = * < > == / * * + / * / = * = > - / - > - * = > - / = + = + + - + * == - / = = * - + < - < == / = = - + > / / * > = < < = - / = - + * > = > / + > < + = / < > > < / < * = * + = = > < + + > / + - = - + + > > + < < > / = < = - + = / > == + * = + - * < == < / + < / > + > + = - * * = < + = = + > = + = - < < * == + / > = < + < + = < / - == > < / = = > + / - = = = / / - / > < > + - + / - - * == < > + = * + * + - < == * / = == / / + + > > = + > < < == > / + - * / / / * = > / = < - / +])] (doseq [c [* / - - + == > + = - <]] (-> c m char print)))

先に挙げた縛りを追加すると，何かを数え上げて char するしかないので， ここでは，関数を並べて frequencies で数えることにしました．

他にも 2 パタン作成し，合計 3 パタン提出したのですが， ここに上げた数え上げパタンが出題意図に最も近かったそうです．

そのほかの解答 (1)

おそらく最も簡単な解答はこちら↓

私の回答は (println 'Hello 'World) でした（Clojure）→ "Restricted Words by cielavenir│CodeIQ" https://t.co/bxgFqZLzjN

— Masakazu Takahashi (@emasaka) September 21, 2013

この解答，println の代わりに prn でも同じ結果になります．

user> (println 'Hello 'World) Hello World nil user> (prn 'Hello 'World) Hello World nil

問題提出時には，残念ながら，私は prn/println のこの使い方を思いつきませんでした． まだまだ修行が足りません．

そのほかの解答 (2)

問題文の条件は満たしていたけれど， なぜか出題者からは認められなかった解答がこちら↓

(pr (str #"Hello World")) #clojure #codeiq

— Tatsuya Tsuda (@otabat_) September 5, 2013

#" ... " は Clojure の正規表現リテラルで文字列ではないのですが， この解答は NG でした．

おわりに

この問題，何がすごいかというと，

プログラミング言語は AppleScript(osascript)/C/C++/C#/Clojure/D/Erlang/Fortran/Go/Groovy/Haskell/ Hello Algorithm/HSP/Java/JavaScript(Node.js)/Kuin/Lisp/Lua/OCaml/Pascal/ Perl/PHP/Pike/Python/R/Ruby/Scala/Scheme/Smalltalk/VB.Net のいずれかを使用して下さい。指定された言語以外での解答は評価されません。

という対応言語数の多さで，しかも，これは最初からこれだけの数を指定されていたのではなく， 私のようなコメントを拾いながら @cielavenir が増やしていったものなのです．とにかく数が多い． 解答の評価も大変だったと思いますが， 指定言語に Clojure を加えてくださったことを @cielavenir に感謝して， この記事を終わります．

[jwhf]

クロッシング問題反省文

The Essence of Programming 結城 浩さんからのアルゴリズムの問題 https://codeiq.jp/ace/yuki_hiroshi/q432 通称クロッシング問題に挑戦しました。 結果間違えていたので反省文です。 提出した結果とアルゴリズムは勘違いしまくっていて恥ずかしすぎるのでここには書けません。 提出後、Twitterのタイムラインを眺めているとマージソート云々が出てきたのでマージソートで考え直し実行した結果、フィードバック前に間違いが判明しました。 以下はクロッシング問題がマージソートだと気付いた前提で正解にたどり着いてから3秒切るまでの過程です。 これを記述している時点で正解は確認していますが解説は読んでいない状況です。

#ENV: Python 2.7.5, MacBook Pro Retina, 2.6GHz Intel Core i7

マージソートに気付いてしまえばあとはその交換回数をカウントするだけです。 実装後、最初の結果は

24659511355 #（不正解なので注意） 0:00:03.431269 #秒

だったのですが、解答を確認すると間違えていました。 マージソートしたリストのインデックスと要素を調べると、

list[0]=1: #OK list[1]=10: #NG list[2]=100: #NG ...

となっていてlist[0]以外全部不一致です。 この並びでピンと来ると思うのですが文字列でのソートになっています。 crossing.txtが改行区切りのファイルだったのでreadlines()を使用していたのですがこれは文字列のリストとして読み込むので文字列比較になっていました。 そこでマージソートの大小比較時に

if int(left(j))<=int(right(k)):

としました。結果、

24689222839 0:00:10.073697 #秒

となり正解です。 ただし、比較の都度strからint変換を呼ぶので変換回数が最大でn^2となってしまい、計測時間が約3倍になっています。 この問題のファイルの行数nは314159行なのでn^2=98695877281で千億近くです。 そこでこれを減らすためにマージソートに渡す前にreadlines()をintにmapすることにしました。

map(int,open('crossing.txt').readlines())

これによりintへの変換回数がn回になりました。 これで実行した結果、

24689222839 0:00:03.515647 #秒

となり、当初の文字列比較時点と近い計測時間となりました。 しかし、クロッシング問題の最高点の5点を取るためには計測時間が3秒を切る必要があります。 これ以上のアルゴリズムの改善は現時点で思い浮かばないのでPythonの上位互換であるCythonで実行してみることにしました。 Python上で記述したものと同じ内容を拡張子pyxとして保存コンパイルし実行した結果、

24689222839 0:00:01.596736 #秒

となり約2秒短縮され無事3秒の壁を突破することができました。 さらにCythonの場合、静的型宣言cdefを記述することによりより実行時間が改善されるようになってます。 そこでcountをdouble、各インデックスをintで宣言し再度計測した結果、

24689222839.0 0:00:00.590304 #秒

となりさらに1秒の短縮になりました。 以上の結果を踏まえて結城浩さんの解説を読み、再度復習しようと思います。 #おまけとしてiOS用のPython2.7を使用してiPhone5上にて実行した結果を記載しておきます。

24689222839 0:00:15.774352 #秒

現時点で最終的なコードは以下の通りです。 cdef部分はpyx用です。Cythonでコンパイルする場合はアンコメントしてください。

import datetime def crossing(f): time1=datetime.datetime.now() print mergeCount(map(int,open(f).readlines())) time2=datetime.datetime.now() print time2-time1 def mergeCount(a): ## cdef double count ## cdef int n, j, k, i count=0 n=len(a) if n>1: b=a[0:n/2] c=a[n/2:n] count+=mergeCount(b) count+=mergeCount(c) j=0 k=0 for i in range(0,n): if k==len(c): a[i]=b[j] j+=1 elif j==len(b): a[i]=c[k] k+=1 elif b[j]<=c[k]: a[i]=b[j] j+=1 else: a[i]=c[k] k+=1 count+=n/2-j return count if __name__=='__main__': print crossing('crossing.txt')

反省文ということで書きましたがそもそも問題文を見た時点でマージソートに思い至らなかった部分が反省点なんですがそこに至るにはこれからもたくさん問題解いていかないとなという結論になりました。 これを機にCodeIQで色々挑戦していこうと思います。 #####補足:OSXでのCythonの実行手順#####

$ Cython filename.pyx

を実行するとfilename.cが作成されます。 上記実行後、以下をfilename_setup.pyなどの名前で保存し、Python上で実行します。

# -*- coding: utf-8 -*- from distutils.core import setup from distutils.extension import Extension from Cython.Distutils import build_ext as build_pyx setup(name = 'filename', ext_modules=[Extension('filename', ['filename.pyx'])], cmdclass = { 'build_ext': build_pyx })

上記のfilename_setup.pyを実行することによりfilename.soが作成されます。 soファイル作成後、Python上で

>> import pyximport; pyximport.install() >> import filename

とすることによりPython上で実行できるようになります。