# 60 Seconds

When you connect you are greeted with:

```
$ nc pwn.institute 22527
a b c d e f g h
1 0 0 1 1 1 0 0 1
2 1 1 1 1 0 0 1 0
3 1 0 1 1 1 0 1 0
4 0 1 1 0 0 0 0 1
5 1 1 1 1 0 1 0 0
6 0 1 0 1 0 1 0 1
7 1 1 0 0 0 1 1 1
8 0 1 1 0 0 1 1 1

>
```

And it's basically a game of Lights Out. You put in a coordinate and the bits(lights) flip in the row/column you target. The goal is to "disarm the bomb" in less than 60 seconds.

My approach was to write a solver for the game. And the heuristinc for the solver was target the fileld where we have the highest count of 0s for a field(in it's row/column) that is an odd number. Found the solution for this in a math paper of sorts(link: [http://www.iespravia.com/rafa/luces/Lights.pdf](http://www.iespravia.com/rafa/luces/Lights.pdf), page 24):

> Solving Flip in its version All, i.e. altering all the squares in the rectangle, is very easy. The
> only thing we have to do is to select all the squares in any row or column, as long as they are an
> odd number. If the rectangle has even dimensions, the only solution will be selecting all the
> squares.

The solver accepts an imput as follows:
```
1 0 0 1 1 1 0 0 1
2 1 1 1 1 0 0 1 0
3 1 0 1 1 1 0 1 0
4 0 1 1 0 0 0 0 1
5 1 1 1 1 0 1 0 0
6 0 1 0 1 0 1 0 1
7 1 1 0 0 0 1 1 1
8 0 1 1 0 0 1 1 1
```

Discards the row for enumeration and populates the matrix. Then solves it and outputs the solution step-by-step.

For the above input, the solution is:

```
b3
c1
f2
h7
d2
d3
f3
d5
e1
e2
b6
f6
f4
e4
e8
c7
e7
e5
a4
g5
g4
h4
a8
h8
```

Here's the solver code:

=> bits-out.py
```python
#!/usr/bin/env python3

# Just an example, will be read in at runtime.
matrix = [
[1, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 1]
]

# Fancy way of output for the matrix state, the way it is in the challenge.
def print_matrix(a):
abc = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
print(" " + " ".join(abc))
for x in range(0, 8):
print(" " + str(x+1) + " " + \
" ".join(str(v) for v in a[x]))
print()

# Flip the bits for the y row and x column.
# Used x and y for clarity same as the Cartesian coordinate system.
def flip(a, y, x):
b = [row[:] for row in a]
for j in range(0, 8):
for i in range(0, 8):
if j == y or i == x:
b[j][i] = (b[j][i] + 1) % 2
return b

# Calls the above, we just pass the imput as in the challenge.
# ie. "b5".
def coord_flip(a, coord):
x = ord(coord[0]) - ord('a')
y = ord(coord[1]) - ord('1')
return flip(a, y, x)

# Calculate the number of 0s in the matrix
def heuristic(a, j, i):
sum = 0
for y in range(0, 8):
for x in range(0, 8):
if (j == y or i == x) and a[y][x] == 0:
sum = sum + 1
return sum

# Gives us the next move based on the heuristic:
# The coord with the max odd count of 0s in its row/column.
def make_heuristic(a):
b = [row[:] for row in a]
max_odd = 1
max_odd_move = ""
for y in range(0, 8):
for x in range(0, 8):
c = flip(b, y, x)
curr = heuristic(c, y, x)
if (curr % 2 == 1) and curr > max_odd:
max_odd = curr
max_odd_move = yx_to_coord(y, x)
return max_odd_move

# Check if all are 0s.
def matrix_check(a):
for y in range(0, 8):
for x in range(0, 8):
if a[y][x] == 1:
return False
return True

# return the required input for the coord as the challenge accepts it for a y, x coord
def yx_to_coord(y, x):
return chr(ord('a') + x) + chr(ord('1') + y)

# Read in the initail matrix.
count = 0
while count < 8:
line = input()
row = line.split()
row = row[1:]
matrix[count] = [int(i) for i in row]
count = count + 1

# Print was used to test out the solution manually, thus commented out.
while True:
# print_matrix(matrix)
coord = make_heuristic(matrix)
print(coord)
matrix = coord_flip(matrix, coord)
# coord = input("> ")
# Exit if no input or q
# if coord == "q" or coord == "":
# exit(1)
if matrix_check(matrix):
# print("Solved!")
exit(1)
```

Connected, pasted the initial state to the solver, typed in the steps and voila.

```
$ nc pwn.institute 22527
a b c d e f g h
1 0 0 1 1 1 0 0 1
2 1 1 1 1 0 0 1 0
3 1 0 1 1 1 0 1 0
4 0 1 1 0 0 0 0 1
5 1 1 1 1 0 1 0 0
6 0 1 0 1 0 1 0 1
7 1 1 0 0 0 1 1 1
8 0 1 1 0 0 1 1 1

> b3
a b c d e f g h
1 0 1 1 1 1 0 0 1
2 1 0 1 1 0 0 1 0
3 0 1 0 0 0 1 0 1
4 0 0 1 0 0 0 0 1
5 1 0 1 1 0 1 0 0
6 0 0 0 1 0 1 0 1
7 1 0 0 0 0 1 1 1
8 0 0 1 0 0 1 1 1

> c1
a b c d e f g h
1 1 0 0 0 0 1 1 0
2 1 0 0 1 0 0 1 0
3 0 1 1 0 0 1 0 1
4 0 0 0 0 0 0 0 1
5 1 0 0 1 0 1 0 0
6 0 0 1 1 0 1 0 1
7 1 0 1 0 0 1 1 1
8 0 0 0 0 0 1 1 1

> f2
a b c d e f g h
1 1 0 0 0 0 0 1 0
2 0 1 1 0 1 1 0 1
3 0 1 1 0 0 0 0 1
4 0 0 0 0 0 1 0 1
5 1 0 0 1 0 0 0 0
6 0 0 1 1 0 0 0 1
7 1 0 1 0 0 0 1 1
8 0 0 0 0 0 0 1 1

> h7
a b c d e f g h
1 1 0 0 0 0 0 1 1
2 0 1 1 0 1 1 0 0
3 0 1 1 0 0 0 0 0
4 0 0 0 0 0 1 0 0
5 1 0 0 1 0 0 0 1
6 0 0 1 1 0 0 0 0
7 0 1 0 1 1 1 0 0
8 0 0 0 0 0 0 1 0

> d2
a b c d e f g h
1 1 0 0 1 0 0 1 1
2 1 0 0 1 0 0 1 1
3 0 1 1 1 0 0 0 0
4 0 0 0 1 0 1 0 0
5 1 0 0 0 0 0 0 1
6 0 0 1 0 0 0 0 0
7 0 1 0 0 1 1 0 0
8 0 0 0 1 0 0 1 0

> d3
a b c d e f g h
1 1 0 0 0 0 0 1 1
2 1 0 0 0 0 0 1 1
3 1 0 0 0 1 1 1 1
4 0 0 0 0 0 1 0 0
5 1 0 0 1 0 0 0 1
6 0 0 1 1 0 0 0 0
7 0 1 0 1 1 1 0 0
8 0 0 0 0 0 0 1 0

> f3
a b c d e f g h
1 1 0 0 0 0 1 1 1
2 1 0 0 0 0 1 1 1
3 0 1 1 1 0 0 0 0
4 0 0 0 0 0 0 0 0
5 1 0 0 1 0 1 0 1
6 0 0 1 1 0 1 0 0
7 0 1 0 1 1 0 0 0
8 0 0 0 0 0 1 1 0

> d5
a b c d e f g h
1 1 0 0 1 0 1 1 1
2 1 0 0 1 0 1 1 1
3 0 1 1 0 0 0 0 0
4 0 0 0 1 0 0 0 0
5 0 1 1 0 1 0 1 0
6 0 0 1 0 0 1 0 0
7 0 1 0 0 1 0 0 0
8 0 0 0 1 0 1 1 0

> e1
a b c d e f g h
1 0 1 1 0 1 0 0 0
2 1 0 0 1 1 1 1 1
3 0 1 1 0 1 0 0 0
4 0 0 0 1 1 0 0 0
5 0 1 1 0 0 0 1 0
6 0 0 1 0 1 1 0 0
7 0 1 0 0 0 0 0 0
8 0 0 0 1 1 1 1 0

> e2
a b c d e f g h
1 0 1 1 0 0 0 0 0
2 0 1 1 0 0 0 0 0
3 0 1 1 0 0 0 0 0
4 0 0 0 1 0 0 0 0
5 0 1 1 0 1 0 1 0
6 0 0 1 0 0 1 0 0
7 0 1 0 0 1 0 0 0
8 0 0 0 1 0 1 1 0

> b6
a b c d e f g h
1 0 0 1 0 0 0 0 0
2 0 0 1 0 0 0 0 0
3 0 0 1 0 0 0 0 0
4 0 1 0 1 0 0 0 0
5 0 0 1 0 1 0 1 0
6 1 1 0 1 1 0 1 1
7 0 0 0 0 1 0 0 0
8 0 1 0 1 0 1 1 0

> f6
a b c d e f g h
1 0 0 1 0 0 1 0 0
2 0 0 1 0 0 1 0 0
3 0 0 1 0 0 1 0 0
4 0 1 0 1 0 1 0 0
5 0 0 1 0 1 1 1 0
6 0 0 1 0 0 1 0 0
7 0 0 0 0 1 1 0 0
8 0 1 0 1 0 0 1 0

> f4
a b c d e f g h
1 0 0 1 0 0 0 0 0
2 0 0 1 0 0 0 0 0
3 0 0 1 0 0 0 0 0
4 1 0 1 0 1 0 1 1
5 0 0 1 0 1 0 1 0
6 0 0 1 0 0 0 0 0
7 0 0 0 0 1 0 0 0
8 0 1 0 1 0 1 1 0

> e4
a b c d e f g h
1 0 0 1 0 1 0 0 0
2 0 0 1 0 1 0 0 0
3 0 0 1 0 1 0 0 0
4 0 1 0 1 0 1 0 0
5 0 0 1 0 0 0 1 0
6 0 0 1 0 1 0 0 0
7 0 0 0 0 0 0 0 0
8 0 1 0 1 1 1 1 0

> e8
a b c d e f g h
1 0 0 1 0 0 0 0 0
2 0 0 1 0 0 0 0 0
3 0 0 1 0 0 0 0 0
4 0 1 0 1 1 1 0 0
5 0 0 1 0 1 0 1 0
6 0 0 1 0 0 0 0 0
7 0 0 0 0 1 0 0 0
8 1 0 1 0 0 0 0 1

> c7
a b c d e f g h
1 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0
4 0 1 1 1 1 1 0 0
5 0 0 0 0 1 0 1 0
6 0 0 0 0 0 0 0 0
7 1 1 1 1 0 1 1 1
8 1 0 0 0 0 0 0 1

> e7
a b c d e f g h
1 0 0 0 0 1 0 0 0
2 0 0 0 0 1 0 0 0
3 0 0 0 0 1 0 0 0
4 0 1 1 1 0 1 0 0
5 0 0 0 0 0 0 1 0
6 0 0 0 0 1 0 0 0
7 0 0 0 0 1 0 0 0
8 1 0 0 0 1 0 0 1

> e5
a b c d e f g h
1 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0
4 0 1 1 1 1 1 0 0
5 1 1 1 1 1 1 0 1
6 0 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0
8 1 0 0 0 0 0 0 1

> a4
a b c d e f g h
1 1 0 0 0 0 0 0 0
2 1 0 0 0 0 0 0 0
3 1 0 0 0 0 0 0 0
4 1 0 0 0 0 0 1 1
5 0 1 1 1 1 1 0 1
6 1 0 0 0 0 0 0 0
7 1 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 1

> g5
a b c d e f g h
1 1 0 0 0 0 0 1 0
2 1 0 0 0 0 0 1 0
3 1 0 0 0 0 0 1 0
4 1 0 0 0 0 0 0 1
5 1 0 0 0 0 0 1 0
6 1 0 0 0 0 0 1 0
7 1 0 0 0 0 0 1 0
8 0 0 0 0 0 0 1 1

> g4
a b c d e f g h
1 1 0 0 0 0 0 0 0
2 1 0 0 0 0 0 0 0
3 1 0 0 0 0 0 0 0
4 0 1 1 1 1 1 1 0
5 1 0 0 0 0 0 0 0
6 1 0 0 0 0 0 0 0
7 1 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 1

> h4
a b c d e f g h
1 1 0 0 0 0 0 0 1
2 1 0 0 0 0 0 0 1
3 1 0 0 0 0 0 0 1
4 1 0 0 0 0 0 0 1
5 1 0 0 0 0 0 0 1
6 1 0 0 0 0 0 0 1
7 1 0 0 0 0 0 0 1
8 0 0 0 0 0 0 0 0

> a8
a b c d e f g h
1 0 0 0 0 0 0 0 1
2 0 0 0 0 0 0 0 1
3 0 0 0 0 0 0 0 1
4 0 0 0 0 0 0 0 1
5 0 0 0 0 0 0 0 1
6 0 0 0 0 0 0 0 1
7 0 0 0 0 0 0 0 1
8 1 1 1 1 1 1 1 1

> h8
a b c d e f g h
1 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0
You made it in 24 moves and 46.168 seconds! Here is your reward: BCTF{cl0ck_is_tick1ng_but_we_are_fasterrr}
```