# 808. Soup Servings -- Part 1

Please see the problem definition in:
https://leetcode.com/problems/soup-servings/description

For this problem, we introduce two approaches: *Tree Diagrams* approach and *Unique Path Count* approach.

# 1. Tree Diagrams Approach

## Intuition

First, we restate the four operations in this problem as:

1. Serve 4 units of soup A and 0 unit of soup B,
2. Serve 3 units of soup A and 1 unit of soup B,
3. Serve 2 units of soup A and 2 units of soup B, and
4. Serve 1 unit of soup A and 3 unit of soup B.

We define $n_A$ and $n_B$ as the current remaining volumes of soup for types A and B, respectively. Given $n_A$ and $n_B$, we define $p_A$ and $p_B$ as the probabilities that **soup A will deplete first** or that **A and B will empty simultaneously**, respectively, .

Using Tree Diagrams, each node in the tree represents the current volume state $(n_A, n_B)$. When $n_A > 0$ and $n_B > 0$, this node can produce four child nodes through four operations. These children nodes correspond to volumes $(n_A-4, n_B)$, $(n_A-3, n_B-1)$, $(n_A-2, n_B-2)$, and $(n_A-1, n_B-3)$, respectively.


If either one or both of the remaining soups A and B are empty (i.e., $n_A \leq 0$ or $n_B \leq 0$), the node cannot expand further and becomes a leaf. The probability of reaching this node is determined by multiplying $0.25$ raised to the power of $d$, where $d$ represents the depth from the root to this node. Conversely, for a non-leaf node, $p_A$ and $p_B$ can be calculated by aggregating the $p_A^i$ and $p_B^i$ values from all its child nodes $i$. To summarize, the derivation of $p_A$ and $p_B$ is as follows:
$$
p_A, p_B =
\begin{cases}
0.25^d, 0 & \text{if $n_A \leq 0$ and $n_B > 0$}, \\
0, 0.25^d & \text{if $n_A \leq 0$ and $n_B \leq 0$}, \\
0, 0 & \text{if $n_A > 0$ and $n_B \leq 0$},\\
\sum_i p_A^i, \sum_i p_B^i & \text{otherwise}.
\end{cases}
$$

An example to obtain $p_A$ and $p_B$ of node $(n_A=2,n_B=2)$ is illustrated below.


## Approach

Initially, we designate the root state as $n,n$, where $n$ represents the volume of soups A and B as defined in the problem statement. For the root node, we set the initial values of $p_A^{\text{root}}=0$ and $p_B^{\text{root}}=0$. The visualization below highlights visited nodes in blue.


Next, we employ Depth-First Search (DFS) to traverse this tree starting from the root to its children. Upon visiting each new child node $i$, we initialize its probabilities as $p_A^i=0$ and $p_B^i=0$.


Upon reaching a leaf node $j$, we assign the probabilities $p_A^j$ and $p_B^j$ depending on whether $n_A \leq 0$ or(and) $n_B \leq 0$, as previously described. Subsequently, we incorporate these probabilities into the $p_A$ and $p_B$ stored at its parent node, as follows:
$$
\begin{cases}
p_A \leftarrow p_A + p_A^j, \\
p_B \leftarrow p_B + p_B^j.
\end{cases}
$$

An example is illustrated below.


Once all the leaf nodes of a particular node $(n_A,n_B)$ have been traversed, the node transfers its probabilities to its parent node $(n_A^{\prime},n_B^{\prime})$, consequently updating the probabilities $p_a^{\prime}$ and $p_b^{\prime}$ in the following manner:
$$
\begin{cases}
p_A^{\prime} \leftarrow p_A^{\prime} + p_A, \\
p_B^{\prime} \leftarrow p_B^{\prime} + p_B.
\end{cases}
$$


Upon visiting all nodes, we derive $p_A^{\text{root}}$ and $p_B^{\text{root}}$ at the root of this tree. Subsequently, we compute the final result specified in the problem definition: $p_A^{\text{root}}+0.5p_B^{\text{root}}$.


Notice that multiple tree nodes may represent identical value pairs of $(n_A,n_B)$. In such instances, there's no necessity to recalculate their $p_A$ and $p_B$ values; rather, we can retrieve them from the previously visited node with the same $(n_A,n_B)$. The example below illustrates nodes representing the same value pairs of $(n_A,n_B)$, highlighted in green.


## Code

import math

# the node of the tree diagram.
class Node:
    def __init__(self, nA, nb, parent=None):
        self.nA = nA
        self.nb = nb
        self.pA = 0
        self.pB = 0
        self.parent = parent

