Czego prawdopodobnie nie wiedzieliście o Excel'u

Home

Sądzę, że wielu z Was otarło się na studiach o programowanie liniowe oraz algorytm sympleks. Ja uczyłem się o tym na przedmiocie zwanym w skrócie POBO, co rozwija się dumnie brzmiące Podstawy badań operacyjnych. Od czasów studiów nie zajmowałem się tym zagadnieniem, aż do dzisiaj. Pomagając siostrze w rozwiązywaniu zadań na studia dowiedziałem się o możliwościach Excel'a, których w ogóle nie byłem świadomy, a są naprawdę super i każdy ma do nich dostęp. Mam tutaj na myśli dodatek Solver, który, między innymi, implementuje algorytm sympleks w bardzo przystępnej formie. Tyle tytułem wstępu. Spójrzmy na prosty przykład.

Zaczynamy od uruchomienia Excel'a. Następnie klikamy tą fikuśną okrągłą ikonę w lewym górnym roku okna i wybieramy Opcje programu Excel. Dalej przechodzimy do zakładki Dodatki i klikamy przycisk Przejdź.



W oknie, jakie się pojawi, wybieramy Dodatek Solver i zatwierdzamy.



Po zatwierdzeniu w zakładce Dane na wstążce pojawi się nowa opcja.



Teraz spróbujmy rozwiązać przykładowe proste zadanie. Załóżmy, że mamy 5 fabryk i chcemy znaleźć lokalizację centrum dystrybucyjnego tak aby suma odległości od wszystkich fabryk była minimalna. Dodatkowe ograniczenie jest takie, że odległość od każdej z fabryk nie może być większa niż 60. Położenia fabryk podane są we współrzędnych kartezjańskich. Odległość pomiędzy fabrykami, a centrum obliczamy przy pomocy standardowego wzoru. Sytuacja początkowa wygląda tak. Dla ułatwienia naniosłem położenia fabryk i początkowe położenie centrum na wykres.



Teraz uruchamiamy Solver. Jako komórkę celu wybieram pole z sumą odległości i zaznaczam, że tą wartość chcę minimalizować. Jako komórki zmieniane wybieram współrzędne centrum. Dodajemy też ograniczenie na odległość każdej z fabryk od centrum. Na koniec uruchamiam obliczenia i klikam Rozwiąż.



Wynik końcowy wygląda w następujący sposób:



To tylko wierzchołek góry lodowej. Dodatek Solver ma dużo większe możliwość i wiele opcji. Można go wykorzystać do harmonogramowania, zdefiniować wiele ograniczeń, ustalić maksymalny czas obliczeń, dokładność uzyskanego wyniku i wiele więcej. Sądzę, że warto sobie zapamiętać, że Excel ma takie możliwości i w razie potrzeby doczytać i douczyć się jak z tego korzystać.

TPL Dataflow + problem filozofów

Home

Jakiś czas temu na blogu Piotrka Zielińskiego przeczytałem o TPL Dataflow Library czyli o bibliotece dostarczającej komponentów ułatwiających komunikację (przekazywanie danych) w środowisku wielowątkowym. Temat mnie zaciekawił i postanowiłem trochę pobawić się z tą technologią. Na tapecie nie miałem żadnego "prawdziwego" projektu, w którym dałoby się wykorzystać nową zabawkę, postanowiłem więc wykonać ćwiczenie umysłowe i rozwiązać klasyczny problem pięciu filozofów z użyciem TPL Dataflow.

W moim rozwiązaniu każda pojedyncza pałeczka do jedzenia ryżu reprezentowana jest przez instancję klasy BufferBlock<T&gt gdzie T to w tym przypadku klasa Chopstick (klasa wydmuszka, nie zawiera żadnych właściwości ani metod). BufferedBlock<T>to nic innego jak kolejka FIFO, która może mieć wielu czytelników i wielu zapisujących.

Filozof potrzebuje jednak dwóch pałeczek aby rozpocząć jedzenie. Aby spełnić to wymaganie używam klasy JoinBlock<T,Z> gdzie T i Z do znowu klasa Chopstick. JoinBlock działa w ten sposób, ze monitoruje dwa źródła danych i jeśli w obu źródłach równocześnie są dane to grupuje je i wysyła do słuchacza. W tym przypadku JoinBlock czeka na dwie wolne pałeczki.

var chopsticks = new JoinBlock<Chopstick, Chopstick>(new GroupingDataflowBlockOptions { MaxNumberOfGroups = 1 });

_left.LinkTo(chopsticks.Target1);
_right.LinkTo(chopsticks.Target2);

_chopsticks = chopsticks.Receive();

