# -*- coding: utf-8 -*- # Verification, en Python pur, des enonces de la partie "Portee 1" de la note sur le coin 2x2. # Aucun module externe. Parametres fixes ci-dessous. Duree totale : environ 4 minutes. # Motif P = [[1,0],[1,1]] : lignes i> l) << l == m def copies(x, y, w): """liste des copies (c, d) de la paire x au-dessus de y""" L = [] for c in range(w): if (x >> c) & 1 and (y >> c) & 1: for d in range(c + 1, w): if (y >> d) & 1 and not (x >> d) & 1: L.append((c, d)) return L def sans_copie(rows): return all(R(rows[i], rows[j]) for i in range(len(rows)) for j in range(i + 1, len(rows))) def portee1(rows): n = len(rows) return all(R(rows[i], rows[j]) for i in range(n) for j in range(i + 2, n)) def hi(v, a): return (v >> a) << a def lo(v, a): return v & ((1 << a) - 1) def poids(v): return bin(v).count('1') def matrice_portee1(rng, n, w, pas): rows = [0] * n for _ in range(pas): i = rng.randrange(n); c = rng.randrange(w) old = rows[i] if (old >> c) & 1: rows[i] = old - (1 << c) else: rows[i] = old + (1 << c) if not portee1(rows): rows[i] = old return rows # ---------------------------------------------------------------- auto-test assert R(0b01, 0b11) is False # x = {0}, y = {0, 1} : copie sur (0, 1) assert R(0b11, 0b01) and R(0b10, 0b11) and R(0, 0b111) assert copies(0b01, 0b11, 2) == [(0, 1)] and copies(0b001, 0b111, 3) == [(0, 1), (0, 2)] assert hi(0b10110, 2) == 0b10100 and lo(0b10110, 2) == 0b10 and poids(0b10110) == 3 assert sans_copie([0b111, 0b110, 0b100]) and not sans_copie([0b001, 0b011]) print("Auto-test arithmetique : correct", flush=True) bilan = [] rng = random.Random(GRAINE) # ---------------------------------------------------------------- test 1 # En portee 1, chaque couple de colonnes porte au plus une copie. t0 = time.time(); vus = 0; pire = 0; affiche = t0 while time.time() - t0 < DUREE: n = rng.randint(4, 9); w = rng.randint(3, 9) rows = matrice_portee1(rng, n, w, rng.randint(30, 300)); vus += 1 compte = {} for i in range(n - 1): for cd in copies(rows[i], rows[i + 1], w): compte[cd] = compte.get(cd, 0) + 1 if compte: pire = max(pire, max(compte.values())) if time.time() - affiche > 10: affiche = time.time(); print(" test 1 :", vus, "matrices", flush=True) ok1 = pire <= 1 print("Test 1 (une copie au plus par couple de colonnes) :", vus, "matrices de portee 1, maximum observe", pire, "->", "CORRECT" if ok1 else "ECHEC", flush=True) bilan.append(("une copie au plus par couple de colonnes en portee 1", vus, ok1)) # ---------------------------------------------------------------- test 2 # Lemme de recollement : si u R x, u R y, et si la partie de x a gauche de la coupe est vide # ou a son dernier element dans y, alors u R (partie gauche de x + partie droite de y). t0 = time.time(); cas = 0; ech = 0; affiche = t0 while time.time() - t0 < DUREE: w = rng.randint(2, 10); u = rng.getrandbits(w); x = rng.getrandbits(w); y = rng.getrandbits(w) if not (R(u, x) and R(u, y)): continue for a in range(w + 1): l = lo(x, a) if l == 0 or (y >> (l.bit_length() - 1)) & 1: cas += 1 if not R(u, l | hi(y, a)): ech += 1 if time.time() - affiche > 10: affiche = time.time(); print(" test 2 :", cas, "cas", flush=True) ok2 = ech == 0 print("Test 2 (lemme de recollement) :", cas, "cas, echecs", ech, "->", "CORRECT" if ok2 else "ECHEC", flush=True) bilan.append(("lemme de recollement", cas, ok2)) # ---------------------------------------------------------------- test 3 # Theoreme de reparation en treillis avec ajouts, forme generale. # B_i : partie de r_i compatible, comme ligne du haut, avec tout r_j, j >= i + 2. # N_i = B_i, ou B_i | hi(N_(i+1), a) si hi(B_i, a) est dans N_(i+1) et si lo(B_i, a) est vide ou finit dans N_(i+1). # Si les paires voisines (N_i, N_(i+1)) sont sans copie, toute la matrice doit l'etre. t0 = time.time(); tirages = 0; retenus = 0; ajouts = 0; ech = 0; affiche = t0 while time.time() - t0 < DUREE: n = rng.randint(4, 7); w = rng.randint(4, 7) rows = matrice_portee1(rng, n, w, rng.randint(30, 250)) adm = [] for i in range(n): els = [c for c in range(w) if (rows[i] >> c) & 1]; L = [] for masque in range(1 << len(els)): B = 0 for q in range(len(els)): if (masque >> q) & 1: B += 1 << els[q] if all(R(B, rows[j]) for j in range(i + 2, n)): L.append(B) adm.append(L) for _ in range(200): tirages += 1; N = [0] * n; N[n - 1] = rng.choice(adm[n - 1]); bon = True; aj = False for i in range(n - 2, -1, -1): B = rng.choice(adm[i]); s = B if rng.random() < 0.6: a = rng.randint(0, w); l = lo(B, a) if (hi(B, a) & ~N[i + 1]) == 0 and (l == 0 or (N[i + 1] >> (l.bit_length() - 1)) & 1): s = B | hi(N[i + 1], a) if s != B: aj = True if not R(s, N[i + 1]): bon = False; break N[i] = s if not bon: continue retenus += 1 if aj: ajouts += 1 if not sans_copie(N): ech += 1 if time.time() - affiche > 10: affiche = time.time(); print(" test 3 :", retenus, "reparations retenues", flush=True) ok3 = ech == 0 print("Test 3 (reparation en treillis avec ajouts) :", retenus, "reparations a paires voisines sans copie, dont", ajouts, "avec ajout ; sorties avec copie :", ech, "->", "CORRECT" if ok3 else "ECHEC", flush=True) bilan.append(("reparation en treillis avec ajouts", retenus, ok3)) # ---------------------------------------------------------------- test 4 # Verrou a une copie : exactement une copie, et l'argument de minoration D >= m + 1 controle # directement : pour tout choix d'une colonne intacte par bloc, les lignes verrous forcent c, t dans x, # c, d dans y, puis d dans x, et la ligne {t} donne alors une copie sur (t, d). def verrou(m): k = m + 1; w = 4 * k + 3; c = 4 * k; t = c + 1; d = c + 2 def bloc(b): return sum(1 << q for q in range(b * k, (b + 1) * k)) U = 1 << t x = bloc(0) | bloc(1) | (1 << c) | (1 << t) y = bloc(2) | bloc(3) | (1 << c) | (1 << d) Zb = bloc(0) | (1 << c); Z4 = bloc(1) | (1 << t); Z2 = bloc(2) | (1 << c); Z3 = bloc(3) | (1 << d) rows = [U] * k + [x, y] + [Zb] * k + [Z4] * k + [Z2] * k + [Z3] * k return rows, w, (c, t, d), (U, x, y, Zb, Z4, Z2, Z3), k ok4 = True; tailles = [] for m in range(0, 7): rows, w, (c, t, d), (U, x, y, Zb, Z4, Z2, Z3), k = verrou(m) n = len(rows); nb = 0 for i in range(n): for j in range(i + 1, n): nb += len(copies(rows[i], rows[j], w)) if nb != 1 or copies(x, y, w) != [(c, d)] or n != 5 * m + 7 or w != 4 * m + 7: ok4 = False # les quatre forcages et la contradiction finale, sur les lignes d'origine f1 = (Zb & x) != 0 and (Zb >> c) & 1 and all(not (Zb >> q) & 1 for q in range(c + 1, w)) # Zb finit par c et rencontre x sous c f2 = (Z4 & x) != 0 and (Z4 >> t) & 1 and all(not (Z4 >> q) & 1 for q in range(t + 1, w)) f3 = (Z2 & y) != 0 and (Z2 >> c) & 1 and all(not (Z2 >> q) & 1 for q in range(c + 1, w)) f4 = (Z3 & y) != 0 and (Z3 >> d) & 1 f5 = U == (1 << t) and c < t < d if not (f1 and f2 and f3 and f4 and f5): ok4 = False tailles.append((n, w)) print("Test 4 (verrou a une copie, m = 0..6) : tailles", tailles, "->", "CORRECT" if ok4 else "ECHEC", flush=True) bilan.append(("verrou a une copie : une seule copie, structure de la minoration", 7, ok4)) # ---------------------------------------------------------------- test 5 # Famille emboitee : portee 1, m paires en conflit de distance 1, et l'ajout de p_i a x_i repare tout. def emboitee(k, m): h = k // 2; w = 2 * k + m L = sum(1 << q for q in range(k)) C = sum(1 << q for q in range(k, k + h)) | sum(1 << q for q in range(k + h + m, w)) p = [k + h + j for j in range(m)] rows = []; rep = [] for i in range(m): Py = sum(1 << p[j] for j in range(i, m)); Px = sum(1 << p[j] for j in range(i + 1, m)) rows += [C | Px, L | C | Py]; rep += [C | Py, L | C | Py] return rows, rep, w ok5 = True; vus5 = 0 for k in (2, 4, 6, 8, 10, 12): for m in (2, 3, 5, 8, 12): rows, rep, w = emboitee(k, m); vus5 += 1 mauvaises = [i for i in range(len(rows) - 1) if not R(rows[i], rows[i + 1])] cout = sum(poids(a) + poids(b) - 2 * poids(a & b) for a, b in zip(rows, rep)) if not (portee1(rows) and len(mauvaises) == m and sans_copie(rep) and cout == m): ok5 = False print("Test 5 (famille emboitee) :", vus5, "tailles ->", "CORRECT" if ok5 else "ECHEC", flush=True) bilan.append(("famille emboitee : portee 1, m conflits, reparee par m ajouts", vus5, ok5)) # ---------------------------------------------------------------- test 6 # Theoreme des deux gestes, portee 1 quelconque, de bas en haut. # (G1) retirer une colonne y de la fermeture verticale partant de la ligne a ou a+1 ; # (G2) remplacer U par U | hi(W, coupe) quand U n'a rien hors de W apres la coupe et que lo(U, coupe) est vide ou finit dans W. # On controle l'etat J apres chaque paire, et l'absence de copie a la fin. def fermeture(rows, r, y): n = len(rows); S = set([r]); bas = (1 << y) - 1; change = True while change: change = False for s_ in range(r + 1, n): if s_ not in S and (rows[s_] >> y) & 1: for t in S: if t < s_ and (rows[t] & rows[s_] & bas): S.add(s_); change = True; break return S t0 = time.time(); vus6 = 0; g1 = 0; g2 = 0; viol = 0; ech6 = 0; affiche = t0 while time.time() - t0 < DUREE: n = rng.randint(4, 9); w = rng.randint(4, 9) rows = matrice_portee1(rng, n, w, rng.randint(30, 300)) if sans_copie(rows): continue vus6 += 1 for a in range(n - 2, -1, -1): essais = 0 while not R(rows[a], rows[a + 1]): essais += 1; U = rows[a]; W = rows[a + 1] if essais > 40: c = copies(U, W, w)[0][0] for t in fermeture(rows, a + 1, c): rows[t] = rows[t] & ~(1 << c) g1 += 1; continue if rng.random() < 0.5: r = rng.choice([a, a + 1]) if rows[r] == 0: continue y = rng.choice([c for c in range(w) if (rows[r] >> c) & 1]) for t in fermeture(rows, r, y): rows[t] = rows[t] & ~(1 << y) g1 += 1 else: coupe = rng.randint(0, w); l = lo(U, coupe) if (hi(U, coupe) & ~W) == 0 and (l == 0 or (W >> (l.bit_length() - 1)) & 1) and (hi(W, coupe) & ~U) != 0: rows[a] = U | hi(W, coupe); g2 += 1 if not all(R(rows[i], rows[j]) for i in range(a, n) for j in range(i + 1, n)): viol += 1 if a >= 1 and not all(R(rows[a - 1], rows[j]) for j in range(a + 1, n)): viol += 1 if not sans_copie(rows): ech6 += 1 if time.time() - affiche > 10: affiche = time.time(); print(" test 6 :", vus6, "matrices", flush=True) ok6 = viol == 0 and ech6 == 0 and g2 > 0 print("Test 6 (deux gestes, de bas en haut) :", vus6, "matrices,", g1, "gestes G1,", g2, "gestes G2 ; etat viole :", viol, "; sorties avec copie :", ech6, "->", "CORRECT" if ok6 else "ECHEC", flush=True) bilan.append(("theoreme des deux gestes (retraits par fermeture, recollement)", vus6, ok6)) print("", flush=True) print("================ RECAPITULATIF ================", flush=True) for nom, nb, ok in bilan: print(("CORRECT " if ok else "ECHEC ") + "| " + nom + " | " + str(nb) + " cas", flush=True) print("Tous les tests sont corrects." if all(b[2] for b in bilan) else "AU MOINS UN TEST A ECHOUE.", flush=True) try: input("Appuyez sur Entree pour fermer...") except EOFError: pass