Strona główna » Poradniki » Logomocja » LOGIA » Logia 2000/01 - Etap III
 

Logia 2000/01 - Etap III

https://mattomatti.com/li003
· Etap I · Etap II · Etap III ·
iOryginalna treść zadań jest dostępna pod oficjalnym adresem konkursu LOGIA

Wprowadzenie

Wężowce to sztuczne wyspy przytwierdzone do dna morskiego u wybrzeży oceanu.

Każdy wężowiec jest zbudowany z kwadratowych platform o wymiarach 10 m x 10 m.

Najprostszy wężowiec składa się z jednej platformy.
Złożony wężowiec jest ciągiem połączonych platform.
Pierwsza platforma w ciągu jest połączona (całym) jednym bokiem z drugą i tylko z nią, ostatnia - z przedostatnią i tylko z nią, a każda inna z dokładnie dwoma - poprzednią i następną.

Układy a i b na rysunku 1 to poprawnie zbudowane wężowce.

Układ c nie jest wężowcem, bo aż 4 platformy mają tylko jednego sąsiada, a 2 mają trzech sąsiadów.

Układ d nie jest wężowcem, bo tylko 1 platforma ma jednego sąsiada, a 3 mają trzech sąsiadów.

Kolonia wężowców może zajmować siatkę 20 x 20 pól, jak na rysunku 2.

Wężowce mogą przylegać do boków siatki, ale żadne dwa nie mogą się ze sobą stykać nawet rogami.

Pola siatki zajmowanej przez kolonię wężowców numerujemy kolejno od 0 do 399. Pola w wierszu najniższym na mapie mają kolejno od lewej do prawej numery od 0 do 19, pola w drugim od dołu wierszu mają numery od 20 do 39 itd. Pole w prawym górnym rogu mapy ma numer 399.

Opisem wężowca jest lista numerów wszystkich zajmowanych przez niego pól.

Kodem wężowca nazywamy taki opis, w którym:

  • każde dwie sąsiednie liczby na liście są numerami pól zajmowanych przez dwie sąsiednie platformy wężowca,
  • pierwsza liczba na liście jest mniejsza od ostatniej.

Każdy wężowiec, zajmujący co najmniej dwa pola ma wiele opisów różniących się porządkiem elementów, ale tylko jeden kod. Np. wężowiec w prawym dolnym rogu siatki na rysunku 2, składający się z 3 platform, ma 6 różnych opisów: [18 19 39] [19 39 18] itd., ale tylko jeden opis - [18 19 39] jest jego kodem.

Kolonie wężowców można kodować na wiele różnych sposobów. My przyjmujemy następujący system kodowania. Każdy wiersz siatki pól 20 x 20 pól zajmowanej przez kolonię opisujemy kolejno od góry do dołu za pomocą słów utworzonych z 20 cyfr binarnych 0 lub 1.

Opisem pierwszych 4 wierszy kolonii na rysunku 2 są odpowiednio słowa:

  •  00110000000000000000
  •  01100000000000001110
  •  11000000000001011010
  •  10000000111100010010

Każde takie słowo interpretujemy jako dwójkowy zapis liczby całkowitej i tłumaczymy na system dziesiętny. Otrzymana w ten sposób lista dwudziestu liczb jednoznacznie opisuje kolonię i jest jej kodem. Kodem kolonii przedstawionej na rysunku 2 jest lista: [196608 393230 786522 528146 125266 75858 338770 338240 339712 352256 262146 458874 3914 125258 76106 10570 125272 68352 122881 3].

Zadanie 1

Zdefiniuj polecenie MAPA :kk, które mając dany kod kolonii wężowców :kk, rysuje na ekranie jej mapę, podobną do rysunku poniżej. Morze na mapie powinno być granatowe, a każdy wężowiec pomalowany na inny kolor. Zakładamy, że dana kolonia może się składać z co najwyżej 12 wężowców, więc 16 podstawowych kolorów zupełnie wystarczy. Uwaga: nie rysujemy linii siatki. Dla danego kodu kolonii przedstawionej na rysunku 2 we wprowadzeniu, mapa utworzona przez Twoją procedurę może się różnić od rysunku poniżej tylko wyborem kolorów, ale każdy wężowiec na mapie musi mieć inny kolor.

Poniższy rysunek przedstawia wywołanie MAPA [196608 393230 786522 528146 125266 75858 338770 338240 339712 352256 262146 458874 3914 125258 76106 10570 125272 68352 122881 3].

MAPA

