Skip to content

Instantly share code, notes, and snippets.

@gotcake
Created April 17, 2020 19:03
Show Gist options
  • Save gotcake/5784e92888f6d9df6b7f9d2e979b23a5 to your computer and use it in GitHub Desktop.
Save gotcake/5784e92888f6d9df6b7f9d2e979b23a5 to your computer and use it in GitHub Desktop.
Non-optimal solution for LeetCode Cat and Mouse problem
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Objects;
import java.util.Stack;
import java.util.stream.IntStream;
class Solution {
static boolean DEBUG = false;
static final int POSITION_HOLE = 0;
static final int POSITION_MOUSE_START = 1;
static final int POSITION_CAT_START = 2;
static final int MOUSE_WIN = 1;
static final int CAT_WIN = 2;
static final int DRAW = 0;
int catMouseGame(int[][] graph) {
// check graph validity
// (mostly to validate our assumptions about the graph that are left un-clarified)
for (int[] moves: graph) {
// each node must have a path out
assert moves.length > 0;
// there may not be any duplicate values
final HashSet<Integer> options = IntStream.of(moves)
.collect(HashSet::new, HashSet::add, HashSet::addAll);
assert options.size() == moves.length;
}
return getResult(
new State(true, POSITION_MOUSE_START, POSITION_CAT_START),
new Stack<>(),
graph,
new HashMap<>()
);
}
/**
* Caches known win results for getResultHelper().
* We cannot cache DRAW results because the DRAW test depends on the
* ancestors when a given state is seen, which can be different each time we see the same
* state.
*/
static int getResult(
final State state,
final Stack<State> previousStates,
final int[][] graph,
final Map<State, Integer> resultsCache
) {
final Integer cachedResult = resultsCache.get(state);
if (cachedResult != null) {
print(previousStates.size(), "[cache] %s => %d", state, cachedResult);
return cachedResult;
}
print(previousStates.size(), "[compute] %s", state);
final int result = getResultHelper(state, previousStates, graph, resultsCache);
print(previousStates.size() + 1, "=> %d", result);
// NOTE: If we allow caching of DRAW results (which would be incorrect)
// we get 44/49 test cases. The remaining 5 test cases most likely trigger the condition where
// it would incorrrectly report a DRAW where the ancestors for a given state are different than the
// ancestors when state which resulted in the cached DRAW.
// I've verified not caching DRAW results in the correct solution for at least 1 of those
// test cases, so I'm fairly certain this solution is now correct, just inefficient.
if (result != DRAW) {
resultsCache.put(state, result);
}
return result;
}
/**
* Recursively checks each possible move path from the given state, determining the
* result for each possible sub-path (DRAW, MOUSE_WIN, or CAT_WIN), and rolling the
* result back up the tree.
*/
static int getResultHelper(
final State state,
final Stack<State> previousStates,
final int[][] graph,
final Map<State, Integer> resultsCache
) {
// check base cases
if (state.isMouseAtHole()) {
return MOUSE_WIN;
} else if (state.isMouseCaughtByCat()) {
return CAT_WIN;
} else if (state.isDraw(previousStates)) {
return DRAW;
}
previousStates.push(state);
// graph[i] gives a list of nodes it's connected to, therefore the list of potential moves
final int[] potentialMoves = graph[state.currentPlayerPos()];
// Assume that the current player loses this path if we don't see a DRAW or a win for
// the current player on a child path.
int result = state.mouseTurn ? CAT_WIN : MOUSE_WIN;
for (final int move: potentialMoves) {
// cat cannot enter hole
if (!state.mouseTurn && move == POSITION_HOLE) {
// it would be invalid for the cat to be able to reach a point where
// the only option is the hole
assert potentialMoves.length > 1;
continue;
}
// recursively find the result if we choose this path
final int moveResult = getResult(
state.moveTo(move),
previousStates,
graph,
resultsCache
);
// If any child path results in a DRAW we're at least guarenteed not to lose,
// but must continue to check to see if we win.
if (moveResult == DRAW) {
result = DRAW;
}
// If a child path results in a win for the current player, this path is
// guarenteed to win, and we can stop checking other children.
else if (state.mouseTurn && moveResult == MOUSE_WIN) {
result = MOUSE_WIN;
break;
} else if (!state.mouseTurn && moveResult == CAT_WIN) {
result = CAT_WIN;
break;
}
}
previousStates.pop();
return result;
}
static class State {
final boolean mouseTurn;
final int mousePos;
final int catPos;
State(
final boolean mouseTurn,
final int mousePos,
final int catPos
) {
this.mouseTurn = mouseTurn;
this.mousePos = mousePos;
this.catPos = catPos;
}
boolean isMouseAtHole() {
return mousePos == POSITION_HOLE;
}
boolean isMouseCaughtByCat() {
return catPos == mousePos;
}
boolean isDraw(final Iterable<State> previousStates) {
// A path is considered a DRAW when the current state has previously been seen
// in this same path, i.e. a cycle has been encountered.
for (final State state: previousStates) {
if (equals(state)) {
return true;
}
}
return false;
}
@Override
public boolean equals(final Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
final State state = (State) o;
return mouseTurn == state.mouseTurn &&
mousePos == state.mousePos &&
catPos == state.catPos;
}
@Override
public int hashCode() {
return Objects.hash(mouseTurn, mousePos, catPos);
}
int currentPlayerPos() {
if (mouseTurn) {
return mousePos;
} else {
return catPos;
}
}
State moveTo(final int newPos) {
if (mouseTurn) {
return new State(false, newPos, catPos);
} else {
return new State(true, mousePos, newPos);
}
}
@Override
public String toString() {
return "(" + (mouseTurn ? "mouse, ": "cat, ") + mousePos + ", " + catPos + ")";
}
}
static void print(int depth, String str, Object... args) {
if (!DEBUG) {
return;
}
final StringBuilder sb = new StringBuilder();
for (int i = 0; i < depth; i++) {
sb.append("| ");
}
sb.append(String.format(str, args));
System.out.println(sb.toString());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment