February 04, 2018 · C Programmazione

Il divertimento nel risolvere esercizi con una sola riga di codice

C'è una cosa che mi ossessiona ogni volta che scrivo righe di codice e cioè il fatto di scrivere poche righe, a volte per esercizi semplici sono letteralmente ossessionato nel cercare di risolverli utilizzando solo una riga sola, un classico esempio è stata la ricerca dei numeri primi in questo articolo.
Per esempio se si vuole calcolare il fattoriale di un numero, si potrebbe utilizzare questo semplice metodo (evito algoritmi complessi perchè l'articolo non parla di ciò):

FATTORIALE DI UN NUMERO

unsigned int fact(unsigned int num){
  
  if(num <= 1){
    return 1;
  }
  
  num = num * fact(num - 1);
  
  return num;
  
}

Ecco io personalmente non ci riesco a scriverlo cosi, a me viene naturale scriverlo e non capisco come le persone possano scriverlo veramente cosi, non so voi ma a me tutte queste righe di codice sono completamente inutili, mi viene naturale scriverlo cosi:

return num <= 1 ? 1 : num * fact(num - 1);

Visto? Una riga e tutto è stato risolto non c'è bisogno di righe su righe e l'esercizio è anche abbastanza semplice non ci dovrebbero essere problemi.

SWAP FRA DUE NUMERI

Dovete scambiare due numeri, bè normalmente si fa cosi:

sentinella = a;
a = b;
b = sentinella;

Ma avete mai provato a fare cosi? :

a ^= b ^= a^= b;

MASSIMO COMUN DIVISORE

Un classico approccio iterativo potrebbe essere:

int gcd(int a, int b) {
  long r, i;
  while(b!=0){
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}

E allora perchè non fare direttamente:

int gcd(int a, int b){
    return (b==0) ? a : gcd(b, a%b);
  }

o peggio ancora !

int gcd(int a, int b)
{
    while(b) b ^= a ^= b ^= a %= b;
    return a;
}

Come dico sempre, binario no?

FATTORIALE MAGGIORE

Un altro esercizio potrebbe essere di trovare il fattoriale maggiore che il vostro sistema sappia calcolare, anche ciò può essere risolto in una sola riga.

unsigned int len(n){
    return (fact(n) != 0)? len(n + 1) : --n);
}

SERIE DI FIBONACCI

Insomma come vedete tutto si può fare in una sola riga, un altro esempio? la serie di fibonacci. Se si vuole ottimizzare il codice questo approccio sarebbe naturale anche se letteralmente da migliorare insomma sappiamo che l'iterazione è più veloce della ricorsione

int Fibonacci(int n) { 
if(n <= 0) return 0;
if(n > 0 && n < 3) return 1;

int result = 0;
int preOldResult = 1;
int oldResult = 1;

for (int i=2;i<n;i++) { 
    result = preOldResult + oldResult;
    preOldResult = oldResult;
    oldResult = result;
}

return result;}

Ma se dovete svolgere un rapido calcolo o un esercizio universitario che non a fine a se stesso perchè non scrivere direttamente cosi?:

unsigned long long fibonacci(unsigned long long num){
  return num <= 1 ? num : fibonacci(num - 1) + fibonacci(num - 2);
}

ESERCIZIO UNIVERSITARIO

Ok questi esercizi erano banali e anche le loro soluzione dunque è naturale che ad un esame non vi si chieda qualcosa di cosi semplice, ma proviamo a prendere questa traccia di esame di fondamenti 1.

Descrizione del problema
Si vuole progettare un algoritmo per risolvere il seguente problema. Data una sequenza di
interi, determinare il numero di sotto-sequenze massimali di interi consecutivi che sono tutti
positivi o tutti negativi.
Ad esempio se la sequenza di interi è [2, 3, -4, -1, 11, -1, -2], la soluzione dell’istanza del
problema è 4. Infatti la sequenza di interi è costituita da 4 sotto-sequenze massimali di interi
consecutivi che sono tutti positivi o tutti negativi: [2, 3], [-4, -1], [11] e [-1, -2].
Se la sequenza di interi è [2, 0, 3], la soluzione dell’istanza del problema è 2. Infatti la sequenza
di interi è costituita da 2 sotto-sequenze massimali di interi consecutivi che sono tutti positivi o
tutti negativi: [2] e [3]. Notare come l’intero 0 non faccia parte di nessun sotto-sequenza.

La soluzione del test illustrata è questa:

int contaSequenze(int interi[], int lunghezza) {
	int numeroSequenze;		// il numero di sequenze
	numeroSequenze = 0; 	// nessuna sequenza inizialmente

	for(int i=0; i<lunghezza; i++) {
		if(i==0) { 
			if(interi[i]!=0)
				numeroSequenze++;
		}
		else{
			if((interi[i]>0 && interi[i-1]<=0) || (interi[i]<0 && interi[i-1]>=0)) 
				numeroSequenze++;
		}
	}
	return numeroSequenze;
}

Scrivere tutte queste righe porta via un pò di tempo durante l'esame, allora perchè non scrivere direttamente una sola riga che faccia tutto il lavoro principale?

int cnt = A[0] != 0;
for (i = 1; i < size_t; i++){
    cnt += A[i] != 0 && A[i - 1] * A[i] <= 0;
}
return cnt;

Che ci crediate o no, farà esattamente la stessa cosa, dunque come vi ho detto tutto può essere ridotto ad una sola riga.

Come è possibile tutto ciò?

Allora il programma ci chiede di contare le sottosequenze, e se vi è uno zero prenderlo come separatore di sequenza. Per la prima sequenza diamo per scontato che la posizione -1 sia uno zero ed in base al segno dell'elemento corrente o successivo vi sono in totale 9 possiblità.

C = Corrente
P = Precedente

C\P| <  0  >
---+---------
 < | 0  1  1
 0 | 0  0  0
 > | 1  1  0

Dunque inizialmente implementiamo la funzione in questo modo modificando passo per passo il codice della soluzione proposto dall'università:

Per risolvere la posizione del primo elemento dobbiamo controllare che non sia zero perchè non possiamo dare per scontato che sia un numero positivo o negativo, dunque la soluzione dell'università ci consiglia di fare cosi:

		if(i==0) { 
			if(interi[i]!=0)
				numeroSequenze++;
		}

Controlla se il contatore vale 0, cioè se punta al primo elemento e se lo fa, esegue un controllo per controllare se esso è diverso da zero e se lo è la variabile numeroSequenze viene incrementata. Il codice non ha molto senso ciò per far si che codesta riga venga controllata i deve valere 0 e sappiamo che i vale zero solo una volta, allora perchè fare il controllo ogni volta? è letteralmente un controllo inutile. Dunque perchè non farlo fuori dal ciclo for in questo modo? (per comodità numeroSequenze verrà rinominata in cnt -> contatore)

cnt = A[0] < 0 || A[0] > 0;

Che può essere tranquillamente riassunto in:

cnt = A[0] != 0;

cnt varrà 1 se l'espressione sarà vera e viceversa 0 se sarà falsa, binario no?

Una volta fatto ciò ci assicuriamo di far partire il contatore da 1 visto che il check sull'elemento 0 è stato già fatto. L'università in questo caso propone codesto codice:

else{
if((interi[i]>0 && interi[i-1]<=0) || (interi[i]<0 && interi[i-1]>=0)) 
	numeroSequenze++;
}

Che non è cosi diverso dal mio ma che comunque può essere ottimizzato. Per esempio possiamo racchiudere il tutto in una sola riga avvalendoci degli operatori logici:

cnt+= (A[i - 1] >= 0 && A[i] < 0) || (A[i - 1] <= 0 && A[i] > 0);

Il seguente codice non farà altro che fare confrontare se l'elemento precedente è maggiore ugugale a 0 e se contemporaneamente l'elemento corrente è minore di zero.

Dunque se per caso l'elemento A[i-1] e A[i] fossero un numero negativo:

A[i - 1] >= 0 && A[i] < 0) e (A[i - 1] <= 0 && A[i] > 0)
ritornerà come risultato 0, visto che sarà falso cioè:

