Bit calculator... I'm going slightly mad

I was solving just for kicks this very famous brain teaser:

Count the number of set bits in a number.

and this is what came out:

//edit: I have to find a proper way of formatting code here before posting...

Find the Largest Square Submatrix in a NxM Matrix

Some time ago a bright intern we had came up with a really interesting brain teaser he was asked during one of the interview he made to get an internship.
The problem is this:

having as input a random generated matrix N x M whose elements are integers with values {1,2,....,9}, you are asked to find the biggest square made of he same digits.
In the case there are multiple equally big squares, just pick up the first one.

Since it is and interesting brain teaser and I'm currently experimenting a bit with Dynamic Programming I came up with this solution:

Let's define T(i,j) as the side's length of the biggest square which is possible to build having those characteristic and having the cell (i,j) as bottom right element, then:

if

• (i,j) == (i-1,j-1) and
• the previous T(i-1,j-1) elements in the same column have the same value as (i,j) and
• the previous T(i-1,j-1) elements in the same row have the same value as (i,j)

then

• T(i,j) = T(i-1,j-1) +1

else

• T(i,j) = 1 since we can't expand the previous square and we have to start building another one instead

so basically if the matrix is:

5,5,6
5,5,5
5,5,5

the respective T(i,j) values when considering the cell (3,3) would be

1,1,1
1,2,1
1,1,X

being X what we want to find out.
So our if else will in turn compare the element (i,j) marked in green with the elements marked in red stopping when one of the checks fails or, if they all pass, updating the value to T(i-1,j-1) +1:

5,5,6
5,5,5
5,5,5

5,5,6
5,5,5
5,5,5

5,5,6
5,5,5
5,5,5

which in this case will fail at the second test causing: X = 1.
If the matrix would have been made of all of 5 then: X = T(i-1,j-1) + 1 = 2 + 1 = 3

Here comes the code:

void findMaxSquare(const unsigned int* aMatrix,

const unsigned int aNumRows, const unsigned int aNumColumns) {



unsigned int *result = (unsigned int*) malloc(sizeof(unsigned int) * aNumColumns * aNumRows);

int i,j;

// set the first row to 1 (it's the biggest square those cells can build)

for(i = 0; i < aNumColumns; ++i) {

result[i] = 1;

}

// set the first column to 1 (it's the biggest square those cells can build)

for(i = 1; i < aNumRows; ++i) {

*(result + i*aNumColumns) = 1;

}

unsigned int maxSquareSide = 1; // store the side of the biggest square we can build

unsigned int maxXIndex = 0; // and its row

unsigned int maxYIndex = 0; // and its column



for(i = 1; i < aNumRows; ++i) {

for(j = 1; j < aNumColumns; ++j) {

// check whether the current item is the same as the previous one

// if so, the previous element aMatrix[i-1][j-1] build a square of side result[i-1][j-1]

// so check whether the same value aMatrix[i][j] is repeated in column j result[i-1][j-1] times.

// if so, check whether the same value aMatrix[i][j] is repeated in row i result[i-1][j-1] times.

if( (aMatrix + i*aNumColumns)[j] == (aMatrix + (i-1)*aNumColumns)[j-1] &&

isColumnTheSame(aMatrix, aNumColumns, i, j, (result + (i-1)*aNumColumns)[j-1]) &&

isRowTheSame(aMatrix, aNumColumns, i, j, (result + (i-1)*aNumColumns)[j-1])) {

// if we get here, this item enlarges of 1 cell

// the square having as bottom right aMatrix[i-1][j-1]

(result + i*aNumColumns)[j] = (result + (i-1)*aNumColumns)[j-1] + 1;



//store the value and relative indexes if it's the biggest square found found so far

if(maxSquareSide < (result + i*aNumColumns)[j]) {

maxSquareSide = (result + i*aNumColumns)[j];

maxXIndex = i;

maxYIndex = j;

}

continue;

}

// this is the begininning of a new square

(result + i*aNumColumns)[j] = 1;

}

}



printf("the maximum square is made of '%d', is %3d digits wide and has top left ( %3d , %3d )\n",

(aMatrix+(maxXIndex-(maxSquareSide - 1))*aNumColumns)[maxYIndex - (maxSquareSide - 1)],

maxSquareSide,

maxXIndex - (maxSquareSide - 1) + 1,

maxYIndex - (maxSquareSide - 1) + 1);

free(result);

}

This algorithm can be still be improved:

1. if the input matrix is not a squared but n >>m or m>>n the first for loop instead of iterating through all the rows should iterate through max{n,m}
2. once found a square made of the same integers we should check whether is possible to build a bigger one, if not stop the procedure

about the complexity I believe it's a O(n*m*(n+m)/4) so for n=m O(n^3)

God Bless Peripheral Vision