Ustawienie właściwości MaxNumberOfGroups jest konieczne, aby blok odczytał tylko dwa komunikaty. Odłożenie pałeczek na stół jest natomiast równoważne z wysłaniem komunikatu (pałeczki) z powrotem do bufora tak, aby oczekujący na nie filozofowie mogli rozpocząć jedzenie.

_left.SendAsync(_chopsticks.Item1);
_right.SendAsync(_chopsticks.Item2);

Do tego, aby filozofowie mogli informować świat zewnętrzny o tym, co robią, również użyłem klasy BufferBlock<T>. Za każdym razem kiedy jeden z filozofów kończy/rozpoczyna jedzenie wysyła komunikat ze swoim aktualnym stanem. Ja napisałem prostą aplikację w WinForms, która nasłuchuje na te komunikaty i odpowiednio uaktualnia UI.

private readonly BufferBlock<PhilosopherState> _philosophersState = new BufferBlock<PhilosopherState>();
...
_philosophersState.LinkTo(new ActionBlock<PhilosopherState>(state => UpdateState(state)), new DataflowLinkOptions());

Każdy filozof modelowany jest przez instancję klasy Philosopher i działa w swoim własnym wątku. Co jakiś losowy czas decyduje, co robić dalej tj.: kontynuować myślenie/jedzenie czy rozpocząć myślenie/jedzenie. Kiedy zbierzemy to wszystko do kupy, otrzymamy następujący kod.

Pokaż/Ukryj kod klasy Philosopher

namespace PhilosopherProblemWithDataFlows
{
    public class Philosopher
    {
        private const int SleepTime = 100;

        private readonly int _index;
        private readonly BufferBlock<Chopstick> _left;
        private readonly BufferBlock<Chopstick> _right;
        private readonly BufferBlock<PhilosopherState> _philosophersState;

        private bool _goHome;
        private Tuple<Chopstick, Chopstick> _chopsticks;

        public Philosopher(int index, BufferBlock<Chopstick> left, BufferBlock<Chopstick> right, BufferBlock<PhilosopherState> philosophersState)
        {
            _index = index;
            _left = left;
            _right = right;
            _philosophersState = philosophersState;
        }

        public void TakeASeat()
        {
            var rand = new Random((int)DateTime.Now.Ticks);

            while (true)
            {
                if (_goHome)
                {
                    PutChopsticks();                
                    return;
                }

                if (rand.Next() % 2 == 0)
                    Eat();
                else
                    Think();

                Thread.Sleep((rand.Next(10) + 1) * SleepTime);
            }
        }

        public void GoHome()
        {
            _goHome = true;
        }

        private void Eat()
        {
            if (_chopsticks == null)
            {
                var chopsticks =
                    new JoinBlock<Chopstick, Chopstick >(new GroupingDataflowBlockOptions { MaxNumberOfGroups  = 1 });

                _left.LinkTo(chopsticks.Target1);
                _right.LinkTo(chopsticks.Target2);

                _chopsticks = chopsticks.Receive();
                chopsticks.Complete();
            }

            _philosophersState.SendAsync(new PhilosopherState { Index = _index,  IsEating = true });
        }

        private void Think()
        {
            PutChopsticks();

            _philosophersState.SendAsync(new PhilosopherState { Index = _index,  IsEating = false});
        }

        private void PutChopsticks()
        {
            if (_chopsticks != null)
            {
                _left.SendAsync(_chopsticks.Item1);
                _right.SendAsync(_chopsticks.Item2);
                _chopsticks = null;
            }
        }
    }

    public class Chopstick
    {
    }

    public class PhilosopherState
    {
        public int Index { get; set; }
        public bool IsEating { get; set; }
    }
}

Pokaż/Ukryj kod okna Win Forms

namespace PhilosopherProblemWithDataFlows
{
    public partial class Form1 : Form
    {
        private readonly Color EatingColor = Color.Red;
        private readonly Color ThinkingColor = Color.Green;

        private readonly List<Label> _stateLabels = new List<Label>();
        private readonly List<Philosopher> _philosophers = new List<Philosopher>();
        private readonly BufferBlock<PhilosopherState> _philosophersState = new BufferBlock<PhilosopherState>();

        public Form1()
        {
            InitializeComponent();
            Closing += (sender, args) =>
                {
                    _philosophersState.Complete();
                    _philosophers.ForEach(p => p.GoHome());
                };

            _stateLabels.Add(philosopher1);
            _stateLabels.Add(philosopher2);
            _stateLabels.Add(philosopher3);
            _stateLabels.Add(philosopher4);
            _stateLabels.Add(philosopher5);
            _stateLabels.ForEach(l => l.BackColor = ThinkingColor);
            
            Start();
        }