class Solution:
    def soupServings(self, n: int) -> float:
        # Restate the n defined in the problem definition.
        n = math.ceil(n/25)
        
        # trivial cases
        if n == 0:
            return 0.5
        
        # It can be shown that pA approach to 1 when n is large.
        if n > 300:
            return 1

        # Initialize the root's pA and pB.
        pA_root, pB_root = 0, 0
        
        # treemap to record visited state
        treemap = {}
        
        # queue to traverse the tree, and initialized with the root node$
        q = [(n,n,0,None)]
        
        # DFS tree traversal
        while len(q) > 0:
            nA, nb, d, parent = q.pop()
            
            # If the state (nA, nB) has been visited, we obtained pA and pB from treemap.
            if (nA,nb) in treemap.keys() :
                node1 = treemap[(nA,nb)]
                node1.parent = parent
                
                # If current node is not root, add pA and pB to its parent.
                if node1.parent is not None:
                    node1.parent.pA += node1.pA
                    node1.parent.pB += node1.pB
                else:
                    # Obtain the root's pA and pB as
                    pA_root = node1.pA
                    pB_root = node1.pB
            else:       
                
                # If the state (nA, nB) hasn't been visited, we create a new treenode.
                node1 = Node(nA, nb, parent)
                treemap[(nA,nb)] = node1
                
                # The current node is a leaf, and soup A empty first.
                if node1.nA <= 0 and node1.nb > 0:
                    node1.pA = 0.25**d
                    node1.parent.pA += node1.pA
                # The current node is a leaf, and soup B empty simultaneously.
                elif node1.nA <= 0 and node1.nb <= 0:
                    node1.pB = 0.25**d
                    node1.parent.pB += node1.pB
                # The current node is a leaf, and soup B empty first.
                elif nA >=0 and nb <=0:
                    pass
                
                # The current node is not a leaf, we need to traverse its nodes.
                else:
                    # Insert current node to the queue, so that we can back to current node when all of its child are visited.
                    q.append((nA   ,nb  , d  , parent))
                    
                    # Append the child node to the queue for DFS.
                    q.append((nA-1 ,nb-3, d+1, node1))
                    q.append((nA-2 ,nb-2, d+1, node1))
                    q.append((nA-3 ,nb-1, d+1, node1))
                    q.append((nA-4, nb-0, d+1, node1))
        
        # Return the result requested from the problem definition.
        return pA_root+0.5*pB_root

While we achieved the correct answer, the runtime and memory usage aren't desirable.


# 2. Unique Path Count Approach

## Intuition
In the previous approach, we employed a map to prevent redundant calculations on the same values. When dealing with nodes having soap volumes $(n_A,n_B)$, multiple repeated nodes emerge with values ranging from $(n_A-7,n_B-1)$ to $(n_A-3,n_B-5)$ after undergoing two operations. We can merge these repetitive nodes, transforming the tree into a graph. The resulting graph is depicted below, with repeated nodes highlighted in green.

In previous approach, we use a map to avoid repeating calculation on the same value. For the node with soap volumes $(n_A,n_B)$, there will be multiple repeated nodes with values rangin from $(n_A-7,n_B-1)$, $(n_A-3,n_B-5)$ after conducting two operations. We can merge these repeated nodes , and the tree is transformed as a graph. The resulting graph is shown below, and the repeated nodes are highlighted in green.


To compute the $p_A$ and $p_B$ of an individual node, we introduce the concept of Unique Path Count (UPC). The UPC represents the number of unique paths from the root to reach a specific node. For a node with the value $(n_A,n_B)$ and its parent $j$ with the value $(n_A^j,n_B^j)$, we denote $c$ as the UPC of this node, and it is obtained by aggregating all of its parent's UPC, denoted as $c_j$, as illustrated:
$$
c = \sum_{j}c_j
$$


When a leaf is reached, to calculate its $p_A$ and $p_B$, we calculate the *Unique Path Count(UPC)* to reach the node denoted by $c$. We multiply by $0.25^d$ where $d$ is the depth to reach this node.

Upon reaching a leaf node with depth $d$, to determine its $p_A$ and $p_B$ values, we compute $c$ first and then then multiplied it by $0.25^d$, as follows
$$
p_A, p_B =
\begin{cases}
c \times 0.25^d, 0 & \text{if $n_A \leq 0$ and $n_B > 0$}, \\
0, c \times 0.25^d & \text{if $n_A \leq 0$ and $n_B \leq 0$}, \\
0, 0 & \text{if $n_A > 0$ and $n_B \leq 0$}.\\
\end{cases}
$$

An example is depicted below, where $p_A^{\text{root}}$ and $p_B^{\text{root}}$ are derived by aggregating the $p_A$ and $p_B$ values from their respective leaf nodes.


## Approach

