paizaオンラインハッカソン7に参加してみた – メガネ(C++, Swift※コードゴルフ版付き)

注意: この記事は1年以上前に掲載されたものです。情報が古い場合がありますのでお気を付け下さい。

当ブログでは順次『paizaオンラインハッカソンVol.7 プログラミングで彼女をつくる』の回答例を上げているが、今回は他のお題を一旦飛ばして、「メガネ」の回答例をあげてみたい。なお、今回はSwiftについてはコードサイズをある程度削減したコードゴルフ版も掲載してみたい。

今回のお題の目的

今回のお題の目的は、以下の順に入力されるため、それを元に、パターンが一致する始点座標(左上ベース)を取得するというものである。

  1. nサイズを表す数値が送られてくる。
  2. nサイズ分の0または1の数値がSSV形式でn回分送られてくる。
  3. mサイズを表す数値が送られてくる。なお、mはnよりも小さい。
  4. mサイズ分の0または1の数値がSSV形式でn回分送られる。

上記から、まずnサイズ分の入力データとmサイズ分の入力データを準備し、それを元にnのパターンとmのパターンが完全に一致する始点を出力することが必要となる。

今回では、以下の要素が支えているかどうかが重要になる。

  • 多次元配列あるいはそれに近いものが使えるかどうか
  • forループと抜ける条件をうまく使えるかどうか
  • (Swiftのコードゴルフの場合)どうやったら簡潔に書けるか

回答例

C++

参考URL: https://github.com/saitomarch/POH7/blob/master/cpp/megane.cpp

[code lang=”cpp”]#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cstdlib>
using namespace std;
string readline() {
string str;
getline(cin, str);
return str;
}
vector<string> split(const string &str, char sep) {
vector<string> vec;
istringstream sstream(str);
string buf;
while (getline(sstream, buf, sep)) {
vec.push_back(buf);
}
return vec;
}

std::vector<std::vector<int>> prepare(int size) {
std::vector<std::vector<int>> vec;
for (int cnt = 0; cnt < size; cnt++) {
std::vector<int> line;
auto arr = split(readline(), ‘ ‘);
for (int idx = 0; idx < size; idx++) {
line.push_back(stoi(arr[idx]));
}
vec.push_back(line);
}
return vec;
}

int main(void){
const auto s1 = stoi(readline());
auto m1 = prepare(s1);
const auto s2 = stoi(readline());
auto m2 = prepare(s2);

int x = 0, y = 0;
bool finished = false;
for (int x1 = 0; x1 <= s1 – s2 && !finished; x1++) {
for (int y1 = 0; y1 <= s1 – s2 && !finished; y1++) {
bool matches = true;
for (int x2 = 0; x2 < s2 && matches; x2++) {
for (int y2 = 0; y2 < s2 && matches; y2++) {
if (m1[x1 + x2][y1 + y2] != m2[x2][y2]) {
matches = false;
}
}
}
if (matches) {
x = x1;
y = y1;
finished = true;
}
}
}
cout << x << " " << y << endl;

return EXIT_SUCCESS;
}[/code]

Swift

通常版

参考URL: https://github.com/saitomarch/POH7/blob/master/swift/megane.swift

[code lang=”swift”]func prepare(times:Int) -> [[Int]] {
var arr : [[Int]] = [[Int]](count: times, repeatedValue: [Int](count: times, repeatedValue: 0))
for (var cnt = 0; cnt < times; cnt++) {
let cells = readLine()!.characters.split{$0 == " "}.map(String.init)
for (var idx = 0; idx < cells.count; idx++) {
arr[cnt][idx] = Int(cells[idx])!;
}
}
return arr;
}
let s1 = Int(readLine()!)!
let m1 = prepare(s1);
let s2 = Int(readLine()!)!
let m2 = prepare(s2)

var x = 0, y = 0;
var finished = false;
for (var x1 = 0; x1 <= s1 – s2 && !finished; x1++) {
for (var y1 = 0; y1 <= s1 – s2 && !finished; y1++) {
var matches = true;
for (var x2 = 0; x2 < s2 && matches; x2++) {
for (var y2 = 0; y2 < s2 && matches; y2++) {
if (m1[x1 + x2][y1 + y2] != m2[x2][y2]) {
matches = false;
}
}
}
if (matches) {
x = x1;
y = y1;
finished = true;
}
}
}
print(x,y)[/code]

コードゴルフ版

参考URL: https://github.com/saitomarch/POH7/blob/master/swift/megane_golf.swift

[code lang=”swift”]func p(t:Int)->[[String]]{var a=[[String]]()
for _ in 0..<t{a.append(readLine()!.characters.split{$0==" "}.map(String.init))}
return a}
let s=Int(readLine()!)!,m=p(s),t=Int(readLine()!)!,n=p(t)
d:for h in 0…s-t{for i in 0…s-t{var e=1
c:for j in 0..<t{for k in 0..<t{if(m[h+j][i+k] != n[j][k]){e=0
continue c}}}
if(e>0){print(h,i)
break d}}}[/code]

解説

今回はC++、Swift共に動的配列を使った。少なくとも入力データからサイズに関しては一致が保証されるからである。

C++とSwift(通常版)では各画像データの配列を整数型に変換してから取得、Swift(コードゴルフ版)ではコード量を削減するため、String型の多次元配列として、入力データを分割したものをそのまま入れる形式を使った。

その後、パターンチェックだが、ループとしては始点はnのサイズ-mのサイズとなる。そうしないと配列外となってしまうからである。その始点を元に、各マスが一致しているかどうかチェックしている。その際、一つでも一致していなければマッチしていないというフラグを立てて、次の処理に進めるようにした。

すべてマッチした場合は、マッチした地点の数値を保持してそれ以降のチェックを打ち切った ((今回では必ず一つであるという条件があるため)) 。

最後にすべてマッチした左上の座標を出力して終わりである。

コードゴルフ版では、コード量削減のため、変数を1文字に抑えたり、余計な空白や冗長な記述を削減したが、これでも完全には削減しきれていない状態である。

最後に

今回のお題は何を求めているのかがわかれば、回答自体はそれほど難しくないが、いかにして短いコードで実現できるかとなると途端に難しくなるのが特徴であると言える。

Swiftではコードゴルフのランキングも行われているので、自信がある方は是非チャレンジしてみると良いだろう。

タイトルとURLをコピーしました