        private void Start()
        {
            _philosophersState.LinkTo(new ActionBlock<PhilosopherState>(state => UpdateState(state)), new DataflowLinkOptions());

            var chopsticks = new[]
                {
                    new BufferBlock<Chopstick>(),
                    new BufferBlock<Chopstick>(),
                    new BufferBlock<Chopstick>(),
                    new BufferBlock<Chopstick>(),
                    new BufferBlock<Chopstick>()
                };

            foreach (var ch in chopsticks)
                ch.Post(new Chopstick());

            for (var i = 0; i < 5; ++i)
                _philosophers.Add(new Philosopher(
                            i,
                            chopsticks[i],
                            chopsticks[(i + 1) % 5],
                            philosophersState));

            for (var i = 0; i < 5; ++i)
            {
                var th = new Thread(_philosophers[i].TakeASeat);
                th.Start();
            }
        }

        private void UpdateState(PhilosopherState state)
        {
            var label = _stateLabels[state.Index];
            label.Invoke((MethodInvoker)delegate { label.BackColor = state.IsEating ? EatingColor : ThinkingColor; });
        }
    }
}

Kod designer'a pominąłem bo jest trywialny i zawiera tylko 5 etykiet o nazwach philosopher1, philosopher2 itd.

Na koniec mała zagadka. Moja implementacja zawiera pewne uproszczenie oryginalnego problemu 5 ucztujących filozofów. Jakie?

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ć.

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());
    
}

Przeszukiwanie przestrzeni stanów 3

Home

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

Zgodnie z obietnicą dzisiaj napiszę jak zaimplementować klasę Fringe i jakie to może mieć znaczenie. Dla przypomnienia potrzebujemy stworzyć kontener, który będzie przechowywał stany, które musimy jeszcze odwiedzić. Wynika to z tego, że przestrzeń stanów ma strukturę drzewiastą albo w ogólności grafową jeśli możliwe jest wrócenie do już odwiedzonego stanu. Węzły tego drzewa/grafu możemy odwiedzać w różnej kolejności, a co z tym związane w różnej kolejności je produkować. Kolejność ta zależy właśnie od implementacji klasy Fringe.

Zacznijmy od dwóch przykładowych implementacji.

public class DFSFringe<TCustomData> : Fringe<TCustomData>
{
    private readonly Stack<State<TCustomData>> _fringe = new Stack<State<TCustomData>>();

    public override int Count
    {
            get { return _fringe.Count; }
    }

    public override bool IsEmpty
    {
        get { return _fringe.Count == 0; }
    }

    public override State<TCustomData> Next
    {
        get { return _fringe.Pop(); }
    }

    public override void Add(State<TCustomData> s)
    {
        _fringe.Push(s);
    }
}

public class BFSFringe<TCustomData> : Fringe<TCustomData>
{
    private readonly Queue<State<TCustomData>> _fringe = new Queue<State<TCustomData>>();

    public override int Count
    {
            get { return _fringe.Count; }
    }

    public override bool IsEmpty
    {
        get { return _fringe.Count == 0; }
    }

    public override State<TCustomData> Next
    {
        get { return _fringe.Dequeue(); }
    }

    public override void Add(State<TCustomData> s)
    {
        _fringe.Enqueue(s);
    }
}

DFS oraz BFS to skróty od Depth-first search czyli przeszukiwania w głąb oraz Breadth-first search czyli przeszukiwania wszerz. DFSFringe opiera się na stosie, a BFSFringe na kolejce. Ma to ogromne znaczenie.

Zastosowanie stosu powoduje, że rozwijany jest najgłębszy jeszcze nie rozwinięty węzeł - stan, a jego następniki ustawiane są na początku zbioru stanów. Natomiast użycie kolejki powoduje, że rozwijany jest najpłytszy jeszcze nie rozwinięty węzeł, a jego następniki ustawiane są na końcu zbioru stanów.

DFS będzie więc, przeważnie, trzymał mniej stanów w pamięci niż BFS. Przy bardzo szerokich drzewach BFS może być wręcz niepraktyczny z powodu zbyt dużego zapotrzebowania na pamięć. Z drugiej strony, przy bardzo głębokich drzewach,  DFS może tracić czas na przeszukiwanie kolejnych gałęzi podczas gdy rozwiązanie będzie znajdować się dość płytko tj. niedaleko korzenia.

DFSFringe, BFSFringe to zresztą tylko dwa przypadki z wielu. Inne podejścia to min.: przeszukiwanie z równomiernym kosztem (ang. uniform-cost search), przeszukiwanie z ograniczoną głębokością (ang. depth-limited search), iteracyjne pogłębianie (ang. iterative deepening) czy przeszukiwanie zgodnie z zasadą najlepszy wpierw (an.g best-first search).

W kolejnym poście w końcu ;) rozwiążemy problem ze statkami.

Przeszukiwanie przestrzeni stanów 2

