Modele de algoritmi in #Excel – Counting Elements (4)

Acest articol continuă seria de articole cu propuneri de rezolvare a algoritmilor clasici din informatică în Excel. În continuare voi explica și rezolva probleme specifice de la adresa: https://app.codility.com/programmers/lessons/4-counting_elements/

Algoritmii de pe Codility și poate de pe multe alte site-uri sunt adresați în special limbajelor de programare, Excelul nefiind un instrument dedicat rezolvării acestor tipuri de probleme, dar în versiunile de cloud Microsoft Excel 365 conține suficiente funcții care îmbinate pot rezolva probleme destul de complexe. În această serie de articole vreau și eu să văd până unde se poate ajunge.

Puțină teorie

În Excel sunt implementate foarte multe funcții de căutare, de la cele mai simple la combinații care permit abordarea vectorilor (celule de date) în diferite formate.

În primul rând pentru a răspund multor probleme de informatică trebuie să descompunem un șir de elemente în componentele sale, de cele mai multe ori pe baza unui delimitator.

În imagine câteva exemple de funcții de căutare și sortare uzuale în Excel 365:

Vă reamintesc că pentru apelarea dinamică a unui vector vom utiliza formatul Celula# în toate funcțiile din exemplu fiind referit vectorul A5# care presupune oricâte linii o fi având acesta, nefiind cunoscută din stard dimensiunea șirului de valori din A2.

Un aspect de noutate teoretică în abordarea acestui articol este generarea de tabele de date (matrici) cu ajutorul funcției MAKEARRAY():

în care avem parametrul 1 numărul de linii care să se genereze, parametrul 2, numărul de coloane și funcția LAMBDA aplicabilă, în care parametrul r este echivalent liniei curente din matrice iar c este echivalentul coloanei curente.

În acest articol referim algoritmul clasic Counting Elements care este o tehnică utilizată în informatică și în special în algoritmică pentru sortare și căutare. Acesta este utilizat pentru a număra numărul de apariții ale fiecărui element dintr-o colecție de date și pentru a efectua diverse operații pe baza acestor numărători. În primă lectură putem crede că ar fi vorba de un COUNTIF() pe un vector de valori pe baza unor valori unice.

În articolul Modele de algoritmi in #Excel – Vectori (2.2) am descris în ultimul update cum determinăm printr-o funcție numărul de apariții a fiecărui element.

Algoritmul Counting Elements este adesea utilizat ca parte a altor algoritmi mai complecși sau în combinație cu alte tehnici de algoritmă pentru a rezolva diverse probleme.

Să trecem la probleme!

Problema FrogRiverOne

Recunosc că până acum mi-a fost cel mai greu de înțeles ce ar dori să calculeze acest algoritm.

FrogRiverOne este o problemă clasică de algoritmă și este parte a algoritmului Counting Elements. Această problemă implică o broască care dorește să traverseze un râu folosind frunze care plutesc pe suprafața apei. Scopul nostru este să determinăm cea mai mică poziție pe malul râului (secunda) de unde broasca poate sări astfel încât să ajungă dincolo de râu într-un timp minim.

Mai specific, avem un râu cu o lățime dată (X) și un șir de numere (A) care reprezintă pozițiile frunzelor care plutesc pe suprafața râului. Fiecare număr din șir reprezintă o poziție pe malul râului, corespondent cu secunda / timpul necesar până când frunza ajunge la acea poziție. Broasca poate sări doar atunci când există cel puțin o frunză pe fiecare poziție a râului, de la 1 la X, unde X este lățimea râului.

De exemplu, având un râu de lățime 5 și șirul [1, 3, 1, 4, 2, 3, 5, 4], broasca poate traversa râul atunci când există frunze pe pozițiile 1, 2, 3, 4 și 5. Astfel, cel mai mic număr de pași necesari pentru ca broasca să traverseze râul este 5, iar aceasta poate sări de pe poziția 6 locul în care apare pentru prima dată valoarea 5, celelalte valori de la 1 la 5 fiind deja întâlnite până la acea secvență.