Główna funkcja MAPA wygląda następująco:

  1. oto MAPA :kk
  2.   niech "h 480
  3.   niech "a :h / 20
  4.   niech "mapa []
  5.   powtórz 20 [
  6.     niech "lista naBinarnaLista element npw :kk
  7.     niech "mapa nap :lista :mapa
  8.   ]
  9.   pod
  10.   ws :h/2 pw 90
  11.   ws :h/2 lw 90
  12.   wielokąt [
  13.     ukm "niebieski5
  14.     powtórz 4 [
  15.       np :h
  16.       pw 90
  17.     ]
  18.   ]
  19.   wróć
  20.   opu
  21.   niech "kolor 0
  22.   powtórz 20 [
  23.     niech "y npw
  24.     powtórz 20 [
  25.       niech "x npw
  26.       jeśli (element (21 - :x) element :y :mapa = 1) [
  27.         niech "mapa MAPA_rys :mapa :x :y :kolor
  28.         zwiększ "kolor
  29.       ]
  30.     ]
  31.   ]
  32. już

Na podstawie (2.) ustalonej wysokości (3.) określ bok najmniejszego kwadratu. (4. - 8.) Przygotuj mapę na podstawie, której zostanie narysowany obraz. (9. - 18.) Narysuj duży granatowy kwadrat i (19.) wróć na środek rysunku. Następnie (21.) ustal kolor pierwszego wężyka i (22.- 31.) zacznij poszukiwania wężyka na stworzonej wcześniej mapie (26.) dla każdego pola. Jeśli jest pole do narysowania to (27.) narysuj całą grupę i (28.) zwiększ wartość zmiennej kolor, aby następna narysowana grupa miała inny kolor.

Tworzenie mapy

Tworzenie mapy, które jest wykonywane przez funkcję MAPA na samym początku procedury jest wspomagane przez funkcje naBinarnaLista, która przyjmuje jeden argument :liczba. Dla podanego argumentu funkcja zwraca 20 cyfr zapisu binarnego podanej liczby w postaci listy cyfr 0 i 1.

  1. oto naBinarnaLista :liczba
  2.   niech "l pot 2 (20 - 1)
  3.   niech "lista []
  4.   powtórz 20 [
  5.     jeżeli (:liczba >= :l)[
  6.       niech "lista nak 1 :lista
  7.       niech "liczba :liczba - :l
  8.     ][
  9.       niech "lista nak 0 :lista
  10.     ]
  11.     niech "l :l / 2
  12.   ]
  13.   wynik :lista
  14. już

W celu wyliczenia najwyższej potęgi dopisana została funkcja pot, która pozwala podnieść wartość :a do potęgi :potega.

  1. oto pot :a :potega
  2.   niech "w 1
  3.   powtórz :potega [
  4.     niech "w :w * :a
  5.   ]
  6.   wynik :w
  7. już

Rysowanie grup

Rysowanie grup wykonuje procedura MAPA_rys, która przyjmuje cztery argumenty: :mapa - aktualna mapa z wartościami pól 0, 1, :x, :y - współrzędne punktu do narysowania oraz :kolor jakiego koloru ma być rysowany kwadrat. Funkcja po narysowaniu kwadratu zamienia w tablicy, pozycji pola, wartość 1 na 0, a później zwraca nową wartość mapy.

  1. oto MAPA_rys :mapa :x :y :kolor
  2.   jeśli (LUB :x < 1 :x > 20 :y < 1 :y > 20) [
  3.     wynik :mapa
  4.   ]
  5.   jeśli (element (21 - :x) (element :y :mapa) = 0) [
  6.     wynik :mapa
  7.   ]
  8.   kwadrat :x :y :a :kolor
  9.   niech "mapa zastąp :y :mapa (zastąp (21 - :x) (element :y :mapa) 0)
  10.   niech "mapa MAPA_rys :mapa :x - 1 :y :kolor
  11.   niech "mapa MAPA_rys :mapa :x + 1 :y :kolor
  12.   niech "mapa MAPA_rys :mapa :x :y - 1 :kolor
  13.   niech "mapa MAPA_rys :mapa :x :y + 1 :kolor
  14.   wynik :mapa
  15. już

(2. - 4.) Sprawdź czy pole jest poprawne: jeśli nie to zakończ działanie poprzez zwrócenie niezmienionej mapy. (5. - 7.) Jeśli dane pole ma wartość 0 to również zwróć niezmienioną mapę. Jednak jeśli oba warunki są fałszywe to (8.) narysuj kwadrat na pozycji :x :y, odpowiedniej wielkości :a i kolorze :kolor i (9.) zmień w tablicy, że pole zostało narysowana i (10. - 13.) spróbuj narysować sąsiednie kwadraty. Na koniec (14.) zwróć nową wartość :mapa.