Home

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

Implementacja przeszukiwania przestrzeni stanów powinna być możliwe ogólna, tak abyśmy mogli zastosować ją również dla innych problemów. Najpierw napiszmy klasę reprezentującą stan. Wygląda ona w następujący sposób:

public class State<TCustomData>
{
    public TCustomData Data { get; set; }

    public double Cost { get; set; }

    public State<TCustomData> Parent { get; internal set; }

    public IList<State<TCustomData>> Children { get; internal set; }
}

TCustomData to dowolna klasa, która przechowuje właściwe dane opisujące stan.

Teraz stwórzmy klasę Problem, która będzie miała trzy zadania: dostarczenie stanu początkowego, produkowanie nowych stanów i określenie kiedy znaleźliśmy stan końcowy. Wszystkie składowe tej klasy są abstrakcyjne, ponieważ ich implementacja zależy od rozwiązywanego problemy.

public abstract class Problem<TCustomData>
{
    public abstract TCustomData DataForInitialState { get; }

    public abstract bool IsFinalState(State<TCustomData> state);

    public abstract IList<State<TCustomData>> Expand(State<TCustomData> state);
}

Potrzebujemy jeszcze jednej klasy. Będzie ona odpowiedzialna za przechowywanie stanów, które musimy odwiedzić. Wracając do zadania ze statkiem. W pewnym momencie może być tak, że nie będziemy mogli jednoznacznie powiedzieć skąd przypłynął statek. Możliwości może być wiele i w najgorszym przypadku musimy sprawdzić je wszytskie. Innymi słowy ze stanu A możemy przejść do stanu B, C, D... i gdzieś te stany musimy zapamiętać.

public abstract class Fringe<TCustomData>
{
    public abstract State<TCustomData> Next { get; }

    public abstract int Count { get; }

    public abstract bool IsEmpty { get; }

    public abstract void Add(State<TCustomData> s);

    public void AddRange(IEnumerable<State<TCustomData>> data)
    {
        foreach (var s in data)
            Add(s);
    }
}

Klasa ta jest abstrakcyjna, ponieważ stany możemy odwiedzać w różnej kolejności co może mieć bardzo duże znaczenie, ale o tym później.

Napiszmy jeszcze jedną prostą klasę zanim przejdziemy do właściwego silnika, czyli klasę modelującą rozwiązanie. W tej implementacji rozwiązanie do sekwencja stanów od początkowego aż do końcowego:

public class Result<TCustomData>
{
    private readonly List<TCustomData> _resultData = new List<TCustomData>();

    public IList<TCustomData> ResultData
    {
        get { return _resultData; }
    }
}

Przygotowaliśmy już całą infrastrukturę. Zobaczmy więc silnik. Wbrew pozorom jest on bardzo prosty.

public class ProblemSolver<TCustomData>
{
    public IList<Result<TCustomData>> SolveProblem(Fringe<TCustomData> fringe, Problem<TCustomData> problem)
    {
        var initialState = new State<TCustomData> { Data = problem.DataForInitialState };
        fringe.Add(initialState);

        var res = new List<Result<TCustomData>>();
        while (!fringe.IsEmpty)
        {
            var next = fringe.Next;

            if (problem.IsFinalState(next))
            {
                res.Add(GetSolution(next));
            }
            else
            {
                next.Children = problem.Expand(next);
                foreach (var child in next.Children)
                    child.Parent = next;

                fringe.AddRange(next.Children);
            }
        }

        return res;
    }

    private static Result<TCustomData> GetSolution(State<TCustomData> state)
    {
        var res = new Result<TCustomData>();
        while (state != null)
        {
            res.ResultData.Add(state.Data);
            state = state.Parent;
        }

        return res;
    }
}

Rola silnika sprowadza się do dwóch zadań:

1. Odwiedzanie kolejnych stanów i sprawdzanie czy są rozwiązaniem.
2. Zapamiętywanie kolejno znalezionych rozwiązań.

W kolejnym poście napiszę więcej o możliwych implementacjach klasy Fringe.

Przeszukiwanie przestrzeni stanów

Home

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

Zacznijmy od rozwiązania zadania z poprzedniego posta. Poprawna sekwencja portów to:

Gdańsk
Szczecin
Kołobrzeg
Szczecin
Gdańsk
Gdańsk
Kołobrzeg
Kołobrzeg
Szczecin
Gdańsk
Szczecin
Kołobrzeg
Szczecin
Gdańsk
Gdańsk
Kołobrzeg
Kołobrzeg
Szczecin
Gdańsk

Zapewne można do niej dojść stosując algorytm na chłopski rozum czyli:

