2016-01-06

paiza Online Hackathon 7 めがね問題をSwiftで

恋愛SLG: プログラミングで彼女をつくる|paizaオンラインハッカソン7 というのを見かけたのでやってみました。

水着問題はちょっと難しかったです。

https://paiza.jp/poh/ando/share/fb746b63

「Swiftオープントップ50」というのもやってみました。 めがねがもらえる問題をSwiftで解き、平均速度とプログラムのバイト数を競うというものです。 この手の競技プログラムはやったことがありませんし、そもそもSwiftでプログラムを作ったこともありませんが、この機会に試してみました。

let
f={readLine()!}, // 1行読み込み関数
g={Int(f())!}, // 1行整数読み込み関数
h={(0..<$0).map{_ in f().characters.flatMap({Int(String($0))})}}, // 画像読み込み関数(h(size)でsize*sizeの2次元配列を返す)
n=g(),a=h(n), // 画像Nを読み込む
m=g(),b=h(m), // 画像Mを読み込む
o=n-m+1, // NとMの大きさの差を求める
s={a[$0/o+$1][$0%o..<$0%o+m] != b[$1][0..<m]}, // 画像の行に沿った1区間を比較する関数(ArraySlice同士の比較)
z=(0..<o*o).indexOf{p in (0..<m).indexOf{s(p,$0)}==nil}! // NにMを重ねたときに一致しない行が見つからなかった最初の左上座標を探す
print(String(z/o)+" "+String(z%o))

改行を削除して 0.01秒 271byte、この記事作成時点で23位。

1位の54 byteなんてどうやっているんでしょうね。ひょっとしてテストケースの性質を利用している?

最初はピクセルデータを文字列のままマッチングする方法を試したのですが、Swiftは文字列の部分取りだしが非常に面倒なようで、startIndex.advancedByなどと長い名前を打たされたあげくスピードもテストケース5で0.01を逃してしまったので方針を変更。諦めて配列を作って比較するようにしました。

Swiftいいですね。Closureは短く書く書き方もあって便利です。

Swiftの言語リファレンスやライブラリリファレンスと睨めっこしながら作成しました。古いバージョンのコードは結構動かなくなってるんですね。ぐぐって調べたコードがコンパイルできなくて難儀しました。

hの中にある"0 1 1 0"みたいな文字列を[0,1,1,0]へ変換する部分が短く書けなくて悩みました。Swiftのバージョンによっても書き方が違ってくるみたいです。

sやzのところで/や%を使っているところがありますが、このあたりの書き方次第で「Expression was too complex to be solved in reasonable time」というエラーが出てコンパイルできない場合が多々ありました。コンパイル時間(サーバの応答時間?)も書き方によって体感できるくらい差が出ます。元々sの比較処理は関数化せずにzの中にあったのですが、1つの式で書くとこのエラーが出てしまうため、式を分割しなければなりませんでした。分割するとletとreturnの文だけ文字数がかかってしまうので悩んだのですが、sを関数としてくくり出したら何とかコンパイルは通りました。

[1,2,3,4,5][2…3]==[3,4]が通るのにlet n=[1,2,3,4,5],m=[3,4];n[2…3]==mが通らないのは不思議でした。n[2…3]==[3,4]は通ります。ArraySlice<Int>と[Int]を引数に取る==演算子が無いからみたいなのですが、mは[Int]だけど[3,4]は違う?

(2015-01-07追記:なんとprint(a,b)でa bと出力されるんですね! あと細かいところを少し調整して、これだと249byte)

let
f={readLine()!},
g={Int(f())!},
h={(0..<$0).map{_ in f().characters.flatMap({Int(String($0))})}},
n=g(),a=h(n),
m=g(),b=h(m),
o=n-m+1,
s={a[$1+$2][$0..<$0+m]==b[$2][0..<m]}, // !=ではなく==にして呼び出し側で!sとした。!=だと!=の前後に空白を入れないとコンパイルエラーになるが==なら空白はいらない(-2 +1)
z=(0..<o*o).indexOf{p in (0..<m).indexOf{!s(p%o,p/o,$0)}==nil}!; //%o,/oはsからzへ移動。文字数は変わらない(-6 +6)けど、この方が分かりやすいし剰余も一回で済む。
print(z/o,z%o) //こう書けたorz(-21 +1)