1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
/**
 * Calculate the probability that soup A will be empty first, plus half the probability
 * that A and B become empty at the same time.
 * Dynamic Programming with Memoization approach.
 *
 * @param {number} n - Initial amount of soup A and B in ml
 * @return {number} - Probability
 */
function soupServings(n) {
  // For large values of n, the probability approaches 1
  if (n > 4800) {
    return 1.0;
  }
 
  // Scale down the problem by dividing n by 25
  n = Math.ceil(n / 25);
 
  // Initialize memoization map
  const memo = new Map();
 
  // Define recursive function
  function calculateProbability(a, b) {
    // Base cases
    if (a <= 0 && b <= 0) {
      return 0.5;  // Both soups become empty at the same time
    }
    if (a <= 0) {
      return 1.0;  // Soup A becomes empty first
    }
    if (b <= 0) {
      return 0.0;  // Soup B becomes empty first
    }
 
    // Create a unique key for the memo map
    const key = a + ',' + b;
 
    // If we've already computed this subproblem, return the cached result
    if (memo.has(key)) {
      return memo.get(key);
    }
 
    // Calculate the probability for the current state
    const result = 0.25 * (
      calculateProbability(a - 4, b) +      // Serve 100 ml of A, 0 ml of B
      calculateProbability(a - 3, b - 1) +  // Serve 75 ml of A, 25 ml of B
      calculateProbability(a - 2, b - 2) +  // Serve 50 ml of A, 50 ml of B
      calculateProbability(a - 1, b - 3)    // Serve 25 ml of A, 75 ml of B
    );
 
    // Cache the result
    memo.set(key, result);
    return result;
  }
 
  return calculateProbability(n, n);
}
 
/**
 * Calculate the probability that soup A will be empty first, plus half the probability
 * that A and B become empty at the same time.
 * Iterative Dynamic Programming approach.
 *
 * @param {number} n - Initial amount of soup A and B in ml
 * @return {number} - Probability
 */
function soupServingsIterative(n) {
  // For large values of n, the probability approaches 1
  if (n > 4800) {
    return 1.0;
  }
 
  // Scale down the problem by dividing n by 25
  n = Math.ceil(n / 25);
 
  // Initialize DP array
  const dp = Array(n + 1).fill().map(() => Array(n + 1).fill(0));
 
  // Set base cases
  dp[0][0] = 0.5;  // Both soups become empty at the same time
  for (let i = 1; i <= n; i++) {
    dp[0][i] = 1.0;  // Soup A becomes empty first
    dp[i][0] = 0.0;  // Soup B becomes empty first
  }
 
  // Fill DP array
  for (let a = 1; a <= n; a++) {
    for (let b = 1; b <= n; b++) {
      dp[a][b] = 0.25 * (
        dp[Math.max(0, a - 4)][b] +      // Serve 100 ml of A, 0 ml of B
        dp[Math.max(0, a - 3)][Math.max(0, b - 1)] +  // Serve 75 ml of A, 25 ml of B
        dp[Math.max(0, a - 2)][Math.max(0, b - 2)] +  // Serve 50 ml of A, 50 ml of B
        dp[Math.max(0, a - 1)][Math.max(0, b - 3)]    // Serve 25 ml of A, 75 ml of B
      );
    }
  }
 
  return dp[n][n];
}
 
/**
 * Calculate the probability that soup A will be empty first, plus half the probability
 * that A and B become empty at the same time.
 * Mathematical Insight approach.
 *
 * @param {number} n - Initial amount of soup A and B in ml
 * @return {number} - Probability
 */
function soupServingsMathematical(n) {
  // For large values of n, the probability approaches 1
  if (n > 4800) {
    return 1.0;
  }
 
  // Use the recursive approach for smaller values of n
  return soupServings(n);
}
 
// Test cases
console.log(soupServings(50));  // 0.625
console.log(soupServings(100));  // 0.71875
 
console.log(soupServingsIterative(50));  // 0.625
console.log(soupServingsIterative(100));  // 0.71875
 
console.log(soupServingsMathematical(50));  // 0.625
console.log(soupServingsMathematical(100));  // 0.71875
console.log(soupServingsMathematical(5000));  // 1.0