第五回オフラインリアルタイムどう書く の解答（Java）

Dahimi.java

import static org.junit.Assert.assertEquals;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.junit.Test;

class Card implements Comparable<Card> {
	String suit;
	String rank;

	Card(char s, char r) {
		suit = String.valueOf(s);
		rank = String.valueOf(r);
	}

	public boolean isStrong(int rank) {
		int n = this.convertRank();
		if (rank < n) {
			return true;
		}
		return false;
	}

	@Override
	public String toString() {
		return suit + rank;
	}

	public int convertRank() {
		if (rank.equals("T")) {
			return 10;
		}
		if (rank.equals("J")) {
			return 11;
		}
		if (rank.equals("Q")) {
			return 12;
		}
		if (rank.equals("K")) {
			return 13;
		}
		if (rank.equals("A")) {
			return 14;
		}
		if (rank.equals("2")) {
			return 15;
		}
		if (rank.equals("o")) {
			return 16;
		}
		return Integer.valueOf(rank);
	}

	@Override
	public int compareTo(Card o) {
		int n = this.convertRank();
		int m = o.convertRank();
		if (m < n) {
			return 1;
		}
		if (n < m) {
			return -1;
		}
		return 0;
	}

	@Override
	public boolean equals(Object obj) {
		if (obj instanceof Card) {
			Card c = (Card) obj;
			if (rank.equals(c.rank) && suit.equals(c.suit)) {
				return true;
			}
		}
		return false;
	}
}

/**
 * 問題: http://nabetani.sakura.ne.jp/hena/ord5dahimi/
 */
public class Dahimi {

	protected String solve(String input) {
		String[] split = input.split(",");
		if (split.length < 2) {
			return "-";
		}
		List<Card> spaceList = getCards(split[0]);
		List<Card> hand = getCards(split[1]);
		int spaceNum = spaceList.size();
		int spaceRank = getMinRank(spaceList).convertRank();

		Map<Integer, List<String>> available = getAvailable(spaceRank,
				spaceNum, hand);
		if (0 == available.size()) {
			return "-";
		}
		return createResult(available, spaceNum);
	}

	protected Card getMinRank(List<Card> space) {
		if (hasJoker(space)) {
			if (space.size() == 1) {
				return new Card('J', 'o');
			}
			space.remove(new Card('J', 'o'));
		}
		return Collections.min(space);
	}

	// ランクごとにコンビネーションを作成する
	protected String createResult(Map<Integer, List<String>> available, int num) {
		StringBuilder result = new StringBuilder();
		Set<Integer> rankSet = available.keySet();
		Iterator<Integer> ite = rankSet.iterator();
		for (; ite.hasNext();) {
			List<String> list = available.get(ite.next());
			result.append(createCombination(list, num));
			result.append(",");
		}
		return new String(result).substring(0, result.length() - 1);
	}

	protected String createCombination(List<String> list, int target) {
		StringBuilder result = new StringBuilder();

		List<String> loop = loop(list, target);
		for (String cards : loop) {
			result.append(cards);
			result.append(',');
		}
		return new String(result).substring(0, result.length() - 1);
	}

	// c.f. http://d.hatena.ne.jp/ibaza/20080303/1204476552
	protected List<String> loop(List<String> list, int r) {
		List<String> result = new ArrayList<>();
		int n = list.size();

		// n = r のとき、選び方は1つなので、リストをそのまま1つのリストにして返す
		if (n == r) {
			StringBuilder sb = new StringBuilder();
			for (String card : list) {
				sb.append(card);
			}
			result.add(new String(sb));
			return result;
		}

		// r = 1 のとき、選び方はn通りあるので、リストの要素をそれぞれリストにして返す
		if (r == 1) {
			for (String card : list) {
				result.add(card);
			}
			return result;
		}

		// r = 0 または r がリストの要素数より大きいとき、空リストを返す
		if (r == 0 || n < r) {
			return result;
		}

		// 「リストの先頭要素を除いたリストからr-1個を選ぶ組合せのそれぞれに先頭要素を加えたもの
		// と、 リストの先頭要素を除いたリストからr個を選ぶ組合せ」の合計
		List<String> paraList = new ArrayList<>(list);
		String removed = paraList.remove(0);
		List<String> looped = loop(paraList, r - 1);
		for (int i = 0; i < looped.size(); i++) {
			String str = looped.get(i);
			looped.set(i, str + removed);
		}
		List<String> looped2 = loop(paraList, r);
		for (String card : looped2) {
			looped.add(card);
		}
		return looped;
	}

