Quiz - rozruszaj towarzystwo

Home

Czy Wasza praca jest zawsze ciekawa i pełna wyznań, a może czasami Was nuży i zastanawiacie się jak ją urozmaicić?

Byłoby super gdyby każdy z nas mógł odpowiedzieć na to pytanie "Tak moja praca jest bardzo ciekawa i nigdy mnie nie nuży", ale w rzeczywistości bywa różnie. Zawsze można zmienić pracę, ale można również próbować zmienić coś w obecnej. Sceptycy pewnie powiedzą, a co ja mały trybik w wielkiej machinie mogę zrobić. Dużo zależy od firmy i bywają przypadki beznadziejne. Ja na rozruszanie zespołu proponuję zorganizować Quiz.

Ja postanowiłem coś takiego zrobić już po raz drugi w swojej karierze i jestem bardzo zadowolony z efektów. Odgórnym celem Quiz'u była zabawa i nauka. Zasady były proste:

• 10 tur po 3 pytania (łatwe, średnie i trudne) dotyczące szeroko pojętego programowania.
• Pytania przygotowałem za wczasu, tak aby nie musieć ich wymyślać co tydzień.
• Starałem się, aby odpowiedzi można było udzielić w jednym zdaniu, czasem wręcz jednym słowem, ewentualnie napisać kilka linijek kodu.
• Pytania rozsyłałem w poniedziałek rano i czekałem na odpowiedzi do końca dnia. Następnego dnia oceniałem wyniki, rozsyłałem odpowiedzi z komentarzami i aktualną statystykę (anonimowa lista).
• Udział był dobrowolny.
• Udział był anonimowy, każdy uczestnik miał przypisany identyfikator i tylko ja znałem mapowanie.
• Zwycięzca mógł wybrać sobie nagrodę ufundowaną przez firmę (wybrał przenośny dysk).

Do Quiz'u zgłosiło się 20 osób. Łącznie zadałem 9 łatwych pytań, 12 średnich oraz 9 trudnych za łącznie 60 punktów. Zwycięzca zdobył 52.5 punkty i walka trwała do ostatniej tury ponieważ druga osoba w rankingu miała 52 punkty, a trzecia i czwarta 51. Zebrane w całości pytania i odpowiedzi utworzyły 22 stronicowy dokument!

Quiz spodobał się i spotkał się z bardzo dobrym odbiorem również ze strony przełożonego, który dał pieniądze na nagrodę. Najbardziej cieszy mnie jednak to, że już kilkukrotnie słyszałem od kolegów, że w trakcie Quiz'u nauczyli się czegoś nowego.

Organizacja Quiz'u to również nauka dla mnie. Aby przygotować pytania i nie zaliczyć wpadki wiele zagadnień musiałem przestudiować dużo dokładniej. Nauczyłem się również jak, wbrew pozorom, trudne jest układanie pytań w taki sposób, aby były zrozumiałe dla wszystkich. Pomimo, że każde zadanie czytałem wielokrotnie zdarzało się, że musiałem odpowiadać na pytania i rozsyłać dodatkowe informacje.

Na koniec kilka przykładów pytań:

Łatwe

We have to measure an execution time with the maximum possible resolution/precision. It was implemented in the following way. Does this code meet this requirement? If yes, why? If not, propose a better solution.

var start = DateTime.Now;
//...
var end = DateTime.Now;

Średnie

.NET 4.5 introduces a new, easy and elegant way to retrieve a name of a method (caller) which executed/called a given method (calle).

public void Fun()
{
//Here, I want to get a name of a method that executed/called Fun method
}

Trudne

We want to use a class called  Fun, that  is defined in an external library. Unfortunately, a constructor of this class contains a bug which causes an exception. In other words, we can't create a new instance of Fun class, but we have to. You have to find a workaround. You mustn't modify Fun class.

Project Euler

Home

Po raz pierwszy o Project Euler usłyszałem już tak dawno temu, że nie pamiętam kiedy ale dopiero ostatnio założyłem konto i rozpocząłem zabawę. W skrócie jest to zestaw zadań matematyczno programistycznych (obecnie ponad 400) o różnym stopniu złożoności i trudności. Rozwiązanie zadania polega na podaniu zawsze jednej liczby np.: liczba cyklicznych liczb pierwszych poniżej 1 miliona. Część problemów można rozwiązać siłowo ale nim dalej w las tym trudniej i trzeba kombinować.

Do założenia konta zachęcił mnie kolega z pracy (Dzięki Piotrek!). Okazało się, że w zabawie bierze udział już kilku z nas. Witryna projektu umożliwia śledzenie postępów innych, dyskusję na temat problemów, podaje statystyki ile osób rozwiązało poszczególne zadania itd.

Do tej pory korzystałem z konkurencyjnego portalu TopCoder. Co przyciągnęło mnie do Project Euler? Sądzę, że kilka rzeczy:

• Proste reguły zabawy.
• Bardzo prosty interfejs.
• Element społecznościowy.
• Stopniowanie trudności. Można zacząć od bardzo prostych problemów i przechodzić do coraz trudniejszych.
• Krótkie i zwięzłe zadania, co nie znaczy, że zawsze proste.
• To coś.

