Come promesso, ecco i vincitori con le loro soluzioni. Ricordiamoci prima il problema:
Dato un array di interi dispari, oddArray, che determina una sequenza monotona crescente, e un intero pari, evenValue, si chiede di implementare la funzione:
public static int IndexOfOddGreaterThanEven(int[] oddArray, int evenValue)
che ritorni l'indice del primo elemento di oddArray maggiore di evenValue. Nel caso evenValue > max(oddArray) la funzione ritorna -1. Si presuppone che i parametri siano validi e che quindi l'implementazione non richieda una verifica di questi. Nell'implementazione è vietato l'uso di istruzioni di selezione, istruzioni di iterazione oppure dell'operatore condizionale "?"!
Abbiamo un array ordinato di elementi (interi dispari) e dobbiamo cercare al suo interno in base a un elemento (intero pari) che sappiamo non fare parte di esso. L'elemento dispari che stiamo cercando dev'essere il primo maggiore dell'intero pari (siccome l'array è una sequenza monotona crescente, il primo sarà anche il più piccolo). Il Framework ci offre il metodo statico System.Array.BinarySearch che, nel caso evenValue > max(oddArray) ritorna "the bitwise complement of (the index of the last element + 1)", mentre nel caso evenValue < max(oddArray) ritorna "the bitwise complement of the index of the first element that is larger than value". In tutti e due i nostri casi, ritorna quindi il complemento binario di un indice. Conviene perciò concentrarsi sulla funzione ~System.Array.BinarySearch (cioè abbiamo applicato il complemento binario al valore ritornato - perché? perché l'operatore complemento binario è identico al suo inverso o, in altre parole, il complemento binario doppiamente applicato non cambia l'operando). Cosa ritorna allora nel nostro caso ~System.Array.BinarySearch?
- oddArray.Length quando evenValue > max(oddArray)
- l'indice del primo elemento di oddArray maggiore di evenValue quando evenValue < max(oddArray)
Ci siamo quasi. Manca solo che ritorni -1 al posto di oddArray.Length. Dobbiamo quindi trovare una funzione che ritorni:
- x quando x è da 0 a oddArray.Length - 1
- -1 quando x = oddArray.Length
Sembra una specie di modulo. Il modulo x % oddArray.Length cosa avrebbe ritornato?
- x quando x è da 0 a oddArray.Length - 1
- 0 quando x = oddArray.Length
Come fare a ottenere -1 al posto di 0? Semplice: (x + 1) % (oddArray.Length + 1) - 1. Per non lasciare spazio a dubbi dimostriamo che (x + 1) % (oddArray.Length + 1) - 1 è:
- x per x da 0 a oddArray.Length - 1
- -1 per x = oddArray.Length
Abbiamo che (x + 1) % (oddArray.Length + 1) - 1 è:
- x + 1 - 1 per x + 1 da 0 a oddArray.Length + 1 - 1
- 0 - 1 per x + 1 = oddArray.Length + 1 - 1
cioè (x + 1) % (oddArray.Length + 1) - 1 è:
- x per x + 1 da 0 a oddArray.Length
- -1 per x + 1 = oddArray.Length
oppure:
- x per x da -1 a oddArray.Length - 1
- -1 per x = oddArray.Length - 1
Ci sta benissimo il fatto che la funzione ritorni x quando x = -1. Quindi? Quindi abbiamo dimostrato che:
// la soluzione di Ernest Morariu (3), Roberto Messora (4)
public static int IndexOfOddGreaterThanEven(int[] oddArray, int evenValue)
{
return (~Array.BinarySearch(oddArray, evenValue) + 1) % (oddArray.Length + 1) - 1;
}
è una soluzione. Ma con il vostro aiuto, non l'unica!
Flavio Polesello è stato il primo che mi ha mandato una soluzione corretta. Eccola qui:
// la soluzione di Flavio Polesello (1)
public static int IndexOfOddGreaterThanEven(int[] oddArray, int evenValue)
{
return ~(Array.BinarySearch(oddArray, evenValue) % (~oddArray.Length));
}
Complimenti Flavio! Flavio ieri sera mi ha mandato un suo quiz con una soluzione di una bellezza non da poco... (e l'ho convinto di aprirsi un blog qui perchè mi sa che ne abbia di cose da dire - ho fatto bene?)
M.rkino (cliccate sul link, non porta al suo blog! :-)) è stato il secondo che mi ha mandato una soluzione corretta:
// la soluzione di Marco Barzaghi (2)
public static int IndexOfOddGreaterThanEven(int[] oddArray, int evenValue)
{
ArrayList numbers = new ArrayList(oddArray);
numbers.Add(evenValue);
numbers.Sort();
numbers.Add(string.Empty);
int evenIndex = numbers.IndexOf(evenValue);
object itemGreaterThanEven = numbers[evenIndex + 1];
return Array.IndexOf(oddArray, itemGreaterThanEven);
}
Ernest Morariu è stato il primo che ha trovato la mia stessa identica soluzione e il terzo che mi ha mandato una soluzione corretta.
Roberto Messora è stato il secondo che ha trovato la mia stessa identica soluzione e il quarto che mi ha mandato una soluzione corretta.
Marco Poponi è stato il quinto e l'ultimo che mi ha mandato una soluzione corretta:
// la soluzione di Marco Poponi (5)
public static int IndexOfOddGreaterThanEven(int[] oddArray, int evenValue)
{
int[] temparray= new int[oddArray.Length + 1];
oddArray.CopyTo(temparray, 0);
temparray[oddArray.Length] = int.MinValue;
return Array.IndexOf(oddArray, temparray[-1 - Array.BinarySearch(oddArray,evenValue)]);
}
In tanti avete provato e questa è la roba più importante.
Grazie a tutti e tenete d'occhio Flavio Polesello! :-)