În urmă cu ceva ani, unul din profesorii mei preferați (am mai mulți) ne povestea despre chinurile proiectării și implementării unui „motoraș” de repartizare a opțiunilor studenților sau candidaților pe anumite locuri în ordinea mediilor și preferințelor. Prima dată l-a făcut în SQL pentru admiterea la facultate. Ulterior l-a făcut în R. Recunosc că am privit oarecum cu invidie, pentru că în SQL chiar dacă am învățat destul de bine la master, nu am reușit să îl implementez, iar partea de R nu am înțeles-o prea bine, chiar dacă am mai cochetat din când în când.
Însă din momentul în care am început cercetarea profundă a programării funcționale în Excel, am reușit să fac lucruri pe care altă dată doar le visam și asta fără ajutorul generatoarelor de text, care sunt depășite de aceste metode. I-am mai spus lui ChatGPT că în Excel NU există FOR. El o ține pe a lui. Nu recomand! :)
Acest articol este un tribut pentru toți profesorii (unii actuali colegi ai mei) care m-au îndrumat și încurajat de-a lungul timpului să performez.
Fișierul de lucru poate fi accesat și descărcat de la adresa: AlocareOptiuni v1.xlsx. Acest fișier funcționează doar în versiunile Office 365 sau versiunile mai noi care suport funcții dinamice.
Proiecția problemei în Excel
În exemplul prezentat în fișier, se presupune că avem o listă de profesori care au disponibile teme pentru lucrările de licență și un anumit număr de locuri pe fiecare temă. Ca să poată funcționa algoritmul propus, este esențial să codificăm fiecare temă în mod numeric. Numărul de locuri le specificăm tot numeric în dreptul codului fiecărei teme. Temele cu 0 locuri vor fi excluse automat din motorașul de repartizare.
Opțiunile studenților sunt prezentate ca un șir de opțiuni delimitate prin ; (punct și virgulă) în care fiecare număr este codul unei teme. Algoritmul aranjează sursa de date în ordine descrescătoare a mediilor după care face repartizarea după prima opțiune, apoi a doua dacă la prima opțiune nu mai sunt locuri și așa mai departe.
Funcția pe care o puteți întâlni și în fișierul Excel în celula K2 este:
în care:
locs este blocul de teme de la A2:B21 și care trebuie înlocuit în funcție cu propriile coduri
optiuni sunt numele studenților cu opțiunile lor și media. Există și posibilitatea de a aborda alocarea și în funcție de principiul primul venit primul servit. În acest caz, dacă ordinea este cea prezentată în foaia de calcul, trebuie să modificăm valorile de pe coloana G cu numere descrescătoare.
Pentru a reduce complexitatea și numărul de caractere, am definit la începutul formulei, 4 funcții recursive: _fCumulare(tab), _fDecumulare(acumulate), _fLast(x) și _fLastN(x) pe care le utilizez în _scan cu precădere și în result.
Explicam în articolele trecute că un SCAN() nu poate lucra cu tabele ci doar cu o singură valoare. Ca să pot scana totuși tabele întregi, am nevoie de a unifica aceste tabele în valori parsabile.
Prin cod se observă un 999 la linia 8, în _scan și apoi în result. Acest 999 mă ajută să determin dacă o opțiune este în afara numărului de locuri disponibile.
Complexitatea acelui SCAN() poate fi văzută într-o proiecție intermediară aici:
Valoarea de final a fiecărui șir intermediar (acumulatorul din SCAN) este o combinație de 0 și rezultatul prelucrării: 999 sau valoarea opțiunii care îndeplinește criteriile alocării pentru acel student.
În momentul în care am alocat un loc, ca să pot face scăderea lui din locurile rămase am apelat la scăderea a două matrici în variabila ramase (linia 19) care adună rezultatul decumulării acumulatorului curent din intro (linia 12) cu o matrice cu două coloane generată dinamic în funcție de numărul de linii rămase din intro.
Vizual această oprațiune de scădere a matricilor ar fi:
Această tehnică mi-a permis să am oricâte opțiuni din partea unui student și să le tratez pe toate în funcție de ce a mai rămas în acumulator.
Chinul cel mare nu a fost la SCAN ci la integrarea rezultatelor în aceeași formulă. În versiunile intermediare MAP() era soluția logică la calculul variabilei resut. Până la urmă l-am folosit, dar am lucrat doar cu șiruri fără reutilizare funcțiilor de Cumulare și Decumulare. Efectiv nu poți într-un MAP dintr-un LET să folosești rezultatul intermediar al lui SCAN pe care sa-l transformi din nou în tabelar, chiar dacă rezultatul în proiectezi ca valoare atomică cumulată.
În celula C2 pentru a calcula pentru fiecare temă studenții alocați am implementat un simplu TEXTJOIN() de filtrare. Formula din C2: =TEXTJOIN(„;”;;FILTER($K$2:$K$18;$L$2:$L$18=A2;””)). Trebuie să modificați adresele dacă aveți mai multe sau mai puține opțiuni.
Cam asta ar fi.. cazurile de aplicare pot fi diverse, important este să aranjam datele de intrare corect dacă dorim să utilizăm acest „motoraș” de repartizare.
Un algoritm greedy este o strategie de rezolvare a problemelor care face alegeri pas cu pas, selectând în fiecare moment opțiunea cea mai bună disponibilă, fără a lua în considerare deciziile viitoare.
Principiul de bază este: „Alege ceea ce pare a fi cea mai bună opțiune la fiecare pas, sperând că această strategie va duce la soluția optimă.”
Acești algoritmi sunt simpli și eficienți, dar nu garantează întotdeauna cea mai bună soluție globală.
În Excel nu avem posibilitatea de a face alegeri numaidecât locale, ci problemele trebuie trate la nivel global. Da o strrategie eficientă este să rezolvi pas cu pas problema, din aproape în aproape pentru a putea ajunge la o soluție integrată. Chiar și în rezolvările individuale trebuie să avem în vedere funcții reutilizabile și tratarea globală a vectorilor de input. De aceea în toată această tehnică este esențială funcția MAP() pentru parcurgerea element cu element a unui vector sau SCAN() tot pentru parcurgere globală, dar cu avantajul acumulării.
Un pic de teorie aplicată
În această secțiune doar voi reaminti cum funcționează o funcție MAP(), SCAN() și BYROW().
Foarte important: Nici una din funcții NU generează tabele. De aceea, în exemplele mele vedeți foarte mult TEXTJOIN() și TEXTSPLIT() ca să pot acumula rezultatele intermediare într-o singură valoare. Dar ca să le pot prelucra trebuie să le splitez ca numere.
MAP() este o funcție care parcurge un vector valoare cu valoare de sus în jos. În multe cazuri putem folosi MAP() pentru a scana un fake vector, generat de exemplu de o funcție SEQUENCE pentru a putea face căutare și înainte pe un vector de valori. De cele mai multe ori dacă dorim să obținem printr-o singură formulă un tabel trebuie să le încapsulăm într-un LET(). Nu am exemple în acest moment despre combinații între MAP() și SCAN(). De obicei eu personal aleg să le tratez separat sau să se separ în funcții recursive distincte.
REPT() este o funcție de replicare a unui șir de un număr specificat de ori.
BYROW() este o funcție care tratează un tabel de date linie cu linie. Similar cu BYROW este BYCOL(). Când dorim să facem calcule simple, atunci putem specifica direct funcția după specificarea tabelului. Dacă avem veva mai mult de calcul, sintaxa generală este: =BYROW(tabel; LAMBDA(linie; calcule))
Funcția TAKE(), CHOOSECOL() sau INDEX() au un rol important în tratarea element cu element a unei linii.
Acestea fiind spuse o să încep atipic această rezolvare cu a doua problemă… pentru că este mai simplă.
Problema TieRopes
Presupune să se determine numărul de funii de o anumită lungime K specificată care pot fi create prin însumarea (înodarea) capetelor dintr-un șir de valori date (A). Valoarea capetelor nu poate depăși K dar funiile pot avea dimensiuni mai mari sau egale cu K. Ordinea de însumare este consecutivă nu se acceptă ca un segment A[0] să fie legat de un alt segment A[n].
Rezolvarea problemei în Excel este foarte simplă, dar rezultatele obținute prin rezolvare locală (subșiruri continue fără verificare globală înainte și înapoi) pot fi oarecum discutabile.
Pornind de la șirul din B2, l-am descompus în A4 apoi am calculat secvența cu start de la 1 în B4. Cheia problemei este în E4 unde prin SCAN am comparat sumele acumulate până în prezent din vectorul A cu valoarea lui K (dimensiunea minimă a unei funii). Ca să pot oferi rezultatele în format de segmente, în H4 am utilizat următoarea formulă:
În care scanez vectorul din G3 rezultat în urma prelucrărilor și pe baza valorii acestui vector concatenez cu TEXTJOIN() valorile de până în acel moment.
Formula integrată pornind de la șirul din B2 și valoarea lui K din C4 este:
Presupunem că avem un lanț de aprovizionare logistic pentru un retailer care trebuie să transporte pachete mici de produse între depozite și punctele de vânzare. Aceste pachete au greutăți variabile, iar pentru a reduce costurile de transport, ele trebuie grupate în unități mai mari, dar respectând anumite restricții minime de greutate pentru eficiență.
Sintetizând descrierea trebuie să respectăm condițiile:
Fiecare palet să aibă o greutate minimă K pentru ca transportul să fie eficient (sub această valoare, paletul nu este rentabil).
Trebuie să formăm cât mai mulți paleți, pentru a maximiza utilizarea spațiului din camion și a reduce numărul de transporturi.
Exemplu concret de date: Să presupunem că avem un set de 10 pachete cu următoarele greutăți (în kg): A=[3,5,1,6,2,4,8,3,7,2] și greutatea minimă necesară pentru transport eficient este K=10 kg.
Rezolvarea este foarte simplă:
în care pentru a calcula numărul de kg pe fiecare palet am introdus o nouă variabilă în funcția prezentată anterior:
care presupune însumarea valorilor coletelor din șirul dat.
Problema MaxNonoverlappingSegments
Problema aceasta a fost un coșmar din punct de vedere al prelucrărilor. 100% rezolvarea ei în Excel este doar un exercițiu de manipulare de date și rezultate, fără a avea pretenții de optimizare.
Problema MaxNonoverlappingSegments este o problemă clasică de optimizare care face parte din categoria Greedy algorithms (algoritmi lacomi). Aceasta constă în selectarea unui număr maxim de segmente (intervale) care nu se suprapun, dintr-un set de segmente date.
Avem o serie de segmente definite prin capete (start și end points), fiecare segment fiind reprezentat printr-o pereche de numere: (A[i],B[i]) unde:
A[i] este punctul de început al segmentului.
B[i] este punctul de sfârșit al segmentului.
Obiectivul este să alegem cât mai multe segmente care nu se suprapun, adică nu au puncte comune, astfel încât să maximizăm numărul total de segmente selectate.
O chichiță a problemei este dată de faptul că rezultatul final trebuie să fie prezentat în segmente de câte 3 și în combinații de câte 3 trebuie să prezentăm output-ul.
În imagine este prezentată rezolvarea graduală a problemei, proiecții intermediare pas cu pas, până a ajunge la forma finală din aproape în aproape.
Așa cum explicam în partea de teorie a acestui articol, cheia rezolvării constă în utilizarea funcției MAP și consțientizarea faptului că rezultatul trebuie să fie permanent o singură valoare.
Având în vedere că trebuie să returnăm valorile în seturi de câte 3 a trebuit să introduc și să salvez funcția _fTripleMatrix(elem) prezentată în aceste articole, care are următorul cod:
în care elem este o valoare mai mare decât 3 și, așa cum explicam cu alte ocazii, poate avea un maxim de 189 pentru că numărul de combinații de 190 luate câte 3 depășește valoarea 2^20 care este numărul de linii dintr-o foaie de calcul Excel. Ca o curiozitate, în Google Spreadheet nu am reușit să generez o secvență de numere mai mare de 2^15.
Cheia rezolvării problemei este identificarea capetelor și intersecția lor cu alte segmente. Această secțiune este rezolvată în F5 și G5 printr-o funcție de mapare în care valoare 1 presupune intsecție cu alt interval, iar 0 lipsa intersecției. Dacă suma ambelor segmente se regăsește pe celălalt segment, atunci valoarea 2 ne spune că avem o intersecție. Valoarea 1 ne spune că acel segment nu se intersectează cu altul. Și de aici încep tot felul de calcule și filtre, mapări pe matricea de triplete dinamică și așa mai departe.
O parte complexă din formulă este definirea funcției recursive _freqBR care înglobează funcția _fTripleMatrix() definită anterior. Am utilizat această tehnică pentru că în anumite moment anumite rezultate intermediare pot avea combinații diferite.
Cam atât pentru astăzi… Mai este o singură lecție pe site-ul Codility… dacă aveți alte colecții de probleme publice puteți să mi le oferiți în comentarii pentru a încerca abordarea lor. Eventual o resursă de probleme în română ar fi și mai fain.
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:
î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ă:
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.
Î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:
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
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:
Având în vedere complexitatea problemei sunt și cazuri pe care soluția oferită nu oferă răspunsul optim. Exemplificare:
Î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.
Valy Greavu - Live Blog 