From d25a73167cd13a7da0cce97414455c210437ae2e Mon Sep 17 00:00:00 2001
From: Bennet Gerlach <bennet_gerlach@web.de>
Date: Mon, 30 May 2011 21:01:48 +0200
Subject: Extracted a AIUtil class from several hand methods

git-svn-id: svn://sunsvr01.isp.uni-luebeck.de/swproj13/trunk@330 72836036-5685-4462-b002-a69064685172
---
 src/jrummikub/control/AIUtil.java | 208 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 208 insertions(+)
 create mode 100644 src/jrummikub/control/AIUtil.java

(limited to 'src/jrummikub/control')

diff --git a/src/jrummikub/control/AIUtil.java b/src/jrummikub/control/AIUtil.java
new file mode 100644
index 0000000..66a3442
--- /dev/null
+++ b/src/jrummikub/control/AIUtil.java
@@ -0,0 +1,208 @@
+package jrummikub.control;
+
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+import java.util.TreeMap;
+
+import jrummikub.model.Stone;
+import jrummikub.model.StoneColor;
+import jrummikub.util.Pair;
+
+/**
+ * A collection of several AI utility methods
+ * 
+ */
+public class AIUtil {
+
+	private AIUtil() {
+	}
+
+	/**
+	 * Finds sets with a certain total of points
+	 * 
+	 * @param pointsMissing
+	 *          the desired number of points
+	 * @param stoneCounts
+	 *          the number of each stone
+	 * @param jokerCount
+	 *          the total number of jokers in the game
+	 * @return whether such sets exist
+	 */
+	@SuppressWarnings("unchecked")
+	public static boolean findSetsWithTotalPoints(int pointsMissing,
+			TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts, int jokerCount) {
+
+		if (pointsMissing <= 0) {
+			return true;
+		}
+
+		stoneCounts = (TreeMap<Pair<Integer, StoneColor>, Integer>) stoneCounts
+				.clone();
+
+		for (int value = 13; value >= 1; value--) {
+			for (StoneColor color : StoneColor.values()) {
+				Pair<Integer, StoneColor> stone = new Pair<Integer, StoneColor>(value,
+						color);
+
+				if (stoneCounts.containsKey(stone)) {
+					decrementStoneCount(stoneCounts, stone);
+
+					if (findRunsWithTotalPoints(pointsMissing - value, stoneCounts,
+							jokerCount, stone, 1))
+						return true;
+					if (findGroupsWithTotalPoints(pointsMissing - value, stoneCounts,
+							jokerCount, stone, 1))
+						return true;
+				}
+
+				if (jokerCount > 0) {
+					if (findRunsWithTotalPoints(pointsMissing - value, stoneCounts,
+							jokerCount - 1, stone, 1))
+						return true;
+					if (findGroupsWithTotalPoints(pointsMissing - value, stoneCounts,
+							jokerCount - 1, stone, 1))
+						return true;
+				}
+			}
+		}
+
+		return false;
+	}
+
+	static boolean findGroupsWithTotalPoints(int pointsMissing,
+			TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts, int jokerCount,
+			Pair<Integer, StoneColor> stone, int groupSize) {
+
+		StoneColor nextColor = getNextColor(stone.getSecond());
+		Pair<Integer, StoneColor> nextStone = new Pair<Integer, StoneColor>(
+				stone.getFirst(), nextColor);
+
+		if (nextColor != null) {
+			if (stoneCounts.containsKey(nextStone)) {
+				decrementStoneCount(stoneCounts, nextStone);
+				if (findGroupsWithTotalPoints(pointsMissing - stone.getFirst(),
+						stoneCounts, jokerCount, nextStone, groupSize + 1))
+					return true;
+				incrementStoneCount(stoneCounts, nextStone);
+			}
+			if (jokerCount > 0) {
+				if (findGroupsWithTotalPoints(pointsMissing - stone.getFirst(),
+						stoneCounts, jokerCount - 1, nextStone, groupSize + 1))
+					return true;
+			}
+			if (findGroupsWithTotalPoints(pointsMissing, stoneCounts, jokerCount,
+					nextStone, groupSize))
+				return true;
+		}
+
+		if (groupSize >= 3) {
+			if (findSetsWithTotalPoints(pointsMissing, stoneCounts, jokerCount))
+				return true;
+		}
+		return false;
+	}
+
+	static boolean findRunsWithTotalPoints(int pointsMissing,
+			TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts, int jokerCount,
+			Pair<Integer, StoneColor> stone, int runLength) {
+
+		Pair<Integer, StoneColor> nextStone = null;
+		if (stone.getFirst() > 1) {
+			int nextValue = stone.getFirst() - 1;
+			nextStone = new Pair<Integer, StoneColor>(nextValue, stone.getSecond());
+
+			if (stoneCounts.containsKey(nextStone)) {
+				decrementStoneCount(stoneCounts, nextStone);
+				if (findRunsWithTotalPoints(pointsMissing - nextValue, stoneCounts,
+						jokerCount, nextStone, runLength + 1))
+					return true;
+				incrementStoneCount(stoneCounts, nextStone);
+
+			}
+			if (jokerCount > 0) {
+				if (findRunsWithTotalPoints(pointsMissing - nextValue, stoneCounts,
+						jokerCount - 1, nextStone, runLength + 1))
+					return true;
+			}
+		}
+
+		if (runLength >= 3) {
+			if (findSetsWithTotalPoints(pointsMissing, stoneCounts, jokerCount))
+				return true;
+		}
+		return false;
+	}
+
+	static void incrementStoneCount(
+			TreeMap<Pair<Integer, StoneColor>, Integer> stones,
+			Pair<Integer, StoneColor> stone) {
+		if (stones.containsKey(stone)) {
+			stones.put(stone, stones.get(stone) + 1);
+		} else {
+			stones.put(stone, 1);
+		}
+	}
+
+	static void decrementStoneCount(
+			TreeMap<Pair<Integer, StoneColor>, Integer> stones,
+			Pair<Integer, StoneColor> stone) {
+		int count = stones.get(stone);
+		count--;
+
+		if (count == 0) {
+			stones.remove(stone);
+		} else {
+			stones.put(stone, count);
+		}
+	}
+
+	static StoneColor getNextColor(StoneColor color) {
+		int index = Arrays.binarySearch(StoneColor.values(), color) + 1;
+		if (index >= StoneColor.values().length) {
+			return null;
+		}
+		return StoneColor.values()[index];
+	}
+
+	private final static Comparator<Pair<Integer, StoneColor>> comparator = new Comparator<Pair<Integer, StoneColor>>() {
+
+		@Override
+		public int compare(Pair<Integer, StoneColor> o1,
+				Pair<Integer, StoneColor> o2) {
+			int firstComparison = o1.getFirst().compareTo(o2.getFirst());
+			if (firstComparison != 0) {
+				return -firstComparison;
+			} else {
+				return o1.getSecond().compareTo(o2.getSecond());
+			}
+		}
+	};
+
+	/**
+	 * Counts the numbers of stones
+	 * 
+	 * @param stones
+	 *          the stones to count
+	 * @return the numbers for all stones
+	 */
+	public static Pair<TreeMap<Pair<Integer, StoneColor>, Integer>, Integer> countStones(
+			List<Stone> stones) {
+		int jokerCount = 0;
+		TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts = new TreeMap<Pair<Integer, StoneColor>, Integer>(
+				comparator);
+
+		for (Stone stone : stones) {
+			if (stone.isJoker()) {
+				jokerCount++;
+			} else {
+				Pair<Integer, StoneColor> key = new Pair<Integer, StoneColor>(
+						stone.getValue(), stone.getColor());
+
+				incrementStoneCount(stoneCounts, key);
+			}
+		}
+		return new Pair<TreeMap<Pair<Integer, StoneColor>, Integer>, Integer>(
+				stoneCounts, jokerCount);
+	}
+}
-- 
cgit v1.2.3