· 8 years ago · May 12, 2018, 06:00 PM
1using System;
2using System.Collections.Generic;
3using System.Numerics;
4using System.Text;
5
6namespace PuzzleAndDragonsRolls {
7
8 static class Program {
9
10 public static BigDecimal PROBABILITY_OF_SUCCESS = 0.1m;
11 public const int GOAL_NUMBER = 4;
12 public const int MAX_ATTEMPTS = 110;
13
14 static void Main() {
15 // Calculate the probability of failure, since we use that a lot
16 BigDecimal probabilityOfFailure = 1 - PROBABILITY_OF_SUCCESS;
17
18 // Start the base case of 0 trials
19 List<Outcome> outcomes = new List<Outcome>();
20
21 // There's a 100% chance that nothing happened. Crazy, eh.
22 outcomes.Add(new Outcome(1, 0));
23
24 // Variable that keeps track of the total probability of success
25 // To optimize this program to finish in a reasonable time frame, outcomes that succeed are
26 // discarded and their probability of happening are just added to this counter
27 // This makes everything much faster but means we can only calculate "at least X" successes
28 // We can't calculate "exactly X" successes.
29 BigDecimal totalProbabilityOfSuccess = 0;
30
31 for (int rolls = 1; rolls < MAX_ATTEMPTS; rolls++) {
32
33 // Calculate the outcomes from one more trails
34 List<Outcome> newOutcomes = new List<Outcome>(outcomes.Count * 2);
35
36 foreach(Outcome oldOutcome in outcomes) {
37 // This outcome is now split between 1 more success and 1 more failure
38 Outcome newOutcome0 = new Outcome(oldOutcome.Probability * probabilityOfFailure, oldOutcome.SuccessCount);
39 Outcome newOutcome1 = new Outcome(oldOutcome.Probability * PROBABILITY_OF_SUCCESS, oldOutcome.SuccessCount + 1);
40
41 newOutcomes.Add(newOutcome0);
42
43 if(newOutcome1.SuccessCount >= GOAL_NUMBER) {
44 // This outcome meets the requirement, so we filter it into our counter and discard it
45 totalProbabilityOfSuccess += newOutcome1.Probability;
46 } else {
47 newOutcomes.Add(newOutcome1);
48 }
49 }
50
51 outcomes = newOutcomes;
52
53 Console.WriteLine($"Probably of getting at least {GOAL_NUMBER} in {rolls} rolls: {ToReadableString(totalProbabilityOfSuccess, 12)}");
54 }
55
56 Console.WriteLine("Please any key to quit");
57 Console.ReadLine();
58 }
59
60 private static String ToReadableString(BigDecimal bd, int maxDecimals) {
61 String number = bd.Mantissa.ToString();
62 int exp = bd.Exponent;
63
64 if(exp == 0) {
65 return number;
66 }
67
68 if(exp > 0) {
69 StringBuilder ret2 = new StringBuilder();
70 ret2.Append(number);
71 for(int i = 0; i < exp; i++) {
72 ret2.Append("0");
73 }
74 return ret2.ToString();
75 }
76
77 int padZeros = -exp - number.Length + 1;
78 StringBuilder ret = new StringBuilder();
79 for(int i = 0; i < padZeros; i++) {
80 ret.Append("0");
81 }
82 ret.Append(number);
83
84 number = ret.ToString();
85
86 // {exp} places to the left
87 int decimalLocation = number.Length + exp;
88
89 return number.Substring(0, decimalLocation) + "." + number.Substring(decimalLocation, Math.Min(number.Length - decimalLocation, maxDecimals));
90 }
91 }
92
93 public class Outcome {
94
95 public BigDecimal Probability;
96 public int SuccessCount = 0;
97
98 public Outcome(BigDecimal probability, int count) {
99 Probability = probability;
100 SuccessCount = count;
101 }
102 }
103
104 /// <summary>
105 /// Arbitrary precision decimal.
106 /// All operations are exact, except for division. Division never determines more digits than the given precision.
107 /// Source: https://gist.github.com/JcBernack/0b4eef59ca97ee931a2f45542b9ff06d
108 /// Based on https://stackoverflow.com/a/4524254
109 /// Author: Jan Christoph Bernack (contact: jc.bernack at gmail.com)
110 /// </summary>
111 public struct BigDecimal
112 : IComparable
113 , IComparable<BigDecimal> {
114 /// <summary>
115 /// Specifies whether the significant digits should be truncated to the given precision after each operation.
116 /// </summary>
117 public static bool AlwaysTruncate = false;
118
119 /// <summary>
120 /// Sets the maximum precision of division operations.
121 /// If AlwaysTruncate is set to true all operations are affected.
122 /// </summary>
123 public static int Precision = 50;
124
125 public BigInteger Mantissa { get; set; }
126 public int Exponent { get; set; }
127
128 public BigDecimal(BigInteger mantissa, int exponent)
129 : this() {
130 Mantissa = mantissa;
131 Exponent = exponent;
132 Normalize();
133 if(AlwaysTruncate) {
134 Truncate();
135 }
136 }
137
138 /// <summary>
139 /// Removes trailing zeros on the mantissa
140 /// </summary>
141 public void Normalize() {
142 if(Mantissa.IsZero) {
143 Exponent = 0;
144 } else {
145 BigInteger remainder = 0;
146 while(remainder == 0) {
147 var shortened = BigInteger.DivRem(Mantissa, 10, out remainder);
148 if(remainder == 0) {
149 Mantissa = shortened;
150 Exponent++;
151 }
152 }
153 }
154 }
155
156 /// <summary>
157 /// Truncate the number to the given precision by removing the least significant digits.
158 /// </summary>
159 /// <returns>The truncated number</returns>
160 public BigDecimal Truncate(int precision) {
161 // copy this instance (remember it's a struct)
162 var shortened = this;
163 // save some time because the number of digits is not needed to remove trailing zeros
164 shortened.Normalize();
165 // remove the least significant digits, as long as the number of digits is higher than the given Precision
166 while(NumberOfDigits(shortened.Mantissa) > precision) {
167 shortened.Mantissa /= 10;
168 shortened.Exponent++;
169 }
170 // normalize again to make sure there are no trailing zeros left
171 shortened.Normalize();
172 return shortened;
173 }
174
175 public BigDecimal Truncate() {
176 return Truncate(Precision);
177 }
178
179 public BigDecimal Floor() {
180 return Truncate(BigDecimal.NumberOfDigits(Mantissa) + Exponent);
181 }
182
183 public static int NumberOfDigits(BigInteger value) {
184 // do not count the sign
185 //return (value * value.Sign).ToString().Length;
186 // faster version
187 return (int)Math.Ceiling(BigInteger.Log10(value * value.Sign));
188 }
189
190 #region Conversions
191
192 public static implicit operator BigDecimal(int value) {
193 return new BigDecimal(value, 0);
194 }
195
196 public static implicit operator BigDecimal(double value) {
197 var mantissa = (BigInteger)value;
198 var exponent = 0;
199 double scaleFactor = 1;
200 while(Math.Abs(value * scaleFactor - (double)mantissa) > 0) {
201 exponent -= 1;
202 scaleFactor *= 10;
203 mantissa = (BigInteger)(value * scaleFactor);
204 }
205 return new BigDecimal(mantissa, exponent);
206 }
207
208 public static implicit operator BigDecimal(decimal value) {
209 var mantissa = (BigInteger)value;
210 var exponent = 0;
211 decimal scaleFactor = 1;
212 while((decimal)mantissa != value * scaleFactor) {
213 exponent -= 1;
214 scaleFactor *= 10;
215 mantissa = (BigInteger)(value * scaleFactor);
216 }
217 return new BigDecimal(mantissa, exponent);
218 }
219
220 public static explicit operator double(BigDecimal value) {
221 return (double)value.Mantissa * Math.Pow(10, value.Exponent);
222 }
223
224 public static explicit operator float(BigDecimal value) {
225 return Convert.ToSingle((double)value);
226 }
227
228 public static explicit operator decimal(BigDecimal value) {
229 return (decimal)value.Mantissa * (decimal)Math.Pow(10, value.Exponent);
230 }
231
232 public static explicit operator int(BigDecimal value) {
233 return (int)(value.Mantissa * BigInteger.Pow(10, value.Exponent));
234 }
235
236 public static explicit operator uint(BigDecimal value) {
237 return (uint)(value.Mantissa * BigInteger.Pow(10, value.Exponent));
238 }
239
240 #endregion
241
242 #region Operators
243
244 public static BigDecimal operator +(BigDecimal value) {
245 return value;
246 }
247
248 public static BigDecimal operator -(BigDecimal value) {
249 value.Mantissa *= -1;
250 return value;
251 }
252
253 public static BigDecimal operator ++(BigDecimal value) {
254 return value + 1;
255 }
256
257 public static BigDecimal operator --(BigDecimal value) {
258 return value - 1;
259 }
260
261 public static BigDecimal operator +(BigDecimal left, BigDecimal right) {
262 return Add(left, right);
263 }
264
265 public static BigDecimal operator -(BigDecimal left, BigDecimal right) {
266 return Add(left, -right);
267 }
268
269 private static BigDecimal Add(BigDecimal left, BigDecimal right) {
270 return left.Exponent > right.Exponent
271 ? new BigDecimal(AlignExponent(left, right) + right.Mantissa, right.Exponent)
272 : new BigDecimal(AlignExponent(right, left) + left.Mantissa, left.Exponent);
273 }
274
275 public static BigDecimal operator *(BigDecimal left, BigDecimal right) {
276 return new BigDecimal(left.Mantissa * right.Mantissa, left.Exponent + right.Exponent);
277 }
278
279 public static BigDecimal operator /(BigDecimal dividend, BigDecimal divisor) {
280 var exponentChange = Precision - (NumberOfDigits(dividend.Mantissa) - NumberOfDigits(divisor.Mantissa));
281 if(exponentChange < 0) {
282 exponentChange = 0;
283 }
284 dividend.Mantissa *= BigInteger.Pow(10, exponentChange);
285 return new BigDecimal(dividend.Mantissa / divisor.Mantissa, dividend.Exponent - divisor.Exponent - exponentChange);
286 }
287
288 public static BigDecimal operator %(BigDecimal left, BigDecimal right) {
289 return left - right * (left / right).Floor();
290 }
291
292 public static bool operator ==(BigDecimal left, BigDecimal right) {
293 return left.Exponent == right.Exponent && left.Mantissa == right.Mantissa;
294 }
295
296 public static bool operator !=(BigDecimal left, BigDecimal right) {
297 return left.Exponent != right.Exponent || left.Mantissa != right.Mantissa;
298 }
299
300 public static bool operator <(BigDecimal left, BigDecimal right) {
301 return left.Exponent > right.Exponent ? AlignExponent(left, right) < right.Mantissa : left.Mantissa < AlignExponent(right, left);
302 }
303
304 public static bool operator >(BigDecimal left, BigDecimal right) {
305 return left.Exponent > right.Exponent ? AlignExponent(left, right) > right.Mantissa : left.Mantissa > AlignExponent(right, left);
306 }
307
308 public static bool operator <=(BigDecimal left, BigDecimal right) {
309 return left.Exponent > right.Exponent ? AlignExponent(left, right) <= right.Mantissa : left.Mantissa <= AlignExponent(right, left);
310 }
311
312 public static bool operator >=(BigDecimal left, BigDecimal right) {
313 return left.Exponent > right.Exponent ? AlignExponent(left, right) >= right.Mantissa : left.Mantissa >= AlignExponent(right, left);
314 }
315
316 /// <summary>
317 /// Returns the mantissa of value, aligned to the exponent of reference.
318 /// Assumes the exponent of value is larger than of reference.
319 /// </summary>
320 private static BigInteger AlignExponent(BigDecimal value, BigDecimal reference) {
321 return value.Mantissa * BigInteger.Pow(10, value.Exponent - reference.Exponent);
322 }
323
324 #endregion
325
326 #region Additional mathematical functions
327
328 public static BigDecimal Exp(double exponent) {
329 var tmp = (BigDecimal)1;
330 while(Math.Abs(exponent) > 100) {
331 var diff = exponent > 0 ? 100 : -100;
332 tmp *= Math.Exp(diff);
333 exponent -= diff;
334 }
335 return tmp * Math.Exp(exponent);
336 }
337
338 public static BigDecimal Pow(double basis, double exponent) {
339 var tmp = (BigDecimal)1;
340 while(Math.Abs(exponent) > 100) {
341 var diff = exponent > 0 ? 100 : -100;
342 tmp *= Math.Pow(basis, diff);
343 exponent -= diff;
344 }
345 return tmp * Math.Pow(basis, exponent);
346 }
347
348 #endregion
349
350 public override string ToString() {
351 return string.Concat(Mantissa.ToString(), "E", Exponent);
352 }
353
354 public bool Equals(BigDecimal other) {
355 return other.Mantissa.Equals(Mantissa) && other.Exponent == Exponent;
356 }
357
358 public override bool Equals(object obj) {
359 if(ReferenceEquals(null, obj)) {
360 return false;
361 }
362 return obj is BigDecimal && Equals((BigDecimal)obj);
363 }
364
365 public override int GetHashCode() {
366 unchecked {
367 return (Mantissa.GetHashCode() * 397) ^ Exponent;
368 }
369 }
370
371 public int CompareTo(object obj) {
372 if(ReferenceEquals(obj, null) || !(obj is BigDecimal)) {
373 throw new ArgumentException();
374 }
375 return CompareTo((BigDecimal)obj);
376 }
377
378 public int CompareTo(BigDecimal other) {
379 return this < other ? -1 : (this > other ? 1 : 0);
380 }
381 }
382}