Compute the winning probability for a certain solitaire game; see http://math.stackexchange.com/questions/594967.

Question594967.java

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Question594967 {
	static class State {
		int [] left;
		int [] board;
		int nleft;
		int nboard;
		
		public State () {
			this (new int [4],new int [4],0,0);
		}
		
		public State (State s) {
			this (s.left.clone (),s.board.clone (),s.nleft,s.nboard);
		}
		
		private State (int [] left,int [] board,int nleft,int nboard) {
			this.left = left;
			this.board = board;
			this.nleft = nleft;
			this.nboard = nboard;
		}
		
		public boolean equals (Object o) {
			State s = (State) o;
			return Arrays.equals (s.left,left) && Arrays.equals (s.board,board);
		}
		
		public int hashCode () {
			return Arrays.hashCode (left) ^ Arrays.hashCode (board);
		}
		
		public String toString () {
			return Arrays.toString (left) + " (" + nleft + "), " + Arrays.toString (board) + " (" + nboard + ")";
		}
	}
	
	static Map<State,Rational> map = new HashMap<State,Rational> (); 
	
	public static void main (String [] args) {
		State s = new State ();
		Arrays.fill (s.left,13);
		s.nleft = 52;
		
		System.out.println (getProbability (s));
		
		final int ntrials = 100000000;
		DrawingWithoutReplacement deck = new DrawingWithoutReplacement (52);
		int [] board;
		int nboard;
		int count = 0;
		
		for (int n = 0;n < ntrials;n++) {
			board = new int [4];
			nboard = 0;
			deck.reset ();
			do {
				while (nboard < 4 && !deck.isEmpty ()) {
					board [deck.draw () / 13]++;
					nboard++;
				}
				for (int i = 0;i < 4;i++)
					if (board [i] > 1) {
						nboard -= board [i];
						board [i] = 0;
					}
			} while (nboard != 4 && !deck.isEmpty ());

			if (nboard == 0)
				count++;
		}
		
		System.out.println (count / (double) ntrials);
	}
	
	static Rational getProbability (State s) {
//		System.out.println (prefix + "get probability : " + s);
		Rational p = map.get (s);
		if (p == null) {
			State c = new State (s);
			if (c.nboard == 4 || c.nleft == 0) {
				for (int i = 0;i < 4;i++)
					if (c.board [i] > 1) {
						c.nboard -= c.board [i];
						c.board [i] = 0;
					}
				p = c.nleft == 0 && c.nboard == 0 ? Rational.ONE : c.nleft == 0 || c.nboard == 4 ? Rational.ZERO : getProbability (c);
				c = new State (s);
			}
			else {
				p = Rational.ZERO;
				for (int i = 0;i < 4;i++)
					if (c.left [i] >  0) {
						c.left [i]--;
						c.nleft--;
						c.board [i]++;
						c.nboard++;
						p = p.add (getProbability (c).multiply (s.left [i])); // undecremented s.left [i], not c.left [i]
						c.left [i]++;
						c.nleft++;
						c.board [i]--;
						c.nboard--;
					}
				p = p.divide (c.nleft);
			}
			map.put (c,p);
		}
		return p;
	}
}