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

どう書く Java

金曜の夜にどう書くへ行ってきました。

オフラインリアルタイムどう書くとは
皆で共通のお題を好きなプログラミング言語で解いて、結果を見せ合う会です。

今回のお題は、「レッスンは何曜日？」です。

英会話レッスンに受講希望者が応募してくるので、希望の曜日に沿うようにクラス分けをしよう、という問題です。

今回はなりゆきで自分が出題を担当しました。問題を作る時に一度実装していたので、当日はそれをJava 8構文にのんびり書き直すつもりでいました。しかし、問題とあわせて提示したテストデータの一部に誤りがあることが発覚したため、回答時間が検算タイムになってしまいました。（その節はご迷惑をおかけしました……）

会場ではデバッグが終らなかったので、帰宅後に解き直しました＞＜ 簡単ですと言って出題しておいて、まさかの敗北というﾌﾟｷﾞｬｰな結果で残念です。

自分の解答

当日発表したコードを、後から書き直したものです。

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

class Applicant {
	public Applicant(int o, int num, List<Integer> clazz, int c) {
		order = o;
		number = num;
		classes = clazz;
		cursor = c;
	}

	Integer order;
	Integer number;
	List<Integer> classes;
	Integer cursor;

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + number;
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj) {
			return true;
		}
		if (obj != null && getClass() != obj.getClass()
				&& number == ((Applicant) obj).number) {
			return true;
		}
		return false;
	}
}

public class Example {
	private static final int MAX = 4;

	public String solve(String input) {
		Map<Integer, List<Applicant>> resultUnit = new HashMap<>(5);
		List<Applicant> empUnit = getEmpUnit(input);

		for (Applicant emp : empUnit) {
			findClass(resultUnit, emp);
		}
		return format(resultUnit);
	}

	void findClass(Map<Integer, List<Applicant>> resultUnit, Applicant emp) {
		List<Integer> classes = emp.classes;
		while (emp.cursor < classes.size()) {
			Integer clazz = classes.get(emp.cursor++);
			List<Applicant> members = resultUnit.computeIfAbsent(clazz,
					t -> new ArrayList<>());
			if (members.size() < MAX) {
				members.add(emp);
				resultUnit.put(clazz, members);
				return;
			} else {
				List<Applicant> targets = findRemovingTarget(resultUnit, clazz,
						emp);
				if (0 < targets.size()) {
					members.remove(targets.get(0));
					members.add(emp);
					resultUnit.put(clazz, members);
					// 押し出した応募者を代替クラスに割り当てる
					findClass(resultUnit, targets.get(0));
					return;
				}
			}
		}
	}

	// すでに割り当てられたメンバーのうち、自分よりも希望順が低い者を、応募順で後ろから特定する
	List<Applicant> findRemovingTarget(
			Map<Integer, List<Applicant>> resultUnit, Integer clazz,
			Applicant emp) {
		List<Applicant> result = new ArrayList<>();

		List<Applicant> targetList = resultUnit.get(clazz);
		targetList.sort((a1, a2) -> {
			if (Integer.compare(a2.classes.indexOf(clazz),
					a1.classes.indexOf(clazz)) == 0) {
				return a2.order.compareTo(a1.order);
			}
			return Integer.compare(a2.classes.indexOf(clazz),
					a1.classes.indexOf(clazz));
		});
		targetList
				.stream()
				.filter(t -> 0 < t.classes.indexOf(clazz)
						- emp.classes.indexOf(clazz)
						|| t.classes.indexOf(clazz) == emp.classes
								.indexOf(clazz) && emp.order < t.order)
				.forEach(t -> result.add(t));
		return result;
	}

	String format(Map<Integer, List<Applicant>> input) {
		if (input.size() == 0) {
			return "-";
		}
		List<String> result = new ArrayList<>();
		for (Integer clazz : input.keySet()) {
			List<Applicant> empList = input.get(clazz);
			empList.sort((a1, a2) -> a1.number.compareTo(a2.number));
			List<String> apps = empList.stream()
					.map(t -> String.valueOf(t.number))
					.collect(Collectors.toList());
			result.add(String.valueOf(clazz) + "_" + String.join(":", apps));
		}
		return String.join("|", result);
	}

	List<Applicant> getEmpUnit(String input) {
		return IntStream.range(0, input.split("\\|").length).boxed()
				.map(t -> createApplicant(input.split("\\|")[t], t))
				.collect(Collectors.toList());
	}

	Applicant createApplicant(String input, int index) {
		return new Applicant(index, Integer.valueOf(input.split("_")[0]),
				parseClass(input.split("_")[1]), 0);
	}

	List<Integer> parseClass(String pattern) {
		return pattern.chars().mapToObj(c -> (char) c)
				.map(c -> Integer.valueOf(String.valueOf(c)))
				.collect(Collectors.toList());
	}
}

どう書くの解答では珍しく、状態を持つクラスを使ってしまいました。べつに悪くはないですが、大げさかもしれません。

考え方

応募者の希望する曜日を順に調べて、クラス（曜日）をKey、応募者のリストをValueとして持つMapに、空きがあれば割り振っていきます。

空きがないときは、すでに割り振られているメンバーを走査して、

  • 自分よりその曜日の希望順位が低い応募者
  • 希望順位は同じだが自分より応募順が遅かった応募者