Nie mówię, że TopCoder jest gorszy. Jest po prostu innych. Dla mnie Project Euler to czysta, nieskomplikowana zabawa. TopCoder ma wyższy próg wejścia ale z drugiej strony daje dużo więcej np.: nagrody pieniężne.

Podsumowując, jeśli jeszcze nie próbowaliście to zachęcam. Ja spróbowałem i nie mogę się oderwać.

Microsoft.Office.Interop

Home

Będzie krótko i zwięźle, temat nie jest pasjonujący ale może komuś oszczędzi trochę nerwów. Ostatnio zdarzyło mi się pracować z kodem używającym Microsoft.Office.Interop do generacji dokumentów programu Word. Kod do najpiękniejszych nie należał ale najwięcej problemów miałem z interoperacyjnością.

Pierwszy błąd napotkałem po otwarciu dokumentu i próbie ustawienia właściwości MailMerge.MainDocumentType lub jak się później okazało dowolnej innej. Ten błąd to:

This command is not available because no document is open.

Przyczyną błędu okazał się brak katalogu C:\Windows\System32\config\systemprofile\Desktop. W moim przypadku po prostu skopiowałem analogiczny katalog C:\Windows\SysWOW64\config\systemprofile\Desktop i błąd przestał występować. Drugi błąd jaki napotkałem to:

Programmatic access to Visual Basic Project is not trusted.

Na początku spróbowałem więc zaznaczyć odpowiednią opcję w programie Word:

Word Options -> Trust Center -> Trust Center Settings -> Trust access to the VBA project object model

Niestety ale to nie pomogło. Skoro nie można po dobroci to skorzystałem z rozwiązanie "siłowego" i dodałem odpowiedni klucz do rejestru:

[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Office\14.0\Word\Security]
"AccessVBOM"=dword:00000001

Problemy te zaobserwowałem na Windows 7 Professional dla Microsoft Word 2010.

Przeszukiwanie przestrzeni stanów 5

Home

Post ten stanowi fragment serii na temat przeszukiwania przestrzeni stanów.

Przeszukiwanie przestrzeni stanów to podejście, które pozwala rozwiązać bardzo wiele problemów. Należy jednak uważać, ponieważ siłą rzeczy wymaga sprawdzenia wielu ścieżek w drzewie/grafie stanów, co może trwać bardzo długo. W końcu uzyskamy poprawny wynik, ale po co czekać skoro dla niektórych problemów rezultat można uzyskać dużo szybciej. Spójrzmy na to zadanie.

Dana jest liczba N (z przedziału od 1 do 1000000) płytek domina. Każda płytka składa się z 2 połówek. Każda połówka zawiera liczbę z przedziału od 1 do 100. Dwie płytki domina pasują do siebie jeśli na jednej z połówek zawierają tą samą liczbę np.: płytka 1|10 pasuje do kostki 10|3 ale nie pasuje do kostki 4|5. Należy napisać program, który sprawdzi czy zadane płytki można ułożyć w łańcuch np.: 10|1 1|100 100|65 65|78...

Problem ten można rozwiązać w oparciu o strategię przeszukiwania przestrzeni stanów np.:

• Definicji stanu początkowego - zbiór płytek.
• Formuła/Akcje - Wyszukanie wszystkich płytek, które mogą zostać dopasowane do ostatniej płytki w łańcuchu. Dla każdej z nich należy wygenerować nowy stan czyli usunąć ze zbioru i dodać do łańcucha.
• Warunku stopu - pusty zbiór płytek
• Funkcja kosztu - brak.

Podejście to da poprawne rozwiązanie, ale dla dużych wartości liczby klocków N zajmie to niepraktycznie dużo czasu. Czemu? W tym podejściu każda płytka to węzeł grafu, który jest połączony z innymi klockami, do których pasuje. Rozwiązanie problemu to znalezienie ścieżki w grafie, która odwiedzi wszystkie jego węzły, ale każdy węzeł tylko raz. Innymi słowy szukamy ścieżki Hamiltona w grafie (rozwiązania problemu komiwojażera), który jest problemem z klasy NP.

Do problemy można podejść inaczej. Użyjmy modelu, w którym płytki reprezentowane będą jako krawędzie grafu, a nie węzły. W ten sposób otrzymamy graf o małej liczbie węzłów (tyle ile różnych liczb na połówkach płytek) i dużej liczbie krawędzi. Na przykład jeśli zbiór początkowy zawiera 1000 płytek postaci 3|57 to w nowej reprezentacji będziemy mieli 1000 krawędzi łączących węzły 3 i 57.

Przy takiej reprezentacji rozwiązanie problemu to znalezienie ścieżki w grafie, która przejdzie przez każdą krawędź tylko raz czyli znalezienie ścieżki Eulera, a to można zrobić w czasie wielomianowym. Aby w grafie istniała ścieżka Eulera muszą zostać spełnione następujące warunki (stopień węzła to liczba krawędzi wchodzących/ wychodzących do/z tego węzła):

