Untitled

import math

class MixingNode:
    """Represents a (1:1) Mix/Split operation in the biochip [cite: 59, 68]"""
    def __init__(self, label, partition=None, level=0):
        self.label = label
        self.partition = partition
        self.level = level
        self.left = None
        self.right = None

def algorithm_1_ratio_approximation(ratios, d=7):
    """Scales target ratios to a sum of 2^d [cite: 264, 266]"""
    L_prime = 2**d
    L = sum(ratios)
    approximated = [round((a * L_prime) / L) for a in ratios]
    
    # Adjust last element to ensure exact sum of 2^d [cite: 266]
    diff = L_prime - sum(approximated)
    approximated[-1] += diff
    return approximated

def algorithm_4_expression_partition(P, L):
    """Decomposes an expression into two equal volume partitions [cite: 292, 310]"""
    L_half = L // 2
    # Find highest coefficient a_u for fluid x_u [cite: 311, 313]
    sorted_fluids = sorted(P.items(), key=lambda item: item[1], reverse=True)
    u_fluid, a_u = sorted_fluids[0]
    
    P1, P2 = {}, {}
    
    if a_u >= L_half:
        # Partition 1 gets exactly L_half of the dominant fluid [cite: 315]
        P1[u_fluid] = L_half
        # Partition 2 gets the remainder of a_u plus all other fluids [cite: 315]
        remainder = a_u - L_half
        if remainder > 0: 
            P2[u_fluid] = remainder
        for f, val in sorted_fluids[1:]:
            P2[f] = val
    else:
        # Group fluids greedily to fill Partition 1 to L_half [cite: 322, 323]
        P1[u_fluid] = a_u
        current_sum = a_u
        for f, val in sorted_fluids[1:]:
            if current_sum + val <= L_half:
                P1[f] = val
                current_sum += val
            else:
                needed = L_half - current_sum
                if needed > 0:
                    P1[f] = needed
                    # Only add to P2 if volume is non-zero [cite: 325]
                    rem = val - needed
                    if rem > 0: P2[f] = rem
                    current_sum += needed
                else:
                    P2[f] = val
                    
    return P1, P2

def build_rma_tree(P, L, level=0):
    """Recursive construction of the binary mixing tree [cite: 287, 292]"""
    # Base Case: Reached a pure reagent (leaf node) 
    if len(P) == 1:
        return MixingNode(list(P.keys())[0], level=level)

    # Recursive step: Partition current volume L into two L/2 droplets [cite: 292, 312]
    P1, P2 = algorithm_4_expression_partition(P, L)
    node = MixingNode("Mix", partition=(P, L), level=level)
    node.left = build_rma_tree(P1, L // 2, level + 1)
    node.right = build_rma_tree(P2, L // 2, level + 1)
    return node

def print_tree(node, indent=""):
    """Visualizes tree structure for midterm demonstration"""
    if node:
        connector = " -> " if not node.left else " [Mix] "
        print(f"{indent}{connector}{node.label} (Level {node.level})")
        if node.left: print_tree(node.left, indent + "    ")
        if node.right: print_tree(node.right, indent + "    ")

# --- MIDTERM DEMO ---
# Target Ratio: 2:3:5:7:11:13:87 [cite: 65, 69]
raw_ratios = [2, 3, 5, 7, 11, 13, 87]
depth = 7 # Accuracy 1/2^7 [cite: 65, 133]

print("Step 1: Scaling Ratios to 2^d (128 units)")
adj = algorithm_1_ratio_approximation(raw_ratios, depth)
fluid_dict = {f"x{i+1}": adj[i] for i in range(len(adj))}
print(f"Final Distribution: {fluid_dict}\n")

print("Step 2: Generating RMA Mixing Tree")
root = build_rma_tree(fluid_dict, 2**depth)
print_tree(root)