path: root/src/jrummikub/control/AIUtil.java

package jrummikub.control;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.TreeMap;

import jrummikub.model.GameSettings;
import jrummikub.model.Stone;
import jrummikub.model.StoneColor;
import jrummikub.model.StoneSet;
import jrummikub.util.Pair;

/**
 * A collection of several AI utility methods with given game settings
 * 
 */
public class AIUtil {
	private GameSettings settings;
	private List<StoneColor> stoneColors;

	/**
	 * The utility class's methods calculate their results based on the game
	 * settings
	 * 
	 * @param settings
	 *          the underlying game settings
	 */
	public AIUtil(GameSettings settings) {
		this.settings = settings;

		stoneColors = new ArrayList<StoneColor>(Arrays.asList(StoneColor.values()));
		stoneColors.retainAll(settings.getStoneColors());
	}

	private static class SearchState {
		int pointsMissing;
		TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts;
		int jokerCount;

		SearchState(int pointsMissing,
				TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts, int jokerCount) {
			this.pointsMissing = pointsMissing;
			this.stoneCounts = stoneCounts;
			this.jokerCount = jokerCount;
		}
	}

	@SuppressWarnings("serial")
	private static class EnoughPoints extends Throwable {
		private Pair<List<StoneSet>, Integer> result;

		public EnoughPoints(Pair<List<StoneSet>, Integer> result) {
			this.result = result;
		}

		public Pair<List<StoneSet>, Integer> getResult() {
			return result;
		}
	}

	/**
	 * Tries to find sets with a certain total of points. If only lower totals are
	 * found, returns the sets with the highest cumulated point total.
	 * 
	 * @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 the sets that have the desired point total or the highest found
	 */
	@SuppressWarnings("unchecked")
	public Pair<List<StoneSet>, Integer> findSetsWithTotalPoints(
			int pointsMissing,
			TreeMap<Pair<Integer, StoneColor>, Integer> stoneCounts, int jokerCount) {
		Pair<List<StoneSet>, Integer> emptyResult = new Pair<List<StoneSet>, Integer>(
				Collections.<StoneSet> emptyList(), 0);
		if (pointsMissing <= 0)
			return emptyResult;

		stoneCounts = (TreeMap<Pair<Integer, StoneColor>, Integer>) stoneCounts
				.clone();

		SearchHelper searchHelper = new SearchHelper(
				pointsMissing,
				new Pair<List<StoneSet>, Integer>(Collections.<StoneSet> emptyList(), 0));
		try {
			for (int value = settings.getHighestValue(); value >= 1; value--) {
				for (StoneColor color : stoneColors) {
					Pair<Integer, StoneColor> stone = new Pair<Integer, StoneColor>(
							value, color);

					if (stoneCounts.containsKey(stone)) {
						SearchState searchState = new SearchState(pointsMissing - value,
								stoneCounts, jokerCount);
						decrementStoneCount(stoneCounts, stone);
						searchHelper.checkResult(findRunsWithTotalPoints(searchState,
								stone, 1));

						searchHelper.checkResult(findGroupsWithTotalPoints(searchState,
								value, Collections.singletonList(color), color));
					}

					if (jokerCount > 0) {
						SearchState searchState = new SearchState(pointsMissing - value,
								stoneCounts, jokerCount - 1);
						searchHelper.checkResult(findRunsWithTotalPoints(searchState,
								stone, 1));

						searchHelper.checkResult(findGroupsWithTotalPoints(searchState,
								value, Collections.singletonList(color), color));
					}
				}
			}
		} catch (EnoughPoints enoughPoints) {
			return enoughPoints.getResult();
		}
		return searchHelper.getBestResult();
	}

	private static class SearchHelper {
		Pair<List<StoneSet>, Integer> bestResult;
		int pointsMissing;

		public SearchHelper(int pointsMissing,
				Pair<List<StoneSet>, Integer> bestResult) {
			this.pointsMissing = pointsMissing;
			this.bestResult = bestResult;
		}

		public void checkResult(Pair<List<StoneSet>, Integer> result)
				throws EnoughPoints {
			if (result.getSecond() >= pointsMissing)
				throw new EnoughPoints(result);
			if (result.getSecond() > bestResult.getSecond())
				bestResult = result;
		}

		public Pair<List<StoneSet>, Integer> getBestResult() {
			return bestResult;
		}
	}

