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