fork download
copy 
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.HashMap;
  4. import java.util.List;
  5. import java.util.Locale;
  6. import java.util.Map;
  7.  
  8. class DeckGame {
  9.  
  10. 	/*
  11. 	 * Wraps the game state, trivial wrapper of an array of 5 elements, in
  12. 	 * 0..13, sum 13 Eg: n=[5,3,0,4,1] says that 5 numbers have not yet
  13. 	 * appeared, 3 numbers have appeared one, 4 numbers has appear three times,
  14. 	 * and 1 number has appeared 4 times
  15. 	 */
  16. 	static class DeckState {
  17. 		final int[] n = new int[5]; // 0-13, must sum 13
  18.  
  19. 		public DeckState(int[] nn) {
  20. 			System.arraycopy(nn, 0, n, 0, 5); // deep copy
  21. 		}
  22.  
  23. 		@Override
  24. 		public int hashCode() {
  25. 			return Arrays.hashCode(n);
  26. 		}
  27.  
  28. 		@Override
  29. 		public boolean equals(Object obj) {
  30. 			if (this == obj) return true;
  31. 			else if (obj == null || getClass() != obj.getClass()) return false;
  32. 			else return Arrays.equals(n, ((DeckState) obj).n);
  33. 		}
  34. 	}
  35.  
  36. 	/*
  37. 	 * Adds to DeckState the (total or partial) probability of reach that state
  38. 	 */
  39. 	static class DeckStateFull {
  40. 		public static final int MAX_ODD = 7;
  41. 		final double prob;
  42. 		final DeckState ds;
  43.  
  44. 		public DeckStateFull(DeckState d, double p) {
  45. 			this.ds = d;
  46. 			this.prob = p;
  47. 		}
  48.  
  49. 		public static DeckStateFull combin(DeckStateFull d1, DeckStateFull d2) {
  50. 			if (d1 == null)
  51. 				return d2 == null ? null : new DeckStateFull(d2.ds, d2.prob);
  52. 			else if (d2 == null)
  53. 				return new DeckStateFull(d1.ds, d1.prob);
  54. 			else
  55. 				return new DeckStateFull(d1.ds, d2.prob + d1.prob);
  56. 		}
  57.  
  58. 		boolean isValid() {
  59. 			return ds.n[1] + ds.n[3] <= MAX_ODD;
  60. 		}
  61.  
  62. 		int getT() { // current time (from 0 to 52)
  63. 			int a = 0;
  64. 			for (int i = 0; i < 5; i++)
  65. 				a += ds.n[i] * i;
  66. 			return a;
  67. 		}
  68.  
  69. 		/*
  70. 		 * Gives all possible states starting from this one, for the next
  71. 		 * iteration It does not take into account the "valid" restriction
  72. 		 */
  73. 		public List<DeckStateFull> generateNext() {
  74. 			int[] nx = new int[5];
  75. 			List<DeckStateFull> states = new ArrayList<DeckStateFull>();
  76. 			double px;
  77. 			int t = getT();
  78. 			for (int i = 0; i < 4; i++) {
  79. 				if (ds.n[i] < 1 || ds.n[i + 1] >= 13)
  80. 					continue;
  81. 				System.arraycopy(ds.n, 0, nx, 0, 5);
  82. 				nx[i]--;
  83. 				nx[i + 1]++;
  84. 				px = (4 - i) * ds.n[i] / (52.0 - t);
  85. 				states.add(new DeckStateFull(new DeckState(nx), px * prob));
  86. 			}
  87. 			return states;
  88. 		}
  89.  
  90. 		@Override
  91. 		public String toString() { // informational
  92. 			return Arrays.toString(ds.n) + " (p= " + prob + " t=" + getT()
  93. 					+ ")";
  94. 		}
  95. 	}
  96.  
  97. 	private List<Map<DeckState, DeckStateFull>> states = new ArrayList<Map<DeckState, DeckStateFull>>();
  98.  
  99. 	public DeckGame() {
  100. 		for (int t = 0; t <= 52; t++)
  101. 			states.add(new HashMap<DeckState, DeckStateFull>());
  102. 	}
  103.  
  104. 	public void compute() {
  105. 		// initial state
  106. 		DeckState ds0 = new DeckState(new int[] { 13, 0, 0, 0, 0 });
  107. 		states.get(0).put(ds0, new DeckStateFull(ds0, 1.0));
  108. 		int nst = 1; // total number of states
  109. 		for (int t = 1; t <= 52; t++) {
  110. 			double pac = 0; // probability accumulator for reaching this
  111. 							// iteration
  112. 			for (DeckStateFull stateprev : states.get(t - 1).values()) {
  113. 				for (DeckStateFull statenew : stateprev.generateNext()) {
  114. 					if (!statenew.isValid())
  115. 						continue;
  116. 					DeckStateFull stnew2 = DeckStateFull.combin(statenew,
  117. 							states.get(t).get(statenew.ds));
  118. 					states.get(t).put(stnew2.ds, stnew2);
  119. 				}
  120. 			}
  121. 			for (DeckStateFull ds : states.get(t).values())
  122. 				pac += ds.prob;
  123. 			nst += states.get(t).keySet().size();
  124. 			System.out.printf("t=%d p=%.6f %d states \n", t, pac, states.get(t)
  125. 					.keySet().size());
  126. 			if (t < 3 || t > 49)// extra information
  127. 				for (DeckStateFull s : states.get(t).values()) {
  128. 					System.out.println(s);
  129. 				}
  130. 		}
  131. 		System.out.println("Total valid states: " + nst);
  132. 	}
  133.  
  134. 	public static void main(String[] args) {
  135. 		Locale.setDefault(Locale.US);
  136. 		DeckGame d = new DeckGame();
  137. 		d.compute();
  138. 	}
  139. }