1. Wiemy, że ostatnim portem był Szczecin.
2. Patrzymy więc na ostatnie wpisy w dziennikach z Gdańska i Kołobrzegu.
3. Okazuje się, że do Szczecina statek przypłynął z Gdańska.
4. Wykreślamy ten wpis.
5. Patrzymy na ostatnie wpisy w dziennikach z Szczecina i Kołobrzegu.
6. Okazuje się, że do Gdańska statek przypłynął z Kołobrzegu.
7. Wykreślamy ten wpis.
8. Patrzymy na ostatnie wpisy w dziennikach z Szczecina i Gdańska.
9. Okazuje się, że do Kołobrzegu statek mógł przypłynąć Szczecina lub Gdańska i musimy rozważyć oba scenariusze.
10. ...

Dla dużej liczby portów jest to zadanie karkołomne. Ja przy takich problemach stosuję przeszukiwanie przestrzeni stanów (ang. State space search), w skrócie PPS. Podejście to pozwala rozwiązać wiele problemów algorytmicznych, które pozornie wydają się bardzo trudne, w prosty sposób. Między innymi stosowane jest w uczeniu maszyn, warto więc je znać.

PPS zakłada, że problem reprezentujemy przy pomocy:

• Definicji stanu początkowego.
• Formuły, która powie nam jakie stany można odwiedzić, z bieżącego stanu. Albo inaczej zbioru akcji, które powodują zmianę stanu.
• Warunku stopu, który powie nam czy znaleźliśmy rozwiązanie.
• Opcjonalnie funkcji kosztu, która pozwala nam wybrać lepsze, bardziej optymalne rozwiązanie.

Na tej podstawie PPS znajduje sekwencję akcji prowadzących od stanu początkowego do rozwiązania. Dla opisanego przeze mnie problemy wygląda to tak:

• Definicji stanu początkowego - port końcowy + stan dzienników.
• Formuła/Akcje - Znalezienie listy portów, z których statek mógł przypłynąć do bieżącego portu. Wybranie portu oznacza dodanie go do listy już odwiedzonych portów oraz wykreślenie odpowiedniego wpisu z dziennika.
• Warunku stopu - Wszystkie dzienniki są puste.
• Funkcja kosztu - brak.

Stan to para składająca się z aktualnej listy odwiedzonych portów oraz aktualnego stanu dzienników. Mając definicję problemu możemy przejść do implementacji o czym napiszę w kolejnym poście.

Zadanie do pogłówkowania

Home

Post ten stanowi pierwszy z serii, w której opisze podejście do rozwiązywania pewnej klasy problemów. W ostatnim czasie po raz kolejny zastosowałem to podejście do rozwiązania problemu, jaki napotkałem, i dlatego postanowiłem o tym napisać. Na początek proponuję zastanowić się nad takim zadaniem.

Treść zadania:

Załóżmy, że statek podróżuje pomiędzy pewną liczną N portów. Za każdym razem kiedy zawinie do portu jest to odnotowywane przez kapitanat w dzienniku. Kapitanat zapisuje również informacje o kolejnym docelowym porcie podróży.

Mając zbiór dzienników ze wszystkich portów, oraz port końcowy należy odtworzyć trasę podróży statku. Statek może wielokrotnie odwiedzać ten sam port. Statek może również wypłynąć z portu A i do niego wrócić.

Niestety dzienniki są prowadzone niechlujnie i nie możemy polegać na datach wpisów. Wpisy są natomiast ułożone chronologicznie w ramach dziennika, czyli jeśli wpis A jest wcześniej w danym dzienniku niż wpis B to znaczy, że statek najpierw odpłynął do A, wrócił po jakimś czasie i popłynął do B.

Przykład 1:

Rozważmy przypadek z 3 portami Szczecin, Gdańsk oraz Kołobrzeg. Portem końcowym jest Szczecin. Dzienniki dla pewnego statku wyglądają w następujący sposób:

Szczecin	Gdańsk	Kołobrzeg
Gdańsk	Kołobrzeg	Gdańsk
Kołobrzeg	Kołobrzeg	Szczecin
	Szczecin	Gdańsk

Z dziennika dla Szczecina możemy odczytać, że statek najpierw odpłynął do Gdańska potem wrócił i odpłynął do Kołobrzegu itd.

Rozwiązanie 1:

Rozwiązaniem jest następująca trasa:

Szczecin
Gdańsk
Kołobrzeg
Gdańsk
Kołobrzeg
Szczecin
Kołobrzeg
Gdańsk
Szczecin

Teraz w ramach ćwiczeń, zanim opiszę swoje podejście, proponuję rozwiązać problem dla poniższych danych. Port końcowy to Gdańsk.

Przykład 2:

