Implementing binary heap without an array

Posted on November 17, 2011 by haaja

So I had this school assignment to implement a binary heap with a twist of not using an array to store the binary tree. You might think that this is an easy problem to solve and after some thinking it turns out that it isn’t much harder than the generic array implementation. However if this is the first time you’re implementing binary heap this way, you’ll likely find it difficult to insert new nodes in O(lg n) time. With arrays you can always find the last element in constant time. Unfortunately this is not the case with object references unless you have a trick or two in your sleeve. Once you’re able to access last node of the heap and sibling nodes of a particular node in constant time, the solution is similar to any text book implementation. It is also worth noting that at the time of writing google isn’t much of a help solving this problem because next to every example shows the array implementation.

I solved the problem by adding all the node into a binary tree AND a doubly linked list. Then I use the linked list to access last node of the heap and siblings of an individual node. There might be other viable solutions as well but this is by far the easiest I’ve heard of. As I’m lazy and can’t be bothered to draw pictures to further explain the solution. I pushed the source code to a github repository. The original repository was a bit messy and in Finnish so no commit history for you guys, sorry.

256 colors in vim and screen

Posted on November 3, 2011 by haaja

For some strange reason at least Fedora ships screen and vim with 256 colors disabled. Here’s a quick guide how to enable 256 colors in vim and screen.

1. Add to you .vimrc file

set t_Co=256

2. Add following lines to your .screenrc file

attrcolor b ".I"
termcapinfo xterm 'Co#256:AB=\E[48;5;%dm:AF=\E[38;5;%dm'
defbce "on"

Also check that your terminal supports or has 256 colors enabled. At least gnome-terminals seems to have this by default. Enjoy combination of vim and screen with 256 colors.

Matkan suunnittelu edistyy

Posted on October 9, 2011 by haaja

Pitkästä aikaa on jotain kerrottavaa matkasta. Olen tässä jonkin aikaa jo pohtinut, että mitä paikkoja käyn katsomassa Indonesiassa. Indonesia on valtavan kokoinen ja kunnollisen infran puuttuessa matkustaminen on hidasta. Lisäksi minulla on vain kuukausi aikaa matkustaa, joten joudun lentämään pidemmät etäisyydet. Mielenkiintoisia kohteita ovat muun muassa Togianin saaret Sulawesillä, Gili saaret ja Lombok, Komodon saari sekä Sumatran Lake Toba. Kaikkeen ei missään tapauksessa riitä aika, joten joudun valitsemaan listalta yhden tai kaksi paikkaa.

Olen tässä jokusen päivän katsellut Indonesian sisäisiä lentoja ja niiden hintoja. Lennot ovat varsin inhimillisen hintaisia, mutta ongelmaksi on muodostunut se ettei luottokortillani onnistu lentojen varaaminen. En oikein tiedä missä vika on ja olen lukenut pallontallaajista että muilla on ollut samoja ongelmia. Kaikki toimii varaamisessa hyvin siihen asti kun verkkopankista pitäisi palata takaisin lentoyhtiön sivuille. Tällöin tulee aina ilmoitus että maksaminen epäonnistui. Kuulemma lennot ovat edullisia ostaa suoraan tiskiltäkin, mutta haluan varmistaa että mahdun heti seuraavan päivän lennolle. Lopulta kuitenkin sain Batavia Air:lta liput ostettua. Tämäkin onnistui varmasti pelkästään sen takia että kyseinen lafka käytti luottokorttimaksuihin paypallia. No loppu hyvin kaikki hyvin ja lippu on nyt hankittu.

Mikäli lentoni ovat ajallaan, olen Jakartassa 19.12 klo: 23.50, ja tarkoitus olisi ehtiä aamu seitsemän lennolle Medaniin. Medanissa luultavasti joudun nukkumaan univelkaa pois sillä siinä vaiheessa on takana matkustamista jo reippaasti. Kaikki riippuu siitä miten hyvin saan nukuttua lennolla Lontoosta Singaporeen tai vaihtoehtoisesti Jakartan kentällä. Medanista suuntaan sitten kulkuvälineellä X kohti Parapatia ja lake Tobaa. Lake Toban lisäksi piipahdan mahdollisesti gili saarilla tai jossakin muualla, mutta vain aika näyttää onnistunko siinä ollenkaan. Tämän pidemmälle en matkaa ole suunnitellut, enkä aio suunnitellakkaan.

