Category: Geeky side of life

18 Feb

Top 10 music for programming

57_Brugge_Belfort_Interno

For programming one needs silence to concentrate at the problem at hand. But comes a time (often) when one has to go in auto mode, and have the hands write the ideas accumulated at the time. Good music is the best thing to let them go, and it must be non-boring, lengthy enough to avoid having to switch back and forth, with the right level of darkness and, above all, top quality. The rule I followed is 1 per author, if an author has more than one submission, they share the same slot (and most, share). So, from bottom to top:

10 – Dido – Life for Rent, No Angel

For some reason when programming sad, melancholic  music feels better than a beach Boys album would, probably because I want my brain to be kidnapped by the music while the hands write like an automaton, and not my brain to start . Life for Rent has fewer good tracks than No Angel, but I’ve listened to No Angel literally too much and it’s starting to get boring.

9 – Dire Straits – Love over Gold

Dire Straits are able to reap a 9th place in this list, and it’s strange. Their music don’t fit the theme, and it’s generally not good to code with; you can’t concentrate with Twisting By The Pool. Still Love over Gold is a strange beast, and they are able to get on the list with just two songs of a single album of all their life. The first two of course.

8 – PFM – Storia di un minuto

The only italian album on the list, this is one of the highest moments of italian progressive rock of the 70s. There are two reasons for being only 8th place: first, the italian lyrics are easily distracting; second Impressioni di Settembre is too beautiful to be listened while working.

7 – Weather Report – Mysterious Traveller, Black Market
Many Weather Report albums are better than Mysterious Traveller. Ok not many, and WR quality is so high that it would not matter anyway, but Mysterious Traveller has the top qualities as a programming music, specially the first track, Nubian Sundance. Black Market, however, is Black Market; you can’t go wrong with Black Market, and code produced under the Black Market effect is basically bug-free! Try it.

6 – Portishead – Dummy

The first trip-hop album in this list (unless you include Dido in the genre but it’s a stretch I think) and there are many, and all at the top – but don’t give it too importance to this fact, infact almost all the list is shared between 70s progressive, trip-hop and jazz/fusion. Dark, disturbing, distressing. Perfect. The reason it’s not first is that it lacks positive energy. But it has plenty of negative one, so plenty to get a 6th place without debates. Plus, one of the less significant songs in this album, shares an introductory sample with another of the less significant tracks of another album in this very list. Go figure.

5 -Miles Davis – Kind of Blue, A tribute to Jack Johnson

No list of top whatever music can be missing Kind of Blue. The only issue with Kind of Blue is if you want something more dynamic. Right Off from “A Tribute To Jack Johnson” is that for a reason. This reason.

4 – Morcheeba – Big Calm, Charango

No other album from Morcheeba has the same feeling as this one. And none will ever be since Skye Edwards left the band. Oh Wait! Skye Edwards returned! But they will not do anything like Big Calm anyway, because Big Calm is unique. Charango is a good alternative, but, slow down!, it’s way beyond no Big Calm, even if you think otherwise; get along with it. And if they can’t redo it who can you trust ?

3 – Hooverphonic – A New Stereophonic Sound Spectacular / The Magnificent Tree bonus album

Not everything from Hooverphonic is good, and no album satisfy the programmers needs fully. A New Stereophonic Sound Spectacular is the one getting closer, but some tracks really don’t cut, with The Magnificent Tree at second place. However the two “Visions” tracks (bonus tracks of the new editions of The Magnificent Tree) are perfect; 100% pure programming tracks.

2 – Pink Floyd – every long suite, Animals, The Dark Side of the Moon

More than 20 minutes of varying tones, with up and downs and ranging from dark to charging. Never boring, you can’t go wrong with Pink Floyd long suites. Be them “Echoes”, “Atom Hearth Mother Suite” or “Shine on you crazy diamond”. Bonus points for the entire Animals album, with Dogs getting again in the >20′ range and being top quality together with Sheep and Pigs while older albums offer gems like “Careful with that Axe, Eugene” and “Astronomy Dominé”. When long suites start getting boring (after some years of continuous listening), classic Floyd albums will take their place; The Dark Side of the Moon is a pleasure to listen, from Clare Torry vocals to the odd tempo changes in Money. Beware the clocks in Time, if you are tired.

1 – Massive Attack – Mezzanine