Gdańsk	Szczecin	Kołobrzeg
Szczecin	Kołobrzeg	Szczecin
Gdańsk	Gdańsk	Kołobrzeg
Kołobrzeg	Gdańsk	Szczecin
Szczecin	Kołobrzeg	Szczecin
Gdańsk	Gdańsk	Kołobrzeg
Kołobrzeg	Gdańsk	Szczecin

Codility

Home

Jestem wielkim zwolennikiem sprawdzania kandydatów na programistów przy pomocy zadań wymagających napisania kodu. Sam również byłem egzaminowany w ten sposób nie raz i nie dwa. W pamięci zapadły mi jednak rekrutacje z udziałem portalu Codility, który weryfikuje nie tylko poprawność kodu ale również jego wydajność, za każdym razem było to dla mnie ciekawe wyzwanie.

Postanowiłem więc skontaktować się z Codility i zapytać czy w ofercie mają produkt pozwalający programistom ćwiczyć ich umiejętności. Odpowiedź na zapytanie dostałem bardzo szybko i niestety okazała się negatywna, ale zostałem zaproszony do ich biura w Warszawie aby porozmawiać o tym pomyśle.

Trochę to trwało zanim udało się nam ustalić termin spotkania, ale w końcu pewnego popołudnia wsiadłem w tramwaj i pojechałem na Plac Bankowy. Na miejscu przywitała mnie przemiła Czeszka Zuzana, miałem okazję poznać zespół pracujący nad rozwojem Codility oraz porozmawiać o ich pracy. Ponieważ nie miałem wcześniej okazji korzystać z portalu od strony rekrutera pokazano mi jak to wygląda.

Na koniec wręczono mi upominek w postaci książki Looking For a Challenge? z opisem kilkudziesięciu ciekawych zadań programistycznych, przygotowanych przez zwycięzców międzynarodowych konkursów programistycznych.

À propos problemów algorytmicznych, dowiedziałem się również, że część zadań Codility dostępna jest w Internecie dla każdego programisty, ale nie wszystkie łatwo znaleźć. Poniżej, dzięki uprzejmości Codility, macie ich pełną listę. Lista ta z czasem będzie z czasem rozszerzana o tzw. zadania well known czyli takie, które są dobrze znane i nie ma sensu przy ich pomocy testować kandydatów ale idealnie nadają się do ćwiczeń.

• psi2012
• phi2012
• chi2012
• upsilon2012
• tau2012
• sigma2012
• rho2012
• pi2012
• omicron2012
• xi2012
• nu2011
• mu2011
• lambda2011
• kappa2011
• iota2011
• theta2011
• eta2011
• zeta2011
• epsilon2011
• delta2011
• gamma2011
• beta2010
• alpha2010

Wizytę wspominam bardzo miło. Tym bardziej, że Codility odwiedziłem nie jako klient, ale jako "człowiek z ulicy". Cieszy również, że to polski start-up odnoszący sukcesy na świecie.

Jeszcze o radzeniu sobie z głęboką rekursją

Home

W poście opisałem ogólne podejście to radzenia sobie z bardzo głęboką rekursją, która prowadzi do StackOverflowException. Dzisiaj powrócę do tematu. Od czasu do czasu, oprócz pogłębiania wiedzy na temat bibliotek, framework'ów itd. lubię rozwiązywać różnego rodzaju algorytmiczne zadania programistyczne. Jakiś czas temu rozwiązywałem takie zadanie:

Zadana jest mapa świata w postaci prostokątnej tablicy dwuwymiarowej. Każdy element tablicy ma swój kolor. Sąsiadujące (stykające się jednym z boków) z sobą elementy tego samego koloru należą do jednego kraju. Należy policzyć liczbę krajów na tej mapie. Jeśli dwa elementy tablicy mają ten sam kolor, ale nie znajdują się w jednym ciągłym obszarze, to należą do różnych krajów. 

Poniższy rysunek przedstawia przykładową mapę takiego świata, na który składa się 6 krajów.



Zacznijmy od głównej metody wykonującej obliczenia. Koncepcja jest prosta. Nie ulega wątpliwości, że należy odwiedzić wszystkie elementy tablicy aby móc zwrócić poprawny wynik. Aby nie zliczać tego samego elementu dwa razy używam wartości Int32.MaxValue jako znacznika już odwiedzonych elementów. Jeśli odwiedzając kolejny element znajduję wartość inną niż Int32.MaxValue to znaczy, że danego elementu jeszcze nie odwiedziłem i zwiększam licznik krajów.

public int Count(int[][] map)
{
 if (map == null) return 0;
 
 if (map.Length == 0) return 0;

 var numberOfCountries = 0;

 for (var y = 0; y < map.Length; ++y)
 {
  for (var x = 0; x < map[0].Length; ++x)
  {
   if (map[y][x] != Int32.MaxValue)
   {
    numberOfCountries++;
    /* Zaznacz elementy należące do danego kraju */
    VisitCountry(map, map[y][x], y, x);
   }
  }
 }

 return numberOfCountries;
}

