Zadania trzeciego etapu Mazowieckiego Konkursu Informatycznego dla gimnazjalistów LOGIA 02, Logo i algorytmy

Wędrówki pionka po nieskończonej siatce

Przyjmujemy - podobnie jak w zadaniach etapu 2 - że pionek mający postać żółwia porusza się po nieskończonej kwadratowej siatce punktów jak na poniższym rysunku.
Z dowolnego punktu siatki, w którym się aktualnie znajduje, może wykonać jeden z 8 ruchów:

ruch 1 - [2 1] o 2 oczka w górę i 1 w prawo,
ruch 2 - [1 2] o 1 oczko w górę i 2 w prawo,
ruch 3 - [-1 2] o 1 oczko w dół i 2 w prawo,
ruch 4 - [-2 1] o 2 oczka w dół i 1 w prawo,
ruch 5 - [-2 -1] o 2 oczka w dół i 1 w lewo,
ruch 6 - [-1 -2] o 1 oczko w dół i 2 w lewo,
ruch 7 - [1 -2] o 1 oczko w górę i 2 w lewo,
ruch 8 - [2 -1] o 2 oczka w górę i 1 w lewo.

Każdą drogę żółwia po siatce można zakodować w postaci liczby, w której występują wyłącznie cyfry od 1 do 8 - numery kolejnych ruchów. Na przykład: kodem drogi na rysunku przypominającego gwiazdę, zaczynającej się w punkcie start, jest liczba 1278563; kodem drogi na drugim rysunku, zaczynającej się w punkcie start, jest liczba 21456782.

Zakresem drogi nazywamy najmniejszy prostokątny wycinek siatki, o bokach w kierunku pionowym i poziomym, w którym leżą wszystkie punkty danej drogi. Zakresy te są widoczne na powyższych rysunkach.

Zadanie 1.

Zdefiniuj polecenie RYSDR :dr, którego skutkiem będzie utworzenie na środku ekranu możliwie dużego rysunku danej drogi, na tle jej zakresu z zaznaczonym za pomocą słowa start punktem początkowym.

Pionki na nieskończonej taśmie

Każdy układ skończonej liczby pionków na nieskończonej taśmie pól, jak na rysunku powyżej, można zapisać za pomocą liczby całkowitej nieujemnej nazywanej kodem dziesiętnym układu, utworzonej w następujący sposób:

najpierw dane ustawienie zapisujemy w  postaci słowa zerojedynkowego: cyfra 0 oznacza, że odpowiednie pole jest wolne, a cyfra 1, że stoi na nim pionek. Skrajne puste pola na lewo i prawo od układu pionków pomijamy.
Zerojedynkowym zapisem układu pionków na rysunkach a, b i c są odpowiednio słowa: 11111, 11111010011101111 oraz 11011011.
Następnie każde słowo zerojedynkowe traktujemy jako dwójkowy zapis liczb i tłumaczymy na zapis dziesiętny.

Układy na rysunkach a, b i c mają następujące kody dziesiętne: 31, 128239 oraz 219.

Zadanie 2.

Zdefiniuj funkcję DŁMP :kd (długość maksymalnego łańcucha pionków), która mając dany kod dziesiętny układu pionków daje w wyniku długość maksymalnego łańcucha pionków, tzn. nieprzerwanej sekwencji pionków, w tym układzie.

Oto przykładowe wyniki:

DŁMP 31 powinno dać wynik 5,
DŁMP 128239 powinno dać wynik 5,
DŁMP 219 powinno dać wynik 2.

Zadanie 3.

Wolno nam dostawić 1 pionek w dowolnym pustym polu na taśmie. Musimy go wstawić tak, aby utworzyć możliwie najdłuższy łańcuch pionków. Zdefiniuj funkcję PLOMBA :kd, która daje w wyniku kod nowego ustawienia, jakie można utworzyć z danego ustawienia przez dodanie 1 pionka, w taki sposób, aby otrzymać maksymalnie długi łańcuch pionków.
W przypadku jeśli takie nowe ustawienie o maksymalnym łańcuchu pionków można otrzymać na wiele sposobów, wynikiem funkcji powinien być kod ustawienia, reprezentowanego przez najmniejszą liczbę.

Oto przykładowe wyniki:

PLOMBA 31 powinno dać wynik 63,
PLOMBA 128239 powinno dać wynik 128255,
PLOMBA 219 powinno dać wynik 223.

Zadanie 4.

Układ pionków na taśmie można też zakodować w postaci listy liczb całkowitych. Możemy przyjąć, że każdy łańcuch pionków na taśmie będzie reprezentowany przez jego długość, a każda sekwencja pustych pól przez liczbę przeciwną do jej długości. W tym systemie kodem układu 11101001111 będzie lista [3 -1 1 -2 4].
Zdefiniuj funkcję KL :kd która dla danego kodu dziesiętnego układu daje w wyniku jego kod listowy.

KL 31 powinno dać wynik [5],
KL 128239 powinno dać wynik [5 -1 1 -2 3 -1 4],
KL 219 powinno dać wynik [2 -1 2 -1 2].