Logia 2007/08 - Etap III

Zadanie 1 (domino)

W tradycyjnej grze w domino występuje 28 kamieni. Każdy kamień składa się z 2 pól zawierających od zera do sześciu oczek. Każdy układ oczek na polach kamieni występuje tylko raz. Poniższe rysunki przedstawiają przykładowe kamienie.

Najczęściej spotykana wersja gry polega na wykładaniu przez graczy kolejnych kamieni w taki sposób, aby stykające się pola na kamieniach miały taką samą liczbę oczek. Alek, przygotowując się do turnieju, postanowił zanotować przebieg rozegranej partii, a następnie go przeanalizować. Dla ułatwienia liczbę oczek na stykających się kamieniach notował raz, pomijając powtórzenia, np. układ [1 0][0 3][3 2] zapisał jako 1032. Napisz procedurę DOMINO :gra, która narysuje przebieg gry według notatek Alka lub wypisze komunikat - Błąd. Parametr :gra jest słowem złożonym z cyfr od 0 do 6. Rysunek musi mieścić się na ekranie, jego szerokość nie może być mniejsza niż 400, kamienie układane są poziomo.

Przykłady: efekt wywołania DOMINO "0123456

wywołanie DOMINO "232 powinno wypisać komunikat Błąd.

Strategia

W celu sprawdzenia poprawności zapisanej rozgrywki należy utworzyć dodatkową liste tymczasową na której przechowywane będą dotychczas położone klocki. Jeśli klocek danego typu został już położony należy wypisać błąd. Należy zauważyć, że wedlug zapisu kładziony jest np. klocek [3 2], ale jest to ten sam klocek co [2 3], dlatego wartości na kostce domina dobrze jest posortować wtedy oba przypadki nie będą rozróżnialne.

W kwestii rysowania warto dopisać dodatkową funkcję rysującą. Jeśli przyjrzeć się jak zostały narysowane symboliczne reprezentacje wartości to wszystkie korzystają z kółek osadzonych na siatce 3×3. Oznacza to, że każdej wartości można przyporządkować pewna tablicę danych złożonych z 0 i 1, która stwierdzi, które kółka mają zostać narysowane. Przykładowo dla czterech będzie to lista [[1 0 1] [0 0 0] [1 0 1]], a dla trójki [[1 0 0] [0 1 0] [0 0 1]].

Procedura główna

Poprawność rozgrywki

Pierwsza część procedury polega na sprawdzeniu czy zapis jest poprawny. Dopiero potem można przejść do rysowania rozgrywki.

1. oto DOMINO :gra
2.   jeśli((długość :gra) <= 1) [
3.     pisz "Błąd
4.     stop
5.   ]
6.   niech "wyk []
7.   powtórz ((długość :gra) - 1)[
8.     niech "a element npw :gra
9.     niech "b element (npw + 1) :gra
10.     niech "p utwórzPare :a :b
11.     jeśli(numel :p :wyk <> 0) [
12.       pisz "Błąd
13.       stop
14.     ]
15.     niech "wyk nak :p :wyk
16.   ]

(1. - 4.) Na początek wyróżniamy przypadek, gdy zapis gry jest niepoprawny czyli, gdy jest mniej niż dwie cyfry na zapiskach. Potem (5.) deklarowana jest lista do przechowywania już wykorzystanych kostek domino. (6.) Dla każdej pary cyfr: (7. - 8.) pobierane są obie wartości na kostce i (9.) zamieniane na posortowaną listę dwuelementową. (10.) Jeśli dana kostka już była wykorzystana to: (11. - 12.) program zostaje przerwany. Jeśli jednak kostka nie była wcześniej użyta to (14.) zostaje dopisana na liste. Jeśli program nie zostanie przerwany do zakończenia pętli oznacza to, że zapis jest poprawny.

Rysowanie

Drugą część kodu można wygodnie zrealizować przy pomocy dodatkowej procedury DOMINO_el, która narysuje część kostki uwzględniając rysowaną wartość na podstawie kodu oraz wielkość kostki.

17.   niech "w 460
18.   niech "kody [[[0 0 0] [0 0 0] [0 0 0]]
19.                             [[0 0 0] [0 1 0] [0 0 0]]
20.                             [[1 0 0] [0 0 0] [0 0 1]]
21.                             [[1 0 0] [0 1 0] [0 0 1]]
22.                             [[1 0 1] [0 0 0] [1 0 1]]
23.                             [[1 0 1] [0 1 0] [1 0 1]]
24.                             [[1 1 1] [0 0 0] [1 1 1]]]
25.   niech "n ((długość :gra) - 1) * 2
26.   niech "a :w/:n
27.   pod
28.   ws :a/2 pw 90
29.   ws :n/2*:a lw 90
30.   opu
31.   powtórz ((długość :gra) - 1)[
32.     niech "ela element npw :gra
33.     niech "elb element (npw + 1) :gra
34.     DOMINO_el (element (:ela+1) :kody) :a
35.     pw 90 np :a lw 90
36.     DOMINO_el (element (:elb+1) :kody) :a
37.     pw 90 np :a lw 90
38.   ]
39. już