I don’t like Massive Attack that much. But tracks 1 to 6 of Mezzanine seem to simply have been composed right for programming. Not boring, rhythmic, dark, impressive, obsessive. When almost every track is that famous, with a track used in the Matrix soundtrack and another being the soundtrack of almost everything (from House M.D. to Assassin’s Creed) and featuring Elizabeth Fraser, you can’t be wrong. Speaking of Elizabeth Fraser, of Cocteau Twins fame, if this list was of 11 places, they would be in.

01 Feb

A smarter but not smartest greedy algorithm for hotel bookings

hotel

Doing homework for my university studies, I stumbled upon the problem of having a somewhat smart logic for hotel bookings. The assignment was to build a model-2 jsp/servlet based website for bookings of a generic hotel chain; the required booking facilities were simple but I wanted to do something smarter, and solve the problem in a satisfactory way.

Let’s say that you are eager to go to Sidney between the 29th Jan and 5th of Feb.. because – well, any reason you want to be there in that period. What bothers me is that most booking facilities just check for a whole availability – a single room available for the entire period. Now, if I really want to go to Sidney, and I’m already willing to take 12+ hours of plane to go there, renew the passport, fight spiders, etc., probably having to change the room at the mid of my stay there is the least of the problems – specially if the alternative is not going to Sidney at all.

Now, apart from the fact that this is a stupid example because I would never want to go to Sidney because there are some of the worst (1) spiders (2) of the world(3) there,  the problem was interesting to solve and the solution happened to me while walking towards home, listening to Alesha Dixon – this to justify the non-optimality of the algorithm. (The rest of the project was built over Miles Davis prestige recordings I received as a present for Christmas… much better food for the brain :))

Step 0 – the data structure

As always, the first step of a good algorithm is a good data structure. Since this is a simple algorithm, the data structure is very simple as well.. the data structure is an integer matrix of rooms rows by days columns. This already suggests that the algorithm complexity will be O(rooms*days), and it is, unless the data fetch from database is more complex for some reason. This step is already O(rooms*days) in space, there is no need to zero-set the matrix, every cell will be overwritten in step 1.

Example of pass0 result

Step 1 – fill data structure with room occupation data

The step 1, of O(rooms*days) time, is simple : store a 1 in each cell where  the corresponding room is available in the corresponding day, a 0 if the room is already booked.

Pass 1 example

Step 2 – does the magic

The step 1, of O(rooms*days) time, is also simple and does the magic that allows the final step to run: parse each row from right to left. If you are in zero cell, leave it as it is. If it’s a 1 cell, sum to it value to its immediate right. The final result is that each cell contains a number which says for how many following days that room is free.

Sample of pass 2

Step 3 – gets the result

Step 3 – O(rooms*days) worst case, but O(rooms) on average – leads us to the final result. Let’s parse each column from left to right. For each column, get the maximum number of that column, choose that room for the period until it reaches a 0 and advance of that many columns. Repeat until time ends, or until a column of only zeros is found – which means no booking is possible even with changes.

The end result

On optimality

The algorithm is a greedy algorithm of O(rooms*days) space and time complexity, optimal in the minimization of  room changes but sub-optimal in fragmentation. With this I mean that the solutions it finds may lead to small fragments of rooms for future bookings. For sure a human can do better, for example:

Better result - from human :)

does not leave a 3 days hole in room3, leaves room1 free for 4 days, sacrificing one day in room2 which would be hard to book anyway (unless it is already free in the weekend!).

On Storage

On a side note, for storage a number of solutions are available. However you have to consider that you need the booking to be a transaction and you want the transaction to fail if one or more days/rooms are not available anymore; basically the two ways I found are using constraints and from/to columns in the table, or simply having a separate entry for each day with (room,day) as the table key : this way if the two bookings conflict they will result in a duplicate key violation and one, or both, transactions will fail. Constraints and from/to periods work too, with the pro of having less rows in the database and reducing the algorithm execution time, and the cons of requiring a bit more database-fu. Of course other solutions might be available, but I’m definetely not a database expert (actually, I more of a database rookie :)).

16 Jun

ScummVM DS Patches – version 4

(Quick download links : .NDS builds or .DS.GBA builds, modified sources here, SourceForge patches here)

I’ve patched ScummVM DS once again..

See here for more details, versioning, how, why, what, which, who..

Changes in ScummVM/DS 0.11.1.MMP4 (.NDS builds or .DS.GBA builds):

  • All previous changes
  • Fixed a bug with mouse icon
  • Attempt to show mouse cursor on upper screen also when LCDs are swapped (sometimes it fails to be in the correct position but it covers most cases).

Be vigilant.