Theory: Diagonalise a table

Build the diagonal string that differs from every row of a table.

What to build

A program that builds g by flipping the diagonal of a square table of bits, then shows where g differs from each row.

Requirements

  • Print g = BITS.
  • Then, for each row i, print row i differs at j, where j is the first position where row i and g differ.

Input

Line 1: m. Then m rows, each a string of m bits.

Output

m + 1 lines.

Constraints

1 ≤ m ≤ 20.

Example

Input:

3
000
010
110

Output:

g = 101
row 0 differs at 0
row 1 differs at 0
row 2 differs at 1

Why it works

g differs from row i at least at position i by construction, so g can never equal any row: the heart of every diagonal argument.

Examples

Example 1 · Input
3
000
010
110
Expected output
g = 101
row 0 differs at 0
row 1 differs at 0
row 2 differs at 1
Example 2 · Input
2
11
00
Expected output
g = 01
row 0 differs at 0
row 1 differs at 1

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

g[i] is the opposite of row i's i-th bit.

Hint 2

For each row, scan from the left for the first position where it differs from g.

Solution

Show one correct solution (try it yourself first)
m = int(input())
rows = [input().strip() for _ in range(m)]
g = "".join("1" if rows[i][i] == "0" else "0" for i in range(m))
print("g =", g)
for i, row in enumerate(rows):
    j = next(k for k in range(m) if row[k] != g[k])
    print(f"row {i} differs at {j}")

Lesson: Decidability and the halting problem →