	protected Map<Integer, List<String>> getAvailable(int spaceRank,
			int spaceNum, List<Card> hand) {
		Map<Integer, List<String>> result = new HashMap<>();

		// ワイルドカードとして使わないJokerを持っていたら捨てる
		boolean hasWildcard = hasJoker(hand) && 1 < spaceNum;
		if (hasWildcard == false) {
			hand.remove(new Card('J', 'o'));
		}

		for (Card card : hand) {
			if (card.isStrong(spaceRank) && card.convertRank() != 16) {
				List<String> list = result.get(card.convertRank());
				if (list == null) {
					list = new ArrayList<>();
				}
				list.add(card.toString());
				result.put(card.convertRank(), list);
			}
		}

		// ワイルドカードとしてJokerを使う
		if (hasWildcard) {
			addWildcard(result);
		}

		// 場札の枚数よりも少ないとき、削除
		Set<Integer> keySet = result.keySet();
		List<Integer> removeIdx = new ArrayList<>();
		for (Integer integer : keySet) {
			List<String> list = result.get(integer);
			if (list.size() < spaceNum) {
				removeIdx.add(integer);
			}
		}
		for (Integer integer : removeIdx) {
			result.remove(integer);
		}
		return result;
	}

	protected void addWildcard(Map<Integer, List<String>> result) {
		Set<Integer> keySet = result.keySet();
		for (Integer integer : keySet) {
			List<String> tmpList = result.get(integer);
			tmpList.add(new Card('J', 'o').toString());
			result.put(integer, tmpList);
		}
	}

	protected boolean hasJoker(List<Card> hand) {
		return 0 < Collections.frequency(hand, new Card('J', 'o')) ? true
				: false;
	}

	protected List<Card> getCards(String hand) {
		List<Card> result = new ArrayList<>();
		for (int i = 0; i < hand.length(); i += 2) {
			Card c = new Card(hand.charAt(i), hand.charAt(i + 1));
			result.add(c);
		}
		return result;
	}

	public static void main(String[] args) {
		Dahimi dahimi = new Dahimi();
		System.out.println(dahimi.solve("JoC8,H6D7C5S9CQH9STDTCAD9S5DAS2CT"));
	}

	// テストのための処理。解答や期待値の文字列をソートする
	protected String answerSort(String string) {
		String result = "";
		String[] split = string.split(",");
		if (split.length == 0) {
			// カンマがない場合は'-'、あるいは1枚だけ
			return string;
		}

		List<String> tmpOuter = new ArrayList<>();
		int innerUnit = split[0].length() / 2;
		for (String str : split) {
			List<String> tmpInner = new ArrayList<>();
			for (int i = 0; i < innerUnit * 2; i += 2) {
				String s = new Card(str.charAt(i), str.charAt(i + 1))
						.toString();
				tmpInner.add(s);
			}
			Collections.sort(tmpInner);
			StringBuilder inner = new StringBuilder();
			for (String s : tmpInner) {
				inner.append(s);
			}
			tmpOuter.add(new String(inner));
		}

		Collections.sort(tmpOuter);
		Iterator<String> ite = tmpOuter.iterator();
		if (ite.hasNext()) {
			result += ite.next() + ",";
		}
		return result.substring(result.length() - 1);
	}

	protected void test(String problem, String expect) {
		String expectSort = answerSort(expect);

		Dahimi dahimi = new Dahimi();
		String answer = dahimi.solve(problem);
		String answerStr = answerSort(answer);

		assertEquals(expectSort, answerStr);
	}