Välihuomautuksena sain myös passini uusittua. Alunperin tarkoitukseni oli uusia passi mahdollisimman myöhäisessä vaiheessa, mutta sitten lentoja varaillessani tajusin että minun on syötettävä passin numero lentoyhtiölle. No ei auttanut muu kuin käydä Pasilan poliisilaitoksella uusimassa passi. Hintaa lystille tuli 53€ + passikuvien hinta jota en nyt tähän hätään muista. Palvelu asemalla oli poliisimaisen töykeää, mutta passin sai kolmessa päivässä. Lisäksi kävin hankkimassa uuden vedenpitävän pussin, sillä vanha taisi jäädä viime reissulla Don detille Laosiin.

Spotify 0.6.1 on Fedora 15/16

Posted on October 3, 2011 by haaja

Edit: This works for version 0.6.2 as well.

Spotify is a popular music streaming service which unfortunately isn’t globally available. Here in Finland we have had the opportunity to enjoy Spotify from the begining which is a rare thing. For a minuscule amount of 9.99€ you’ll have pretty much unlimited collection of music at your hands and on your mobile phone. Ok, granted not every artist has their music in Spotify but the collection is huge! Better yet they “support” Linux with their preview client. The support is nothing compared to Windows or OS X but it’s more than most services ever offer. While the service is certainly rewarding for the end-user, I’ve heard stories about artists complaining that the money coming from Spotify is next to nothing. Personally I don’t know what real situation is, probably record labels are taking most of the money. Enough said, lets get our hands dirty.

Spotify used to have separate packages for Fedora, but currently the repository is empty. This is a minor annoyance and with little work we can use the packages they provide for Debian.

Download the packages from the apt repository

$ wget http://repository.spotify.com/pool/non-free/s/spotify/spotify-client-gnome-support_0.5.2.84.g6d797eb-1_all.deb
$ wget http://repository.spotify.com/pool/non-free/s/spotify/spotify-client-qt_0.6.1.309.gb871a7d-1_amd64.deb

Deb packages are ar archives which we can easily open (note that it is ar not tar ).

$ ar vx spotify-client-gnome-support_0.5.2.84.g6d797eb-1_all.deb

Both packages have similar content so extract them into different directories or follow this guide for one package at a time. Following files should be extracted: contor.tar.gz, data.tar.gz and debian-binary. data.tar.gz file contains the files we need to make Spotify work on fedora.

This step will require root privileges. Copy data.tar.gz into system root, cd yourself to root, extract the data.tar.gz and finally remove the data.tar.gz file.

# cp data.tar.gz /
# cd /
# tar -xzvf data.tar.gz
# rm data.tar.gz

Repeat the procedure for the spotify-client as well.

Now you can try to execute spotify from command line and it should fail to launch with following errors. You only get the first error until spotify can successfully find libssl.so, but to save time I’ve listed both errors here. On a side note ldd is a great tool for finding out dynamic library dependencies.

spotify: error while loading shared libraries: libssl.so.0.9.8: cannot open shared object file: No such file or directory
spotify: error while loading shared libraries: libcrypto.so.0.9.8: cannot open shared object file: No such file or directory

Fedora uses newer versions of openssl and Spotify does not check the version of the library correctly. First make sure you have openssl-devel package installed and then help spotify to find libssl.so by creating a symbolic link to the correct path depending on your architecture.

# This is for 64 bit installations
ln -s /usr/lib64/libssl.so /usr/lib64/libssl.so.0.9.8
ln -s /usr/lib64/libcrypto.so /usr/lib64/libcrypto.so.0.9.8
# This is for 32 bit installations
ln -s /usr/lib/libssl.so /usr/lib/libssl.so.0.9.8
ln -s /usr/lib/libcrypto.so /usr/lib/libcrypto.so.0.9.8

Now you should be able to start Spotify and enjoy some great music with native linux client!

Unmounting a busy drive

Posted on October 3, 2011 by haaja