Co kryje się pod tajemniczym Zaznacz elementy należące do danego kraju? W pierwszym podejście napisałem funkcję rekurencyjną, która począwszy od zadanego elementu odwiedzała wszystkie pola należącego do danego kraju i oznaczała je jako odwiedzone.

public void VisitCountry(int[][] map, int currentColor, int y, int x)
{
 if (y < 0 || x < 0 || y >= map.Length || x >= map[0].Length) return;

 if (map[y][x] != currentColor) return;
            
 map[y][x] = Int32.MaxValue;

 VisitCountry(map, currentColor, y + 1, x);
 VisitCountry(map, currentColor, y, x + 1);
 VisitCountry(map, currentColor, y - 1, x);
 VisitCountry(map, currentColor, y, x - 1);
}

Poniżej kod testujący dla przykładu z początku postu:

int[][] map = new int[5][];

for (int i = 0; i < map.Length; ++i)
 map[i] = new int[4];

map[0][0] = 1; map[0][1] = 3; map[0][2] = 3; map[0][3] = 2;
map[1][0] = 1; map[1][1] = 2; map[1][2] = 3; map[1][3] = 2;
map[2][0] = 1; map[2][1] = 1; map[2][2] = 1; map[2][3] = 1;
map[3][0] = 2; map[3][1] = 3; map[3][2] = 3; map[3][3] = 1;
map[4][0] = 2; map[4][1] = 2; map[4][2] = 2; map[4][3] = 2; 

var result = Count(map);

W warunkach zadania było jednak napisane, że szerokość/wysokość mapy może znajdować się w przedziale od 1 do 1000000. Sprawdźmy, więc czy kod ten obsłuż dużo większą mapę:

int[][] bigMap = new int[10000][];
for (int i = 0; i < bigMap.Length; ++i)
{
 bigMap[i] = new int[10000];
 for (int j = 0; j < bigMap.Length; ++j)
  bigMap[i][j] = i;
}

var result = Count(bigMap);

Na mojej maszynie wystarczy już mapa 10000 x 10000 aby pojawił sie wyjątek StackOverflowException. Zgodnie z tym co napisałem we wcześniejszym poście metoda VisitCountry powinna więc wyglądać tak:

public void VisitCountry(int[][] map, int startY, int startX)
{
 var toCheck = new Queue<Tuple<int, int>>();
 toCheck.Enqueue(new Tuple<int, int>(startY, startX));

 var currentColor = map[startY][startX];

 while (toCheck.Count > 0)
 {
  var t = toCheck.Dequeue();

  if (t.Item1 < 0 || t.Item2 < 0 || t.Item1 >= map.Length || t.Item2 >= map[0].Length) continue;

  if (map[t.Item1][t.Item2] != currentColor) continue;

  map[t.Item1][t.Item2] = Int32.MaxValue;

  toCheck.Enqueue(new Tuple<int, int>(t.Item1 + 1, t.Item2));
  toCheck.Enqueue(new Tuple<int, int>(t.Item1, t.Item2 + 1));
  toCheck.Enqueue(new Tuple<int, int>(t.Item1 - 1, t.Item2));
  toCheck.Enqueue(new Tuple<int, int>(t.Item1, t.Item2 - 1));
 }
}

Tym razem mapa 10000 x 10000 i większe zostanie poprawnie obsłużona. Kod ten można jeszcze optymalizować. Na przykład zliczać ile pól się już odwiedziło i przerwać dalsze przetwarzanie, jeśli odwiedziło się wszystkie. Dalszą optymalizację kodu można potraktować jako ćwiczenie.

StackOverflowException - jak sobie z nim radzić

Home

Każdy programista, czy to C#, C++ czy Java, musiał się kiedyś spotkać z przepełnieniem stosu, który, w przypadku platformy .NET, objawia się wyjątkiem StackOverflowException. Najłatwiej do takiego błędu doprowadzić pisząc nieskończoną rekursję. W tym poście zajmę się jednak tym jak poradzić sobie z przepełnieniem stosu, kiedy napisana metoda rekurencyjna wcale nie jest nieskończona. Zacznijmy od przykładu. Załóżmy, że mamy klasę Node i przy jej pomocy tworzymy drzewo binarne, w którym dla uproszczenia będziemy przechowywać liczby. Drzewa, które rozpatrujemy w tym przypadku nie są drzewami przeszukiwań i mogą być niezrównoważone.

public class Node
{
 public uint Data { get; set; }

 public Node Left { get; set; }
 public Node Right { get; set; }
}

