Logia 2009/10 - Etap III

Zadanie 1 (statki)

W grze w statki, każdy z graczy rysuje na swojej kartce mapę o wielkości 10 na 10 kwadratowych pól. Przed rozpoczęciem gry zaznacza na mapie jeden czteromasztowiec, dwa trójmasztowce, trzy dwumasztowce oraz cztery jednomasztowce. Liczba masztów statku określa, ile sąsiednich pól zajmuje on na mapie. Statki można ustawiać dowolnie, poziomo lub pionowo, nie wolno ich jednak wyginać. Różne statki nie mogą zajmować sąsiednich pól, ani stykać się rogami.

Napisz procedurę STATKI, po wywołaniu której na ekranie zostanie narysowana plansza do gry w statki, o boku długości 400, wraz z losowo (ale poprawnie) rozmieszczonymi statkami, widocznymi jako zamalowane pola.Poniżej przykładowy efekt wywołania procedury STATKI.

Strategia rozkładania

Jednym z najprostszych sposobów na rozkładanie jest ustawienie statków w kolejności od największego do najmniejszego. Pozwoli to na znalezienie rozwiązania niezależnie od pozycji ustawiania kolejnych statków. Wszystko to dzięki temu, że nie ma wtedy problemu, że małe statki mogą zablokować miejsce dla dużych statków, a z kolei dla mniejszych statków wielkości 1 pozycję jest bardzo łatwo znaleźć.

Rozwiązanie

Rozwiązywanie zadania można podzielić na dwa etapy. Pierszy z nich polega na znalezieniu mapy rozmieszczenia statków, a drugi to narysowanie na podstawie znalezionej mapy planszy. Rozpocznijmy od części kodu poszukującej rozwiązania:

1. oto STATKI
2.   niech "mapa []
3.   powtórz 10 [
4.     niech "wiersz []
5.     powtórz 10 [
6.       niech "wiersz nak 0 :wiersz
7.     ]
8.     niech "mapa nak :wiersz :mapa
9.   ]
10.   niech "statki [4 3 3 2 2 2 1 1 1 1]
11.   powtórz (długość :statki) [
12.     niech "el element npw :statki
13.     niech "pozx (losowa 10) + 1
14.     niech "pozy (losowa (10 - :el)) + 1
15.     niech "dopostawienia "prawda
16.     niech "o (losowa 2)
17.     niech "zx reszta :o 2
18.     niech "zy reszta (:o + 1) 2
19.     dopóki [:dopostawienia][
20.       jeżeli (STATKI_sprawdz :mapa :el :pozx :pozy :zx :zy) [
21.         niech "dopostawienia "fałsz
22.         niech "mapa STATKI_ustaw :mapa :el :pozx :pozy :zx :zy
23.       ][
24.         niech "pozx :pozx + 1
25.         jeśli (:pozx = 11) [
26.           niech "pozx 1
27.           niech "pozy :pozy + 1
28.         ]
29.         jeśli (:pozy = 11) [
30.           niech "pozy 1
31.         ]
32.       ]
33.     ]
34.   ]

Na początku działania programu należy (2. - 9.) utworzyć mapę. Jest to tablica dwuwymiarowa 10x10. Następnie (10.) deklarowane są statki do umieszczenia na planszy. Listę tę można zmodyfikować w dowolny sposób np. dodając pięciomasztowiec, ale należy się liczyć z faktem, że utworzona plansza może być za mała na ustawienie danego zestawu statków. (11.) Dla każdego statku: (12.) pobierana jest jego wartość i zapamiętana jako :el. Następnie losowana jest (13. - 14.) pozycja. (15.) Zmienna :dopostawienia jest to zmienna, która sprawdza czy statek wymaga ustawienia. (16.) Losowanie orientacji jest dokonywane poprzez wylosowanie wartości 0 lub 1. Na jej podstawie określa się (17. - 18.) orientację statku. Zakładamy, że na pozycji (x, y) ustawia się statek na kolejne pola w dół, albo na kolejne w prawo. Wylosowane wartości nie zawsze oznaczają, że wylosowana pozycja jest poprawna. Z tego powodu (19.) dopóki statek wymaga ustawienia to: (20.) należy sprawdzić daną pozycję i jeśli pasuje to (21.) zgłaszamy, że statek został ustawiony oraz (22.) ustawiamy statek na planszy. Jednak w przypadku, gdy pozycja jest niepoprawna to (24. - 31.) przehcodzimy po kolejnych polach mapy, aż do znalezienia odpowiedniej pozycji.

