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}")