Just saved my macbook pro from falling from the armrest of my sofa (yeah, I shouldn't have put it there in the first place, I know).
While I was reading a book something was bothering me, at the last (milli)second I realised it was my macbook that was slowly sliding out of the armrest.
Saved it when it had just begun the free fall.
God bless peripheral vision...that and my feline reaction time.

Underground Extreme Sports

If you're feeling like looking for some strong sensations, or maybe you're wondering which your limits are...in London you can find what you're looking for.
Jump on the piccadilly line, head to Covent Garden and alight there, look for the way out and, eh no! don't cheat!, please don't take the lift. There is a small corridor and if you just look up you'll see a fancy clue of what is smirky waiting for you: a nice 193 steps stair!
It is an experience that will get you out of breath.
Now I'm not particularly fit and actually I've never been that way, nonetheless I've never backed out while going up the stairs, on the contrary I really like them; my palmares proudly shows my achievements as the really big one that is in Caltagirone, the one that takes you to the youth hostel in Finale Ligure, Asinelli's tower in Bologna, the Tour Eiffel in Paris and counting...but this is a completely new sensation: it is a winding staircase whom you're not able to see the end of, nor understand how much of it you still have to face, it seems that you're wasting energies in vain!
No ok, maybe Covent Gardens' is not the worst, I had a similar experience when I went to San Pietro in Rome, there when you are on your way to reach the cupola's top you're actually walking inside it and the more you go up the more there isn't space enough to swing a cat :)
So, luckily, when you get out of Covent Garden there are plenty of food shops where to stop and get your energy back...in San Pietro when you're on top...you can just meditate instead! :)

Fear and Loathing in Stansted

Sbollita la rabbia eccomi qui a Stansted su di una panchina incazzato nero (ok, forse non mi sono ancora calmato del tutto).
Qualcuno mi deve 12 ore della mia vita, quel qualcuno le ha prese in cambio di miei 5 minuti di ritardo: 35 minuti prima del volo contro i 40 che la "strict" policy aziendale prevede. Non si finisce mai d'imparare inglese, "strict" pensavo volesse dire rigida/stretta invece, ecco!, è un false friend e vuol dire bensì "godo-nel-vederti-contorcere-su-di-una-panchina". Buono a sapersi, me ne ricorderò quando il CEO di ryanair attraverserà la strada mentre io sopraggiungo, con sospetto tempismo e malcelata calma, alla guida della mia R4 finemente agghindata per l'occasione con allegri rostri arrugginiti.
Ok, ora basta pensare a quel canazzo di bancata del CEO.
La situazione in aeroporto è surreale nè vuoto nè pieno, qualche persona corre, alcune invece hanno l'aria incredula di chi come me dovrà passare la notte qui.
E' appena passata davanti a me una ragazza che quasi in lacrime ha appena chiuso il telefonino; mi viene la brillante idea di consolarla con un po' di smalltalk e candidamente chiedo:
-you lost your flight too, haven't you?
-what? oh no no, I think I've just lost my job
vedendo la mia faccia sbiancare dalla vergogna sorride e si allontana tristemente. Ecco l'ennesima prove che nel mio caso pater certus est (non son sicuro di aver coniugato certo correttamente ma....), certe funamboliche abilità di gaffeur non possono essere frutto di un darwiniano salto evolutivo. No, decisamente non mi hanno messo in qualche culla sbagliata alla nursery.

Intanto qui il via vai continua ai passeggeri si sono aggiunti gli impiegati dei negozi ormai chiusi che tra 4 ore riapriranno. Fa effetto, sono veloci, quasi meccanici, sembra quando al teatro tra una scena e l'altra si spengono le luci e sul palco si vedono tante persone che nel buio si muovono a colpo sicuro, ognuno ha un suo compito per preparare la scenografia per la prossima scena.

Magneticamente gli sguardi adesso si dirigono verso un punto.
Sta passando una ragazza non tanto attraente, ma...sta spingendo un carrello a più piani pieno di cornetti, doughnuts, beveraggi vari!
Gli sguardi immediatamente non sono più per il carello, ma tra di noi lupi solitari, anime in pena, late-comers...ed è facile leggere il pensiero anarcoide che passa nella mente di ognuno di noi: si scrutano gli sguardi alla ricerca di un complice disposto all'assalto del carrello approviggionamenti.
La tensione adesso cala, la ragazza si allontana sana e salva. I freni inibitori stavolta hanno tenuto, pericolo scampato.

In tutto questo comunque sono sempre su di un panchina che cerco di dormire. La dinamica della ricerca di una posizione accettabile per dormire da parte dell'aspirante airport-bench-sleeper (mi è uscita così!), su panchine rigorosamente posto singolo, merita qualche riga.
Si comincia con 5 minuti di frenetico arrabbattamento necessari per familiarizzare con quello che non è esattamente il proprio giaciglio usuale. Dopo poco si trova una posizione che è sorprendetemente comoda, si incomincia a pensare che, tutto sommato, non sarà una notte così lunga, basta sopportare il piede che penzola fuori dalla panchina, non far caso a un qualcosa di non indentificato che ostinatamente prova a penetrarti nel fianco e l'inezia che per poter entrare in quello spazio ristretto la tua testa è piegata in un qualcosa degno dell'esorcista. Si capisce allora che, forse, questa soluzione non è proprio l'ottimale e se ne cerca un'altra; per successive approsimazioni il processo va avanti finchè la stanchezza cala come una lama di ghigliottina e ci addormenta in una posizione e con una smorfia che chiunque vi abbia visto deve necessariamente essere fatto fuori prima che possa scattarvi una foto.
Il sonno comunque è appagante, dura per pochi minuti, ma è intenso. Sembra che tutto vada bene ma qualcuno comincia a urlare per l'aeroporto "Fuck you, Fuck you Goteborg", e inevitabilmente ci si sveglia.
Meno male che un poster davanti a me riportante un frase di Oscar Wilde mi fa sorridere: "Work is the curse of the drinking class".

Sono ormai le 5. E' tempo di un caffè, un muffin e nel contempo cercare la forza di non lasciarsi andare a gesti di violenza contro gli impiegati ryanair. E' tempo di andare al check-in. Secondo tentativo. Speriamo stavolta ingrani. Italia sto arrivando!