「第16回オフラインリアルタイムどう書く」解答（Java）
前回のオフラインリアルタイムどう書く（http://atnd.org/events/45016）では、第16回というキリ番にもかかわらず負けてしまいました。
- オフラインリアルタイムどう書くとは
- 鍋谷さんが出してくださるお題を、参加者が好きなプログラミング言語で解いて楽しむ会です。
年も改まったことですし、気持ちを新たに問題を解き直してみました。といいたいところですが、ギブアップして、nidouchiさんの解答を読んでほぼ同じ内容をJavaで書いてみました。ヘタレですみません。
なぜJavaから遠いRubyの解答を参考にしたかというと、nidoさんの解答がビット演算を使っていなかったので、ビット演算弱者の自分にとっては理解しやすかったからです。ヘタレですみません……。
問題
今回は、「境界線分」です！
白黒に塗り分けられたマス目が与えられ、白と黒の境界を構成する線分の長さと数を計算します。
詳細は、問題ページをご覧ください。
ここから先はネタバレです。
ボツにした自分の戦略
イベント当日に自分が考えた戦略では、マス目に着目していました。
すべてのマスは四方に長さ1の線分を持つものと考えて、境界を見つけるたびに、それを消し込んでいくつもりでした。
境界線が交差することはない。
境界線分 横へな 2013.12.7
言い換えると、一つの頂点をぐるっと巡った時に「白黒白黒」となることはない。
上の条件を生かせていないので、これはダメでした。
nidoさん解答
nidoさんの解答は、次のページにあります。
- 第16回オフラインリアルタイムどう書く rubyで解く http://qiita.com/nidouchi/items/433563d664c0a1983919
nidoさんの戦略は、図にするとこんな感じであると理解しています。
マスではなく線分に着目します。
まず、2行ずつ見ていき、上の行と下の行で色が異なるところを見つけたら、線分としてマークします。
次に、マークが連続する数を数えて、線分の長さを出します。
そして、平行と垂直のチェックを行うため、図全体を90度回転して同じことをします。
最後に、平行ラインと垂直ラインを足し合わせて、答えを出します。
なお、他の方の解答は、Qiitaから辿れます（http://qiita.com/Nabetani/items/6a9f5593d0f3d7e0568c）。
Java解答（nidoさん解答のJava版）
import java.util.ArrayList; import java.util.Arrays; import java.util.List; /** * Question: http://nabetani.sakura.ne.jp/hena/ord16boseg/ * -- this answer is a RE implementation of the answer, * http://qiita.com/nidouchi/items/433563d664c0a1983919 */ public class Boseg { public String solve(String input) { int[][] table = parse(input); int[] hLineCount = countLine(table); int[] vLineCount = countLine(transpose(table)); return format(hLineCount, vLineCount); } String format(int[] hlist, int[] vlist) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < hlist.length; i++) { sb.append(String.valueOf(hlist[i] + vlist[i])); sb.append(","); } sb.deleteCharAt(sb.length() - 1); return new String(sb); } int[][] transpose(int[][] old) { int[][] result = new int[old[0].length][old.length]; for (int i = 0; i < old.length; i++) { for (int j = 0; j < old[0].length; j++) { result[j][old.length - 1 - i] = old[i][j]; } } return result; } int[] countLine(int[][] table) { List<boolean[]> lines = new ArrayList<>(); for (int i = 0; i < table.length - 1; i++) { boolean[] w = new boolean[table.length]; for (int j = 0; j < table.length; j++) { if (table[i][j] != table[i + 1][j]) { w[j] = true; } } lines.add(w); } int[] result = { 0, 0, 0, 0, 0, 0 }; for (boolean[] row : lines) { int count = 0; for (boolean cell : row) { if (cell) { count++; } else { if (0 < count) { result[count - 1] = result[count - 1] + 1; count = 0; } } } if (0 < count) { result[count - 1] = result[count - 1] + 1; } } return result; } int[][] parse(String input) { char[] charArray = input.toCharArray(); StringBuilder sb = new StringBuilder(); for (int i = 0; i < charArray.length; i++) { sb.append(toBinary(String.valueOf(input.charAt(i)))); } String str = new String(sb); int cnt = 0; int[][] result = new int[6][6]; for (int i = 0; i < 6; i++) { for (int j = 0; j < 6; j++) { result[i][j] = Integer.parseInt(String.valueOf(str .charAt(cnt++))); } } return result; } String toBinary(String s) { int o = Integer.parseInt(String.valueOf(s), 8); String binary = Integer.toBinaryString(o); if (binary.length() < 3) { for (; binary.length() < 3;) { binary = "0" + binary; } } return binary; } }
テストを除いて、ほぼ100行になりました。
- 上のコードと、テストコード https://gist.github.com/torazuka/8209724
