Modele de algoritmi în #Excel – Caterpillar method (15)

Nu am idee cum s-ar traduce cel mai bine în limba română această metodă. Unii spun că ar fi metoda omidei alți autori metoda ferestrei glisante bidirecționale. Scopul meu este să rezolv în Excel problemele din această categorie, rezolvări care mi s-au părut relativ simple în Excel.

Mă apropii de finalul problemelor de pe Codility, iar astăzi vă propun câteva metode de rezolvare din cadrul probemelor Caterpillar method explicate la această adresa: https://app.codility.com/programmers/lessons/15-caterpillar_method/

Denumirea vine de la modul în care algoritmul își extinde și retrage fereastra de procesare, similar cu modul în care o omida se mișcă – înaintează secvențial, dar își ajustează poziția astfel încât să acopere eficient o zonă, fără suprapuneri inutile.

În Excel operațiunile acestea le putem face prin indexarea unui vector în funcție de diferite poziții curente de căutare, adresabile prin variabilele R și C ale lui MAKEARRAY() sau cele 3 valori ale matricelor de triplete TripleG (denumire pe care o dau eu acestei tehnici descrise în mai multe ocazii).

Dar înainte de a începe să prezentăm…

Foarte puțină teorie

Pentru a secvenția un vector sau un tabel în Excel avem la dispoziție mai multe funcții, modul în care le utilizează fiecare dintre noi depinzând de experiență, inspirația de moment sau cunoașterea lor.

Principalele funcții pe care le adresez în această secțiune sunt: TAKE(), CHOOSECOOLS(), COOSEROWS(), DROP(), INDEX().

Exemplificare funcții de păstrare a anumitor valori dintr-o matrice.

INDEX() în combinație cu MATCH() a fost mult timp considerat o alternativă la VLOOKUP(). Doar că această funcție poate face mult mai mult chiar dinainte de funcțiile dinamice, când artificiul suprem erau funcțiile CSE (Ctrl+Shift+Enter). Combinat cu SEQUENCE() în versiunile moderne de Excel nu mai este nevoie să introducem funcția cu CSE ci funcționează automat. Plus dinamica lui Sequence ne poate duce la soluții extraordinar de spectaculoase. Vezi exemplul din A14 unde aducem ultimele 3 numere din tabel de pe ultima coloană în ordine inversă.

Avantajul lui DROP și TAKE este că pot adresa atât linii cât și coloane prin parametrii 2 și 3. Coloanele și liniile pot fi adresate cu numere pozitive în ordinea coloanelor (1 prima coloana, 2 primele două coloane) cât și negative (-1 ultima linie/coloana, -2 ultimele două linii sau coloane). Choosecols sau Chooserows sunt oarecum mai precise pentru că adresează exact coloana sau linia specificată, dar pot fi și ele combinate cu SEQUENCE() pentru a adresa mai multe linii sau coloane. De exemplu în K6 putem face o optimizare cu sequence în forma: =CHOOSEROWS(COOSECOLS(vNumere;1); SEQUENCE(5;;2))

Personal consider că în cele mai multe cazuri INDEX() este de departe funcția câștigătoare, dar nu sunt de neglijat nici celelalte cazuri de utilizare.

Sortarea valorilor pe linie?!

Într-o zi una din firmele cu care lucrez pe partea de training privat de Excel mi-a trimis o agendă personalizată pentru un curs de Excel Avansat în care unul din puncte era sortarea valorilor pe linii. Eu când nu știu ceva, nu predau sau nu accept deloc clientul. Având în vedere că era totuși un client vechi și important am cerut clarificări… dar nu înainte de a mă uita pe internet dacă există așa ceva…

Ceea ce mi s-a confirmat și am găsit pe Internet mi s-a părut ceva simplist așa că am mers înainte. Dar cazul nu este deloc așa cum ar trebui.

Pentru versiunea manuală de sortare dacă vrei să faci sortarea pe linie:

Dacă vrei să sortezi valorile existente direct în tabel trebuie să parcurgi următorii pași:

Selectează rândul cu datele pe care vrei să le sortezi.
Mergi la „Home” sau „Data” → „Sort & Filter” → „Custom Sort”.
În fereastra de sortare, apasă pe „Options” și selectează „Sort left to right”.
Alege criteriul de sortare (ordine crescătoare sau descrescătoare) și apasă OK.

