Codility

Codility to ciekawy serwis dla osób z HR, który służy do automatycznego testowania umiejętności programistycznych kandydatów.

Serwis w założeniach przypomina automatyczne sprawdzarki stosowane na konkursach programistycznych. Firma powstała w Anglii, ale sadząc po imionach i nazwiskach założyli ją Polacy ;) Może w końcu na rozmowach kwalifikacyjnych częściej będzie się dostawać zadania programistyczne niż te typu "Wieśniak musi przewieźć przez rzekę wilka, kozę i kapustę..."

Aby zobaczyć jak działa Codility można:
a) mieć szczęście i trafić na dział HR który tego używa,
b) samemu wykupić subskrypcję,
c) kliknąć przycisk "Demo test".

Jeżeli kogoś przeraża "geeks only!", to niech się nie przejmuje ;) Rozwiążmy tutaj (w Javie) zadanie, które jest tam prezentowane.

Pierwiastek sześcienny na zwykłym kalkulatorze

Na maturze z matematyki można mieć kalkulator - ale "zwykły". Czyli najbardziej wyszukana operacja na nim dostępna to pierwiastek kwadratowy :P

Ale jest możliwość wyliczenia na standardowym kalkulatorze pierwiastka trzeciego stopnia (gdyby ktoś potrzebował). Algorytm jest prosty i nie wymaga żadnej kartki papieru czy innego rodzaju pamięci ;)

"Microsoft RandomSort"

Ekran wyboru przeglądarki pojawił się jako aktualizacja do Windowsa na początku marca tego roku i z miejsca stał się kontrowersyjny - tak samo jak kontrowersyjny był jego brak.

Użytkownik ma do wyboru 12 przeglądarek, z czego 5 najpopularniejszych (Internet Explorer, Firefox, Chrome, Opera, Safari) widać na pierwszy rzut oka w losowym porządku, a mniej popularną siódemkę można obejrzeć po przewinięciu listy. "Mali" oczywiście oprotestowali ten układ (słusznie, bo co, 12 się nie zmieści na ekranie?).

Ale jak się okazuje, "losowanie" pierwszej piątki też nie jest losowe. Hm...

Wyszukiwanie binarne

Jeden z wydawać by się mogło z prostszych algorytmów - przecież nie ma tu nic trudnego. Znalezienie środkowego elementu tablicy, porównanie go z tym wyszukiwanym i wykonanie tego samego kroku dla odpowiedniej pozostałej części tablicy. Nic trudnego?

Jon Bentley w "Perełkach oprogramowania" (1986) podkreśla, że o ile powyższy algorytm został opisany w druku w 1946r., to pierwsza wersja bez błędów ukazała się w 1962r. (bite 16 lat). Autor przy okazji wspomina, że kiedy na prowadzonym przez niego szkoleniu zadanie napisania wyszukiwania binarnego w ciągu paru godzin dostali zawodowi programiści, to 90% z nich skończyło z błędami.

Następnie w swojej książce Bentley opisuje prawidłową wersję algorytmu i na 30 stronach formalnie dowodzi jej poprawności oraz poprawności implementacji w C. W drugim wydaniu (2000) nie wprowadził żadnych zmian w swoim wyszukiwaniu binarnym.

W 2006r. został odnaleziony w nim błąd.

Anagramy w języku polskim

Zastanawialiście się kiedyś, jaka jest najfajniejsza grupa anagramów w języku polskim? Ja też nie, aż do wczoraj ;)

Na wypadek jeżeli ktoś nie wie - anagram to wyraz powstały poprzez zmianę kolejności liter innego wyrazu, np. "kot" i "tok". Anagramy tworzą całe zbiory (klasy równoważności :P) - np. "kot", "tok" i "kto" to jedna klasa.

Zacząć musimy oczywiście od listy wyrazów. Ja wykorzystałem darmowy słownik SJP przystosowany do gier słownych (takich jak Scrabble bądź Literaki): http://www.sjp.pl/slownik/growy/. Ma on 35 MB i zawiera 2,7 miliona słów. Czyli nie powinno być źle :)

