# Toggling Grid
You are given a grid (2d array) of 0/1's. All 1's represents a solved puzzle. Your job is to come up with a sequence of toggle moves that will solve a scrambled grid.

Solved:

```
[ [1, 1, 1],
  [1, 1, 1],
  [1, 1, 1] ]
``` 

"0" (first row) toggle:
```
[ [0, 0, 0],
  [1, 1, 1],
  [1, 1, 1] ]
```

then "3" (first column) toggle:
```
[ [1, 0, 0],
  [0, 1, 1],
  [0, 1, 1] ]
```

The numbers in quotes are codes for the row/column, and will be explained.

## Your task: findSolution()
Your task is to write a function, `findSolution()` (or `find_solution()`), which takes as input a 2d array, and returns an array of "steps" that represent a sequence of toggles to solve the puzzle.

For example:

```python
solution = find_solution(puzzle)
print(solution);
> [0, 3]
```
Note that, in the above example, `[1, 2, 4, 5]` is also a valid solution! Any solution will pass the tests.

The solution is tested like this, for each number in the solution:

```python
if n < puzzle.size:
  toggleRow(n)
else:
  toggleCol(n - puzzle.size)
```
To elaborate, possible n's for a 3x3 puzzle:

- Row numbers = (0    --> size - 1)
- Cols numbers = (size --> size * 2 - 1)

### Example of "2" toggle:

### Example of "4" toggle:

## More examples:

```python
puzzle = [
  [ 0, 1, 0 ],
  [ 1, 0, 1 ],
  [ 1, 0, 1 ]
];
solution = find_solution(puzzle)
print(solution);
> [0, 4]
```
let's try some bigger puzzles:

```python
puzzle = [
  [ 1, 0, 1, 0, 0 ],
  [ 0, 1, 0, 1, 1 ],
  [ 0, 1, 0, 1, 1 ],
  [ 0, 1, 0, 1, 1 ],
  [ 1, 0, 1, 0, 0 ]
];
solution = find_solution(puzzle)
print(solution);
> [ 0, 5, 4, 7 ]
```

```python
puzzle = [
  [ 1, 1, 1, 0, 1, 1, 1 ],
  [ 1, 1, 1, 0, 1, 1, 1 ],
  [ 1, 1, 1, 0, 1, 1, 1 ],
  [ 0, 0, 0, 1, 0, 0, 0 ],
  [ 1, 1, 1, 0, 1, 1, 1 ],
  [ 1, 1, 1, 0, 1, 1, 1 ],
  [ 1, 1, 1, 0, 1, 1, 1 ]
];
solution = find_solution(puzzle)
print(solution);
> [ 3, 10 ]
```

There are randomized tests with puzzles of up to 100x100 in size. Have fun!

Difficulty: introductory

Starter code:

def find_solution(puzzle):
	

Solutions:
def find_solution(m):
    return [j for j,r in enumerate(m) if r[0]^m[0][0]] + [len(m)+i for i,b in enumerate(m[0]) if not b]

find_solution = lambda m: [n for n, r in enumerate(m) if r[0]] + [n for n, c in enumerate(m[0],len(m)) if not m[0][0] ^ c]

def find_solution(puzzle):
    n, sol = len(puzzle), []
    for i in range(n):
        if puzzle[i][0] ^ 1:
            sol.append(i)
    for i in range(1, n):
        if puzzle[0][i] ^ 1 ^ (sol and sol[0] == 0):
            sol.append(n + i)
    return sol

import copy

def find_solution(puzzle):
    moveset = []
    while(True):
        # Find first rows with most 0's
        move_to_exe = 0
        max_zeros = 0
        for i in range(len(puzzle) * 2):
            score = count_zeros(i, puzzle)
            if score > max_zeros:
                max_zeros = score
                move_to_exe = i
        if max_zeros == 0:
            return moveset
        moveset.append(move_to_exe)
        if move_to_exe < len(puzzle):
            puzzle[move_to_exe] = [0 if y == 1 else 1 for y in puzzle[move_to_exe]]
        else:
            index = move_to_exe - len(puzzle)
            for i in range(len(puzzle)):
                puzzle[i][index] = 0 if puzzle[i][index] == 1 else 1
        