Având în vedere că în Excelul modern, operațiunile manuale sunt înlocuit cu funcții, operațiunea se poate realiza și prin funcția SORT() cu valoarea FALSE pentru parametrul 4.

Funcția de sortare pentru valorile pe o linie.

Și totuși dacă am dori să sortăm toate valoarile crescător pe fiecare linie în parte?

Lucrurile nu mai sunt la fel de simple pentru că funcția sort nu mai funcționează așa cum ne-am aștepta. În Excel, SORT() este dedicat implicit valorilor de pe o coloană, iar ca să ducem o linie în coloană folosim TRANSPOSE().

Exemplificare valori random:

Tabel cu numere sortate crescător pe linie.

Pentru această operațiune introduc în acest articol funcția _fSortRows() care are următorul corp:

=LET(arr; A2:F25;
     join; BYROW(arr; LAMBDA(r; TEXTJOIN(";";;r)));
     rez; MAP(join; LAMBDA(x; TEXTJOIN(";";;SORT(TRANSPOSE(--TEXTSPLIT(x; ";"))))));
     result; TEXTSPLIT(TEXTJOIN("|";TRUE;rez);";";"|");
  result
)

în care:

arr – este blocul de numere generat aleator cu RADARRAY();
join – unește toate valorile de pe linie pentru a le putea parcurge linie cu linie cu MAP() din rez;
result – este rezultatul cu artificiul de splitare a blocurilor de valori pe linii și coloane.

Această parte am sintetizat-o și într-un scurt clip video.

Acestea fiind spuse, să trecem la rezolvarea problemelor:

Problema AbsDistinct

Problema AbsDistinct presupune determinarea numărului de valori distincte dintr-un array, luând în considerare doar valoarea absolută a fiecărui element.

Exemplu
Dacă avem următorul array sortat: -5,-3,-1,0,3,6
Valorile absolute sunt: 0,1,3,3,5,6
Valorile distincte sunt: 0, 1, 3, 5, 6 (5 valori distincte).

Rezolvarea este foarte simplă în Excel:

în C2 am utilizat formula: =SORT(UNIQUE(ABS(A2:A7)))

în care ABS calculează absolutul fiecărui număr din vectorul A, UNIQUE() determină toate valorile unice, iar SORT() le sortează ascendent.

Această metodă poate fi utilizată în cazul tranzacțiilor bursiere pentru a identifica variațiile unice absolute ale unei acțiuni într-o perioadă de timp.

Problema CountDistinctSlices

În cardrul acestei probleme avem un șir de numere (A) și vrem să determinăm câte sub-secvențe distincte (numite și slice-uri) pot fi formate, astfel încât toate elementele din fiecare sub-secvență să fie distincte.

Scopul problemei este să aflăm câte sub-secvențe (slice-uri) distincte există, astfel încât niciun număr dintr-un slice să nu se repete.

Rezolvarea problemei nu a fost chiar atât de simplă cum pare la final din cauză că nu am identificat de la început calea cea mai simplă de rezolvare, eu abordând matricial problema cu Makearray(). Doar că matricile nu rezolvă problema sau cel puțin nu am identificat calea corectă.

Rezultatul sugerat de cei de la Codility era dat de următoarele combinații unice: (0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2), (3, 3), (3, 4) and (4, 4) eu personal neînțelegând la început că slice (0,2) înseamnă valorile 3,4,5.

Ca să pot rezolva problema am introdus în E2 o formulă destul de abstractă pe care încercă să o explic:

=MAP(B2#; 
      LAMBDA(poz; 
           TEXTJOIN("|";;
           SCAN(0; DROP($A$2:$A$6;poz); 
                    LAMBDA(a;v; 
                         IF(a=0; v; 
                                 IF(IFERROR(TAKE(--TEXTSPLIT(a;";");;-1);v)=v;
                                  "";
                                   IF(a="";"";TEXTJOIN(";";TRUE;a;v))
                                   ) 
                            )
                           )
                )
                )
           )
)