	@Test
	public void testSolve() throws Exception {
		/* #1 */test("DJ,", "-");
		/* #2 */test("H7,HK", "HK");
		/* #3 */test("S3,D4D2", "D4,D2");
		/* #4 */test("S9,C8H4", "-");
		/* #5 */test("S6,S7STCK", "CK,ST,S7");
		/* #6 */test("H4,SAS8CKH6S4", "S8,CK,H6,SA");
		/* #7 */test("ST,D6S8JoC7HQHAC2CK", "Jo,C2,CK,HA,HQ");
		/* #8 */test("SA,HAD6S8S6D3C4H2C5D4CKHQS7D5", "H2");
		/* #9 */test("S2,D8C9D6HQS7H4C6DTS5S6C7HAD4SQ", "-");
		/* #10 */test("Jo,HAC8DJSJDTH2", "-");
		/* #11 */test("S4Jo,CQS6C9DQH9S2D6S3", "DQCQ,D6S6,H9C9");
		/* #12 */test("CTDT,S9C2D9D3JoC6DASJS4", "JoC2,SJJo,DAJo");
		/* #13 */test("H3D3,DQS2D6H9HAHTD7S6S7Jo",
				"JoHA,JoD6,JoH9,D6S6,D7S7,JoS6,HTJo,JoDQ,S2Jo,JoD7,JoS7");
		/* #14 */test("D5Jo,CQDAH8C6C9DQH7S2SJCKH5", "CQDQ");
		/* #15 */test("C7H7,S7CTH8D5HACQS8JoD6SJS5H4",
				"HAJo,JoSJ,H8S8,H8Jo,CQJo,CTJo,JoS8");
		/* #16 */test("SAHA,S7SKCTS3H9DJHJH7S5H2DKDQS4", "-");
		/* #17 */test("JoC8,H6D7C5S9CQH9STDTCAD9S5DAS2CT",
				"CTDT,H9D9,S9D9,DACA,CTST,H9S9,DTST");
		/* #18 */test("HTST,SJHJDJCJJoS3D2",
				"DJCJ,SJDJ,JoHJ,CJHJ,SJJo,HJSJ,DJJo,JoCJ,JoD2,SJCJ,DJHJ");
		/* #19 */test("C7D7,S8D8JoCTDTD4CJ",
				"D8S8,JoS8,CTJo,DTJo,JoCJ,CTDT,D8Jo");
		/* #20 */test("DJSJ,DTDKDQHQJoC2", "JoDK,HQDQ,DQJo,C2Jo,JoHQ");
		/* #21 */test("C3H3D3,CKH2DTD5H6S4CJS5C6H5S9CA", "S5H5D5");
		/* #22 */test("D8H8S8,CQHJCJJoHQ", "JoCQHQ,JoHJCJ");
		/* #23 */test("H6D6S6,H8S8D8C8JoD2H2",
				"D2H2Jo,D8JoS8,D8S8C8,C8D8H8,JoC8S8,H8JoC8,S8H8C8,JoS8H8,C8JoD8,D8H8S8,D8JoH8");
		/* #24 */test("JoD4H4,D3H3S3C3CADASAD2", "DACASA");
		/* #25 */test("DJHJSJ,SQDQJoHQCQC2CA",
				"SQJoCQ,DQCQJo,JoSQHQ,SQCQHQ,DQHQSQ,HQDQCQ,HQDQJo,SQDQCQ,CQJoHQ,SQJoDQ");
		/* #26 */test("H3D3Jo,D4SKH6CTS8SAS2CQH4HAC5DADKD9", "HASADA");
		/* #27 */test("C3JoH3D3,S2S3H7HQCACTC2CKC6S7H5C7", "-");
		/* #28 */test("H5C5S5D5,C7S6D6C3H7HAH6H4C6HQC9", "C6D6S6H6");
		/* #29 */test("H7S7C7D7,S5SAH5HAD5DAC5CA", "SADACAHA");
		/* #30 */test(
				"D4H4S4C4,S6SAH6HAD6DAC6CAJo",
				"C6H6S6D6,SAJoDACA,S6H6C6Jo,SACAJoHA,HADASAJo,HADAJoCA,CADAHASA,D6C6JoH6,S6D6C6Jo,H6JoS6D6");
		/* #31 */test("DTCTSTHT,S3SQH3HQD3DQC3CQJo",
				"HQSQJoDQ,SQCQDQJo,DQCQHQJo,SQHQJoCQ,CQDQHQSQ");
		/* #32 */test("JoS8D8H8,S9DTH9CTD9STC9CAC2", "H9C9D9S9");
	}
}