読者です 読者をやめる 読者になる 読者になる

matsukaz's blog

Agile, node.js, ruby, AWS, cocos2d-xなどなどいろいろやってます

Google DevFest 2010 Quizのパッチワーク問題

Java

パッチワーク

ここに "A" または "B" という文字のみを含む 600 桁、600 行のテキストがあります。これを 600 x 600 の升目状に並べ、上下左右に同じ文字がある部分をつながっているとみなします。
まず、最も多くの文字がつながっている領域をすべて "_" で塗りつぶしてください。 最も多くの文字がつながっている領域が複数存在するならば、それらすべての領域を "_"で塗りつぶすこととします。
そして、各行ごとに "_" が何個含まれているかを数え、それらの数値を改行区切りのテキスト(600 行)として答えてください。
以下の例1を見てください。この入力には単一の文字4つでつながった領域が3箇所あります。これらすべてが「最も多くの文字がつながっている領域」なので、全て"_"で塗りつぶし、その数を数えています。

http://devquiz.appspot.com/problems?problem=patchwork

いろいろ回答例が晒されてるので、自分のも晒してみます。ベタベタですが。

やってることは、ファイルの内容をPatchクラスの二次元配列に変換して、最大領域を占める部分の検出、および指定した文字列への変換をして、最後に集計してるってだけです。

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

/**
 * パッチワーク問題の回答
 *
 * @author matsukaz
 */
public class Main {
	private static final String INPUT_FILE = "patchworkinput.txt";
	private static final String OUTPUT_FILE = "patchworkoutput.txt";
	private static final int MAX_LINE_SIZE = 600;
	private static final int MAX_ROW_SIZE = 600;
	private static final char REPLACE_CHAR = '_';

	/**
	 * メイン
	 *
	 * @param args
	 */
	public static void main(String[] args) {
		Patch[][] patches =
			createPatches(INPUT_FILE, MAX_LINE_SIZE, MAX_ROW_SIZE);
		List<Patch[]> maxPatchAreaList = getMaxPatchAreaList(patches);
		replaceVal(maxPatchAreaList);
//		outputPatches(patches, OUTPUT_FILE);
		outputPatchesCnt(patches, OUTPUT_FILE);
	}

	/**
	 * ファイルを読み込んでPatchクラスの二次元配列に変換する。
	 *
	 * @param fileName
	 * @param maxLineSize
	 * @param maxRowSize
	 * @return
	 */
	private static Patch[][] createPatches(final String fileName,
			final int maxLineSize, final int maxRowSize) {
		Patch[][] patches = new Patch[maxLineSize][maxRowSize];
		int linePos = 0;
		BufferedReader reader = null;
		try {
			String line = null;
			reader = new BufferedReader(new FileReader(fileName));
			while ((line = reader.readLine()) != null) {
				int rowSize = line.length();
				for (int rowPos = 0;rowPos < rowSize; rowPos++) {
					patches[linePos][rowPos] =
						new Patch(linePos, rowPos, line.charAt(rowPos));
				}
				linePos++;
			}
		} catch(IOException e) {
			throw new RuntimeException(e);
		} finally {
			try {
				reader.close();
			} catch (IOException e) {}
		}
		return patches;
	}

	/**
	 * Patchクラスの二次元配列のうち、最大領域を占めるPatchクラスの
	 * 配列のリストを返す。本来であればPatchクラスの配列のみで良いが、
	 * 最大領域が複数存在する(数が一致する)場合を考えリストにしている。
	 *
	 * @param patches
	 * @return
	 */
	private static List<Patch[]> getMaxPatchAreaList(final Patch[][] patches) {
		List<Patch[]> maxPatchAreaList = null;
		int maxPatchAreaCnt = 0;
		int maxLineSize = patches.length;
		for (int linePos = 0; linePos < maxLineSize; linePos++) {
			int maxRowSize = patches[linePos].length;
			for (int rowPos = 0; rowPos < maxRowSize; rowPos++) {
				Patch patch = patches[linePos][rowPos];
				List<Patch> result = new ArrayList<Patch>();
				checkPatchArea(patches, patch, patch.val, result);
				if (maxPatchAreaCnt < result.size()) {
					maxPatchAreaCnt = result.size();
					maxPatchAreaList = new ArrayList<Patch[]>();
					maxPatchAreaList.add(
						result.toArray(new Patch[result.size()]));
				} else if (maxPatchAreaCnt == result.size()) {
					maxPatchAreaList.add(
						result.toArray(new Patch[result.size()]));
				}
			}
		}
		return maxPatchAreaList;
	}