Pentru a realiza acest lucru, putem folosi un tabel de frecvență pentru a număra câte frunze avem pe fiecare poziție a râului. Apoi, parcurgem șirul de frunze și verificăm când toate pozițiile de pe malul râului sunt acoperite. Odată ce aceasta se întâmplă, găsim cea mai mică poziție de pe malul râului și returnăm acest rezultat.

Rezultate intermediare:

în C6: =SEQUENCE(;B1) am generat secvența de pași (1, X) care reprezintă lățimea râului.

în B7: =TRANSPOSE(B3#) am returnat șirul de numere (frunzele) în ordinea lor de apariție.

în C7 am realizat un tabel în care verific fiecare valoare din B7# și poziția sa în zona C6#. Fiecare linie din tabel reprezintă o secundă în acest algoritm.

Funcția pentru generare dinamică tabel:

=MAKEARRAY(COLUMNS($B$3#);$B$1;
     LAMBDA(r;c;
		LET(valc; INDEX($C$6#;;c);
		    valr; INDEX($B$7#;r);
			IF(valr=valc;1;0))))

în care folosesc funcția INDEX() pentru a aduce valoarea de pe linie și de pe coloană pentru a le compara ulterior. Dacă cele două valori X și frunza sunt egale atunci returnez 1, dacă nu 0.
În imagine un exemplu vizual:

Pasul următor este să determin numărul de apariții pe fiecare coloană în așa fel încât odată apărută valoarea 1 pe linia 1 să fie vizibilă și pe linia 2, ar dacă apare de două ori să se adune.

Practic pentru am mers pe abordarea de a folosi funcția BYCOL() cu SCAN() doar că cele două funcții nu se pot utiliza împreună în cadrul unui LET() cu alte valori dinamice. Și de aici au pornit exporările pentru a găsi o soluție. Salvarea a venit din articolul: Unable to use BYCOL and SCAN in the same formula

Așadar pentru a calcula pe coloană numărul de apariții a fiecărei valori, am folosit în M7: funcția:

=LET(n; ROWS(C7#);
     m; COLUMNS(C7#);
     rows; MAKEARRAY(n; m; LAMBDA(r;c; r));
     cols; MAKEARRAY(n; m; LAMBDA(r;c; c));
     MAP(rows; cols;
         LAMBDA(r;c;
            SUM(INDEX(C7#; 1; c):INDEX(C7#; r; c)) ))
   )

în care: n este numărul de linii ale tabelului inițial și m, numărul de coloane. După care realizez două tabele independente unul cu liniile și altul cu coloanele în așa fel încât să le pot parcurge cu MAP(). În partea de calcul fac o sumă pe două rezultate din INDEX() până la celălalt INDEX().

Din păcare versiunea aceasta este prea abstractă pentru a fi integrată mai tarziu într-o funcție finală, așa că am folosit mai jos versiunea un pic mai complexă.

Ca să pot determina linia (secunda) în care sunt acoperite toate pozițiile râului (X-urile), am folosit în V7 funcția: =BYROW(M7#;LAMBDA(r;IF(COUNTIF(r;0)=0;”x”;0))) în care identific linie cu linie dacă numărul de 0-uri (poziții neacoperite) este egal cu 0. Atunci marchez cu „x”. Poziția lui x pe această coloană rezultat este de fapt numărul secundei în care broasca poate traversa râul. În W7 determin secunda: =LET(poz; IFNA(MATCH(„x”;V7#;0);-1); IF(poz=-1;-1;poz-1)) în care MATCH() caută primul x în rezultatul din V7 apoi dacă nu se găsește nici un X înseamnă că problema este fără soluție de aceea trebuie să returneze, conform algoritmului, valoarea -1.

Alternativa la funcția din M7 este:

=LET(set; C7#; 
	m; COLUMNS(set); 
	seq; SEQUENCE(m;1);
	CUMULATE; LAMBDA(x; SCAN(0; x; LAMBDA(acc;item; acc+item)));
	DROP(REDUCE(0;seq; LAMBDA(acc;idx; HSTACK(acc; CUMULATE(INDEX(set;;idx)))));;1)
)

Având în vedere că funcția nu-mi aparține am lăsat întocmai numele variabilelor. În această funcție determinăm setul de valori ca rezultat din C7# după care calculăm în m numărul de coloane apoi generăm o secvență seq cu numărul de coloane m. Cheia este în variabila CUMULATE care declară un fel de funcție recursivă de scanare, utilizată în DROP-ul cu REDUCE din partea finală a LET-ului.

În mod cumulat funcția finală de rezolvare a problemei este:

=LET(Xs; SEQUENCE(;B1);
sir; TRANSPOSE(--TEXTSPLIT(B2;","));
tabi; MAKEARRAY(ROWS(sir);$B$1;LAMBDA(r;c;LET(valc; INDEX(Xs;;c);valr; INDEX(sir;r);IF(valr=valc;1;0))));
tabfin; LET(set; tabi;
m; COLUMNS(set);
seq; SEQUENCE(m;1);
CUMULATE; LAMBDA(x; SCAN(0; x; LAMBDA(acc;item; acc+item)));
DROP(REDUCE(0;seq; LAMBDA(acc;idx; HSTACK(acc; CUMULATE(INDEX(set;;idx)))));;1)
);
verif; BYROW(tabfin; LAMBDA(r; COUNT(FILTER(r;r=0))));
rezfin; LET(poz; IFNA(MATCH(0;verif;0);-1); IF(poz=-1;-1;poz-1));
rezfin)

în care:

• Xs este lățimea râului din B1;
• sir este A-ul, lista de valori / poziții în care cad frunzele în fiecare secundă;
• tabi este primul tabel de tip matrice în care avem fiecare frunză cu poziția ei, echivalentul tabelului din C7#;
• tabfin este matricea de calcul cumulativă a aparițiilor frunzelor la fiecare salt, echivalentul tabelului din M7;
• verif este variabila care calculează numărul de apariții ale lui 0 pentru fiecare linie din tabfin;
• rezfin este valoarea cea mai mică a secundei in care broasca poate traversa râul. Rezfin întoarce valoarea -1 în cazul în care nu sunt frunze pentru toate pozițiile în șirul specificat.

Problema PermCheck

Avem la dispoziție un șir A format din N numere întregi. Scopul este să determinăm dacă acest șir reprezintă o permutare validă a numerelor de la 1 la N.

O permutare validă înseamnă că șirul conține exact o dată fiecare număr întreg de la 1 la N, fără a exista duplicări și fără a lipsi vreun număr. În plus, ordinea numerelor în șir nu contează, astfel că o permutare validă poate avea numerele în orice ordine.

Pentru a rezolva această problemă, putem folosi o abordare simplă și eficientă. Vom construi un set care să conțină numerele de la 1 la N și vom parcurge șirul A, verificând dacă fiecare număr întreg este prezent în set. Dacă toate numerele de la 1 la N sunt prezente în șirul dat și nu există duplicări, atunci considerăm că șirul este o permutare validă și returnăm 1. În caz contrar, returnăm 0 pentru a indica că șirul nu este o permutare validă.

Această abordare are o complexitate a timpului de O(N), unde N reprezintă lungimea șirului dat A, deoarece trebuie să parcurgem șirul o singură dată și să verificăm fiecare element în set.

Personal am ales să rezolv problema prin includerea duplicatelor și în șirul original și în șirul de comparare, pentru a o face puțin mai complicată.

În exemplul meu, sir2 este o permutare (aceleași elemente ca și valoare și număr de apariții) a șirului 1. Șir 3 nu este o permutare pentru că lipsește valoarea 2, iar șir 3 nu are același număr de elemente ca Sir1.

Pentru a rezolva problema de permutări pentru două șiruri date folosind o singură funcție atunci putem folosi:

=LET(so; SORT(--TEXTSPLIT(A2;;","));
     sc; SORT(--TEXTSPLIT(A5;;","));
     IFS(SUM(--IFNA(so=sc;0))<>ROWS(so);0;SUM(--(so=sc))=ROWS(so);1))

în care so este șirul original iar sc este șirul de comparare. Ca funcție de verificare am folosit funcția IFS() pentru a determina în primă fază daca nummărul de linii a celor două șiruri este egal, apoi a doua condiție este de a verifica dacă fiecare linie a șirurilor, sortate crescător este identic. După cum observăm din imagine, în comparația S1 vs S3 vedem că valoarea 2 este lispă în Sir 3 ceea ce rezultă că S3 nu este o permutare de S1.

În practică PermCheck poate fi folosit pentru a verifica dacă un utilizator a ales dintr-o listă de valori toate opțiunile disponibile indiferent de ordinea lor. Rezolvarea mea corespunde și șirurilor cu valori unice.

Problema MaxCounters

MaxCounters este foarte asemănătoare cu FrogRiverOne doar că de data aceasta ni se solicită calcularea numărului maxim de apariții a unui element într-un total într-un anumit număr de iterații (N).

Pentru rezolvarea pas cu pas am descompus A-ul în C2# apoi am generat două secvențe pe orizontală și verticală, după care compar coloanele din rezultatele intermediare după care adaug valoarea 1 la cea anterioară.

Problema solicită determinarea maximului de apariții ale unui număr ceea ce în cazul nostru este de 4.

Funcția adaptată după același algormitm ca la FrogRiverOne este:

=LET(Xs; SEQUENCE(;B1);
    sir; TRANSPOSE(C2#);
    tabi; MAKEARRAY(ROWS(sir);$B$1;LAMBDA(r;c;LET(valc; INDEX(Xs;;c);valr;        INDEX(sir;r);IF(valr=valc;1;0))));
    tabfin; LET(set; tabi;
                m; COLUMNS(set);
                seq; SEQUENCE(m;1);
                CUMULATE; LAMBDA(x; SCAN(0; x; LAMBDA(acc;item; acc+item)));
                DROP(REDUCE(0;seq; LAMBDA(acc;idx; HSTACK(acc; CUMULATE(INDEX(set;;idx)))));;1)
);
 MAX(tabfin))

în care tabfin calculează tabelul echivalent din C5.

Problema MissingInteger

Problema MissingInteger implică găsirea celui mai mic număr întreg pozitiv care lipsește dintr-un șir dat de numere întregi. În cazul în care șirul este consecutiv, atunci va returna următoarea valoare întreagă consecutivă.

În rezolvarea pas cu pas:

în B2: am descompus șirul original și l-am sortat creascător: =SORT(UNIQUE((–TEXTSPLIT(B1;;”,”))))

În C2: am generat șirul cu valorile întregi cuprinse între minimul și maximul din B2: =SEQUENCE(MAX(B2#);;MIN(B2#))

În D2: am calculat dacă există sau nu fiecare număr din C2# în B2# =IFNA(XMATCH(C2#;B2#;0);”x”)

Rezolvarea dintr-o singură funcție este foarte asemănătoare problemei PermMissingElem explicată în articolul: Modele de algoritmi in #Excel – Time complexity (3)

Funcția finală este:

=LET(arr; SORT(--TRIM(TEXTSPLIT(B1;;",")));
	  all; SEQUENCE(MAX(arr)-MIN(arr)+1; ;MIN(arr); 1);
      vCheck; IFNA(XMATCH(all; arr;0 ); "x");
TEXTJOIN(", ";;FILTER(all;vCheck="x"; IF(MIN(all)<0;1;MAX(all)+1))))

în care:

• arr este valoarea șirului A specificat, sortat ascendent, echivalentul lui B2;
• all este valoarea șirului întreg, echivalentul lui C2;
• vCheck este vectorul de comparație șiruri, prin returnare valoare „x” în cazul în care unul sau mai multe numere întregi sunt lipsă.
• funcția TEXTJOIN() este folosită pentru a afișa toate numerele întregi lipsă dintr-un șir dat.

Această metodă este foarte utilă în practică pentru a determina de exemplu dacă avem numere lipsă dintr-un șir dat (exemplu coduri, sau zile calendaristice, etc)

Cam asta a fost pentru acest algoritm. Sper să fie util cuiva!

Nu uitați să folosiți secțiunea de comentarii dacă aveți opinii legate de subiect sau propuneri de îmbunătățire.