(17. - 25.) Zadeklaruj zmienne początkowe: maksymalną szerokość rysunku oraz kody poszczególnych cyfr (i-ta lista opisuje cyfrę i - 1), ile będzie rysowanych fragmentów kostek domina :n oraz bok pojedynczego fragmentu :a. (26. - 29.) Przejdź w lewy dolny róg rysunku i (30. - 37.) narysuj każdą parę wartości.

Rysowanie fragmentu kostki

Poniżej został zamieszczony kod procedury DOMINO_el używanej do rysowania kostek:

1. oto DOMINO_el :kod :a
2.   niech "b :a/4
3.   opu
4.   powtórz 4 [
5.     np :a
6.     pw 90
7.   ]
8.   pod
9.   pw 90 np :b
10.   lw 90 np 3*:b
11.   powtórz 3 [
12.     niech "wiersz element npw :kod
13.     pw 90
14.     powtórz 3 [
15.       niech "el element npw :wiersz
16.       jeśli (:el = 1)[
17.         kropka :b/2
18.       ]
19.       np :b
20.     ]
21.     ws :b*3 lw 90
22.     ws :b
23.   ]
24.   pw 90
25.   ws :b
26.   lw 90
27.   opu
28. już

(3. - 8.) Narysuj obramowanie i (9. - 11.) przejdź do pierwszej pozycji w pierwszym rzędzie kropek. (12.) Narysuj trze wiersze po (16.) trzy kropki i (18.) rysuj kropkę tylko wtedy, gdy powiązana wartość na liście wynosi 1.

Strategia

Pierwszym przyjętem założeniem będzie ignorowanie dwuliterowych przedrostków La i El, więc program niekoniecznie będzie działać z każdym zestawem danych (np. inna lista miast i odległości). W funkcji zostaną zadeklarowane dwie listy. Pierwsza z nich będzie przechowywać nazwy miejscowości, a druga to będzia lista list, gdzie i-ty element będzie listą odległości do j-tej miejscowości.

W celu znalezienia odległości za początkowe miasto przyjęte zostanie pierwsze miasto na liście. Potem zostanie określony cel i po znalezieniu odległości i jej dodaniu za aktualnie miasto należy przyjąć miasto docelowe.

Funkcja główna

(2.) Zadeklaruj listę miast oraz (3. - 4.) tablicę odległości. (5.) Wyszczególniamy przypadek, gdy trasa podróży jest pusta: wtedy (6.) należy zwrócić 0. (7.) Jeśli jednak trasa ma pewne cele to (8.) ustal, że aktualnie Jaś znajduje się w pierwszej miejscowości na liście i (9.) aktualnie przebyty dystans wynosi 0. (10.) Dla każdego pozostałego punktu podróży, o ile (12.) nie istnieje to (13.) wybierz odległości z aktualnego miasta i (14.) wybierz odpowiednią odległość. (15.) Do przebytego dystansu dodaj znaleziony odcinek i (16.) zmień aktualne miasto pobytu. Na koniec (19.) zwróć przebyty dystans.

Tworzenie klucza

Zasada tworzenia klucza polega na przeglądaniu kolejnych liter klucza, a następnie wpisaniu tych, które do tej pory nie wystąpiły wcześniej. Podobna zasada dotyczy później dopisywania pozostałych liter alfabetu, więc oba zadania można połączyć dopisując na koniec klucza cały alfabet. Funkcja SZYFR_klucz przyjmuje jeden argument :słowo, którym jest klucz. Wynikiem jest nowy alfabet do szyfrowania.

1. oto SZYFR_klucz :słowo
2.   niech "s "
3.   niech "słowo (słowo :słowo "abcdefghijklmnopqrstuvwxyz)
4.   powtórz (długość :słowo) [
5.     niech "el element npw :słowo
6.     jeśli (numel :el :s = 0) [
7.       niech "s (słowo :s :el)
8.     ]
9.   ]
10.   wynik :s
11. już

Szyfrowanie wyrazu

Do szyfrowania pojedynczego wyrazu służy funkcja SZYFR_szyfruj, która akceptuje szyfrowane :słowo oraz używany :alfabet.