Sprawdzanie pozycji odbywa się poprzez funkcję STATKI_sprawdz, która przyjmuje kolejno :mapa - mapę planszy, :dl - długość statku, :pozx i :pozy - kolejno współrzednie "poczatku planszy" oraz przesunięcie jego kolejnych części o (:zx, :zy).

Działanie opiera się na sprawdzaniu (2.) dla każdego pola na którym ma stać statek czy (3. - 11.) nie będzie stykać się z innym statkiem lub nie wyjdzie poza planszę. Jeśli pole pasuje to (12. - 13.) modyfikujemy aktualne pole. Należy pamiętać, że (14. - 16.) możliwe jest wyjście poza mapę, więc należy upewnić się czy następne pole będzie poprawne. Ze względu na fakt, że kolejne części statku są dokładane do dołu i na prawo to wystarczy sprawdzić współrzędne :pozx i :pozy nie są większy od 10.

Analogicznie działającą funkcją jest ustawianie statku na planszy. Przyjmuje podobne argumenty, ale nie sprawdza poprawności ustawienia.

1. oto STATKI_ustaw :mapa :dl :pozx :pozy :zx :zy
2.   powtórz (:dl) [
3.     niech "wiersz element :pozy :mapa
4.     niech "wiersz zastąp :pozx :wiersz 1
5.     niech "mapa zastąp :pozy :mapa :wiersz
6.     niech "pozx :pozx + :zx
7.     niech "pozy :pozy + :zy
8.   ]
9.   wynik :mapa
10. już

Rysowanie planszy

W celu narysowania planszy wystarczy poniższy kod:

35.   niech "w 400
36.   niech "a :w/10
37.   pod
38.   ws :w/2 pw 90
39.   ws :w/2 lw 90
40.   opu
41.   powtórz 10 [
42.     niech "wiersz element (10 - npw + 1) :mapa
43.     powtórz 10 [
44.       niech "kolor "biały
45.       jeśli (element npw :wiersz = 1) [
46.         niech "kolor "zielony
47.       ]
48.       wielokąt [
49.         ukm :kolor
50.         powtórz 4 [
51.           np :a
52.           pw 90
53.         ]
54.       ]
55.       pod
56.       pw 90 np :a
57.       lw 90
58.       opu
59.     ]
60.     pod
61.     pw 90 ws :w
62.     lw 90 np :a
63.     opu
64.   ]
65. już

Strategia

Podczas rozwiązywania zadania należy pamiętać, że jeśli kostka ma u góry wartość x to od spodu ma wartość 7 - x czyli ze wszystkich możliwości ścian: [1 2 3 4 5 6] nie ma na niej x i 7 - x. Jeśli z posortowanej listy usunie się obydwie wartości to pierwszy element na liście będzie szukanym minimum dla danego rzutu monetą, a ostatni szukanym maksimum.

Rozwiązanie

Poniżej zostało zamieszczone pełne rozwiązanie zadania:

1. oto GRA :kość :moneta :limit
2.   niech "tura []
3.   niech "wyniki []
4.   powtórz (długość (pierw :moneta)) [
5.     niech "wyniki nak 0 :wyniki
6.     niech "tura nak 0 :tura
7.   ]
8.   powtórz (długość :moneta) [
9.     niech "numertury npw
10.     niech "el element npw :moneta
11.     powtórz (długość :el) [
12.       niech "lista [1 2 3 4 5 6]
13.       niech "lista be :kość :lista
14.       niech "lista be (7 - :kość) :lista
15.       jeżeli ((element npw :el) = "r) [
16.         niech "kość pierw :lista
17.       ][
18.         niech "kość ost :lista
19.       ]
20.       niech "punkty (element npw :wyniki) + :kość
21.       niech "wyniki zastąp npw :wyniki :punkty
22.       jeśli (I (:punkty >= :limit)
23.                         (element npw :tura = 0)) [
24.         niech "tura zastąp npw :tura :numertury
25.       ]
26.     ]
27.   ]
28.   wynik :tura
29. już

(2. - 7.) Na początku działania funkcji GRA należy utworzyć tablicę do przeszukiwania wyników dla kolejnych graczy. Następnie (8.) dla kolejnych rzutów monetą: (9.) zapamiętajemy numer tury i pobieramy kolejny element z listy :moneta. (10.) Dla każdego rzutu monetą: (11.) przygotowywujemy posortowaną tablicę wartości kości i (12. - 13.) usuwamy z niej dwie wartości. Potem (14. - 18.) na podstawie wylosowania reszki czy orła wybieramy odpowiedni element. (19. - 20.) Dodajemy go do wyniku odpowiedniego gracza oraz sprawdzamy (21. - 24.) czy dany gracz osiągnął ustalony :limit. Jednak nalezy pamiętać, że :limit raz osiągnięty będzie osiągnięty w kolejnych turach, więc należy upewnić się, że dany gracz już wcześniej nie osiągnął. Na koniec (27.) zwracamy listę :tura.

