<p>You are given two groups of points where the first group has <code>size<sub>1</sub></code> points, the second group has <code>size<sub>2</sub></code> points, and <code>size<sub>1</sub> &gt;= size<sub>2</sub></code>.</p>

<p>The <code>cost</code> of the connection between any two points are given in an <code>size<sub>1</sub> x size<sub>2</sub></code> matrix where <code>cost[i][j]</code> is the cost of connecting point <code>i</code> of the first group and point <code>j</code> of the second group. The groups are connected if <strong>each point in both groups is connected to one or more points in the opposite group</strong>. In other words, each point in the first group must be connected to at least one point in the second group, and each point in the second group must be connected to at least one point in the first group.</p>

<p>Return <em>the minimum cost it takes to connect the two groups</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/03/ex1.jpg" style="width: 322px; height: 243px;" />
<pre>
<strong>Input:</strong> cost = [[15, 96], [36, 2]]
<strong>Output:</strong> 17
<strong>Explanation</strong>: The optimal way of connecting the groups is:
1--A
2--B
This results in a total cost of 17.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/03/ex2.jpg" style="width: 322px; height: 403px;" />
<pre>
<strong>Input:</strong> cost = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]
<strong>Output:</strong> 4
<strong>Explanation</strong>: The optimal way of connecting the groups is:
1--A
2--B
2--C
3--A
This results in a total cost of 4.
Note that there are multiple points connected to point 2 in the first group and point A in the second group. This does not matter as there is no limit to the number of points that can be connected. We only care about the minimum total cost.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> cost = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]]
<strong>Output:</strong> 10
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>size<sub>1</sub> == cost.length</code></li>
	<li><code>size<sub>2</sub> == cost[i].length</code></li>
	<li><code>1 &lt;= size<sub>1</sub>, size<sub>2</sub> &lt;= 12</code></li>
	<li><code>size<sub>1</sub> &gt;= size<sub>2</sub></code></li>
	<li><code>0 &lt;= cost[i][j] &lt;= 100</code></li>
</ul>


# Submitted by Samy Vilar <samy_vilar> on 08/03/2024

# Leverage the commutative nature of addition, while mapping each distinct member,
# (from either group) to some arbitrary but distant binary power; 
# Afterwhich we can apply a top-down recursive, w/ memoization/caching approach;
# if at all times we keep track of all those members missing, then we will
# choose an arbitrary member and consider all its edges, recursing through
# each of the size_1 or size_2 "edges" it could chose, should the chosen
# member be from group_2 or group_1 respectively, taken care to both remove
# the 2 members as well keeping tracking of the overall minimal solution
# witnessed;

# Since at one point or another we would had to remove all members, implies
# our recurssion halts, yielding 0 in the aforementioned case, and given
# addition is commutative for any edge disregarded at some common arbitrary 
# point, at one point or another said edge would need to be considered;
# Overall this would take O(size_2*2**size_1 + size_1*2**size_2) 
# time/additionals-space

# Note we could also apply a bottom-up BFS approach; essentially at each layer,
# we propagate forward all those "better" or never before seen solution(s); 
# halting as soon as no further progress was be made; 
# Since at any given time we are only interested in the preceeding set of 
# solution(s) we can discard all those that preceed it, reducing the additional
# space taken;


# version 1.2 micro-optimization(s)
#             pre-built edges and masks, speeding-up/simplifying traversal
#             NOTE care must be taken to account for 0th vertex, for the
#             sake of simplicity we will let its "neighbors" be an empty
#             sequence;

# version 1.2.1  

class Solution:
    def connectTwoGroups(self, costs: List[List[int]], 
                         bin_power=(1).__lshift__) -> int:
        targets = (    (base := 1 << (size_1 := len(costs))) \
                    << (size_2 := len(costs[0]))    ) - 1
        edges = tuple(chain(
            ((),),

            (tuple(zip(
                deltas,
                map((targets - (1 << at)).__sub__, map(bin_power, count(size_1)))
            )) for at, deltas in enumerate(costs)),

            (tuple(zip(
                map(itemgetter(at.bit_length() - 1 - size_1), costs),    
                map((targets - at).__sub__, map(bin_power, count()))
            )) for at in map(bin_power, range(size_1, size_1 + size_2)))
        ))               
        progress = {(1 << (size_1 + size_2)) - 1: 0}
        while progress:                          
            prev = (solutions := progress).get
            setdefault = (progress := {}).setdefault            
            for missing, total in solutions.items():                
                for candidate, others in edges[(missing & -missing).bit_length()]:
                    if (candidate := candidate + total) \
                            < prev((others := others & missing), 14401) \
                            and candidate < setdefault(others, candidate):
                        progress[others] = candidate            
        return solutions[0]
            

        # Simpler, though with greater overhead;
        # size_1 = len(costs)
        # size_2 = len(costs[0])
        # cost = (costs := tuple(chain.from_iterable(costs))).__getitem__
        # pending = deque(((((base := 1 << size_1) << size_2) - 1, 0),))
        # push = pending.append
        # pop = pending.popleft
        # get = (solutions := {pending[0][0]:0}).get
        # solution = 14401
        # while pending:
        #     missing, total = pop()
        #     if total == solutions[missing]:
        #         if not missing and total < solution:
        #             solution = total
        #             continue
        #         missing -= (at := missing & -missing)
        #         row = (at.bit_length() - 1) * size_2
        #         others = enumerate(
        #             map(total.__add__, map(cost, range(row, row + size_2))), size_1
        #         ) if at < base else enumerate(
        #             map(total.__add__, 
        #                 map(cost, range(at.bit_length() - 1 - size_1, 
        #                                 size_1 * size_2, 
        #                                 size_2)))
        #         )                    
        #         for at, total in others:
        #             if total < get((at := missing & ~(1 << at)), 14401):
        #                 solutions[at] = total
        #                 push((at, total))
        # return solution

        # version 1.0 top-down recurssive w/ memoization/cachine
        @cache
        def solve(
            missing=(1 << ((size_1:=len(costs)) + (size_2:=len(costs[0])))) - 1,
            size_2=size_2, bound=size_1*size_2, diff=size_1 + 1, base=1 << size_1,
            costs=tuple(chain.from_iterable(costs))
        ):
            if missing:
                missing -= (at := missing & -missing)
                if at < base:                    
                    low = (at.bit_length() - 1) * size_2
                    return min(costs[low + at] + solve(missing & ~(base << at))
                               for at in range(size_2))                
                return min(costs[at] + solve(missing & ~(1 << tail))
                           for tail, at in enumerate(range(at.bit_length() - diff,
                                                           bound, 
                                                           size_2)))
            return 0
        return solve()

17500