Odpalamy swoje wybrane środowisko C++ i do roboty :)

F# - sortowanie przez scalanie

Większość P.T. Czytelników nie jest crazy na punkcie F#, ale ja się nie poddaje :P

W końcu rozwiązanie ostatniego ćwiczenia z http://wojtek-m.blogspot.com/2009/10/f-i-gimnastyka-umysu.html ;)

*3. Sortowanie listy przez scalanie (merge sort). Pamiętaj o złożoności O(nlogn) i stabilności. Pierwszym argumentem sortowania powinna być funkcja porównująca, np. dla int byłaby to funkcja (<).

F# - wyniki gimnastyki

Ok, rozwiązań do F-szarpowych ćwiczeń z posta http://wojtek-m.blogspot.com/2009/10/f-i-gimnastyka-umysu.html nikt nie umieścił, więc pora na mnie :P

1. Własna funkcja zwracająca długość listy (rekurencja ogonowa).

Wersja bez rekurencji ogonowej jest dość oczywista:

let length l =
    match l with
    | [] -> 0
    | h::t -> (length t) + 1

Rekurencję ogonową można osiągnąć z użyciem drugiego parametru, który będzie zliczał długość dotychczas przejrzanej listy - początkowo ma on wartość 0. Jeżeli dojdziemy do końca listy, zwracamy wartość tego parametru. Dzięki temu nie wykorzystujemy w ogóle stosu wywołań funkcji - działamy jak iteracyjna pętla ;)

let length l =
    let rec length l acc =
        match l with
        | [] -> acc
        | h::t -> length t (acc + 1)
    in
        length l 0

Prosty wielokąt (NWERC 2009)

Po NWERC 2009 żałowałem, że nie udało nam się wklepać jeszcze jednego zadania - "Prostego wielokąta", a miało to zadanko wiele drużyn. Treść zadania jest dostępna tutaj: http://www.nwerc.eu/results/nwerc09.pdf (strona 19).

Jak widać nawet historyjki nie chciało się wymyślać ;) A do rozwiązania wystarczył jeden prosty pomysł, którego nam zabrakło...

Po NWERC 2009

Tydzień temu w weekend pociłem się na North Western European Regional Contest w Norymberdze, jako dodatek do teamu reprezentującego duńską uczelnię ;) Wyposażeni od początku zawodów w normalny układ klawiatury (en-us) zrobiliśmy 3 zadania i zdobyliśmy 23. miejsce (czyli takie samo jak NCPC, gdzie byli tylko reprezentanci krajów nordyckich). Wśród duńskich uczelni zajęliśmy miejsce drugie, czyli o jeden lepiej niż na NCPC :)

Duńczycy z DTU, którzy dostali 10000 DKK za pierwsze miejsce w Kopenhadze nie zrobili ani jednego zadania. Oddawać kasę tępaki ;)

Po NCPC 2009 :)

W sobotę odbyła się kolejna edycja Nordic Collegiate Programming Contest. Pierwsza i pewnie jedyna, w której brałem udział ;) Byłem tam dzięki szczęśliwemu zbiegowi okoliczności - Krzysiek i Michał szukali trzeciej osoby do drużyny :) Zawody odbywały się jednocześnie we wszystkich krajach nordyckich - Danii, Finlandii, Islandii, Norwegii i Szwecji, więc konkurs był niebagatelnie międzynarodowy ;)

Kolejka priorytetowa w C#

Ostatnio implementując A* w C# potrzebowałem kolejki priorytetowej.
W odmętach internetu odnalazłem następującą implementację:
http://blogs.msdn.com/ericlippert/archive/2007/10/08/path-finding-using-a-in-c-3-0-part-three.aspx
Wykorzystuje ona uporządkowany słownik (czyli drzewo BST) "zwykłych" kolejek. Oczywiście nie byłbym sobą, gdybym nie poprawił tego trochę ;)