Pentru aceast articol am ales să rezolv problema vectorilor (arrays) în Excel. Sursa de inspirație este https://app.codility.com/programmers/lessons/2-arrays/cyclic_rotation/
Un pic de teorie
Termenul de vector este des întâlnit în matematică/geometrie, fizică și nu numai. În Excel sau informatică în general se folosește de cele mai multe ori termenul englezesc array. De multe ori problemele de vectori au legătură cu șirurile de numere sau caractere în general.
În Excel un vector poate fi un șir de caractere/numere parsabile sau o linie, sau o coloană cu valori multiple, sau chiar un bloc de căsuțe NxM care poate fi parcurs. Problemele de vectori se referă în general la manipularea acestora (parcurgere, extragere valori, numărare elemente, etc).
Dacă avem un șir de valori într-o celulă, acesta poate fi descompus după unul sau mai mulți delimitatori. Una din funcțiile de bază pentru descompunerea unui șir în celule este: TEXTSPLIT() dacă identificăm unul sau mai mulți delimitatori sau o combinație de MID() cu SEQUENCE() prezentată în articolul trecut în cazul în care nu avem un delimitator definit.
Exemple:
În formula din C2 folosim TEXTSPLIT() cu delimitatorul , (virgulă). De menționat că se pot pune mai mulți delimitatori în cadrul aceleiași formule.
În C5 am folosit funcția MID() combinată cu SEQUENCE() de LEN() de valoare pentru a descompune literă cu literă textul. UPPER() este pentru a transforma toate literele în litere mari.
O funcție matematică foarte importantă în acest context este funcția MOD() care determină restul împărțirii a două numere între ele. Aceasta ne ajută în general în probleme cu ciclicitate pe același interval de valori. Restul împărțirii unui număr la el însuși este întotdeauna 0: MOD(n;n) = 0. Dacă dorim să forțăm o secvență de numere în care trebuie să obținem valoarea numărului, atunci va trebui să facem un artificiu matematic pentru acest lucru: MOD(n-1; n)+1 = n.
în care: avem o secvență de 16 numere în care dacă rulăm MOD(n;8) obținem valori de la 1 la 7 după care 0. Dacă dorim să realizăm numere repetitive de la 1 la 8 atunci va trebui să utilizăm: MOD(n-1;8)+1 în care n-1 va determina pentru n=8 valoarea 7 care în MOD cu 8 devine 7 la care adăugăm 1 pentru a se transforma în 8.
CyclicRotation în Excel
Așa cum specificam la începutul seriei, provocarea este de a rezolva probleme clasice de algoritmică în Excel. În zona de vectori o problemă clasică este aceea de a roti repetitiv elementele sale după un anumit K dat, în care K este numărul de rotații. Numărul de valori ale vectorului care se rotesc este în această problemă valoarea 1, ceea ce înseamnă că la fiecare execuție nouă ultima valoare devine prima în vector.
în care:
B5: =TEXTSPLIT(A2;”,”) – descompun șirul într-un vector pe linie.
B6: =LET(arr; B5#; last; TAKE(arr;;-1); firsts; TAKE(arr;;COLUMNS(arr)-1); HSTACK(last;firsts))
În care preiau rezultatul split de pe rând anterior. Vectorii dinamici rezultați din execuția funcțiilor dynamic array se pot apela cu formatul celula_start# referind toate liniile sau coloanele rezultat. Funcția TAKE() cu parametrul -1 o folosesc pentru a prelua ultima valoare din dreapta vectorului. Următoarea funcție TAKE() care compune variabila firsts este folosită pentru a prelua numărul de elemente ale vectorului determinat de funcția COLUMNS() -1 care este cel preluat deja în variabila last . Pentru a da noua stare a șirului folosesc funcția HSTACK() în care combin cele două variabile rezultat.
Formula din B6 se copie în jos cu drag-and-drop pentru oricâte iterații sunt necesare. Eu am afișat numărul de iterații pe coloana A printr-o funcție SEQUENCE( de K).
C2: și E2: sunt doar formule care nu au implicații în acest model de rezolvare.
Unificarea într-o singură funcție
Pentru a rezolva problema de rotație pentru orice șir de numere la orice K dat, inclusiv K negativ, atunci când vectorul s-ar muta în sens descerscător am propus o rezolvare care ia în calcul restul împărțirii K la lungimea vectorului. În imagine:
C2: =COLUMNS(B5#) – determinarea lungimii vectorului descompus.
E2: =MOD(B4-1;C2)+1 – Funcția MOD de determinare a restului împărțirii.
Logica este că la fiecare pas se realizează incrementarea cu 1 a vectorului față de K. Asta înseamnă că șirul ajunge în poziția inițială în momentul în care lungimea vectorului este egală cu K sau multipli de K. Ceea ce rezultă că mișcările efective sunt doar în zona de rest a împărțirii lui K cu numărul de coloane ale blocului.
Funcția propusă:
=LET(arr; TRIM(TEXTSPLIT(A2;","));
vk; B4;
vMod; MOD(vk;COLUMNS(arr));
IF(vMod=0;arr;HSTACK(TAKE(arr;;-vMod);TAKE(arr;;COLUMNS(arr)-vMod))) )În care:
- arr – este variabila care stochează descompunea șirului într-un vector. Forma din imaginea de mai sus este reprezentarea în localizarea Romanian a blocului.
Hint: într-o funcție oarecum mai complexă dacă dorim să vedem rezultate intermediare ele apar ca tool-tip pe funcție în Excel sau se pot afișa direct în construcția formulei folosind tasta F9:
- vk – preia valoarea lui K din celula B4
- vMod – calculează restul împărțirii dintre K și numărul de coloane a șirului arr
- IF-ul tratează excepțiile când vMod ia valoarea 0 ceea ce înseamnă că lungimea vectorului este egală cu K, deci afișez vectorul, iar dacă vMod nu este 0 se afișează cele două șiruri construite cu HSTACK() asemănător cu versiunea din B6 dar puțin mai concentrată funcția.
În formatul cu K negativ, șirul se descompune din stânga spre dreapta, prima valoare din stânga devenind ultima valoare din dreapta. Șirul: {1, 2, 3, 4, 5, 6, 7, 8} devine în -2 rotații: {3, 4, 5, 6, 7, 8, 1, 2}.
Rotația șirurilor de K ori în seturi specifice
Oare de ce nu am complica puțin problema?! Adică în loc de valoarea 1 să introducem un număr nou care să reprezinte un set de numere cu care să treacă la iterația următoare. Aici probocarea a fost puțin mai mare pentru că lucrurile merg destul de rău cu numere de rotații și seturi de numere care depășesc lungimea șirului.
Pentru rezolvare a trebuit să calculez și MOD-ul de set ca rest al împărțirii setului dat la lungimea șirului, în așa fel încât dacă setul este mai mare ca șirul să se rotească doar restul valorilor rămase. De exemplu dacă am avea un șir: {1, 2, 3, 4, 5, 6, 7, 8} într-un set de 9 ar însemna să ne întoarcem de la capătul șirului cu numărarea până la nouă, ceea ce înseamnă că avem un rest de 1. Șirul rezultat într-o rotație (K=1) ar fi: {8, 1, 2, 3, 4, 5, 6, 7}
Ca să pot calcula totuși într-o singură funcție avem nevoie de MOD(ModK * ModSet; lungimea șirului). Funcția din G2 este în exemplul meu: =MOD(E2*F2;C2)
Rotațiile pe fiecare K în seturi specifice numere naturale pozitive sau negative, se pot rezolva cu funcția:
=LET(arr;TEXTSPLIT(A2;",");
vk;B4;
vSet;B5;
vLen;COLUMNS(arr);
vModk;MOD(vk;vLen);
vModSet;MOD(vSet;vLen);
vMod;MOD(vModk*vModSet;vLen);
final;IF(vMod=0;arr;HSTACK(TAKE(arr;;-vMod);TAKE(arr;;vLen-vMod)));final)în care:
- arr – preia șirul splitat;
- vk – preia valoarea lui K;
- vSet – preia valoarea setului;
- vLen – calculează lungimea vectorului;
- vModK – calculează restul înmpărțirii lui K la lungime vector;
- vModSet – calculează restul înmpărțirii setului la lungime vector;
- vMod – calculează restul împărțirii celor două resturi anterioare la lungime;
- final – este calcului de final în care folosesc aceeași tehnică specificată anterior.
Cel mai dificil a fost să ajung la acel MOD de MOD-uri, în rest manipulare de valori simplă.
Dincolo de exercițiu matematic, la ce putem folosi? Eu mă gândesc la criptografie dar și la schimbul de ture pentru angajați sau alocarea de tickete și poate și altele.
În articolul viitor voi trata tot o problemă de vectori, poate puțin mai simplă: OddOccurrencesInArray
Sper să fie util cuiva!
Valy Greavu - Live Blog 