# 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: EASY
Tags: Bit manipulation

Data structures

Ad-hoc
Skill types: Bit manipulation

Data structures

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:
		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
	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


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)


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


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