Pierwszym zadaniem na pracownię z programowania było rozwiązanie zagadki "Skarby" z Wiedzy i Życia zaimplementowane w prologu, który idealnie nadaje się do takich zadań.Treść zadania brzmi tak:
Mamy planszę n x m. Cyfra w danym polu oznacza, w ilu sąsiednich kratkach – stykających się z polem z cyfrą bokiem lub rogiem – znajdują się skarby. W kratkach z cyframi skarbów nie ma. Znajdź wszystkie miejsca gdzie mogą być zakopane skarby.
Jak zatem rozwiązać taki problem w prologu? Standardowo: generuj-sprawdź-nawróć.
Po pierwsze każde pole numeryczne można traktować jako nasycone jeśli sąsiaduje z tyloma skarbami jaką ma wartość oraz nienasycone w przeciwnym wypadku.
Idea mojego (całkiem szybkiego!) algorytmu polega na tym by brać po kolei nienasycone pola, wygenerować wszystkie możliwe sposoby rozstawienia dokładnie tyle skarbów by nasycić dane pole, wybrać jeden i sprawdzić czy będzie to poprawne rozstawienie, jak się nie uda - nawracamy i wybieramy inne rozstawienie, jak znowu nie wyjdzie - nawracamy poziom wyżej.
Nietrudno udowodnić, że w ten sposób znajdziemy (o ile istnieje) rozwiązanie bo co krok liczba pól nienasyconych maleje, zatem będziemy mieć na końcu wszystkie pola nasycone. Oczywiście po zapamiętaniu rozwiązania nawracamy i sprawdzamy czy nie ma innego rozwiązania aż ostatecznie dojdziemy do momentu, że przejdziemy wszystkie możliwe kombinacje i stwierdzimy, że nic więcej nie da się znaleźć :)
Dodatkowo aby uatrakcyjnić program stworzyłem ładny interfejs w XPCE do prezentacji wyniku :)
Implementacja tego rozwiązania wraz z komentarzami i plikami z testami jest dostępna tutaj. Pochwalę się, że program został oceniony na 15/15 (WZY).
Jeśli ktoś będzie miał znowu tą zagadkę to odradzam użycia mojego programu - jest system antyplagiatowy i naprawdę nie warto, raczej radzę zaimplementować to po swojemu i czerpać tylko inspirację.
Brak komentarzy:
Prześlij komentarz