My computer setup consists of Lenovo x220 with a docking station, two external screens and of course mouse and keyboard. Even though my laptop has a fast hard drive, it has only 120GB disk space which means I need external hard drives to store my data. I have one external hard drive and one docking station which accepts regular internal 3.5″ and 2.5″ hard drives. Since I prefer suspend over shutdown I sometimes get problems with my external docking station.

Usually the error is something like this:

# umount /media/storage1
umount: /media/storage1: device is busy

Luckily there is a great tool called fuser which lets you identify the process using a file or socket. This means that I can easily find out which process is keeping my drive busy and simply kill the process.

To find out which process is keeping your drive busy

# fuser -mv /dev/sdXY
/dev/sdc1: 6772

In the command letter X is the drive letter and letter Y is the number of partition. The output gives the process id that prevents mounting/unmounting the drive by using the resources. Even though fuser can kill the processes using resources, it is generally safer to first find out what you going to kill.

ps auxw|grep 6772
haaja 6772 0.4 2.7 219212 56792 ? SLl Oct 3 02:25 banshee

Here we can see that I have banshee open and still accessing media files on my external hard drive. This was just a staged situation where I intentionally left banshee open and dried unmounting. Usually I have some terminal tab still open accessing the hard drive. I think that outputting the process information should be the default behavior of umount in this type of error situations. Kill the process and proceed to unmounting the no-longer-busy drive.

Disabling URL trimming in Firefox 7

Posted on September 29, 2011 by haaja

Mozilla released Firefox 7 released yesterday (actually day before yesterday since it’s already 29th here) and of course I did an upgrade as soon as RPM files were available in koji. Call me old fashioned but I didn’t like the new feature which trims the http:// part of URL. Perhaps it’s something that I’ll eventually get used to but for now I disabled it. Luckily disabling the feature was easy enough.

Here is how you do it:

1. Open new tab and write about:config
2. Search for option browser.urlbar.trimURL
3. Set the value to false by double-clicking the option.

Yay, you’re all set!

Project Euler

Posted on September 27, 2011 by haaja

Project Euler is a website containing computational problems intended to be solved by small programs. Currently there are 351 problems to be solved and all of the problems should be doable within one-minute-rule. In other words you are doing something wrong if computing the solution takes more than one minute (or at least your program could be optimized). If you’re interested in programming or mathematics then Project Euler is for you. Solving problems is fun and along the way you may learn something new.

I remember hearing about Project Euler a long time ago but for some reason never tried solving the problems. Last Sunday I was bored and somehow ended up on Project Euler and started doing problems. I decided to use python because I haven’t really used python before. So far I have solutions for the first 21 problems and problem 67 which was exactly the same as problem 18, except computationally harder. My solutions can be found from GitHub. I’ll try to make it a habit and continue solving these problems every now and then but I give no guarantees.

NTMLv2 authentication on Linux

Posted on September 15, 2011 by haaja

Today at work I was trying to get my virtual machine, running Fedora, to access internet. Unfortunately the place I work is pretty much married to products from Microsoft. All the networking to the outside world go through proxies and in this case through Microsoft ISA. ISA uses NTLMv2 authentication mechanism which is not supported out of the box by Linux. Luckily there was multiple applications that were able to act as a man in the middle proxy, such as cntlm and NTLAMPS.

These proxies are installed locally and then applications will talk to them. In turn these proxies will relay the requests to the actual proxy. This way we can point our whole system to use this locally installed proxy and everything just works. There are few applications, such as Firefox, that can authenticate to NTLMv2 proxy but this is not the overall case.

I managed to get both of the replacement proxies working but ended up using cntlm because it was way faster and required less system resources. Nevertheless installation is easy for both of them since most distributions provide packages for both of them. In this guide I will use Fedora but besides the installation part, it should apply to other distributions as well.

1. Install cntlm

# yum install cntl

2. Test your authentication method

# cntlm -I -M http://www.google.fi

The command should output something like this:

----------------------------[ Profile 0 ]------
Auth NTLMv2
PassNTLMv2 DA95C27958430DESH829C0E38985484A
------------------------------------------------

3. Use this auth information in your /etc/cntlm.conf file.

Username        your_username
Domain          your_domain

Auth            NTLMv2
PassNTLMv2      DA95C27958430DESH829C0E38985484A

