Zadanie numer 1 z laboratorium programowania obiektowego
Laboratorium programowania obiektowego Zadanie zaliczeniowe 1 termin oddawania rozwiazan: 16 kwietnia 2008 Lamiglowki z dopasowaniem krawedzi (ang. edge-matching puzzle) polegaja na ukladaniu danego zbioru elementow tak, by elementy sasiadujace pasowaly do siebie. Istnieje wiele wariantow lamiglowek tego typu, rozniacych sie, miedzy innymi, liczba wymiarow przestrzeni, w ktorej rozwiazujemy lamiglowke. W przestrzeni trojwymiarowej zadaniem rozwiazujacego jest skladanie trojwymiarowych "klockow". W przestrzeni jednowymiarowej kazdy element ma maksymalnie dwoch sasiadow, jak w grze w domino. Najczesciej lamiglowki rozwiazywane sa w przestrzeni dwuwymiarowej, czyli wymagaja ukladania elementow na plaszczyznie. Przykladem takich lamiglowek sa popularne "puzzle", a takze Tetravex i Eternity II. W lamiglowce Tetravex kwadratowe elementy, ktorych jest n*n, nalezy ulozyc na kwadratowej planszy o boku dlugosci n. Spotyka sie warianty z plansza 2 na 2, 3 na 3, 4 na 4 itd. Krawedzie kazdego elementu oznaczone sa cyframi dziesietnymi. Dwa elementy moga ze soba sasiadowac, jesli na krawedziach, ktorymi sie stykaja, sa te same cyfry. Np. na prawo od elementu, ktory na prawej krawedzi ma cyfre "5" mozna polozyc tylko element, ktory na lewej krawedzi ma "5". Kazdy element Tetravex ma okreslona orientacje na planszy, tzn. wiadomo, ktora krawedz ma byc u gory, ktora po prawej itd. Inaczej mowiac, elementow Tetravex nie mozna obracac. Lamiglowka Rotavex ma takie same zasady, jak Tetravex, ale pozwala na obracanie elementow - kazdy mozna umiescic na planszy na cztery rozne sposoby. Moglibysmy tez rozwazac lamiglowke, ktorej elementy sa oznaczone cyframi po obu stronach. Jej rozwiazanie wymagaloby ustalenia nie tylko, gdzie ma byc dany element i jak go obrocic, lecz takze, na ktora strone go odwrocic. Zarowno Tetravex, jak i Rotavex, mozna tez rozwiazywac, poslugujac sie elementami, ktorych krawedzie oznaczono nie cyframi, lecz symbolami lub kolorami. Zasady rozwiazywania bylyby w tym wypadku takie same. Osoby rozwiazujace lamiglowki z dopasowaniem krawedzi staraja sie ustalic pozycje poszczegolnych elementow na drodze dedukcji. Podczas rozwiazywania Tetravex mozna np. zauwazyc, ze jesli jest element, ktory na lewej krawedzi ma cyfre, ktora nie wystepuje na prawej krawedzi zadnego innego elementu, to element ten musi sie znalezc na lewej krawedzi planszy. Innym sposobem rozwiazywania jest uzycie "metody prob i bledow", tzn. umieszczanie na poszczegolnych polach planszy, na wszystkie mozliwe sposoby, kolejnych elementow i sprawdzanie na biezaco, czy aktualny element nie koliduje z tymi, ktore juz sa na planszy. Ten sposob jest bardzo pracochlonny, ale jesli rozwiazywaniem lamiglowki mialby sie zajmowac komputer, nie stanowi to problemu. Zaleta tego sposobu rozwiazywania jest latwosc znalezienia wszystkich rozwiazan lamiglowki, ktora ma wiecej niz jedno rozwiazanie. Na efektywnosc dzialania "metody prob i bledow" wplyw moze miec kolejnosc wypelniania pol elementami. Robienie tego "losowo" raczej nie jest dobrym pomyslem. Lepiej jest ukladac elementy wiersz po wierszu, albo np. wypelniac nimi kolejne kwadraty o lewym gornym wierzcholku w lewym gornym rogu planszy. W pierwszym przypadku, na planszy 3 na 3, ukladalibysmy elementy na polach (1,1), (1,2), (1,3), (2,1), (2,2) itd. W drugim przypadku kolejnosc pol bylaby nastepujaca: (1,1), (1,2), (2,2), (2,1), (1,3), (2,3), (3,3), (3,2), (3,1). Tu najpierw wypelnilismy kwadrat o boku 1 (czyli pole (1,1)), nastepnie rozszerzylismy go do kwadratu o boku 2 (dodajac pola (1,2), (2,2), (2,1)) a nastepnie 3. Zbuduj w Smalltalku hierarchie klas pozwalajacych na reprezentacje lamiglowek z dopasowaniem krawedzi i ich rozwiazywanie. Klasy nalezy zdefiniowac tak, by bylo mozliwe wykonanie nastepujacego fragmentu kodu z wynikiem zgodnym z komentarzami: """""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" s:=Set new. s add: ( ElementKwadratowyJednostronny gora: (KrawedzZWartoscia new: 8) prawo: (KrawedzZWartoscia new: 1) dol: (KrawedzZWartoscia new: 2) lewo: (KrawedzZWartoscia new: 9)). s add: ( ElementKwadratowyJednostronny gora: (KrawedzZWartoscia new: 0) prawo: (KrawedzZWartoscia new: 2) dol: (KrawedzZWartoscia new: 4) lewo: (KrawedzZWartoscia new: 3)). s add: ( ElementKwadratowyJednostronny gora: (KrawedzZWartoscia new: 6) prawo: (KrawedzZWartoscia new: 9) dol: (KrawedzZWartoscia new: 4) lewo: (KrawedzZWartoscia new: 2)). s add: ( ElementKwadratowyJednostronny gora: (KrawedzZWartoscia new: 2) prawo: (KrawedzZWartoscia new: 9) dol: (KrawedzZWartoscia new: 4) lewo: (KrawedzZWartoscia new: 8)). s add: ( ElementKwadratowyJednostronny gora (KrawedzZWartoscia new: 0) prawo: (KrawedzZWartoscia new: 2) dol: (KrawedzZWartoscia new: 2) lewo: (KrawedzZWartoscia new: 5)). s add: ( ElementKwadratowyJednostronny gora: (KrawedzZWartoscia new: 7) prawo: (KrawedzZWartoscia new: 9) dol: (KrawedzZWartoscia new: 0) lewo: (KrawedzZWartoscia new: 9)). s add: ( ElementKwadratowyJednostronny gora: (KrawedzZWartoscia new: 4) prawo: (KrawedzZWartoscia new: 8) dol: (KrawedzZWartoscia new: 0) lewo: (KrawedzZWartoscia new: 7)). s add: ( ElementKwadratowyJednostronny gora: (KrawedzZWartoscia new: 2) prawo: (KrawedzZWartoscia new: 1) dol: (KrawedzZWartoscia new: 7) lewo: (KrawedzZWartoscia new: 1)). s add: ( ElementKwadratowyJednostronny gora: (KrawedzZWartoscia new: 4) prawo: (KrawedzZWartoscia new: 3) dol: (KrawedzZWartoscia new: 8) lewo: (KrawedzZWartoscia new: 2)). "Na zmiennej 's' umiescilismy zbior dziewieciu elementow dla Tetravex lub Rotavex" l1:=Tetravex elementy: s. "Na zmiennej 'l1' jest obiekt reprezentujacy lamiglowke Tetravex o zadanym zbiorze elementow. Plansza jest rozmiaru 3 na 3, bo elementow bylo 9." l2:=Rotavex elementy: s. "Na zmiennej 'l2' jest obiekt reprezentujacy lamiglowke Rotavex o tym samym zbiorze elementow." l3:=Tetravex losowaOBoku: 4. "Na zmiennej 'l3' znalazla sie lamiglowka Tetravex o planszy 4 na 4, wygenerowana losowo. Generujac lamiglowke nalezy zadbac, by miala przynajmniej jedno rozwiazanie." r1:=UkladanieWierszami new rozwiazanie: l1. "Na zmiennej 'r1' znalazla sie reprezentacja rozwiazania lamiglowki 'l1' znaleziona metoda prob i bledow, ukladajaca poszczegolne elementy wierszami. Gdyby rozwiazanie nie istnialo (tu istnieje), na 'r1' powinien byc nil. Reprezentacja rozwiazania moze byc np. kolekcja elementow uporzadkowana wg kolejnosci ich wystapienia na planszy." r2:=UkladanieKwadratow new wszystkieRozwiazania: l1. "Na zmiennej 'r2' jest kolekcja wszystkich rozwiazan lamiglowki 'l1', znalezionych metoda prob i bledow, ukladajaca poszczegolne elementy w kolejnosci wypelniania kwadratow." r3:=UkladanieWierszami new wszystkieRozwiazania: l2. "Na zmiennej 'r3' jest kolekcja rozwiazan lamiglowki 'l2' znalezionych metoda prob i bledow, ukladajaca elementy wierszami." r4:=UkladanieKwadratow new rozwiazanie: l3. "Na zmiennej 'r4' jest rozwiazanie lamiglowki 'l3' znalezione metoda prob i bledow, ukladajaca elementy kwadratami." """""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" Uwaga 1: zadanie trzeba rozwiazac obiektowo. Nalezy unikac powtarzania kodu lub pisania wielokrotnie podobnych fragmentow. Uwaga 2: hierarchia klas powinna umozliwiac latwe rozbudowywanie systemu o inne lamiglowki i inne metody rozwiazywania. Wskazowka: jesli chcemy miec gwarancje, ze wylosowana lamiglowka bedzie miala rozwiazanie, nalezy ja wylosowac w stanie ulozonym. Pytania do tresci zadania prosze kierowac na adres: zaroda@mimuw.edu.pl
A oto rozwiązanie (Paczka do Dolphina Smalltalka):
zadanie_zaliczeniowe