Napisaliśmy również metodę rekurencyjną przeszukującą zadane drzewo w poszukiwaniu węzła przechowującego określoną wartość.

public static Node FindRec(Node root, uint i)
{
 if (root == null)
  return null;

 if (root.Data == i)
  return root;

 var res = FindRec(root.Right, i);

 if (res != null)
  return res;

 return FindRec(root.Left, i);
}

Metoda ta będzie działać, ale do czasu. Utwórzmy zdegenerowane drzewo czyli takie, które w rzeczywistości jest listą. Do wygenerowania takiego drzewa użyjemy następującego kodu:

public static Node CreateDegeneratedTree(uint noOfNodes)
{
 Node root = new Node() { Data = 0 };
 Node temp = root;

 for (uint i = 0; i <= noOfNodes; ++i)
 {
  temp.Right = new Node() { Data = i };
  temp = temp.Right;
 }

 return root;
}

W przypadku wystarczająco dużej liczby węzłów w zdegenerowanym drzewie (patrz parametr noOfNodes) wywołanie FindRec zakończy się wyjątkiem StackOverflowException. Wbrew pozorom, nie musi to być jakaś ogromna wartość. Na komputerze, na którym testowałem ten kod, wystarczyło aby drzewo zawierało 10 tyś węzłów. Trochę mało, czyż nie?

W takiej sytuacji musimy zrezygnować z rekursji na rzecz poczciwej pętli. Ja bym napisał taki kod:

public static Node Find(Node root, uint i)
{
 Queue<Node> toCheck = new Queue<Node>();
 toCheck.Enqueue(root);

 while (toCheck.Count > 0)
 {
  var node = toCheck.Dequeue();

  if (node != null)
  {
   if (node.Data == i)
    return node;
    
   toCheck.Enqueue(node.Right);
   toCheck.Enqueue(node.Left);
  }
 }

    return null;
}

Korzystam w nim z pomocniczej kolekcji, do której wrzucam kolejne węzły do sprawdzenia. Pętla kręci się dopóki nie zostanie znaleziony szukany węzeł albo dopóki wszystkie węzły nie zostaną sprawdzone. Podobne podejście możemy zastosować dla innych dla innych zagadnień tego typu.

Problem z StackOverflowException można również rozwiązać w sposób nie algorytmiczny, poprzez zwiększenie domyślnego rozmiaru stosu (1MB) przy pomocy narzędzia editbin albo tworząc nowy wątek o odpowiedniej wielkości stosu. Ja był jednak tego nie robił. Jeśli można osiągnąć jakiś efekt pisząc kod w odpowiedni sposób, to należy tak zrobić. W swojej karierze nie spotkałem jeszcze przypadku kiedy musiałbym zwiększyć wielkość stosu.

Na koniec załączam jeszcze kod metody Main. Cały program pozwala pobawić się pokazanymi powyżej metodami do wyszukiwania (iteracyjną i rekurencyjną) dla zdegenerowanego drzewa o zadanej liczbie węzłów. Program umożliwia również ustalenie wielkości stosu (w celach edukacyjnych :)). Kod może i jest trochę pokraczny, ale dla celów edukacyjnych się nada. Uwaga! Podanie zbyt dużej wartości jako Stack size in kilobytes (0 for default): albo Number of nodes in tree: może zakończyć się OutOfMemoryException.

static void Main(string[] args)
{
    Console.Write("Do you want to use recursion (Y for yes)?: ");
    
    string line = Console.ReadLine();
    bool useRecursion = String.Equals(line, "Y", StringComparison.OrdinalIgnoreCase);

    if(useRecursion)
        Console.WriteLine("Recursion search will be used");

    Console.Write("Stack size in kilobytes (0 for default): ");

    line = Console.ReadLine();
    uint stackSize;
    if (!UInt32.TryParse(line, out stackSize))
        stackSize = 1024

    Console.WriteLine("Stack size is {0} kilobytes ", stackSize);

    var th = new Thread(
  new ThreadStart(() =>
  {
   Console.Write("Number of nodes in tree: ");

   while ((line = Console.ReadLine()) != String.Empty)
   {
    uint noOfNodes;
    if (UInt32.TryParse(line, out noOfNodes))
    {
     Node root = CreateDegeneratedTree(noOfNodes);

     Stopwatch sw = new Stopwatch();

     if (useRecursion)
     {
      sw.Start();
      var res = FindRec(root, noOfNodes);
      sw.Stop();
     }
     else
     {
      sw.Start();
      var res = Find(root, noOfNodes);
      sw.Stop();
     }

     root = null;
     Console.Write("Processing time (ms): {0}\n\n", sw.ElapsedMilliseconds);
    }

    Console.Write("Number of nodes in tree: ");
   }
  }), (int)stackSize * 1024);

 th.Start();
}