Proxy           your_proxy:your_proxy_port

# This is the port number where Cntlm will listen
Listen        3128

4. Configure your system to use the local proxy:

export http_proxy=http://localhost:3128
export https_proxy=http://localhost:3128

5. Start cntlm by executing:

# /etc/init.d/cntlmd start

If everything works, you should be able to access internet normally. Remember you need to create new hash every time your password changes!

Also you might want to start cntlm automatically on start-up:

chkconfig --level 35 cntlmd on

Note to self

Posted on August 23, 2011 by haaja

Kun olet lentolippusi ostanut, unohda lentoliput äläkä missään nimessä enää seuraa lentotarjouksia samalle ajankohdalle. Olisin säästänyt reilut 250 euroa jos olisin tarttunut Lufthansan tämän päivän tarjouksiin.

Ostin tuossa Indonesian lounarin, mutta noin muuten suunnitelmat ovat jäissä. Odotellaan kesäduunit loppuun ja syksyn opinnot alkuun ennen kun aletaan pohtimaan talven rientoja sen tarkemmin.

Uutta reissua pukkaa

Posted on August 14, 2011 by haaja

Morjensta pöytään!

Long time no see, long time no ABC. Tässä on taas kesä ja osa kevättä lusittu duunissa ja vielä on muutama viikko jäljellä. Syksyn kurssit ovat vielä edessä mutta katse kääntyy jo talven reissuun. Viime talvi tuli vietettyä Suomessa, joten nyt on taas aika päästä lämpimään. En kuitenkaan pysty ottamaan omaa lomaa lipastolta, joten reissuun on nyt käytettävissä vain tuo noin kuukausi mitä joululomaa yliopistolta on. Olen tässä muutamat päivät katsellut lentoja Aasiaan. Valitettavan kalliita tuppaavat olemaan tuolla joulun alla, mutta minkäs teet. Tänään onneksi löysin ok hintaiset lennot hyvillä vaihtoajoilla Helsingistä Jakartaan. Lystille tuli hintaa 880€, joka ei mielestäni ole mahdottoman kova hinta kun ottaa huomioon ajankohdan. Lento on 18.12 Helsingistä Lontoon kautta Singaporeen ja sieltä lopulta Jakartaan. Saman homman teen käänteisessä järjestyksessä 18.1 ja lopulta 19.1 minun pitäisi olla taas Helsingissä. Fiksuimmat sen nyt jo tajusivatkin mutta kerrottakoon penaalin tylsemmille kynille että talven reissun kohde on siis Indonesia. Tai no oikeammin vain pieni osa Indonesiasta, sillä aikaa on sen verran vähän ja maalla pinta-alaa pauttiarallaa saman verran kuin Euroopalla. Seuraavaksi pitäisikin tehdä vähän researchia ja päättää missä päin Indonesiaa haluan lomani viettää. Valitettavan monta mielenkiintoista kohdetta Indonesiasta löytyy, luonnollisesti aivan eri puolilla maata. Onneksi maan sisäiset lennot pitäisi olla melko edullisia. Pikaisella tsekkauksella ainakin Air Asia lennättää Denpasariin ja Medaniin n. 35e per suunta.

Muista hankinnoista mainittakoon uusi rinkka. Bongasin netistä tarjouksen Deuter Futura Pro 42 rinkasta ja pitihän se sitten poistaa. Vanha haltini koki kovia viime reissulla kun kambodẑalainen rotta päätti syödä itsensä rinkan läpi muutamaan otteeseen. Nooh jospa tämä uudempi rinkka kestäisi pidempään. Vielä pitää hoitaa lennot Jakartasta paikkaan X, uusia passi ja tiedustella vähän rokotuspoliittisia asioita YTHS:ltä. Passin uusimisen jätän kyllä mahdollisimman viime tinkaan kun ne perkeleet eivät nykyään ole voimassa kuin sen viisi vuotta. Muuten hankinnat taitavat olla aika pitkälti tehtyjä jo edellisen reissun jäljiltä. Tällä kertaa taidan lopettaa tähän mutta eiköhän tässä vielä palailla ennen kuin reissu alkaa, ja jos ei niin reissun päältä sitten viimeistään.