Ca să pot scana blocul de la poziția 0, apoi de la poziția 1 și așa mai departe, a trebuit să definesc secvența din B2 pe care o parcurg cu MAP(). Apoi pentru fiecare poziție, returnez o combinație de valori de pe blocul A2:A6 pe care-l parcurg cu SCAN(). Partea frumoasă a acestei construcții este dată de faptul că în acumulatorul a introduc întotdeauna valorile în ordinea lor, ceea ce-mi permite să le iau cu acel TAKE() pentru a-l putea compara cu valoarea curentă V ca să identific dacă valorile sunt egale. Scan-ul funcționează la început pentru valoarea 0 a vectorului din B2#. Apoi map-ul duce Scanul mai jos pentru restul de slices.

În H2 folosesc artificiul de splitare: =TEXTSPLIT(TEXTJOIN(„|”;;E2#);;”|”)

Integrate toate operațiunile într-o singură formulă ar arăta:

=LET(_a; A2:A6; seqa; SEQUENCE(ROWS(_a);;0);
     perechi; MAP(seqa; LAMBDA(poz; TEXTJOIN("|";;
              SCAN(0; DROP(_a;poz); LAMBDA(a;v; IF(a=0; v; 
              IF(IFERROR(TAKE(--TEXTSPLIT(a;";");;-1);v)=v;"";
                   IF(a="";"";TEXTJOIN(";";TRUE;a;v)))))))));
     rezi; TEXTSPLIT(TEXTJOIN("|";;perechi);;"|");
     result; ROWS(rezi);
     result
)

în care în variabila prerechi calculez acel MAP cu SCAN integrat.

O variantă oarecum diferită a acestei soluții este să oprim SCAN-ul în momentul în care o valoare din A se repetă anterior. Exemplificare:

În acest context când în prima rundă de scanare apare varianta 3 care este deja mai sus, se oprește scan și trece la secvența următoare. Pentru aceasta folosesc o funcție ușor diferită dar cu aceeași logică.

=LET(_a; A27#; seqa; SEQUENCE(ROWS(_a);;0);
     perechi; MAP(seqa; LAMBDA(poz; TEXTJOIN("|";;
                      SCAN(0;DROP(_a;poz);LAMBDA(a;v; IF(a=0;v; 
                        IF(IFERROR(SUM((--(--TEXTSPLIT(a;";")=v)))>0;0);"";
                            IF(a="";""; TEXTJOIN(";";;a;v)))))))));
     rezi; TEXTSPLIT(TEXTJOIN("|";;perechi);;"|");
     result; ROWS(rezi);
     UNIQUE(rezi)
)

În prima variantă folosesc doar ultima valoare din acumulatorul a iar în varianta 2 compar toate valorile din acumulator cu valoarea curentă. De reținut aici că nu putem utiliza un COUNTIF() într-un SCAN așa că a trebuit să introduc artificiul de a compara oricare valoare din A cu V și transformarea în valori 0,1.

Problema CountTriangles

Problema CountTriangles se referă la identificarea tripletelor dintr-un șir de numere care pot forma triunghiuri valide conform inegalității triunghiului.

Inegalitatea triunghiului afirmă că, pentru trei laturi a,b,c ale unui triunghi, trebuie să se respecte condiția:
a+b>c , b+c>a, c+a>b
Într-un șir sortat, regula devine mai simplă: dacă avem trei elemente A[i],A[j],A[k] unde i<j<k , triunghiul este valid doar dacă: A[i]+A[j]>A[k].

Ca să putem compara oricare 3 elemente dintr-un vector avem nevoie de matricea de triplete introdusă în articolul Modele de algoritmi in #Excel – Sorting (6). De asemenea, problema triunghiurilor a mai fost tratată în articolul menționat la Problema Triangle. De asemenea, a fost descrisă puțin mai pe larg în articolul Programarea funcțională în Excel Modern din pinmagazine.ro una din ultimele reviste de IT, pe care le cunosc eu, disponibilă și offline.

Scopul matricei de triplete este de a genera toate combinațiile unice de câte 3 valori corespunzătoare indexului valorilor pozițiilor unui vector A cu începere de la 1. În articolul din PIN Magazine scriam că această matrice este echivalentului unui triplu FOR din programare. Reamintesc funcția de generare a matricei de indecsi unici.

=LET(sir;R1;split; TEXTSPLIT(sir;;";"); nrElemente; ROWS(split);
          combinatii; COMBIN(nrElemente; 3);
TripleG; SCAN("1;2;2"; SEQUENCE(combinatii);
   LAMBDA(a;v;
       LET(arr; --TEXTSPLIT(a;";");
           x; TAKE(arr;;1); y; TAKE(TAKE(arr;;2);;-1); z; TAKE(arr;;-1);
           newx; IF(AND(y=nrElemente-1; z=nrElemente); 
                        IF(x<nrElemente-2; x+1; x); x);
           newy; IF(newx=x; IF(z=nrElemente; 
                        IF(y<nrElemente-1; y+1; y);y); newx+1);
           newz; IF(newx=x; IF(z<nrElemente;z+1;y+2); newy+1);
newx&";"&newy&";"&newz)));
tabf; --TEXTSPLIT(TEXTJOIN("|";;TripleG);";";"|");
tabf)

Această funcție este optimizată în raport cu numărul de elemente din șirul din R1 în cazul acesta pentru că suportă până la 185 de elemente în șir față de 101 în varianta din articolul 6.

Proiecție problemă în Excel

Formula din K3 este bazată pe o variantă a articolului 6 și este:

=LET(vector; A2:A7;
     nr; ROWS(vector);
     matrix; MAKEARRAY(nr^3; 3; LAMBDA(i;j; IF(j = 1; INT((i-1)/nr^2)+1; IF(j = 2; MOD(INT((i-1)/nr); nr)+1; MOD(i-1; nr)+1))));
     fReq; LAMBDA(x; AND(INDEX(x;1)<>INDEX(x;2);INDEX(x;2)<>INDEX(x;3);INDEX(x;1)<>INDEX(x;3)));
     verif; BYROW(matrix; LAMBDA(r; fReq(r )));
     tabi; HSTACK(matrix; verif);
     unics; FILTER(tabi; TAKE(tabi;;-1)=TRUE);
     unicsm; CHOOSECOLS(unics;1;2;3);
     fReqv; LAMBDA(x; CONCAT(INDEX(vector;INDEX(x;1));";";INDEX(vector;INDEX(x;2));";";INDEX(vector;INDEX(x;3))));
     vals; BYROW(unicsm; LAMBDA(r; fReqv(r )));
     sVals; UNIQUE(MAP(vals; LAMBDA(v; TEXTJOIN(";"; ; SORT(--TEXTSPLIT(v;;";"))))));

     Split; --TEXTSPLIT(TEXTJOIN("|";1;sVals);";";"|");
     fverif; LAMBDA(x;AND(INDEX(x;1)+INDEX(x;2)>INDEX(x;3);
                     INDEX(x;1)+INDEX(x;3)>INDEX(x;2);
                     INDEX(x;2)+INDEX(x;3)>INDEX(x;1)));
     verift; BYROW(Split; LAMBDA(r; fverif( r)));
     tabf; HSTACK(Split; verift );
     triplef; TAKE(FILTER(tabf; TAKE(tabf;;-1)=TRUE;"0");;3);

     triplef)

În care în prima parte se generează matricea de căutare, după care prin funcția recursivă fReqv se indexează vectorul de valori A cu scopul de a determina inegalitățile de tipul a+b>c solicitate de problemă. În felul acesta determinăm că anumite combinații de numere pot reprezenta triunghiuri din punct de vedere geometric.

Problema MinAbsSumOfTwo

Având în vedere că este o problemă cu două valori dintr-un vector care trebuie comparate, soluția optimă în Excel este utilizarea unui MAKEARRAY().

Problema constă într-un vector de numere a cător sumă în format aboslut trebuie să fie cea mai mică. Formal, dacă avem un array A de dimensiune N, trebuie să determinăm: min(|A[i]+A[j]|) unde 0≤i≤j<N.

Proiecția problemei în Excel:

în care formula din C3 este:

=LET(arr; A2:A6; rr; ROWS(arr);
    MAKEARRAY(rr;rr;LAMBDA(r;c; 
           IF(r>c;"";ABS(INDEX(arr;r)+INDEX(arr;c))))))

în care matricea generată cu MAKEARRAY indexează vectorul arr pentru fiecare combinație de linie și coloană.

O variație a acestei probleme care nu există pe Codility este să determin mimimul sau maximul absolut a trei valori din vector. Această problemî în Excel ar arăta:

în care am utilizat din nou matricea de triplete, dar de data aceasta cu scopul de a păstra toate valorile posibile în matrice nu doar valorile unice.

Formula din D2 devine astfel:

=LET(arr;A2:A6;
     seq; SEQUENCE(ROWS( arr));
     matrix; LET(vector; arr;
                nr; ROWS(vector);
                matrix; MAKEARRAY(nr^3; 3;
                         LAMBDA(i;j;
                          IF(j = 1;
                            INT((i-1)/nr^2)+1;
                            IF(j = 2; MOD(INT((i-1)/nr); nr)+1;
                                     MOD(i-1; nr)+1))));
   fReq; LAMBDA(x; AND(INDEX(x;1)<INDEX(x;2);INDEX(x;2)<INDEX(x;3)));
   verif; BYROW(matrix; LAMBDA(r; fReq(r )));
   tabi; HSTACK(matrix; verif);
   unics; FILTER(tabi; (TAKE(tabi;;-1)=TRUE)*(CHOOSECOLS(tabi;3)<=nr));
   unicsm; CHOOSECOLS(unics;1;2;3);
   TAKE(tabi;;3));

summax; BYROW(matrix;
        LAMBDA(r; LET(x; TAKE(r;;1);
                      y; TAKE(TAKE(r;;2);;-1);
                      z; TAKE(r;;-1);
                    ABS(INDEX(arr;x)+INDEX(arr;y)+INDEX(arr;z)))));

HSTACK(matrix; summax))

Cam atât pentru astăzi… să aveți o săptămână productivă și

Sper să fie util cuiva!

10/02/2025

Modele de algoritmi în #Excel – Binary search algorithm (14)

Continui seria de articole despre algoritmii clasici din programare cu o metodă de rezolvare a problemelor de căutare descrise în articolul de pe Codility: https://app.codility.com/programmers/lessons/14-binary_search_algorithm/

Ar trebui să specificăm de la începutul articolului că metodele de rezolvare propuse nu sunt poate cele mai optime din punct de vedere al vitezei de procesare, dar sunt un mod interesant de a demonstra că Excelul este mult mai mult decât A1+B2 și fiecare dintre utilizatorii de Excel pot găsi funcții și formule interesante pe care să le aplice în diverse domenii și operații pe care le efectuează în activitatea lor.

Dacă sunteți doar în căutarea unor funcții de căutare, vă reamintesc un articol mai vechi Funcția Filter() din #Excel 365 în care sunt descrise comparativ mai multe funcții de căutare din Excel.

În articolul curent forța Excelului este demonstrată prin funcțiile MAKEARRAY() și SCAN() într-o construcție specială. Veți vedea.

Nu avem numaidecât o parte de teorie în afara algoritmului descris la începutul articolului. Ambele probleme în schimb mi-au dat destul de multă bătaie de cap cu înțelegerea cerințelor. Cred că aici este de fapt dificultatea lor.

Problema MinMaxDivision

Această problemă este orientată pentru a determina care este minimul sumei unor numere din poziții consecutive dintr-un vector, dacă îl împarți în K părți de diferite dimensiuni. Un aspect ciudat al problemei este că vectorul poate fi împărțit în elemente vide. De exemplu dacă ai un vector de 7 elemente și un K de 3 poți împărți vectorul în 3 segmente de 7, 0, 0. Suma tuturor numerelor din vectorul de 7 este suma maximă care poate fi atinsă. Scopul este să îl împarți în segmente a căror sumă maximă să fie cea mai mică din toate formele de a împărți elementele.

În problemă este introdus și termenul M care reprezintă de fapt dimensiunea maximă a valorilor din vectorul A. Această valoare M trebuie să fie mai mică decât minimul de maximum combinații.

Propunerea de rezolvare

În primă fază a rezolvării problemei nu am înțeles numaidecât că numărul K reprezintă numărul de segmente în care se poate împărți șirul și am ralizat un calcul de însumare a tuturor combinațiilor de numerele consecutive în E9.

Funcția din E9: =MAP(C9#;LAMBDA(v;SUM(INDEX(D9#;SEQUENCE(3;;v)))))

în care în MAP() refer secvența de numere generate pe dimensiunea vectorului -2. Valoarea de -2 este pentru a preveni erorile în funcție datorate indexării în afara vectorului. În acest fel ultima poziție de indexare v este dimensiunea vectorului -2 ceea ce înseamnă că valoarea 3 din Sequence() de final va face indexarea până la finalul vectorului D9#.

Pentru cei mai puțin familiarizați cu funcțiile dinamice un index() poate aduce mai multe elemente dintr-un vector dacă specificăm acest lucru prin SEQUENCE(3) sau ROW(1:3) de exemplu. Eu prefer SEQUENCE pentru că poți specifica valori dinamice, pe când ROW() nu funcționează cu variabile.

Pentru a înțelege toate combinațiile posibile am generat o matrice în I5 în care indexez lista de elemente consecutive în ordinea lui r: câte unul, câte două, câte 3… și așa mai departe. Formula din I5 este:

=MAKEARRAY(ROWS(A4#);ROWS(A4#);LAMBDA(r;c;IFERROR(TEXTJOIN(";";TRUE;INDEX(D9#;SEQUENCE(r;;c)));"")))

în care pentru a putea aduce și afișa valorile din vectorul D9# folosesc funcția TEXTJOIN(). Magic în această formulă este indexul de secvență de r valori începând de la coloana c.

A fost destul de dificil să ajung la această abstractizare. Ulterior în I14 am înlocuit TEXTJOIN() cu SUM() de indexare dinamică pentru a calcula valorile fiecărui segment.

În Q14 am utilizat funcția =MAX(I14:O14) pentru a determina maximul pe fiecare linie, după care în R14 am filtrat doar valorile mai mari decât M, obținând apoi prin MIN() valoarea 7.

Integrați toți acești pași dau următoarea formulă:

=LET(sir; --TEXTSPLIT(B1;;",");
     _k;E2; _m; F2; _rs; ROWS(sir);
     matrix; MAKEARRAY(_rs;_rs;LAMBDA(r;c;IFERROR(SUM(INDEX(sir;SEQUENCE(r;;c)));"")));
     _maxs; BYROW(matrix;MAX);
     return; MIN(FILTER(_maxs; _maxs>_m));
return)

Frumos în această formulă este variabila _maxs care aplică noua formă de utilizare a BYROW() în cadrul tabelelor fără a folosi separat o LAMBDA() care ar complica problema.

Exemplu practic: Alocarea unui buget de investiții

O companie are un buget total de investiții pe care trebuie să-l împartă între mai multe proiecte. Problema constă în împărțirea optimă a bugetului astfel încât suma maximă alocată unui singur proiect să fie cât mai mică posibil.

Datele problemei:
Ai N proiecte de investiții (echivalentul secțiunilor dintr-un șir de numere).
Fiecare proiect necesită o anumită sumă de bani (vectorul A din problemă).
Ai K departamente (echivalentul lui K din problemă), iar fiecare departament trebuie să gestioneze un set de proiecte.
Scopul este să împarți proiectele între cele K departamente astfel încât suma maximă alocată unui singur departament să fie minimizată.

Exemplu numeric:
Să presupunem că avem 5 proiecte care necesită următoarele sume de bani (în milioane):
A = [2, 1, 5, 1, 2, 2, 2]

Și trebuie să le alocăm la K = 3 departamente.

Obiectiv: Împărțirea optimă astfel încât suma maximă cheltuită de un singur departament să fie minimizată.

Posibile împărțiri
O posibilă împărțire ar fi:
[2, 1, 5] | [1, 2] | [2, 2]
Sumele alocate fiecărui departament: 8, 3, 4
Maximul este 8 (prima grupă).

O altă împărțire mai echilibrată:
[2, 1] | [5, 1] | [2, 2, 2]
Sumele alocate: 3, 6, 6
Maximul este 6 – mai echilibrat decât primul caz.

Problema NailingPlanks

În această problemă este vorba despre optimizarea numărului de cuie (C) care pot fi folosite pentru fixarea unui set de scânduri A-B.

Ca orice problemă de optimizare și aceasta este destul de dificilă de abordat pentru că avem foarte multe excepții. De exemplu cuiul din poziția 4 poate fișa și scândura 1 cât și scândura 2, ceea ce înseamnă că nu mai are sens să folosim cuiul din poziția 2 care poate fixa doar scândura 1. Cu ajutorul cuielor 6 și 7 putem fixa scândura 3, deci nu are sens să îl folosim pe al doilea.

NailingPlanks propunere de rezolvare in Excel

În rezolvarea problemei am căutat în G2 și H2 în ce interval de valori din A și B se află valoarea poziției cuiului. îmn XMATCH() am folosit parametrul -1 (egal sau mai mic decât valoarea căutată) pentru capătul de jos al scândurii (A) iar pentru capăt B am folosit parametrul 1 (egal sau mai mare decât valoarea căutată). Acesta este artificiul de căutare în intervale de numere prin XMATCH()

Ca să văd dacă un cui fixează mai multe scânduri în J2 am făcut o concatenare de numere unice. Rezultatul prelucrării anterioare fiind de tipul unui vector pe linie, ca să pot aplica funcția UNIQUE(), trebuie transpozate numerele rezultat, funcția de unicitate funcționează doar la nivel de vectori în coloană. Al doilea TRANSPOSE() nu este numaidecât obligatoriu atât timp cât folosesc TEXTJOIN() dar pentru a vedea rezultatele pe parcurs atunci l-am utilizat.

Partea cea mai dificilă dincolo de G2 și H2 a fost să determin care scândură a fost inserată cu un cui și să o elimin din rezultat. Pentru asta am abordat cu SCAN() în K2. Formula din K2 este:

=SCAN(0;J2:J6;LAMBDA(a;v; IF(a=0; v;
      LET(_a; TEXTSPLIT(a; ";");
          _v; TEXTSPLIT(v; ";");
          ver; IFNA(XMATCH(_v;_a;0);0);
          fil; TEXTJOIN(";";TRUE;FILTER(_v;ver=0;""));
          TEXTJOIN(";";TRUE;a;fil)))))

Ca să pot prelucra și compara numerele în variabila ver, a trebuit să descompun întâi valorile acumulatorului a și a valorii curente v. Dacă nici una din valorile curente nu se găsesc în ce a fost anterior, facem join între valoarea curentă și cea acumulată. Dacă valorile sunt deja în șir atunci aducem doar valoarea existentă.

Această formulă este foarte utilă pentru a putea compara șiruri de numere între ele și a acumula doar numărul care nu a mai fost. Exemplificare de extragere a tuturor valorilor unice dintr-un vector de valori

Functie de returnare a valorilor unice dintr-un vectori de valori multiple.

Funcția REDUCE() din D2 imi aduce doar rezultatul final al unui SCAN() fără a mai fi necesară trecerea prin fiecare etapă. Funcția din D2 este identică cu cea prezentată anterior doar că în loc de SCAN am folosit Reduce. Pentru a determina valorile în ordinea lor în D4 am introdus formula: =SORT(TEXTSPLIT(D2;;”;”))

Aceasta este cea mai de valoroasă funcție din acest articol, după opinia mea.

Revenind la problema inițială, în celula L2 am introdus o nouă funcție de scanare pentru a determina valorile unice din Scan 1 în poziția lor inițială. Apoi pentru a determina poziția cuielor am folosit Filtrarea în N2 apoi indexarea în O2 pentru a afla scândurile fixate de acele cuie.

Aparent complicat, dar soluționabil. Ar trebui testate pentru mai multe seturi de valori pentru îmbunătățirea soluției.

Pentru integrarea funcție trebuie avut în vedere că folosesc un Textjoin care nu funcționează într-un Byrow pentru construcția variabilei Dist, deci trebuie construită o funcție recursivă (fReqDist) anterioară. În final formula ar fi:

=LET(_a; B2:B5; _b; C2:C5; _c; E2:E6;
    CapatA; IFNA(XMATCH(_c;_a;-1);"");
    CapatB; IFNA(XMATCH(_c;_b;1);"");
    fReqDist; LAMBDA(v; TEXTJOIN(";";TRUE;(UNIQUE(TRANSPOSE(v)))));
    tabi; HSTACK(CapatA; CapatB);
    Dist; BYROW(tabi; LAMBDA(r; fReqDist(r)));
    Scan1; SCAN(0;Dist;LAMBDA(a;v; IF(a=0; v;
          LET(_a; TEXTSPLIT(a; ";");
          _v; TEXTSPLIT(v; ";");
          ver; IFNA(XMATCH(_v;_a;0);0);
          fil; TEXTJOIN(";";TRUE;FILTER(_v;ver=0;""));
          TEXTJOIN(";";TRUE;a;fil)))));
    Scan2; SCAN("";Scan1;LAMBDA(a;v; IF(a="";v;IF(v=a;"";v))));
    Cuie; FILTER(_c;--(Scan2="")=0);
    Scanduri; INDEX(Dist;XMATCH(Cuie;_c;0));
    Result; HSTACK(Cuie;Scanduri);
Result
)

Având în vedere complexitatea problemei sunt și cazuri pe care soluția oferită nu oferă răspunsul optim. Exemplificare:

Exemplu de problemă care nu are soluție optimă.

În această problemă optimul ar fi două cuie… poziția 5 și 7 sau 5 și 9, dar rezolvarea propusă anterior are o mică problemă cu scan-ul pentru prima valoare. Mi-ar plăcea să văd dacă un cititor poate să-mi trimită o soluție mai corectă pentru cazurile particulare.

Cam atât pentru astăzi.

Sper să fie util cuiva!

05/02/2025

Modele de algoritmi în #Excel – Fibonacci numbers (13.2) – Ladder

Acest articol este o continuare a articolului despre numerele Fibonacci: Modele de algoritmi în #Excel – Fibonacci numbers (13) – Partea 1 – FibFrog și prezintă o metodă de rezolvare a problemei Ladder de pe site-ul Codility: https://app.codility.com/programmers/lessons/13-fibonacci_numbers/ladder/

Odată rezolvată problema șirurilor Fibonacci explicată în articolul anterior, această problemă nu are nimic special, atât timp cât autorii problemei explică în detaliu modul de rezolvare.

Pe scurt, problema presupune calcularea numărului de combinații prin care se poate urca o scară de dimensiune N pâșind una sau două trepte.

Datele de intrare ale problemei sunt doi vectori A și B în care:

Vectorul A: Numărul de trepte pentru fiecare scară
Fiecare element A[i] din vectorul A reprezintă numărul de trepte pentru o anumită scară.
De exemplu, dacă A = [4, 3, 5], atunci avem trei scări:
Prima scară are 4 trepte
A doua scară are 3 trepte
A treia scară are 5 trepte
Practic, fiecare element al lui A definește dimensiunea unei scări pentru care trebuie să calculăm numărul de moduri în care putem ajunge în vârf.

Vectorul B: Modulo pentru fiecare scară
Fiecare element B[i] din vectorul B reprezintă valoarea modulo 2^B[i] care trebuie aplicată rezultatului.
Deoarece valorile Fibonacci cresc foarte rapid, trebuie să calculăm rezultatul modulo 2^B[i] pentru a evita depășirea limitelor numerice.
De exemplu, dacă B = [3, 2, 4], atunci:
Pentru prima scară, rezultatul trebuie modulo 2^3=8
Pentru a doua scară, rezultatul trebuie modulo 2^2=4

Rolul lui B este să controleze dimensiunea rezultatului final pentru fiecare scară, evitând numere prea mari.

Rezolvare problema în Excel

În care:

D2 – Care este maximul sir Fibonnaci +1
În problema Ladder, folosim Fibonacci(N+1) pentru că trebuie să numărăm modurile distincte de a urca scara.
Fibonacci(N+1) se bazează pe faptul că pentru a ajunge la treapta 𝑁 putem veni fie de la 𝑁 − 1 (1 pas), fie de la 𝑁 − 2 (2 pași).

E2 – Puterile lui 2 la valoarea lui B

F2 – Se calculeaza restul impartirii numarului Fibonaci rezultat la puterile lui B

Funcția _fFibonacciSir() a fost introdusă și explicată în articolul anterior.

Rezolvarea integrată a problemei printr-o singură formulă cu funcții recursive nesalvate anterior ar fi:

=LET(_a; A2:A6; _b; B2:B6;
     fReqFibSir; LAMBDA(n; (((1+SQRT(5))/2)^SEQUENCE(n)-((1-SQRT(5))/2)^SEQUENCE(n))/SQRT(5));
      fibocat; MAP(_a; LAMBDA(v; MAX(fReqFibSir(v+1))));
      PuteriB; MAP(_b; LAMBDA(v; 2^v));
      return; MOD(fibocat;PuteriB);
return)

în care locul funcției presalvate _fFibonacciSir() este luat de funcția recursivă: fReqFibSir.

De remarcat în această formulă faptul să în partea de return am aplicat MOD() pentru cei 2 vectori cu număr de elemente egale, fără a întâmpina nici un fel de eroare.

Cam atât pentru acest articol!

Sper să fie util cuiva!

03/02/2025