	private Pair<List<StoneSet>, Integer> findGroupsWithTotalPoints(
			SearchState searchState, int value, List<StoneColor> chosenColors,
			StoneColor testedColor) {

		StoneColor nextColor = getNextColor(testedColor);
		Pair<Integer, StoneColor> nextStone = new Pair<Integer, StoneColor>(value,
				nextColor);

		SearchHelper searchHelper = new SearchHelper(
				searchState.pointsMissing,
				new Pair<List<StoneSet>, Integer>(Collections.<StoneSet> emptyList(), 0));
		try {
			if (nextColor != null) {
				List<StoneColor> newColors = new ArrayList<StoneColor>(chosenColors);
				newColors.add(nextColor);
				if (searchState.stoneCounts.containsKey(nextStone)) {
					decrementStoneCount(searchState.stoneCounts, nextStone);
					searchHelper.checkResult(findGroupsWithTotalPoints(searchState,
							value, newColors, nextColor));
					incrementStoneCount(searchState.stoneCounts, nextStone);
				}
				if (searchState.jokerCount > 0) {
					searchHelper.checkResult(findGroupsWithTotalPoints(new SearchState(
							searchState.pointsMissing, searchState.stoneCounts,
							searchState.jokerCount - 1), value, newColors, nextColor));
				}
				searchHelper.checkResult(findGroupsWithTotalPoints(searchState, value,
						chosenColors, nextColor));
			}

			if (chosenColors.size() >= 3) {
				searchHelper.checkResult(handleFoundGroup(searchState, value,
						chosenColors));
			}
		} catch (EnoughPoints enoughPoints) {
			return enoughPoints.getResult();
		}
		return searchHelper.getBestResult();
	}

	private Pair<List<StoneSet>, Integer> handleFoundGroup(
			SearchState searchState, int value, List<StoneColor> chosenColors) {
		int groupPoints = chosenColors.size() * value;
		Pair<List<StoneSet>, Integer> result = findSetsWithTotalPoints(
				searchState.pointsMissing - groupPoints, searchState.stoneCounts,
				searchState.jokerCount);
		List<Stone> newStones = new ArrayList<Stone>();
		for (StoneColor color : chosenColors) {
			newStones.add(new Stone(value, color));
		}
		List<StoneSet> newResultList = new ArrayList<StoneSet>(result.getFirst());
		newResultList.add(new StoneSet(newStones));
		result = new Pair<List<StoneSet>, Integer>(newResultList,
				result.getSecond() + groupPoints);
		return result;
	}

	private Pair<List<StoneSet>, Integer> findRunsWithTotalPoints(
			SearchState searchState, Pair<Integer, StoneColor> testedStone,
			int runLength) {

		SearchHelper searchHelper = new SearchHelper(
				searchState.pointsMissing,
				new Pair<List<StoneSet>, Integer>(Collections.<StoneSet> emptyList(), 0));
		try {
			Pair<Integer, StoneColor> nextStone = null;
			if (testedStone.getFirst() > 1) {
				int nextValue = testedStone.getFirst() - 1;
				nextStone = new Pair<Integer, StoneColor>(nextValue,
						testedStone.getSecond());

				if (searchState.stoneCounts.containsKey(nextStone)) {
					decrementStoneCount(searchState.stoneCounts, nextStone);
					searchHelper.checkResult(findRunsWithTotalPoints(searchState,
							nextStone, runLength + 1));
					incrementStoneCount(searchState.stoneCounts, nextStone);

				}
				if (searchState.jokerCount > 0) {
					searchHelper.checkResult(findRunsWithTotalPoints(new SearchState(
							searchState.pointsMissing, searchState.stoneCounts,
							searchState.jokerCount - 1), nextStone, runLength + 1));

				}
			}

			if (runLength >= 3) {
				searchHelper.checkResult(handleFoundRun(searchState, testedStone,
						runLength));
			}
		} catch (EnoughPoints enoughPoints) {
			return enoughPoints.getResult();
		}
		return searchHelper.getBestResult();
	}

	private Pair<List<StoneSet>, Integer> handleFoundRun(SearchState searchState,
			Pair<Integer, StoneColor> testedStone, int runLength) {
		int below = testedStone.getFirst() - 1;
		int high = below + runLength;
		int runPoints = (high * (high + 1)) / 2 - (below * (below + 1)) / 2;

		Pair<List<StoneSet>, Integer> result = findSetsWithTotalPoints(
				searchState.pointsMissing - runPoints, searchState.stoneCounts,
				searchState.jokerCount);

		List<Stone> newStones = new ArrayList<Stone>();
		for (int i = 0; i < runLength; i++) {
			newStones.add(new Stone(i + testedStone.getFirst(), testedStone
					.getSecond()));
		}
		List<StoneSet> newResultList = new ArrayList<StoneSet>(result.getFirst());
		newResultList.add(new StoneSet(newStones));
		result = new Pair<List<StoneSet>, Integer>(newResultList,
				result.getSecond() + runPoints);
		return result;
	}

	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);
		}
	}

	StoneColor getNextColor(StoneColor color) {
		int index = stoneColors.indexOf(color) + 1;
		if (index >= stoneColors.size()) {
			return null;
		}
		return stoneColors.get(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);
	}
}