We start by initializing the root with the value $(n,n)$, setting $p_A^{\text{root}}=p_B^{\text{root}}=0$, and assigning its UPC as $c=1$. Subsequently, we iteratively generate the next level of children using the following procedure.

1. **Step 1: Compute $n_A$ and $n_B$.**

Given a non-leaf node $(n_A,n_B)$ at the first position in the current level, if this level comprises $k$ non-leaf nodes, it can be demonstrated that the sequence of nodes in this level is $(n_A,n_B)$, $(n_A+1,n_B-1)$, $\cdots$, $(n_A+k-1,n_B-k+1)$. Additionally, the sequence of nodes in the next level is $(n_A-4,n_B)$, $(n_A-3,n_B-1)$, $\cdots$ ,$(n_A+k-2, n_B-k-2)$, and the counts of nodes is $k+3$.


2. **Step 2: Compute UPC $c$.**
To determine the value of $c$ in the subsequent level, we can employ 1-D convolution operations. Here, $c_i$ denotes the UPC of the current-level node at index $i$, while $c_i^{\prime}$ represents the UPC of the next-level node at index $i$. The 1-D convolutions are calculated using $c_i^{\prime} =\sum_{j=0}^{3}c_{i-j}$.
As the subsequent level comprises $k+3$ nodes, in order to apply the convolution operator, we must pad the left and right sides of the current level with three nodes possessing $c=0$, as illustrated below.

3. **Step 3: Compute $p_A$ and $p_B$.**
Once $c$ is computed, we proceed to verify whether the node is a leaf. If it is a leaf, we update $p_A^{\text{root}}$ and $p_B^{\text{root}}$ according to the following operations.
$$
\begin{cases}
p_A^{\text{root}} \leftarrow p_A^{\text{root}} + c \times 0.25^d & \text{if $n_A \leq 0$ and $n_B > 0$}, \\
p_B^{\text{root}} \leftarrow p_B^{\text{root}} + c \times 0.25^d & \text{if $n_A \leq 0$ and $n_B \leq 0$}.
\end{cases}
$$

4. **Step 4: Collect non-leaf nodes and repeat step 1 until $n_a+n_b\leq0$.**
We gather the non-leaf nodes within this level and then iterate through step 1. This process continues until $n_a+n_b \leq 0$, indicating that all nodes at this level are leaf nodes.

The implementation is shown below.

## Code

import math

class Solution:
    def soupServings(self, n: int) -> float:
        # Restate the n  in the provlem definition.
        n = math.ceil(n/25)
        
        # trivial cases
        if n == 0:
            return 0.5
        
        # It can be shown that pA approach to 1 when n is large.
        if n > 300:
            return 1

        # Initialize.
        nA, nB = n, n
        pA_root, pB_root = 0, 0
        d = 0
        
        # N is to store (nA, nB), and C is the array to stor c.
        N = [(nA,nB)]
        C = [1]
        
        
        # If there is any non-leaf node (nA,nB), continue for the next level.
        while nA+nB > 0 :
            
            # Add padding to the C array for convolution with kernel size=4.
            C_p = [0,0,0]+C+[0,0,0]
            
            # to store nA, nB and cat the next level.
            N_next = []
            C_next = []
            
            # We reach a new level; hence, depth += 1.
            d += 1
            
            # Compute nA, nB and c for each index i.
            for i in range(len(C)+3):
                
                # Step 1. compute nA, nB
                nA = N[0][0]-4+i
                nB = N[0][1]-i
                
                # Step 2. compute c

                c = sum(C_p[i:i+4])
                
                # Step 3. compute pA and pB, and add them to pA_root and pB_root
                # Case 1: The current node is a leaf, and soup A empty first.
                if nA <= 0 and nB > 0:
                    pA_root += c*(0.25**d)
                # Case 2: The current node is a leaf, and soup B empty simultaneously.
                elif nA<=0 and nB <= 0:
                    pB_root += c*(0.25**d)
                # Case 3: The current node is a leaf, and soup B empty first.
                elif nA > 0 and nB <= 0:
                    pass
                # Case 4: The current node is not a leaf, and we need to compute for its children.
                else:
                    # Step 4. collect non-leaf node for the next level
                    C_next.append(c)
                    N_next.append((nA, nB))
                    
            # Repeat the same steps until nA+nB <= 0.
            C = C_next
            N = N_next
            
        # Return the result requested from the problem definition.
        return pA_root+0.5*pB_root
    

This implementation demonstrates significantly improved speed compared to the previous one.


Nevertheless, I believe there's potential for enhancing this implementation by utilizing *generalized Pascal triangles and polynomial expansion* to derive an *analytic solution* for the UPC in each node. I plan to introduce this method in the forthcoming article.