def count_zeros(move, puzzle):
    count = 0
    # Row toggle
    if move < len(puzzle):
        for i in puzzle[move]:
            count += 1 if i == 0 else 0
    else:
        index = move - len(puzzle)
        for row in puzzle:
            count += 1 if row[index] == 0 else 0
    return count

# UGH that solution is so BASIC! Greedy execution? Lame. I perfer the BF tree search below.

"""
# Use BFS?
def find_solution(puzzle):
    fringe = [([], puzzle)]
    while (True): # We should always find a solution for any configuration?
        
        (moveset, current_state) = fringe.pop()
        
        # Test if current state is a solution
        valid = True
        for x in range(len(current_state)):
            if 0 in current_state[x]:
                valid = False
                break
        if valid:
            return moveset
        
        # If state is not solution then we generate successor states add to fringe queue
        successors = generate_successors(moveset, current_state)
        for s in successors:
            fringe.insert(0, s)
            
    
    
# This function takes a moveset and a puzzle and returns all the possible successors for that puzzle
def generate_successors(move_list, puzzle):
    successors = []
    for x in range(len(puzzle) * 2):
        
        new_state = copy.deepcopy(puzzle)
        new_move_list = move_list[:]
        new_move_list.append(x)
        
        # If x < len(puzzle) we toggle a row
        if x < len(puzzle):
            new_state[x] = [1 if y == 0 else 0 for y in new_state[x]]
            successors.append((new_move_list, new_state))
        
        # Else toggle column
        else:
            index = x - len(puzzle)
            for i in range(len(puzzle)):
                new_state[i][index] = 0 if new_state[i][index] == 1 else 1
            successors.append((new_move_list, new_state))
            
    return successors
"""

def find_solution(puzzle):
    moves = set()
    n = len(puzzle)
    zeros = {(i, n + j) for i, row in enumerate(puzzle) for j, v in enumerate(row) if v == 0}
    if not zeros: return []
    def get():
        v = None
        if len(moves) == 0: return zeros.pop()
        for r, c in zeros:
            if r in moves or c in moves:
                if r in moves and c in moves: continue
                v = (r, c)
                zeros.remove(v)
                return v
        if v is None: return zeros.pop()
    while zeros:
        r, c = get()
        if r not in moves:
            moves.add(r)
            for k in range(n, 2 * n):
                if k == c: continue
                if (r, k) in zeros: zeros.remove((r, k))
                else: zeros.add((r, k))
        elif c not in moves:
            moves.add(c)
            for k in range(n):
                if k == r: continue
                if (k, c) in zeros: zeros.remove((k, c))
                else: zeros.add((k, c))

    return list(moves)


# returns a sequence of row/column toggles to solve the puzzle
# - Examples: 
#   - [3, 7]
#   - [0, 5, 4, 7]
def find_solution(puzzle):
    first_column = [i for i in range(len(puzzle))  if puzzle[i][0] == 0]
    value = 1 if 0 in first_column else 0
    first_row = [i + len(puzzle) for i in range(len(puzzle)) if puzzle[0][i] == value]
    return first_row + first_column


# returns a sequence of row/column toggles to solve the puzzle
# - Examples: 
#   - [3, 7]
#   - [0, 5, 4, 7]
def find_solution(puzzle):
    res = []
    first_column = [i for i in range(len(puzzle))  if puzzle[i][0] == 0]
    first_row = [i + len(puzzle) for i in range(len(puzzle)) if puzzle[0][i] == 1] if 0 in first_column else [i + len(puzzle) for i in range(len(puzzle)) if puzzle[0][i] == 0] 
    return first_row + first_column


def flip_row(puzzle, i):
    puzzle[i] = list(map(lambda cell: abs(cell - 1), puzzle[i]))

def flip_col(puzzle, i):
    for row in puzzle:
        row[i] = abs(row[i] - 1)

def find_solution(puzzle):
    result = []
    n = len(puzzle)
    
    for i in range(1,n):
        if puzzle[i] != puzzle[i-1]:
            flip_row(puzzle, i)
            result.append(i)

    for i in range(n):
        if puzzle[0][i] != 1:
            flip_col(puzzle, i)
            result.append(i+n)

    return result