# qr_find.py - stand where the scanner stands: find the three squares
import random
N = 25
def build():
g = [[0] * N for _ in range(N)]
def finder(r, c):
for i in range(7):
for j in range(7):
frame = i in (0, 6) or j in (0, 6)
core = 2 <= i <= 4 and 2 <= j <= 4
g[r + i][c + j] = 1 if frame or core else 0
for r, c in [(0, 0), (0, N - 7), (N - 7, 0)]:
finder(r, c)
for k in range(8, N - 8):
g[6][k] = 1 if k % 2 == 0 else 0
g[k][6] = 1 if k % 2 == 0 else 0
random.seed(11)
for r in range(N):
for c in range(N):
near_finder = ((r < 8 and c < 8) or
(r < 8 and c >= N - 8) or
(r >= N - 8 and c < 8))
if not near_finder and r != 6 and c != 6 and random.random() < 0.45:
g[r][c] = 1
return g
def signature(cells):
"run lengths of a 7-cell line: the finder's fingerprint is 1:1:3:1:1"
runs, cur, n = [], cells[0], 1
for v in cells[1:]:
if v == cur:
n += 1
else:
runs.append(n)
cur, n = v, 1
runs.append(n)
return runs
def find_finders(g):
hits = [] # (row, col) of signature hits
for r in range(N): # horizontal sweep
for c in range(N - 6):
win = g[r][c:c + 7]
if win[0] == 1 and signature(win) == [1, 1, 3, 1, 1]:
hits.append((r, c + 3))
for c in range(N): # vertical sweep
for r in range(N - 6):
win = [g[r + k][c] for k in range(7)]
if win[0] == 1 and signature(win) == [1, 1, 3, 1, 1]:
hits.append((r + 3, c))
clusters = [] # group nearby hits
for h in sorted(hits):
for cl in clusters:
if abs(h[0] - cl[0][0]) <= 1 and abs(h[1] - cl[0][1]) <= 1:
cl.append(h)
break
else:
clusters.append([h])
solid = [cl for cl in clusters if len(cl) >= 4] # one hit = coincidence
return [tuple(round(sum(p[i] for p in cl) / len(cl)) for i in range(2))
for cl in solid]
g = build()
first = next((r, c) for r in range(N) for c in range(N - 6)
if g[r][c] == 1 and signature(g[r][c:c + 7]) == [1, 1, 3, 1, 1])
print(f"signature found at row {first[0]}: "
f"{' '.join(map(str, signature(g[first[0]][first[1]:first[1]+7])))}")
squares = find_finders(g)
print(f"squares found: {len(squares)}")
for r, c in sorted(squares):
print(f" corner center at (row {r}, col {c})")
empty = {(3, 3), (3, N - 4), (N - 4, 3)} - set(squares)
if len(squares) == 3:
print("missing corner: the one WITHOUT a square -> orientation locked")
# damage test: scribble on random data cells
random.seed(99)
scratched = 0
while scratched < 30:
r, c = random.randrange(N), random.randrange(N)
if (r, c) not in {(3, 3), (3, N - 4), (N - 4, 3)}:
g[r][c] ^= 1
scratched += 1
after = find_finders(g)
print(f"after scratching 30 data cells: squares found = {len(after)}")
# worse: erase one landmark completely
for i in range(7):
for j in range(7):
g[i][j] = 0
lost = find_finders(g)
print(f"after erasing the top-left square: squares found = {len(lost)}")