Programmando in C

La scorsa settimana l'ho dedicata prevalentemente a correggere il paper e ripassare C.

Alla fine non e' cosi' male come linguaggio, non mi ricordavo piu' la potenza dei puntatori, ed un bel ripassone e' servito. Ne ho approfittato cosi' per creare un programma che mi risolvesse un giochino che sul cellulare, che mi sta facendo dannare dato che non riesco a trovarne la soluzione.

Il giochino si chiama Stone Bricks, ed e' presente sotto forma di gioco java sui Moto Razr V3. Il gioco e' abbastanza semplice: data una scacchiera a forma di croce, vengono disposte n pedine sulla scacchiera. Se una pedina e' adiacente ad un altra su un lato (verticale o orizzontale), mentre sull'altro lato e' presente una casella vuota, la pedina puo' essere mangiata da quella adiacente, che si posizionera' sulla casella vuota. Il gioco termina quando c'e' solo una pedina sulla scacchiera. Ci sono 5 configurazioni iniziali, la cui difficolta' varia in base al numero di pedine iniziali presenti. La scacchiera e' composta da 45 caselle, con blocchi di 3x3 messi a croce.

Io ho risolto le prime quattro, mentre non riesco a finire la quinta (rimango sempre con almeno 3 pedine sulla scacchiera, disposte in modo tale che non possono annullarsi a vicenda). Allora ho pensato di fare un programma per risolverlo.

Il programma C e' strutturato come segue: data una matrice 9x9, valorizzo le caselle della croce a "1" se e' presente una pedina, "0" altrimenti. Le caselle non facenti parte della croce hanno valore "-9". Una struttura dati ad albero tiene traccia delle mosse effettuate e da effettuare, utilizzando un algoritmo DFS ricorsivo per scoprire ed analizzare i nuovi nodi. Una struttura ad albero binario parallela poi e' usata per memorizzare le configurazioni della matrice gia' visitate, in modo tale da non ri-applicare la DFS su configurazioni gia' visitate (capita spesso che una stessa configurazione possa essere raggiunta partendo da passi diversi).

I problemi principali di questo programma sono due: l'esplosione di stati della DFS e la lentezza nel controllo di una configurazione gia' osservata. In particolare osservo gravi rallentamenti sull'ultimo livello, che riempie 44 delle 45 caselle disponibili.
Il primo problema non e' poi cosi' grave: la DFS non ha bisogno di memorizzare troppi nodi contemporaneamente, in quanto ogni volta sono allocati solo tutti i nodi padri, i relativi fratelli e il nodo stesso. Contando che avendo 44 pedine al massimo risolvero' il problema in 43 mosse (ma che generalmente ci si ferma a 5 pedine sulla scacchiera), e che mediamente ad ogni mossa ne ho a disposizione altre 5, i nodi allocati contemporaneamente sono 38*5.
Il secondo problema invece e' piu' noioso. Le configurazioni possibili sulla scacchiera sono 2^45: non posso andare in accesso diretto alla memoria con 2^45 combinazioni cosi' son stato costretto a costruire un albero binario, che per ogni casella della matrice avesse un puntatore a un nodo "1" o "0". Ogni volta che cosi' ho un nuovo passo mi trovo a scorrere tutto l'albero per vedere se e' gia' stato visitato o meno.

Miglioramenti

• Ogni matrice che visito la registro 4 volte nell'albero, ovvero registro anche quella speculare da ogni lato. In questo modo aumento la probabilita' di trovare un nodo gia' visitato (e che non porta a soluzione).

• Valutavo l'idea del backtracking, al posto della ricorsione. Dovrei implementare un sistema per salvare gli iteratori delle matrici ad ogni singolo step, nulla di complicato, ma non so quanto migliori il programma, in quando reputo che non sia li' il problema principale.
  

• Dimezzare l'albero binario. Potrei portare l'albero binario a "soli" 13 nodi al posto di 45, ed allocare per gli ultimi 32 un array lungo 2^32.

Tutti questi miglioramenti comunque mi pare non abbassino la complessita' del problema, che rimane sempre alta.

E nel frattempo non ho ancora la soluzione...

Bloomberg e il C

Lunedi' scorso ho avuto un colloquio a Londra presso gli uffici di Bloomberg.

Sede stupenda, piu' bella ancora di quella di Accenture. Peccato che mi abbiano segato.

Il colloquio e' durato due ore e' un quarto, precisamente dall'una fino alle tre e un quarto del pomeriggio. Il posto era un internship in R&D presso il loro laboratorio informatico, e sono arrivato al colloquio dopo aver superato la prima scrematura dei curriculum, quindi un test su Java della Brainbench.