• Graf musi być spójny.
• Co najwyżej dla jednego węzła spełnione jest (stopień wchodzący) - (stopień wychodzący) = 1
• Co najwyżej dla jednego węzła spełnione jest (stopień wychodzący) - (stopień wchodzący) = 1
• Dla wszystkich pozostałych węzłów stopień wchodzący jest taki sam jak stopień wychodzący.

20/05/2013:
Powyższe warunki dotyczą grafu skierowanego. Graf z płytkami jest natomiast grafem nieskierowanym, a więc powyższe warunki jeszcze się uproszczą.

Innymi słowy wśród wszystkich możliwych grafów są takie ich odmiany, dla których problem znalezienia ścieżki Hamiltona można sprowadzić do znalezienia ścieżki Eulera.

Przeszukiwanie przestrzeni stanów może być bardziej intuicyjne, ale zawsze warto zastanowić się dwa razy.

Przeszukiwanie przestrzeni stanów 4

Home

Post ten stanowi fragment serii na temat przeszukiwania przestrzeni stanów.

Napisaliśmy już silnik przeszukiwania przestrzeni stanów. Teraz, przy jego pomocy, rozwiążemy problem statków, który stanowił początek naszych rozważań. Zacznijmy od klasy, która będzie przechowywała informacje o bieżącym stanie.

public class ShipsProblemData
{
    public Dictionary<string, Stack<string>> Ports { get; private set; }

    public Stack<string> CurrentPath { get; private set; }

    public ShipsProblemData()
    {
        Ports = new Dictionary<string, Stack<string>>();
        CurrentPath = new Stack<string>();
    }

    public ShipsProblemData Clone()
    {
        var state = new ShipsProblemData();

        foreach (var pair in Ports)
        {
            var stack = new Stack<string>();
            foreach (var target in pair.Value.Reverse())
                stack.Push(target);

            state.Ports[pair.Key] = stack;
        }

        foreach (var item in CurrentPath.Reverse())
            state.CurrentPath.Push(item);

        return state;
    }
}

Właściwość Ports to słownik, którego kluczami są nazwy portów, a wartości to dzienniki modelowane przy pomocy stosu. Właściwość CurrentPath przechowuje natomiast listę odwiedzonych już portów. Metoda Clone ułatwi nam generowanie nowych stanów. Właściwa definicja problemu wygląda tak:

public class ShipsProblem : Problem<ShipsProblemData>
{
    public override ShipsProblemData DataForInitialState
    {
        get
        {
            var data = new ShipsProblemData();

            var port1 = "Gdańsk";
            var port2 = "Szczecin";
            var port3 = "Kołobrzeg";

            data.CurrentPath.Push(port1);

            var book = new Stack<string>();

            book.Push(port2);
            book.Push(port1);
            book.Push(port3);
            book.Push(port2);
            book.Push(port1);
            book.Push(port3);
            data.Ports[port1] = book;

            book = new Stack<string>();

            book.Push(port3);
            book.Push(port1);
            book.Push(port1);
            book.Push(port3);
            book.Push(port1);
            book.Push(port1);
            data.Ports[port2] = book;

            book = new Stack<string>();

            book.Push(port2);
            book.Push(port3);
            book.Push(port2);
            book.Push(port2);
            book.Push(port3);
            book.Push(port2);
            data.Ports[port3] = book;

            return data;
        }
    }

    public override bool IsFinalState(State<ShipsProblemData> state)
    {
        return state.Data.Hosts.All(kvp => !kvp.Value.Any());
    }

    public override IList<State<ShipsProblemData>> Expand(State<MyData> state)
    {
        var newStates = new List<State<ShipsProblemData>>);

        var currentHost = state.Data.CurrentPath.Peek();
        foreach (var host in state.Data.Hosts.Keys)
        {
            if (state.Data.Hosts[host].Count > 0 && state.Data.Hosts[host].Peek() == currentHost)
            {
                var copy = state.Data.Clone();
                copy.Hosts[host].Pop();
                copy.CurrentPath.Push(host);

                newStates.Add(new State<ShipsProblemData> { Data = copy });
            }
        }

        return newStates;
    }
}

Stan początkowy można odczytać z pliku lub bazy danych, ale w naszym przypadku równie dobrze można go zaszyć w kodzie. Stan końcowy możemy wykryć bardzo łatwo, tj. wszystkie dzienniki powinny być puste. Generowanie nowych stanów też jest proste. W każdym kroku musimy znaleźć porty, z których mógł wypłynąć statek i przybić do portu bieżącego czyli takie, których dziennik zawiera na ostatnim miejscu bieżący port. Następnie kopiujemy dane i modyfikujemy je tak aby odpowiadały nowemu stanowi.

Nie pozostaje nic innego jak uruchomić silnik i uzyskać wynik.

var solver = new ProblemSolver<ShipsProblemData>();
var results = solver.SolveProblem(new DFSFringe<ShipsProblemData>(), new ShipsProblem ());

foreach (var res in results)
{
    Console.WriteLine(" ----------- Solution ----------- ");
    foreach (var data in res.ResultData)
        Console.WriteLine(data.CurrentPath.Peek());
    
}