1. oto SZYFR_szyfruj :słowo :alfabet
2.   niech "s "
3.   powtórz (długość :słowo) [
4.     niech "el element npw :słowo
5.     niech "poz (ascii :el) - (ascii "a) + 1
6.     niech "s (słowo :s (element :poz :alfabet))
7.   ]
8.   wynik :s
9. już

(3.) Dla każdej litery: (4.) pobierz ją i (5.) określ pozycję w alfabecie. (6.) Do wyniku dopisz literę z :alfabet z wyliczonej linijkę wcześniej pozycji :poz.

Funkcja główna

Teraz w głównej funkcji pozostaje wykorzystać napisane funkcje:

1. oto SZYFR :klucz :list
2.   niech "alfabet SZYFR_klucz :klucz
3.   niech "s "
4.   powtórz (długość :list) [
5.     niech "el element npw :list
6.     niech "f SZYFR_szyfruj :el :alfabet
7.     niech "s (słowo :s :f)
8.   ]
9.   wynik :s
10. już

(2.) Utwórz alfabet, a potem (4.) Dla każdego wyrazu z listy: (5.) pobierz go, (6.) zaszyfruj przy pomocy wcześniej znalezionego alfabetu i (7.) połącz z dotychczasowym wynikiem.

Strategia

Na początek napiszmy funkcję czyAnagram?, która będzie sprawdzać czy dane dwa wyrazy są anagramami. W celu porównania oba wyrazy zostaną zamienione na listę znaków funkcją naListe, następnie posortowane i porównane.

Z kolei główna funkcja będzie w pętli wykonywać określone polecenia. Po pierwsze pobierany będzie pierwszy wyraz z listy i nazwany wzór, a następnie pozostała część listy zostanie podzielona na dwie podlisty: pierwsza z nich będzie zawierać słowa z którymi wzór jest anagramem oraz na listę tych z którymi nie. Pierwsza lista jest dopisywana do listy wynikowej, a dla drugiej listy powtarzany jest ten sam zestaw instrukcji.

Czy anagram?

Funkcja czyAnagram? sprawdza czy wyrazy :a i :b są anagramami.

1. oto czyAnagram? :a :b
2.   jeśli ((długość :a) <> (długość :b)) [
3.     wynik "fałsz
4.   ]
5.   niech "alista sortuj naListe :a
6.   niech "blista sortuj naListe :b
7.   powtórz (długość :alista) [
8.     jeśli (element npw :alista <>
9.                   element npw :blista) [
10.       wynik "fałsz
11.     ]
12.   ]
13.   wynik "prawda
14. już

(2. - 4.) Wyklucz przypadki, gdy wyrazy nie są tej samej długości. (5. - 6.) Zamień oba wyrazy na listę znaków i każdy posortuj oddzielnie. (7. - 12.) Sprawdź czy elementy na obu listach są identyczne. (13.) Jeśli wszystkie warunki zostaną spełnione zwróć, że :a i :b są anagramami.

W celu zamiany wyrazu na listę znaków została napisana funkcja naListe. Przyjmuje ona tylko jeden argument :słowo, którym jest wyraz do rozbicia.

1. oto naListe :słowo
2.   niech "l []
3.   powtórz (długość :słowo) [
4.     niech "l nak element npw :słowo :l
5.   ]
6.   wynik :l
7. już

Funkcja główna

Wybieranie anagramów będzie trwało tak długo jak lista :wyrazy nie będzie pusta.

1. oto ANAGRAMY :wyrazy
2.   niech "w []
3.   dopóki [
4.     (długość :wyrazy) > 0
5.   ][
6.     niech "pasuje []
7.     niech "pozostałe []
8.     niech "wzor pierw :wyrazy
9.     powtórz ((długość :wyrazy) - 1) [
10.       niech "el element (npw + 1) :wyrazy
11.       jeżeli (czyAnagram? :wzor :el)[
12.         niech "pasuje nak :el :pasuje
13.       ][
14.         niech "pozostałe nak :el :pozostałe
15.       ]
16.     ]
17.     niech "pasuje nak :wzor :pasuje
18.     niech "w nak :pasuje :w
19.     niech "wyrazy :pozostałe
20.   ]
21.   wynik :w
22. już

(2.) Dopóki (3.) lista nie jest pusta to przygotuj listę (6.) na anagramy (7.) i pozostałe. (8.) Wybierz pierwszy element jako wzór (praktycznie może być dowolny element). (9.) Dla każdego wyrazu prócz wybranego: (10.) pobierz element i (11. - 15.) przyporządkuj do odpowiedniej listy. (17.) Na koniec dopisz :wzor do listy elementów pasujących, (18.) i dopisz listę :pasuje do wyniku :w. (19.) Liste nie pasujących wyrazów przypisz zmiennej :wyraz i wróć na początek pętli.

• Rozwiązania zadań