Success #stdin #stdout 0.12s 380544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
t=1 p=1.000000 1 states 
[12, 1, 0, 0, 0] (p= 1.0 t=1)
t=2 p=1.000000 2 states 
[11, 2, 0, 0, 0] (p= 0.9411764705882353 t=2)
[12, 0, 1, 0, 0] (p= 0.058823529411764705 t=2)
t=3 p=1.000000 3 states 
t=4 p=1.000000 5 states 
t=5 p=1.000000 6 states 
t=6 p=1.000000 9 states 
t=7 p=1.000000 11 states 
t=8 p=0.887920 14 states 
t=9 p=0.887920 17 states 
t=10 p=0.748589 20 states 
t=11 p=0.748589 24 states 
t=12 p=0.620945 27 states 
t=13 p=0.620945 32 states 
t=14 p=0.514393 34 states 
t=15 p=0.514393 41 states 
t=16 p=0.427891 42 states 
t=17 p=0.427891 50 states 
t=18 p=0.357809 50 states 
t=19 p=0.357809 60 states 
t=20 p=0.300526 58 states 
t=21 p=0.300526 69 states 
t=22 p=0.253105 65 states 
t=23 p=0.253105 76 states 
t=24 p=0.213349 70 states 
t=25 p=0.213349 80 states 
t=26 p=0.179691 72 states 
t=27 p=0.179691 80 states 
t=28 p=0.151062 70 states 
t=29 p=0.151062 76 states 
t=30 p=0.126779 65 states 
t=31 p=0.126779 69 states 
t=32 p=0.106432 58 states 
t=33 p=0.106432 60 states 
t=34 p=0.089781 50 states 
t=35 p=0.089781 50 states 
t=36 p=0.076639 42 states 
t=37 p=0.076639 41 states 
t=38 p=0.066788 34 states 
t=39 p=0.066788 32 states 
t=40 p=0.059959 27 states 
t=41 p=0.059959 24 states 
t=42 p=0.055866 20 states 
t=43 p=0.055866 17 states 
t=44 p=0.054161 14 states 
t=45 p=0.054161 11 states 
t=46 p=0.054161 9 states 
t=47 p=0.054161 6 states 
t=48 p=0.054161 5 states 
t=49 p=0.054161 3 states 
t=50 p=0.054161 2 states 
[0, 0, 0, 2, 11] (p= 0.0502082185231828 t=50)
[0, 0, 1, 0, 12] (p= 0.003952440516964939 t=50)
t=51 p=0.054161 1 states 
[0, 0, 0, 1, 12] (p= 0.05416065904014774 t=51)
t=52 p=0.054161 1 states 
[0, 0, 0, 0, 13] (p= 0.05416065904014774 t=52)
Total valid states: 1806
https://ideone.com/8v64Gn
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!