grade: 125/100
Looking for a translated version? Just click here!
Data la mancanza di spiegazioni del progetto attraverso l'utilizzo del Longest Increasing Suqsequence algorithm (trad. "algoritmo della maggiore sottosequenza crescente"), ho deciso di scrivere questo README per venire in soccorso a tutti quegli studenti che non hanno ben capito come implementarlo.
Il progetto richiede di ordinare una qualsiasi sequenza di numeri interi, esattamente come fa un qualsiasi algoritmo Sort ideato e collaudato da almeno 60 anni. Tuttavia, non stareste leggendo questo testo se non apparteneste ad un qualsiasi corso della 42 in giro per il mondo, ed è statisticamente appurato che la vostra probabilità di perdere capelli aumenta proporzionalmente al vostro leggere nuovi subject. Quindi, senza alcun indugio, spieghiamo le particolarità delle richieste!
Abbiamo anzitutto due stack: una riempita dai numeri casuali dati, lo stack_a, e una vuota che ci servirà da appoggio, la stack_b.
Le stack non hanno una definizione obbligatoria! Noi abbiamo lavorato a liste per ovviare al fatto che gli array di int non hanno un termine nullo di conclusione col quale contarne la lunghezza.
Altre idee che abbiamo sentito da colleghi sono quelle di lavorare a strutture, con i due array accompagnati dalle loro size ed eventualmente da altri array di appoggio per i vostri calcoli successivi. Personalmente mi sento di dissuadervi da questa idea semplicemente per non dover gestire troppe allocazioni, ma lascio al vostro giudizio la decisione. Dopotutto, quello che conta è il risultato!
Le mosse a nostra disposizione sono 11, ma per semplicità le andremo a suddividere nelle 4 tipologie:
sa/sb/ss: switch, scambia il primo numero della stack col secondo.ra/rb/rr: rotate, sposta l'ultimo numero della stack in prima posizione, facendo conseguentemente scalare tutti gli altri.rra/rrb/rrr: reverse rotate, banalmente la stessa cosa di cui sopra ma nel senso opposto.pa/pb: _push in *, sposta il numero in prima posizione della stack opposta nella stack nominata. Quindi pb porta il primo numero da a a b.
Non starò qui a spiegare per bene come funzionano e come vanno utilizzate, penso che a riguardo ci siano ottimi lavori scritti da colleghe e colleghi in giro per il mondo. Vi lascio un link che ha aiutato me e il mio compagno di merende durante il brainstorming iniziale. Sappi che le sue istruzioni sono valide anche per il nostro progetto fino alla size 3 e size 5. Ecco a te!
Il motivo per cui non abbiamo voluto seguire tutta la sua linea di pensiero è perché purtroppo a nostro parere non si può arrivare al massimo dei voti con una tecnica del genere, ma saremmo ben lieti di essere smentiti! Nel caso in cui il suo ragionamento vi piaccia di più, un altro ragazzo italiano ha pubblicato questo codice molto simile e super ordinato col quale ha ottenuto un ottimo voto di 90/100.
N.b.: purtroppo senza il massimo dei voti, il bonus non verrà contato. 90/100 è praticamente il secondo miglior voto ottenibile. Vi conviene davvero clonare e pushare senza prima quantomeno provare a prendere qualcosa in più?
Veniamo ora alla vera bestia di Satana di questo progetto: il numero di mosse possibili. Se leggete approfonditamente il subject, non troverete comunque un riferimento a riguardo. Vi basta tuttavia sapere che per ottenere il massimo dei voti servono 700 mosse con 100 numeri e 5.500 mosse con 500 numeri. Abbiamo stimato un 58% di bestemmie sul progetto dedicate soltanto alla loro ottimizzazione. Noi abbiamo agito così.
L'idea di fondo è particolarmente semplice ma non altrettanto facile da pensare senza aiuti da parte di altri. Per chi è particolarmente bravo in matematica, la logica è molto simile a quella dei sottoinsiemi ordinati. Per tutti gli altri, partiamo dall'analisi del nome dell'algoritmo:
- longest: fin qui tutto ok, no?
- increasing: letteralmente "crescente"
- subsequence: sottosequenza, ossia un gruppo di numeri presi dall'insieme totale, solitamente (ma non necessariamente) con un criterio matematico.
Banalmente, significa che tra tutte le possibili sottosequenze o combinazioni dobbiamo prenderne una ordinata in maniera crescente, in particolare la più lunga di tutte!
Facciamo un esempio: abbiamo una serie di numeri casuali come
4 - 8 - 2 - 9 - 12 - 1 - 27 - 13 - 32 - 10
Di questi, una sottosequenza crescente può benissimo essere 4 - 8 - 9, 2 - 9 - 13 - 32 o anche 1 - 10.
Il nostro obiettivo tuttavia è quello di prendere la più lunga possibile, in questo caso:
4 - 8 - 9 - 12 - 27 - 32 oppure 4 - 8 - 9 - 12 - 13 - 32.
Le due sottosequenze sono equivalenti in quanto entrambe sono lunghe 6.
Fate caso al mantenimento dell'ordine iniziale! Non possiamo prima mescolare i numeri e poi prenderci i valori che più ci piacciono, o avremmo già ordinato tutto e il nostro lavoro sarebbe finito...
Non è mio compito qui spiegarvi come implementare il codice, l'idea di fondo di fatto è lunga 4 righe di codice (che vi lascio qui sotto) ma il grosso viene nel prendersi tutti i valori desiderati. I due cicli necessari sono:
for (int i = 1; i < n; i++)
{
lis[i] = 1;
for (int j = 0; j < i; j++)
{
if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
}
}
Per aiutarvi nella comprensione dell'algoritmo, vi lascio il link di GeeksForGeeks che ci ha aiutato a capire la logica dietro. Prestate attenzione al fatto che loro ritornano soltanto la grandezza massima della sottosequenza...
Una volta trovata la sequenza ordinata, vi rimane soltanto da tenervela sulla stack_a e da portare tutti gli altri numeri sulla stack_b.
A fine lavoro vi risulterà una struttura simile:
Ancora non vi ho parlato del visualizer? Vi tornerà molto utile a fine stesura del codice...
Nei passaggi precedenti non ho esternato il motivo per cui cominciamo il progetto calcolando il LIS. Nel caso non lo abbiate capito, l'obiettivo è quello di inserire tutti gli altri numeri in uno stack già ordinato, seppur non completo! Questo ci permette infatti di effettuare scambi tra lo stack_a e lo stack_b soltanto una volta, per poi chiudere subito l'ordinamento. Il modo per spostare i numeri puó essere uno soltanto: spostare il primo numero della stack_b di fronte al numero successivamente maggiore dello stack_a, che dovrà essere obbligatoriamente messo in prima posizione nello stesso.
Abbiamo tuttavia un problema non banale: inserire sempre il primo numero della stack_b nella stack_a fa roteare quest'ultima a vuoto troppe volte, aumentando esponenzialmente le mosse.
Vi basti sapere che l'algoritmo più banale possibile supera abbondantemente le 100.000 mosse con 500 numeri... Quindi, come ottimizzare?
La nostra soluzione è molto a rischio di TLE (lett. Time Limit Exceeded), siamo consapevoli che esistono soluzioni più veloce e meno rischiose, ma siamo estremamente certi che a livello teorico-pratico funzioni e che permetta una delle migliori ottimizzazioni su tutte le possibili. Ma prima, forse è meglio prendersi una pausa, che ne dici?
Se state immaginando una quindicina di funzioni da scrivere dopo questo titolo, probabilmente avete sottostimato il lavoro che avete ancora di fronte.
Non c'è molto da fare: dovete calcolarvi per ogni numero quante mosse dovete fare nel migliore dei casi. Abbiamo ragionato così:
- Create due array di appoggio (
mov_aemov_bpossono andare benissimo!) dove salvare i valori di cui sotto 😉 Entrambi devono avere dimensionesize_b: infatti i numeri da salvarsi sono riferiti unicamente ai numeri nella stack_b. Mi spiego peggio: siccome il nostro obiettivo è riportare tutti i numeri di b nella a, dobbiamo calcolare quante mosse dobbiamo fare sia per muovere il numero di b in prima posizione, sia per muovere lo stack_a in modo tale da poter inserire correttamente il numero di b. Conseguentemente, ad ogni numero di b corrisponde non solo un tot di mosse per arrivare in prima posizione ed applicare quindipa, ma anche un tot di mosse per mettere in prima posizione il numero corretto di a, tale per cui con l'inserimento del numero di b la stack_a rimanga ordinata. - Cominciamo quindi a fare i nostri calcoli: si prende la stack_b e si calcola la distanza di ogni numero dalla prima posizione. Banalmente, a seconda che loro si trovino sopra o sotto la posizione
size_b / 2, si utilizzeranno le mosserborrb. Il valore assegnato sarà positivo se bisogna utilizzarerb, negativo se bisogna utilizzarerrb. - si trova nello stack_a il numero immediatamente maggiore a quello preso in considerazione nello stack_b. Aiutatevi col presupposto che lo stack_a è già ordinato! Trovate la coppia per il quale
mov_a[i] < mov_b[j] < mov_a[i + 1]e mettetemov_a[i + 1]in prima posizione. Esempio: se abbiamo da inserire un5in uno stack_a uguale a3 - 8 - 19 - 25, sarà l'8ad andare in prima posizione. - si calcola lo stesso valore del passaggio 2, ma riguardante
mov_a[i + 1].
Vi porto un esempio pragmatico più complesso, preso da una simulazione reale in cui avevo 7 numeri sullo stack_b e più di 12 numeri sullo stack_a:
MOV_A MOV_B
4 0
-5 1
3 2
-1 3
0 -3
4 -2
-5 -1
La colonna B indica la distanza di ogni numero di stack_b, mentre la colonna A indica la distanza del numero di stack_a immediatamente maggiore al suo corrispondente in b. Vediamo ora come arrivare all'atto pratico!
Ok, sappiamo tutte le mosse per ogni numero che abbiamo nella stack_b. Ma quale prendiamo? La risposta dipende dalle casistiche, a seconda del senso di rotazione del vettore:
| mov_b + | mov_b -
--------|-----------------------|-----------------------
mov_a + | max(mov_a, mov_b) | mov_a + |mov_b|
--------|-----------------------|-----------------------
mov_a - | |mov_a| + mov_b | |min(mov_a, mov_b)|
Prendo per assodato che ricordiate il valore assoluto...
In tutti e quattro i casi, il valore rilasciato altro non è che il numero totale di mosse che dovete fare prima di pa!
Ma prima occorre sottolineare perché sia necessario prendere il massimo o il minimo dei due valori nel caso dello stesso segno per i due numeri. Se vogliamo ottimizzare al meglio il codice, dobbiamo per forza usufruire delle mosse rr e rrr, che con una sola riga di output effettuano la rotazione ad entrambi gli stack. Va da sé che dividere per 2 le mosse è un guadagno di tempo che non possiamo lasciarci sfuggire...
Riprendendo quindi l'esempio di cui alla sezione sopra, va da sé che 4 0 diventa meno conveniente di 3 2, in quanto per il primo si eseguono 4 mosse mentre per il secondo 3.
Ovviamente tutti questi calcoli vanno ripetuti size_b volte!
Una volta effettuate tutte le mosse pa possibili, dovreste ritrovarvi in una situazione simile in cui il vettore è ordinato ma non comincia nella giusta posizione:
Ricordatevi di minimizzare le mosse anche qui! O rischierete di perdervi qualche centinaio di mosse nell'ultima parte.
Il nostro progetto è così concluso! Fatemi sapere se avete problemi o suggerimenti, sarò ben lieto di discuterne con voi su Slack (@mcerchi) o via mail.