Rozwiązanie

Dla każdej linii należy pamiętać, aby znaleźć pozycję jednego i drugiego przystanku. Odległością będzie wartość absolutna różnicy pozycji tych przystanków (docelowy przystanek może być wcześniej od początkowego). Poniżej zostało przedstawione przykładowe rozwiązanie:

1. oto DROGA :linie :p1 :p2
2.   niech "min -1
3.   powtórz (długość :linie) [
4.     niech "el element npw :linie
5.     niech "trasa zd :el wspak bo :el
6.     niech "poz numel :p1 :trasa
7.     niech "trasa odElementu :p1 :trasa
8.     niech "poz2 numel :p2 :trasa
9.     jeśli (:poz <> 0) [
10.       niech "odl :poz2 - 1
11.       jeśli (LUB (:min = -1) (:odl < :min)) [
12.         niech "min :odl
13.       ]
14.     ]
15.   ]
16.   wynik :min
17. już

(2.) Początkowo przyjmujemy, że nie istnieje bezpośrednie połączanie. Nastepnie (3.) dla każde linii autobusowej: (4.) pobieramy kolejne trasy i (5. - 6.) szukamy pozycji przystanków na trasie. Warunkiem obliczenie odległości (7.) jest to, że oba przystanki na trasie występują. Jeśli tak to (8.) wyliczamy odległość pomiędzy przystankami i (9. - 11.) sprawdzamy czy jest to najkrótsze połączenie. Na koniec (14.) zwracamy wartość minimalną :min.

Strategia

Implementacja zadania jest bardzo podobna do zadania 3 z poprzedniego etapu. Wtedy należało sprawdzić, które punkty robot odwiedził dwa razy. Tu z kolei należy sprawdzić, które odcniki drogi odwiedzi dwa razy. Zadanie można rozwiązać przy pomocy tego samo szkieletu rozwiązania. Mianowicie tym razem zamiasy przechowywać kolejnych punktów należy przechować posortowaną listę złożoną z dwóch punktów: początkowego i końcowego. Posortowanie jest bardzo ważne, ponieważ inaczej przejście z (a, b) na (c, d) odróżniałby od przejścia (c, d) na (a, b).

Rozwiązanie

1. oto ROBOT :trasa
2.   niech "pozx 0
3.   niech "pozy 0
4.   niech "pozlista [[[0 0] [0 0]]]
5.   niech "ile 0
6.   powtórz (długość :trasa) [
7.     niech "el (element npw :trasa)
8.     niech "poz1 (lista :pozx :pozy)
9.     wybierz (:el) [
10.       N [niech "pozy :pozy + 1]
11.       E [niech "pozx :pozx - 1]
12.       W [niech "pozx :pozx + 1]
13.       S [niech "pozy :pozy - 1]
14.     ]
15.     niech "poz2 (lista :pozx :pozy)
16.     niech "poz sortuj (lista :poz1 :poz2)
17.     jeżeli (numel :poz :pozlista = 0) [
18.       niech "pozlista nak :poz :pozlista
19.     ][
20.       niech "ile :ile + 1
21.     ]
22.   ]
23.   wynik :ile
24. już

W rozwiązaniu kolejno: (2. - 3.) ustalana jest pozycja wejściowa oraz (4.) wykonany ruch i (5.) licznik do zliczania odcinków po których robot przeszedł dwa razy lub więcej. (6.) Dla każdego elementu trasy :trasa: (7.) pobiera kierunek kolejnego ruchu i (8.) utworzeniu listy reprezentujacej punkt początkowy. Nastepnie (9. - 14.) wykonywane jest przesunięcie w odpowiednim kierunku. Po przejściu można (15.) utworzyć kolejny punkt i (16.) utworzyć drogę przejścia robota złożoną z punktu początkowego i końcowego, posortowaną. (17.) Jeśli dane przejście nie wystąpiło to (18.) dopisujemy na listę, a jeśli wystąpiło to (20.) zwiększamy licznik :ile. Na koniec (23.) zwracamy licznik :ile.

• Rozwiązania zadań