Cum scrii un program care găsește o submatrice într-o matrice „pușcă” fără erori la terminarea execuției?

Salutare, dragi pasionați de programare și logică! 💡 Azi ne aruncăm cu capul înainte într-o provocare ce poate părea la prima vedere o simplă joacă, dar care, odată abordată cu seriozitate, ne învață principii esențiale despre robustețe, eficiență și, mai ales, cum să evităm acele mesaje enervante de „programul s-a oprit neașteptat”. Vorbim despre crearea unui program capabil să găsească o submatrice într-o matrice „pușcă”, totul fără erori la terminarea execuției. Sună interesant, nu-i așa?

### Ce Este o Matrice „Pușcă” și De Ce Ne Preocupă?

Termenul „matrice pușcă” nu este unul academic, standardizat în lumea informaticii. Însă, contextul sugerează că vorbim despre o matrice rară (sau *sparse matrix* în engleză). Ce înseamnă asta? Imaginăm-ne o foaie de calcul imensă, plină de zerouri, cu doar câteva celule ici și colo care conțin valori diferite de zero. Aceasta este o matrice rară. Dacă am reprezenta o astfel de matrice în mod tradițional (adică un tablou bidimensional plin cu toate zerourile), am irosi enorm de multă memorie. Plus, operațiile pe o astfel de matrice ar fi lentă, deoarece am procesa o mulțime de date irelevante.

De ce ne preocupă? Ei bine, în domenii precum analiza rețelelor sociale, inteligența artificială, procesarea imaginilor sau simulările științifice, matricile rare sunt la ordinea zilei. Optimizarea stocării și procesării lor devine crucială pentru performanța aplicației. 🚀

### Ce Căutăm, de Fapt? Definirea Submatricii

O submatrice este, pur și simplu, o parte mai mică, continuă, dintr-o matrice mai mare. Gândiți-vă la ea ca la o „fereastră” dreptunghiulară care se deplasează peste matricea principală. Scopul nostru este să identificăm locația (sau locațiile) în care o anumită submatrice „țintă” se regăsește în cadrul matricei noastre „pușcă”. Această identificare poate însemna fie o potrivire exactă a valorilor, fie respectarea unui anumit model (de exemplu, o submatrice cu toate elementele non-zero, sau una cu o sumă specifică). Pentru a păstra lucrurile la un nivel pragmatic, ne vom concentra pe potrivirea exactă a valorilor.

### Capcane și Pericole: De Ce Apar Erorile la Execuție?

Înainte să ne avântăm în scrierea codului, e vital să înțelegem de ce un program s-ar putea „rupe”. Scopul nostru este să creăm o aplicație care să ruleze impecabil, fără acele mesaje frustrante de „crash”. Iată câteva dintre cele mai comune cauze ale erorilor de execuție, în special când vorbim de manipularea matricilor:

1. **Index Out of Bounds (Indecși în Afara Limitelor):** ⚠️ Acesta este, probabil, cel mai frecvent tip de eroare. Încercăm să accesăm un element la o adresă (rând, coloană) care nu există în matrice. De exemplu, într-o matrice de 5×5, încercăm să accesăm elementul de la (6, 2). Boom! Programul se oprește.
2. **Memorie Insuficientă (Out of Memory):** Dacă reprezentăm matricea rară ineficient sau dacă încercăm să procesăm o matrice gigantică fără a optimiza utilizarea memoriei, putem epuiza resursele sistemului.
3. **Bucle Infinite (Infinite Loops):** O eroare de logică în buclele de parcurgere poate duce la o rulare continuă a programului, fără a ajunge vreodată la o concluzie, blocând resursele.
4. **Date de Intrare Invalide:** Ce se întâmplă dacă utilizatorul specifică o submatrice mai mare decât matricea principală? Sau dimensiuni negative? Programul nostru trebuie să anticipeze și să gestioneze astfel de scenarii, nu să cedeze sub presiunea lor.
5. **Neatenție la Cazul Particular al Matricilor Rare:** Dacă tratăm o matrice rară ca pe una densă (completă), pierdem avantajele specifice structurii rare, iar algoritmul devine ineficient și, implicit, mai susceptibil la probleme de performanță.

### Primul Pas Crucial: Reprezentarea Eficientă a Matricilor Rare

Cheia optimizării performanței și a evitării erorilor într-o matrice rară stă în modul în care o reprezentăm în memorie. Dacă am stoca fiecare zero, am avea un consum uriaș de resurse. Iată câteva abordări eficiente:

1. **List of Lists (LIL):** Fiecare rând este o listă de perechi (coloană, valoare).
2. **Dictionary of Keys (DOK):** O structură de tip dicționar unde cheile sunt tupluri (rând, coloană), iar valorile sunt elementele non-zero. `{(r, c): valoare}`. Aceasta este o abordare intuitivă și relativ ușor de implementat pentru exemplul nostru, ideală pentru adăugarea/modificarea elementelor.
3. **Coordinate List (COO):** O listă de tupluri (rând, coloană, valoare) pentru fiecare element non-zero. Similar cu DOK, dar poate fi mai eficientă pentru anumite operații.
4. **Compressed Sparse Row (CSR) / Column (CSC):** Acestea sunt mai complexe, dar extrem de eficiente pentru operații matematice pe matrici mari și rare. Necesită o înțelegere mai profundă a structurilor de date.

Pentru scopul nostru – găsirea unei submatricii – reprezentarea de tip DOK sau COO este suficient de simplă și eficientă conceptual. Să presupunem că vom folosi un dicționar Python, unde cheia este o pereche `(rând, coloană)`, iar valoarea este elementul corespunzător.

„`python
# Exemplu de matrice „pușcă” (rară) reprezentată ca DOK
matrice_rara = {
(0, 2): 5,
(1, 0): 10,
(1, 3): 12,
(2, 2): 8,
(3, 1): 3,
(3, 3): 7
}
# Dimensiunile reale ale matricei (e.g., 4×4)
num_randuri_matrice = 4
num_coloane_matrice = 4

# Submatricea pe care o căutăm
submatrice_cautata = {
(0, 0): 10,
(0, 1): 12
}
# Dimensiunile submatricii căutate (2×2)
num_randuri_sub = 1 # doar un rând
num_coloane_sub = 2 # două coloane
„`
În exemplul de mai sus, am declarat `submatrice_cautata` ca fiind `(0,0):10` și `(0,1):12`. Aici, `(0,0)` și `(0,1)` sunt *indecși relativi* în cadrul submatricii. Când căutăm, va trebui să translatăm acești indecși la indecși absoluți în matricea principală.

### Algoritmul Robus de Căutare a Submatricii: Pas cu Pas

Acum, să construim scheletul logic al programului, punând accent pe programarea defensivă și gestionarea erorilor.

#### 1. Validarea Intrărilor 🛡️

Primul pas înainte de orice calcul este să ne asigurăm că datele de intrare sunt valide. Un program robust *nu* presupune că utilizatorul îi va furniza întotdeauna date corecte.

* **Verifică Dimensiunile:**
* Sunt dimensiunile matricei principale și ale submatricii non-negative?
* Este submatricea mai mică sau egală ca dimensiune cu matricea principală? (adică `num_randuri_sub <= num_randuri_matrice` și `num_coloane_sub <= num_coloane_matrice`)
* Sunt valorile din matrici de tipul așteptat (e.g., numerice)?
* **Verifică Matricea Goală:** Ce se întâmplă dacă matricea principală sau submatricea căutată este goală? Decidem cum să tratăm acest caz (de obicei, returnăm o listă goală de potriviri).

Dacă una dintre aceste condiții nu este îndeplinită, programul ar trebui să ridice o eroare (excepție) explicită sau să returneze un mesaj de eroare, indicând problema. Aceasta este o formă de prevenire a erorilor la terminare, deoarece prindem problema înainte ca algoritmul de căutare să înceapă și să genereze o eroare ambiguă.

„`python
def valideaza_input(matrice_rara, num_rand_m, num_col_m, submatrice_cautata, num_rand_s, num_col_s):
if not isinstance(matrice_rara, dict) or not isinstance(submatrice_cautata, dict):
raise TypeError(„Matricea și submatricea trebuie să fie dicționare.”)
if num_rand_m <= 0 or num_col_m <= 0 or num_rand_s <= 0 or num_col_s num_rand_m or num_col_s > num_col_m:
raise ValueError(„Submatricea nu poate fi mai mare decât matricea principală.”)
# Adăugați alte verificări specifice tipurilor de date sau valorilor
print(„✅ Datele de intrare au fost validate cu succes.”)
„`

#### 2. Strategia de Căutare Adaptată pentru Matricile Rare ⚙️

Cum găsim o submatrice într-o matrice rară?
Abordarea naivă ar fi să parcurgem fiecare celulă `(r, c)` din matricea principală ca potențial punct de plecare al submatricii și să verificăm dacă submatricea căutată se potrivește începând de acolo. Acest lucru ar implica o mulțime de verificări pentru zerouri, ceea ce este ineficient pentru o matrice rară.