Spendo due parole sul test, perche' mi sembrano doverose in caso che qualcuno debba affrontare queste prove. Il test consiste in 40 domande, 3 minuti massimo a domanda, non c'e' possibilita' di tornare sulle risposte precedenti e ci si puo' prendere una sola pausa di al massimo 30 minuti.
Le domande del test Java Fundamental consistevano nel capire il funzionamento di porzioni di codice (per esempio dire il valore di una variabile dopo un flusso computativo), oppure nella conoscenza e nell'uso di svariate librerie, in particolare quella dei Thread, dell'RMI e della AWT.
Il test non e' complicato: avendo la pagina delle API Java a disposizione su un'altra finestra, e il buon Google sempre pronto, credo che questo test voglia piu' che altro capire quanto tempo ci si metta a trovare una soluzione a domande non troppo difficili. Curioso comunque il fatto che, pur programmando da quattro anni in Java (sempre a livello scolastico ovviamente) e ritenendomi un discreto programmatore non fossi in grado di rispondere a quasi nessuna domanda senza andare su internet a controllare bene.
Nessuna domanda su algoritmi, complessita', logiche di codice distribuito.. insomma, solo mera programmazione Java.

A Bloomberg l'avevo specificato che conoscevo Java, mentre C l'avevo visto molto tempo fa (un annetto circa quattro anni fa e un esame). Immaginate il mio sconforto quando mi vedo i primi due esaminatori con un bell'esamino in C! A parte le domande di rito, del tipo "Cosa ti piace della programmazione, perche' vuoi lavorare per Bloomberg" che mi ero gia' preparato a casa, credevo che il colloquio vertesse sulla costruzione di algoritmi e di processi concorrenti, e perche' no un pizzico di economia. Mi ero infatti ben preparato su queste materie..

I primi due esaminatori mi mettono davanti un semplicissimo codice C, e mi chiedono il valore delle variabili finali. La difficolta' stava appunto nel ricordarsi i puntatori degli array e simili.. ma boh, li' con qualche problemuccio iniziale me la son ancora cavata. Il secondo codice (sempre in C) invece era un programma che stampava una data. Questo programma aveva un problema sulla seconda stampa, e bisognava capire quale fosse. Li' ho fatto molta fatica a capire che era un problema di allocazione della memoria nello stack.. e chi se la ricordava piu' la gestione della memoria in C!

Oltre a queste due domande iniziali, il resto penso sia andato bene: mi e' stato chiesto di scrivere un programmino per calcolare il fattoriale, e si e' discusso sui vantaggi e gli svantaggi delle funzioni ricorsive. Quindi mi son stati proposti due test logici:

• un treno sta arrivando presso una galleria, in cui all'interno c'e' un uomo. L'uomo si trova ad 1/4 dall'uscita della galleria da dove sta arrivando il treno. Sia che l'uomo corra verso quell'uscita (andando quindi verso il treno, e percorrendo 1/4 di galleria) sia che l'uomo corra verso l'altra uscita (andando nella stessa direzione del treno, e percorrendo 3/4 di galleria), l'uomo si salva al pelo. Dire qual'e' il rapporto tra la velocita' del treno e dell'uomo.
• su un foglio e' disegnata una croce, la cui verticale e' composta da 3 coppie di quadretti bianchi, e l'orizzontale e' composta da 4 quattro quadretti bianchi (due sono in comune con la verticale). Riempire le otto caselle con i primi 8 numeri naturali, in modo tale che in nessuna casella adiacente (anche quelle diagonali sono da considerarsi adiacenti) contengano due numeri che sono successivi tra loro.

Dopo questi due test, e' arrivato il secondo esaminatore. Questo era piu' interessato agli algoritmi, e mi ha chiesto di pensare (ed implementare) un codice che, dato un array di numeri, ricavasse il primo numero univoco nell'array. Con lui si e' parlato di complessita' di algoritmi, quindi mi ha proposto un'altro quiz logico:

• tre carcerati hanno la possibilita' di uscire dalla prigione, indovinando il colore del proprio cappello. Se sbagliano vengono giustiziati, se non lo sanno rimangono in cella. Il guardiano benda uno dei tre carcerati, e dispone i cappelli sulle loro teste. I cappelli a disposizione del guardiano sono 5, 3 bianchi e 2 neri. Ogni carcerato non puo' vedere il proprio cappello ma solo quello dei colleghi (ovviamente quello bendato non vede nulla). Alla fine i due carcerati non bendati rispondono che non sanno qual'e' il loro cappello, mentre quello bendato dice di saperlo. Perche'?

Questo e' come si e' svolto il colloquio: mi e' stata poi alla fine fatta vedere come funziona il Bloomberg Terminal, quindi ho fatto un piccolo tour all'interno degli uffici.. quindi due giorni dopo mi han scaricato.

Dopo tutto questo ho sbagliato aereoporto al ritorno (al posto di andare a Luton son finito a Stansted) e cosi' son tornato a casa che era la mezza.

Presumbilmente volevano una persona che conoscesse bene C, o che lo conoscesse meglio di me in quel momento: pazienza.. ora sono quattro giorni che sto programmando C tutto il giorno e la notte, la prossima volta non mi fregheranno piu'. Anche perche' la preparazione che ho fatto per Bloomberg sta volta mi e' molto piaciuta, e sono soddisfatto comunque delle risposte che ho dato sui test logici e sugli algoritmi.

A breve tocca IBM.. ho passato la revisione del curriculum, ora devo fare un test attitudinale: chi sa che sia la volta buona!

PS: I codici che ho postato potrebbero non essere esattamente quelli che mi hanno proposto a Bloomberg. Sono abbastanza simili, ma non identici.