「第19回オフラインリアルタイムどう書く」のへなちょこ解答(Java)

7日の金曜日、どう書くへ行ってきました。

オフラインリアルタイムどう書くとは
鍋谷さんが出してくださるお題を、参加者が好きなプログラミング言語で解いて楽しむ会です。

今回は、「不良セクタの隣」です!

デスクを模した画像がインパクトありますね。広場の円形タイルみたいです。

不良セクタの番号が、入力として与えられます。このとき、2つ以上の不良セクタに隣接するセクタ(保留セクタ)を出力せよ、というのがお題です。問題の詳細は、上のページでご確認ください。

当日はいつも通りJavaで挑んだのですが、残念ながら回答途中で時間切れになってしまいました。週末に最後まで解いたので、解答を載せておきます。

自分の解答

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Nebasec {

	public String solve(String input) {
		List<Integer> defects = parse(input);
		Set<Integer> reservedSet = new HashSet<>();
		List<Integer> result = new ArrayList<>();
		for (Integer defect : defects) {
			List<Integer> tmp = getReserved(defect);
			for (Integer reserved : tmp) {
				if (reservedSet.add(reserved) == false
						&& result.contains(reserved) == false) {
					result.add(reserved);
				}
			}
		}
		for (Integer defect : defects) {
			if (result.contains(defect)) {
				result.remove(defect);
			}
		}
		Collections.sort(result);
		return format(result);
	}

	List<Integer> parse(String input) {
		String[] split = input.split(",");
		List<String> tmp = Arrays.asList(split);
		List<Integer> result = new ArrayList<>();
		for (String string : tmp) {
			result.add(Integer.valueOf(string));
		}
		return result;
	}

	List<Integer> getReserved(Integer sec) {
		List<Integer> result = new ArrayList<>();
		result.add(getNext(sec));
		result.add(getPrev(sec));

		int n = sec / 100;
		if (n == 1) {
			int mod = sec % 100 * 2;
			result.add(200 + mod);
			result.add(getPrev(200 + mod));
			result.add(getNext(200 + mod));
		} else if (n == 2) {
			if (sec % 2 == 0) { // 200台の偶数
				int mod = sec % 200 / 2;
				result.add(100 + mod);
				result.add(300 + mod * 3);
				result.add(getPrev(300 + mod * 3));
				result.add(getNext(300 + mod * 3));
			} else {
				int div = (sec - 200) / 2;
				result.add(100 + div);
				result.add(getNext(100 + div));
				result.add(300 + div * 3 + 1);
				result.add(getNext(300 + div * 3 + 1));
			}
		} else if (n == 3) {
			if (sec % 3 == 0) { // 300台の3の倍数
				int div = (sec - 300) / 3;
				result.add(200 + div * 2);
				result.add(400 + div * 4);
				result.add(getPrev(400 + div * 4));
				result.add(getNext(400 + div * 4));
			} else {
				int div = (sec - 300) / 3;
				int mod = (sec - 300) % 3;
				result.add(200 + div * 2 + mod - 1);
				result.add(getNext(200 + div * 2 + mod - 1));
				result.add(400 + div * 4 + mod);
				result.add(getNext(400 + div * 4 + mod));
			}
		} else if (n == 4) {
			if (sec % 4 == 0) { // 400台の4の倍数
				int div = (sec - 400) / 4;
				result.add(300 + div * 3);
			} else {
				int div = (sec - 400) / 4;
				int mod = (sec - 400) % 4;
				result.add(300 + div * 3 + mod - 1);
				result.add(getNext(300 + div * 3 + mod - 1));
			}
		}
		return result;
	}

	int getNext(int n) {
		if (n == 107) {
			return 100;
		}
		if (n == 215) {
			return 200;
		}
		if (n == 323) {
			return 300;
		}
		if (n == 431) {
			return 400;
		}
		return n + 1;
	}

	int getPrev(int n) {
		if (n == 100) {
			return 107;
		}
		if (n == 200) {
			return 215;
		}
		if (n == 300) {
			return 323;
		}
		if (n == 400) {
			return 431;
		}
		return n - 1;
	}

	String format(List<Integer> result) {
		if (result.isEmpty()) {
			return "none";
		}
		StringBuilder sb = new StringBuilder();
		for (Integer integer : result) {
			sb.append(String.valueOf(integer));
			sb.append(",");
		}
		return sb.toString().substring(0, sb.length() - 1);
	}
}

考え方

処理の概要はsolveメソッドで、こんなかんじです。

  1. 入力文字列をカンマで分けて、IntegerのListにする。これが、不良セクタのリスト。
  2. 不良セクタのリストを1つずつ調べる。
    1. getReservedメソッドで、隣接するセクタ群をIntegerのListに取る。これが、保留セクタの候補リスト。
    2. 保留セクタの候補リストを1つずつ調べる。
      1. HashSetへの追加を試みる。同じ値がすでに登録されている場合、falseが返ってくるので、不良セクタの隣接セクタとして2度以上検出されたとみなし、解答のリストに加える。
      2. ただし、解答のリストにすでに追加されている場合は、無視。
  3. 不良セクタのリストにある値を、解答のリストから除去する。
    • 問題に明記されていませんでしたが、保留セクタとして検出されたセクタが不良セクタでもある場合は、保留セクタとして扱わないという制約があるため。(この制約を確認するために、gistのコードにはテストデータを1つ足しました)
Setについて

Setに追加できないことをもって重複を検出するのは、Setの便利な使い方ですよね。

しかし、重複が検出されたものを集めるCollectionにもまた、重複を許してはいけないという制約があるのに、Listを使ってしまっています。そのため、最後にフィルタリングが必要になりました。

改善するならこの部分だと思います。TreeSetとか使えばよいのかもしれません。

戦略

隣接するパターンを式で表わす戦略にしました。

不良セクタが100台のとき、隣接するセクタは1パターンです。

次の図は、101が不良セクタの場合の例です。

不良セクタが200台のとき、2の倍数とそうでないときで、隣接するセクタは2パターンあります。

次の図は、202(2の倍数)と207(2の倍数でない数)が不良セクタの場合の例です。

不良セクタが300台のとき、3の倍数とそうでないときで、隣接するセクタは2パターンあります。

次の図は、303(3の倍数)と310(3の倍数でない数)が不良セクタの場合の例です。

不良セクタが400台のとき、4の倍数とそうでないときで、隣接するセクタは2パターンあります。

次の図は、404(4の倍数)と413(4の倍数でない数)が不良セクタの場合の例です。

このパターンを式にしたのが、getReservedメソッドの中身です。もうちょっとパターン化して書ける気がしますが、こういうの苦手で……(ゴニョゴニョ)。当日は、400台を書いているあたりで時間切れになりました。悔しい!

数字のリングについて

リング状になった数列を辿るイディオムが知りたいです。

問題では、107の次が100に、215の次が200に、323の次が300に、431の次が400になっています。これを上手く前に辿ったり後ろに辿ったりする書き方のことです。

今回は4箇所だったので、getNextメソッドとgetPrevメソッドの中に、値を直書きしてしまいました。

追記(2014/03/12) 教えていただきました。 リング状の数列を辿る

というわけで

しばらく広場のタイルを見たくない気分ですが、今回も楽しかったです。ありがとうございました。