#codeiq

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

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;}

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

カードゲームの役の判定

概要

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

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 のいずれかを使用して下さい。指定された言語以外での解答は評価されません。

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