O abordare mai inteligentă este să ne concentrăm pe elementele non-zero ale submatricii căutate.
**Ideea:** Iterăm prin *fiecare element non-zero* din matricea noastră rară. Fiecare astfel de element ar putea fi punctul de plecare al unui element non-zero din submatricea căutată. Apoi, verificăm dacă celelalte elemente non-zero din submatricea căutată se aliniază corect.

Algoritmul ar arăta cam așa:

„`python
def gaseste_submatrice_rara(matrice_rara, num_rand_m, num_col_m, submatrice_cautata, num_rand_s, num_col_s):
valideaza_input(matrice_rara, num_rand_m, num_col_m, submatrice_cautata, num_rand_s, num_col_s)

potriviri = []

# Iterăm prin fiecare element non-zero din matricea rară principală.
# Fiecare element (r_m, c_m, val_m) este un potențial punct de start pentru un element non-zero din submatrice.
for r_m, c_m in matrice_rara:
# Pentru fiecare element non-zero (r_s, c_s, val_s) din submatricea căutată
# încercăm să-l aliniem cu (r_m, c_m, val_m).
for r_s, c_s in submatrice_cautata:
if matrice_rara[(r_m, c_m)] == submatrice_cautata[(r_s, c_s)]:
# Am găsit un potențial punct de ancorare (match pentru un element non-zero).
# Calculăm punctul de origine (r_start, c_start) al submatricii candidate.
r_start = r_m – r_s
c_start = c_m – c_s

# Verificăm dacă submatricea candidate este în limitele matricei principale
if not (0 <= r_start <= num_rand_m – num_rand_s and
0 <= c_start <= num_col_m – num_col_s):
continue # Nu este în limite, trecem la următoarea încercare

# Acum verificăm dacă întreaga submatrice se potrivește
este_potrivire = True

# Pasul 1: Verificăm toate elementele non-zero din submatricea căutată
for sr, sc in submatrice_cautata:
# Coordonatele absolute în matricea principală
abs_r = r_start + sr
abs_c = c_start + sc

# Verificăm dacă se află în limite (deși am verificat deja intervalul general al r_start, c_start,
# e bine să fim defensivi aici)
if not (0 <= abs_r < num_rand_m and 0 <= abs_c < num_col_m):
este_potrivire = False
break

if matrice_rara.get((abs_r, abs_c), 0) != submatrice_cautata[(sr, sc)]:
este_potrivire = False
break

if not este_potrivire:
continue

# Pasul 2: Foarte important! Verificăm și elementele care *trebuie să fie zero* în matricea principală.
# Aceasta este esențială pentru matricile rare! Dacă submatricea căutată are un 0, iar matricea principală
# are un non-zero în acea poziție, atunci nu e o potrivire.

# Iterăm prin toate pozițiile din submatricea conceptuală
for r_offset in range(num_rand_s):
for c_offset in range(num_col_s):
abs_r = r_start + r_offset
abs_c = c_start + c_offset

# Dacă elementul (r_offset, c_offset) *nu* este în submatricea_cautata (adică e 0),
# dar în matricea_rara este non-zero, atunci nu este o potrivire.
if (r_offset, c_offset) not in submatrice_cautata and (abs_r, abs_c) in matrice_rara:
este_potrivire = False
break
if not este_potrivire:
break

if este_potrivire:
potriviri.append((r_start, c_start))
# Adăugăm punctul de pornire al submatricii găsite (colțul stânga sus)
# Pentru a evita duplicatele, am putea folosi un set sau o verificare suplimentară
# (deoarece o submatrice poate fi ancorată de mai multe elemente non-zero)

# Eliminăm duplicatele, deoarece aceeași submatrice poate fi găsită pornind de la diferite puncte de ancoră.
return list(set(potriviri))

„`

#### 3. Testarea Granițelor și Cazurilor Speciale ✨

Un program este robust doar dacă poate gestiona situațiile extreme. Testarea unitară este prietenul nostru cel mai bun aici.
* **Matrice Goală:** Ce se întâmplă dacă `matrice_rara` este un dicționar gol?
* **Submatrice Goală:** Ce se întâmplă dacă `submatrice_cautata` este goală? (în funcție de definiția noastră, am putea considera că o submatrice goală se găsește oriunde, sau nicăieri). Recomandarea ar fi să cerem ca ambele să aibă cel puțin un element.
* **Submatrice 1×1:** O singură celulă.
* **Matrice de 1×1:** Matricea principală este de doar o celulă.
* **Submatrice identică cu Matricea:** Când submatricea căutată este exact la fel ca matricea principală.
* **Fără Potriviri:** Când submatricea pur și simplu nu există în matricea principală.
* **Potriviri Multiple:** Când aceeași submatrice apare de mai multe ori.

