「1000のアルゴリズムを持つ男」vs.「やわらか頭脳」の第二問目の解答を試みる
「1000のアルゴリズムを持つ男」vs.「やわらか頭脳」 (1/3) - ITmedia エンタープライズ
前回に引き続き第二問目、2次元カントール集合に関する問題。
回答が与えられているので、答えを新たに考えるわけではありませんが、内容が難しいので、答えを参照しつつ、自分に分かりやすいように書き直しました。特に記事の回答がマズイ等なことを主張しているわけではないですよ、と一応注意。
自分の改変部分について
- getstring関数は文字列型を返しますが、結局C[k+x] == 'X'と、ブール値判定を行ったものを用いているので、最初からブール型の1次元カントール集合(2次元カントール集合の射影集合(projection set))を返すようにした。
- オーバラップの判定部分を分離してisOverlap関数とした。
あと、個人的には全て'.'で構成されているパターンの計算が難しかったですね。
Code
private static bool[] get1DimCantorDust(int time) { if (time == 0) return (new bool[] { true }); bool[] prev = get1DimCantorDust(time - 1); bool[] res = new bool[3 * prev.Length]; prev.CopyTo(res, 0); prev.CopyTo(res, 2 * prev.Length); return res; } private static bool isOverlap(bool[] pat, bool[] patC, int init) { for (int it = 0; it < pat.Length; ++it) if (pat[it] != patC[init + it]) return false; return true; } private static bool isWhitePattern(string[] pat) { foreach (string p in pat) if (p.IndexOf('X') != -1) return false; return true; } public int occurrencesNumber(string[] pattern, int time) { bool[] projX = new bool[pattern.Length]; bool[] projY = new bool[pattern[0].Length]; for (int x = 0; x < pattern.Length; ++x) for (int y = 0; y < pattern[0].Length; ++y) if (pattern[x][y] == 'X') projX[x] = projY[y] = true; for (int x = 0; x < pattern.Length; ++x) for (int y = 0; y < pattern[0].Length; ++y) if ((pattern[x][y] == '.') && projX[x] && projY[y]) return 0; bool[] patCantor = get1DimCantorDust(time); int mX = 0; int mY = 0; for (int initX = 0; initX + projX.Length <= patCantor.Length; ++initX) if (isOverlap(projX, patCantor, initX)) ++mX; for (int initY = 0; initY + projY.Length <= patCantor.Length; ++initY) if (isOverlap(projY, patCantor, initY)) ++mY; return isWhitePattern(pattern) ? mY * (patCantor.Length - pattern.Length + 1) + mX * (patCantor.Length - pattern[0].Length + 1) - mX * mY : mX * mY; }
結果
Test Case #0...PASSED Test Case #1...PASSED Test Case #2...PASSED Test Case #3...PASSED Test Case #4...PASSED Test Case #5...PASSED Test Case #6...PASSED Test Case #7...PASSED Test Case #8...PASSED Test Case #9...PASSED