## Solution
[Link](https://gist.github.com/richardliang/b56d1d687b3cacdb3954e55303c610e5)

## Approach
At a high level, I broke the problem down into 3 parts
1. First find `num_match`
2. Then identify the correct indexes each tuple should be
3. Lastly, shift elements and create new array

### 1. Finding num_match
Circom doesn't have any control flows and each signal can only be assigned once. So, I used an intermediate signal `sum[101]` to store the running sum. The 0th index stores a 0 and adds a match to the sum when IsEqual returns 1. Return the last index which will return the final `num_match`

Example tuple of 4 elements
`[(3,5), (4,6), (8,7), (3,8)] -> [0,1,1,1,2]`

### 2. Identifying where the correct index each tuple should be
This was a simple step, simply multiply the return values of IsEqual and the running sum from i+i to 101 which gives you where the correct index where match should be plus one (so we need to subtract 1 from the index later on)

Example
`[1,0,0,1] * [1,1,1,2] -> [1,0,0,2]`

### 3. Shift elements
This was the trickiest part, since Circom doesn't allow you to index into arrays with signals. I can't just do the naive way e.g. `out[i] <== in[index_plus_one[i] - 1]` since the value of index_plus_one[i] isn't known at compile time

Instead, Circom needs O(n) to iterate across the set of all possible index values for a single element. For each element in the index_plus_1 array (row), we first check if the element matches the ith element (column). If there is a match, we return the second value of the `in` tuple and accumulate it over `j` and returning the last value of the running sum. We need to do this accumulation for all 100 elements

Conceptually, we're looping through `j` to find where the matched index is and placing it in a new array element `i`

To save constraints:
1. I only stored the second value of the matched. This is because we already know that the first `num_match` elements will be equal to `match`.
2. I subtracted each element in index_plus_one by 1. So the nonmatches become `-1` which ensures that it doesn't match any `i`th element

Example:

in: [(3,5), (4,6), (8,7), (3,8)]

    0 1 2 3
    -------
0 | 1 0 0 0
-1| 0 0 0 0
-1| 0 0 0 0
1 | 0 1 0 0
    -------
    1 1 0 0
   [5 8 0 0]

To achieve the final solution of the filtered array, I populate `out` by checking if tuple_2 is matched, and outputting the `match` in the first element, and outputting the corresponding tuple_2 value in the second element.

This was a fun puzzle! Overall, made me appreciate lower level circuit writing a lot more, despite the limitations of Circom