を探します。もし存在すれば、その応募者を押し出して、自分が納まります。

押し出された応募者に対しては、納まる場所を再発見するか、どこにも納まれないことが判明するまで、同じ処理を再帰で適用します。

バグが入り込んだ箇所

テストデータに間違いを仕込んだ原因は、押し出す応募者を選ぶ処理にバグがあったためでした。

ある曜日に納まった応募者のリストには、かならずしも応募順に応募者が入っているわけではありません。そのことを失念していたため、単純に末尾から走査していました。

# 複数キーでのソートをlambda式で初めて書いたので、勉強になりました。

悩み（だれか教えてください）

上のコードでは、Java 8のストリームAPIを使っているのに、外側のデータにアクセスしている箇所がいくつかあります。

その1

parseClassメソッドでは上手くいきましたが、たとえば、formatメソッドがダメです。

formatメソッドに次の記述があります。

		List<String> result = new ArrayList<>();
		for (Integer clazz : input.keySet()) {
			List<Applicant> empList = input.get(clazz);
			empList.sort((a1, a2) -> a1.number.compareTo(a2.number));
			List<String> apps = empList.stream()
					.map(t -> String.valueOf(t.number))
					.collect(Collectors.toList());
			result.add(String.valueOf(clazz) + "_" + String.join(":", apps));
		}

List resultに、forの中から触っているのがダメダメだという話です。

とはいえ、Mapでデータを持っているので、値を走査するには、KeyかValueでイテレートするしかありません。どちらかでイテレートすれば、処理中にもう一方に触るためには、どうしても外側の値にアクセスしてしまうと思います（何か良い書き方があるなら知りたいです）。データの持ち方から変更すべきなのかもしれません。

その2

さらに、getEmpUnitメソッドの書き方もよくないです。本来は、引数で受け取った文字列を起点に処理を開始するのがよいのだと思いますが、内部で連番を使いたいがために、IntStreamから開始しています。

上のコードでは、1行で書くために（splitの実行回数には目をつぶって）次のように書いています。

	List<Applicant> getEmpUnit(String input) {
		return IntStream.range(0, input.split("\\|").length).boxed()
				.map(t -> createApplicant(input.split("\\|")[t], t))
				.collect(Collectors.toList());
	}

要は次の内容と同じことがしたいわけです。

	List<Applicant> getEmpUnit(String input) {
		String[] split = input.split("\\|");
		return IntStream.range(0, split.length).boxed()
				.map(t -> createApplicant(split[t], t))
				.collect(Collectors.toList());
	}

rangeやmapの中から、外にあるString[] splitに触らないような書き方に直したいわけですが、どうすればいいのか分かりません。2つのStreamを組み合わせる処理が書けてないという認識です。

問題作成について

問題を作る作業は、とても勉強になりました。いつも解いている鍋谷さんの問題が、いかにクォリティが高いかを実感しました。でも、鍋谷さんが「解く側で参加するのって面白いですね！」とおっしゃっていたので、問題作ってよかったなあと思いましたｗ

内容については、（安定マッチング問題の1つである）安定結婚問題の亜種を目指したつもりでしたが、解法が収束してしまうのが難でした。もちろん、テストデータのミスが最大の反省点ですが……。反省点や分かったことについては、せっかくなので、あとで別途まとめたいと思います。

貴重な機会をいただきありがとうございました。回答してくださった皆さん、お付き合いいただきありがとうございました m(_ _)m

追記

コメントいただきました。どうもありがとうございます。

データの持ち方について（from: まこたんさん）

データの持ち方がこれだと実装しにくくない？ 自分がやるんなら map<曜日,map<希望順,list<ユーザ情報>>>ってやって希望順に"決定済みユーザ"以外を集めるだけにするなぁ〜

実装しにくかったです。当日こんな解き方をしていたのは自分だけでした。その方法で書いてみます。

ストリーム＝パラレル処理ではない（from: さくらばさん）

@torazuka ストリームで書くことと、パラレルで処理できるかどうかを同じレベルで考えない方がいいですよ。ストリームで効率的に書ければいいのではないでしょうか。パラレルで書くとしたら、もっと考え方を変えないとダメだと思います。

https://twitter.com/skrb/status/465464498724536320

ストリームで書けばすべてがすべてパラレルになるかというとそんなことはなくて、パラレルにできるのはごくごく一部だけにすぎないということを、最近身をもって感じています。

https://twitter.com/skrb/status/465466144338743296

ストリームを使うからといって、かならずしも並列化可能な形で書く必要はないんですね。誤解していました。

ストリームをきれいに使った書き方（from: うらがみさん）

まさにこういう風に書きたいです。参考にします。

Mapの走査とStreamの混成について（from: しえるさん）

- for (Integer clazz : input.keySet())
+ for (Map.Entry> clazz_and_emplist : input.entrySet())
で良いと思います。
あと、2つのStreamを混成するには、AtomicIntegerかStream.iterate(...).iterator()を使うと良いです。
# 前はzipがあったのですがね…。

http://qiita.com/torazuka/items/cbdb6b581a57e4754dd4#comment-9f4d5560b5f549c9d115

どちらも思いつきませんでした。試してみます。