	/**
	 * 指定された領域が対象か否かチェックする。
	 * 対象の場合は上下左右の領域を再帰チェックする。
	 *
	 * @param patches
	 * @param patch
	 * @param val
	 * @param result
	 */
	private static void checkPatchArea(final Patch[][] patches,
			final Patch patch, final char val, final List<Patch> result) {
		if (patch.isDone) return; // すでにチェック済みの領域はスキップ
		if (val != patch.val) return; // 値が一致しない場合はスキップ
		patch.isDone = true;
		result.add(patch);
		if (patch.linePos > 0) { // 上のセル確認
			checkPatchArea(patches,
				patches[patch.linePos - 1][patch.rowPos],
				patch.val, result);
		}
		if (patch.rowPos < patches[patch.linePos].length - 1) { // 右のセルを確認
			checkPatchArea(patches,
				patches[patch.linePos][patch.rowPos + 1],
				patch.val, result);
		}
		if (patch.linePos < patches.length - 1) { // 下のセルを確認
			checkPatchArea(patches,
				patches[patch.linePos + 1][patch.rowPos],
				patch.val, result);
		}
		if (patch.rowPos > 0) { // 左のセルを確認
			checkPatchArea(patches,
				patches[patch.linePos][patch.rowPos - 1],
				patch.val, result);
		}
	}

	/**
	 * 最大領域を占めるPatchクラスの配列のリストの値を指定された文字に置き換える。
	 *
	 * @param maxPatchAreaList
	 */
	private static void replaceVal(List<Patch[]> maxPatchAreaList) {
		for (Patch[] patches : maxPatchAreaList) {
			for (Patch patch : patches) {
				patch.val = REPLACE_CHAR;
			}
		}
	}

	/**
	 * 文字列を置き換えた状態でファイル出力する。
	 *
	 * @param patches
	 * @param fileName
	 */
	private static void outputPatches(final Patch[][] patches,
			final String fileName) {
		String separator = System.getProperty("line.separator");
		BufferedWriter writer = null;
		try {
			writer = new BufferedWriter(new FileWriter(fileName));
			int maxLineSize = patches.length;
			for (int linePos = 0; linePos < maxLineSize; linePos++) {
				int maxRowSize = patches[linePos].length;
				char[] line = new char[maxRowSize];
				for (int rowPos = 0; rowPos < maxRowSize; rowPos++) {
					line[rowPos] = patches[linePos][rowPos].val;
				}
				writer.write(line);
				writer.write(separator);
			}
		} catch(IOException e) {
			e.printStackTrace();
		} finally {
			try {
				writer.close();
			} catch (IOException e) {}
		}
	}

	/**
	 * 置き換えられた文字列をカウントした結果を出力する。
	 *
	 * @param patches
	 * @param fileName
	 */
	private static void outputPatchesCnt(final Patch[][] patches,
			final String fileName) {
		String separator = System.getProperty("line.separator");
		BufferedWriter writer = null;
		try {
			writer = new BufferedWriter(new FileWriter(fileName));
			int maxLineSize = patches.length;
			for (int linePos = 0; linePos < maxLineSize; linePos++) {
				int targetCnt = 0;
				int maxRowSize = patches[linePos].length;
				for (int rowPos = 0; rowPos < maxRowSize; rowPos++) {
					if (patches[linePos][rowPos].val == REPLACE_CHAR) {
						targetCnt++;
					}
				}
				writer.write(Integer.toString(targetCnt));
				writer.write(separator);
			}
		} catch(IOException e) {
			e.printStackTrace();
		} finally {
			try {
				writer.close();
			} catch (IOException e) {}
		}
	}
}

/**
 * パッチを表すクラス
 *
 * @author matsukaz
 */
class Patch {
	public int linePos;
	public int rowPos;
	public boolean isDone = false;
	public char val;
	public Patch(int linePos, int rowPos, char val) {
		this.linePos = linePos;
		this.rowPos = rowPos;
		this.val = val;
	}
}