„`python
# Exemplu de utilizare:
matrice_rara_mare = {
(0, 0): 1, (0, 1): 2, (0, 2): 0,
(1, 0): 3, (1, 1): 4, (1, 2): 0,
(2, 0): 0, (2, 1): 0, (2, 2): 5,
(3, 0): 1, (3, 1): 2, (3, 2): 0
} # Presupunem 4×3
num_randuri_mare = 4
num_coloane_mare = 3

submatrice_mica = {
(0, 0): 1,
(0, 1): 2
} # Presupunem 1×2
num_randuri_mica = 1
num_coloane_mica = 2

submatrice_nu_exista = {
(0, 0): 99
}
num_randuri_nu_exista = 1
num_coloane_nu_exista = 1

print(„nCăutăm submatricea mică:”)
print(gaseste_submatrice_rara(matrice_rara_mare, num_randuri_mare, num_coloane_mare, submatrice_mica, num_randuri_mica, num_coloane_mica))
# Rezultat așteptat: [(0,0), (3,0)]

print(„nCăutăm submatricea care nu există:”)
print(gaseste_submatrice_rara(matrice_rara_mare, num_randuri_mare, num_coloane_mare, submatrice_nu_exista, num_randuri_nu_exista, num_coloane_nu_exista))
# Rezultat așteptat: []

# Exemplu cu ValueError
try:
print(„nTestăm input invalid (submatrice mai mare):”)
gaseste_submatrice_rara(matrice_rara_mare, num_randuri_mare, num_coloane_mare, submatrice_mica, 5, 5)
except ValueError as e:
print(f”Eroare capturată: {e}”)
„`

#### 4. Performanța și Complexitatea Algoritmică 📈

Complexitatea algoritmului nostru depinde de numărul de elemente non-zero în matrici.
Dacă `N` este numărul de rânduri/coloane din matricea principală și `K_m` este numărul de elemente non-zero din matricea principală, iar `K_s` este numărul de elemente non-zero din submatricea căutată, algoritmul nostru:

* Iterează prin `K_m` elemente non-zero din matricea principală.
* Pentru fiecare, iterează prin `K_s` elemente non-zero din submatricea căutată.
* Apoi, verifică `num_rand_s * num_col_s` poziții pentru o potrivire completă.

Complexitatea este aproximativ `O(K_m * K_s * num_rand_s * num_col_s)`. Pentru matrici rare, `K_m` și `K_s` sunt mult mai mici decât `N*N`. Acest lucru este mult mai eficient decât `O(N^4)` sau `O(N^6)` pe care le-am obține cu o parcurgere naivă a matricilor dense.

> „Scrierea unui cod „fără erori la terminarea execuției” nu înseamnă să nu apară *niciodată* erori, ci să anticipezi unde pot apărea și să le gestionezi cu grație. A ignora validarea intrărilor și testarea cazurilor limită este echivalent cu a construi o casă fără fundație solidă: va arăta bine la exterior, dar se va prăbuși la primul vânt mai puternic. Datele arată că o bună acoperire a codului cu teste reduce costurile de mentenanță și crește fiabilitatea software-ului cu până la 50% pe termen lung.”

### Concluzie: Artizanatul Unui Cod Solid

Am parcurs un drum lung, de la înțelegerea conceptului de matrice „pușcă” (matrice rară) până la proiectarea unui algoritm robust pentru căutarea submatricelor, cu accent pe prevenirea erorilor la terminarea execuției. Cheile succesului sunt:
1. **Reprezentarea eficientă** a datelor.
2. **Validarea riguroasă a intrărilor**.
3. Un **algoritm bine gândit**, care profită de specificul problemei (raritatea matricei).
4. **Gestionarea excepțiilor** și a cazurilor limită.
5. **Testarea amănunțită**.

Scrierea unui program care să nu „crape” nu este doar o chestiune de noroc sau de talent pur. Este o disciplină, o artă a programării defensive. Este vorba despre a anticipa problemele, a le confrunta și a le rezolva înainte ca ele să devină erori frustrante pentru utilizatori. Făcând asta, nu doar că scriem cod funcțional, ci scriem cod *de încredere*. Iar în lumea software-ului, încrederea este valuta forte. Așa că, luați-vă instrumentele, testați cu zel și construiți aplicații de neclintit! ✨