Rysowanie kwadratu

Rysowanie każdego kwadratu jest rysowane względem środka rysunku na podstawie pozycji :pozX, :pozY, rozmiaru :rozmiar.

  1. oto kwadrat :pozX :pozY :rozmiar :kolor
  2.   pod
  3.   np (:pozY - 11) * :rozmiar
  4.   lw 90
  5.   np (:pozX - 10) * :rozmiar
  6.   pw 90
  7.   ukp :kolor
  8.   wielokąt [
  9.     ukm :kolor
  10.     powtórz 4 [
  11.       np :rozmiar
  12.       pw 90
  13.     ]
  14.   ]
  15.   ws (:pozY - 11) * :rozmiar
  16.   pw 90
  17.   np (:pozX - 10) * :rozmiar
  18.   lw 90
  19.   opu
  20. już

(2. - 6.) Przesuń w lewy dolny róg rysowanego kwadratu, (7. - 14.) Narysuj kwadrat odpowiedniej wielkości i odpowiednim kolorem. (15. - 19.) Wróć tam skąd żółw rozpoczął rysowanie.

Zadanie 2

Zdefiniuj funkcję ODBICIE :kw, która mając kod wężowca, daje w wyniku kod jego symetrycznego odbicia względem pionowej osi symetrii kwadratowej siatki pól.

Oto przykładowe wyniki:

ODBICIE [48 68 88 108 128 148 149 150 151 131 111 91 71 51 50]
powinno dać wynik [49 48 68 88 108 128 148 149 150 151 131 111 91 71 51]
ODBICIE [18 19 39]
powinno dać wynik [1 0 20]

W celu odbicia rysunku względem pionowej osi Y należy odwrócić współrzędną X każdego punktu, dlatego zadeklarowane zostaną dwie funkcje pomocnicze: naPunkt - zamieni numer pola na jego współrzędne oraz naLiczbe - zamieni współrzędne na numer pola.

  1. oto ODBICIE :kw
  2.   niech "w []
  3.   powtórz (długość :kw)[
  4.     niech "pkt naPunkt element npw :kw
  5.     niech "w nak naLiczbe (lista (19 - pierw :pkt) (ost :pkt)) :w
  6.   ]
  7.   wynik :w
  8. już

(2.) Zadeklaruj listę wynikową i (3.) dla każdego pola: (4.) wylicz jego współrzędne. Następnie (5.) zmodyfikuj dane i zamień na numer pola i dopisza na listę :w. Po zakończeniu pętli (7.) zwróć listę :w.

Współrzędne punktu

Współrzędna pola można odczytać na podstawie jego numeru, ponieważ wiadomo, że każdy rząd ma dokładnie 20 pól. Zadanie to realizuje funkcja naPunkt. Jej działanie polega na odczytaniu współrzędnych i zwróceniu ich w postaci dwuelementowej listy.

  1. oto naPunkt :liczba
  2.   niech "r reszta :liczba 20
  3.   wynik (lista :r (:liczba - :r) / 20)
  4. już

Odwrotne działanie ma funkcja naLiczbe, która na podstawie współrzędnych punktów określa jego numer:

  1. oto naLiczbe :punkt
  2.   wynik (pierw :punkt) + 20 * (ost :punkt)
  3. już

Zadanie 3

Zdefiniuj funkcję PROST :kw, która mając dany kod wężowca, znajduje minimalny prostokąt pól na mapie, w którym mieści się dany wężowiec. Wynikiem funkcji ma być lista dwóch nieujemnych liczb całkowitych: pierwsza - to numer pola w lewym dolnym rogu wyznaczonego prostokąta, a druga - to numer pola w prawym górnym rogu.

Oto przykładowe wyniki:

PROST [48 68 88 108 128 148 149 150 151 131 111 91 71 51 50]
powinno dać wynik [48 151]
PROST [22]
powinno dać wynik [22 22]
PROST [3 23 22 42 41]
powinno dać wynik [1 43]