cnt = cnt + 0

Viceversa se A[i - 1] fosse positivo e A[i] fosse zero per esempio per come è strutturato l'esercizio anche se A[i + 1] fosse positivo dovremmo lo stesso incrementare il valore di cnt e dunque verrebbe come risultato:

cnt = cnt + 1

Ricomponendo insieme i pezzi ci viene:

cnt = A[0] != 0;
for (i= 1; i < size; i++)
    cnt += (A[i - 1] >= 0 && A[i] < 0) || (A[i - 1] <= 0 && A[i] > 0);

Che già è meglio di:

for(int i=0; i<lunghezza; i++) {
		if(i==0) { 
			if(interi[i]!=0)
				numeroSequenze++;
		}
		else{
			if((interi[i]>0 && interi[i-1]<=0) || (interi[i]<0 && interi[i-1]>=0)) 
				numeroSequenze++;
		}
	}

Ma la cosa non è finita, può essere ancora migliorato ma a discapito della sicurezza. Se siamo sicuri che il prodotto della moltiplicazione non vada in overflow possiamo direttamente abbreviarlo in questa maniera:

cnt += A[i] != 0 && A[i - 1] * A[i] <= 0;

proviamo a scomporla per decifrarla con i seguenti dati:
A[i-1] = 2
A[i] = -3:

A[i] != 0

dunque sarebbe:

cnt+= 1 && A[i - 1] * A[i] <= 0;

Poi
A[i - 1] * A[i] <= 0

cioè 2 * -3 è minore uguale a 0? Si! perchè fa -6.

cnt= cnt + 1 && 1

cioè:

cnt= cnt + 1

E se tutti e due i numeri sono positivi?
A[i-1] = 2
A[i]= 2
bè:

cnt += A[i] != 0 && A[i - 1] * A[i] <= 0;
cnt += 1 && A[i - 1] * A[i] <= 0;
cnt += 1 && 2 * 3 <= 0;
cnt += 1 && 0;
cnt = cnt + 0;

Visto? Logica no? Da 10 righe lo abbiamo reso lungo 3 righe !

int cnt = A[0] != 0;
for (i = 1; i < size_t; i++){
    cnt += A[i] != 0 && A[i - 1] * A[i] <= 0;
}
return cnt;

La priorità di questo esempio non era la sicurezza ma quella di cercare di accorciare il più possibile il codice.
Tutto ciò nella in un ambiente lavorativo è sconsigliato per ovvie ragioni, ma come gioco a mio parere vale la candela, prova a prendere un qualsiasi esercizio risolvilo e vedi se riesci a renerlo meno lungo di quanto sia o addirittura renderlo lungo una riga !.

  • LinkedIn
  • Tumblr
  • Reddit
  • Google+
  • Pinterest
  • Pocket
Comments powered by Disqus