Wyznaczenie najmniejszego prostokąta, który zawiera wszystkie elementy wężyka polega na wyznaczeniu minimalnej i maksymalnej wartości współrzędnej X i Y, a następnie na podstawie minimalnych i maksymalnych współrzędnych wyliczyć numery pól będących rogami prostokąta.

  1. oto PROST :kw
  2.   niech "ldX pierw naPunkt pierw :kw
  3.   niech "ldY ost naPunkt pierw :kw
  4.   niech "pgX :ldX
  5.   niech "pgY :ldY
  6.   powtórz ((długość :kw) - 1) [
  7.     niech "pkt naPunkt element (npw + 1) :kw
  8.     jeśli (pierw :pkt < :ldX) [
  9.       niech "ldX pierw :pkt
  10.     ]
  11.     jeśli (pierw :pkt > :pgX) [
  12.       niech "pgX pierw :pkt
  13.     ]
  14.     jeśli (ost :pkt < :ldY) [
  15.       niech "ldY ost :pkt
  16.     ]
  17.     jeśli (ost :pkt > :pgY) [
  18.       niech "pgY ost :pkt
  19.     ]
  20.   ]
  21.   wynik (lista naLiczbe (lista :ldX :ldY) naLiczbe (lista :pgX :pgY))
  22. już

(2. - 5.) Współrzędne :ldX, :ldY określają współrzędne lewego, dolnego rogu prostokąta, a :pgX, :pgY analogicznie prawego, górnego. (6.) Następnie dla każdego pola: (7. - 19.) porównywane są współrzędne z każdym punktem. Jeśli któraś współrzędna wymaga zmiany to jest ona dokonywana. Na koniec (21.) zwracane są numery pól na podstawie wyznaczonych współrzędnych.

Wykorzystane funkcje naPunkt i naLiczbe zostały wyjaśnione w zadaniu 2.

Zadanie 4

Zdefiniuj funkcję KODW :opis, która mając dany jakikolwiek opis wężowca, daje w wyniku jego kod.

Oto przykładowe wyniki:

KODW [48 50 51 68 71 88 91 108 111 128 131 148 149 150 151]
powinno dać wynik [48 68 88 108 128 148 149 150 151 131 111 91 71 51 50]
KODW [22]
powinno dać wynik [22]
KODW [22 3 42 41 23]
powinno dać wynik [3 23 22 42 41]

Wyznaczanie kodu

Zaprowadzenie porządku w opisie wężowca tak, aby powstał kod polega na wyznaczeniu początku wężowca, a następnie poukładaniu pozostałego opisu. Zgodnie z opisem stworzenia należy pamiętać, że każde dwa kolejne pola w kodzie wężowca muszą leżeć koło siebie na planszy.

Na początek należy znaleźć najmniejszy element na liście. Następnie wśród pozostałych liczb z opisu należy znaleźć sąsiada. Drugi krok jest powtarzany, aż opis będzie pusty. Algorytm ten zadziała, ponieważ którykolwiek z elementów końcowych może mieć tylko jednego sąsiada. Podczas dokładania będzie istniał dokładnie tylko jeden element, który jest sąsiadem pierwszego punktu. Dołożony punkt w pozostałym opisie będzie miał również tylko jednego sąsiada, ponieważ pierwszy został wyznaczony podczas dokładania.

  1. oto KODW :opis
  2.   niech "opis sortuj :opis
  3.   niech "w (lista pierw :opis)
  4.   niech "opis bezElnum 1 :opis
  5.   dopóki [długość :opis > 0][
  6.     niech "i 1
  7.     dopóki [nie czySasiad naPunkt ost :w naPunkt (element :i :opis)][
  8.       zwiększ "i
  9.     ]
  10.     niech "w nak element :i :opis :w
  11.     niech "opis bezElnum :i :opis
  12.   ]
  13.   wynik :w
  14. już

(2.) Posortuj dane. (3.) Na początku kodu posortuj dane, aby (4.) znaleźć najprostszą wartość. (5.) Po pobraniu elementu usuń go z listy. (6.) Dopóki są nieprzydzielone elementy w opisie to (7.) utwórz indeks :i i (8. - 10.) rozpocznij poszukiwania sąsiada do ostatniego punktu zapisanego w kodzie wynikowym :w. Po znalezieniu (11.) dopisz element do kodu i (12.) usuń z listy pierwotnej. (14.) Zwróć wynik.

Czy sąsiad?

Funkcja KODW nie może działać w pełni prawidłowo bez funkcji czySasiad. Jest to funkcja, która przyjmuje dwa argumenty, którymi są dwa punkty. Na początek (1. - 2.) wyliczana jest odległość punktów w osi X oraz osi Y, a następnie (3.) zwracane porównanie z 1.

  1. oto czySasiad :pkt1 :pkt2
  2.   niech "a abs((pierw :pkt1) - (pierw :pkt2))
  3.   niech "b abs((ost :pkt1) - (ost :pkt2))
  4.   wynik (:a + :b = 1)
  5. już

W celu wyjaśnienia, dlaczego powyższa funkcja działa sugeruje przeanalizować poniższą tabelkę. Rozpatrywane jest otoczenie punktu (0, 0):

y \ x-101
-1212
0101
1212