Būvējam paši savu robotu!

Atminoties vecos labos studiju laikus, kad vajadzēja uztaisīt kādu pavisam triviālu programmiņu robotam, lai tas spētu atrast ceļu ārā no labirinta (uz šādām atmiņām mani uzvedināja laikraksta “Skaitļotājs” marta numurs), man radās iedvesma un es sacerēju pats savu uzdevumu. Tad nu lūkojiet, vai spējat tikt ar to galā!

 

Uzdevums vienā teikumā – uzrakstīt komandu virkni, pēc kuras vadoties robots-putekļu sūcējs spētu izsūkt putekļus istabā, apejot šķēršļus.

 

Precīzāks formulējums ir izlasāms tālāk. Dota taisnstūrveida istaba ar izmēriem m*n. Varam iedomāties to kā rūtiņu režģi. Divas rūtiņas sauc par blakusrūtiņām, ja tām ir kopīga mala. Uz dažām rūtiņu malām atrodas šķēršļi (visas malas garumā). Visa istaba ir ietverta sienās, kas arī ir šķēršļi. Piemēram, dotais rūtiņu režģis varētu izskatīties tāds kā šajā zīmējumā, kur treknākās līnijas apzīmē šķēršļus:

 

Telpas piemērs

 

Dots robots, kas pēc izmēra vienāds ar vienas rūtiņas izmēru un apveltīts ar zināmu atmiņu – tas spēj pie sevis noglabāt kopu S, kas sastāv no naturālu skaitļu pārīšiem (vienosimies, ka 0 ir naturāls skaitlis). Faktiski varētu iedomāties, ka robots spēj glabāt rūtiņu kopu, kur katra rūtiņa tiek identificēta ar tās x un y koordinātām (robežās, attiecīgi, 0..n-1 un 0..m-1).

 

Robots katrā laika momentā atrodas kādā no rūtiņām ar seju pret kādu no rūtiņas malām un spēj izpildīt septiņas dažādas komandas, kas tiek numurētas no 00 līdz 99. Pieņemot, ka ar `nn` tiek apzīmēts komandas numurs, komandas ir šādas:

1)     nnGo – pārvietoties uz blakusrūtiņu pāri tai malai, pret kuru robots atrodas ar seju. Ja šī mala marķēta kā šķērslis (trekninātās malas zīmējumā), robots tiek neglābjami sabojāts.

2)     nnTurn – pagriezties par 90 grādiem pretēji pulksteņa rādītāja virzienam.

3)     nnCan(YesNr,NoNr) – pārbaudīt, vai iespējams pāriet uz atbilstošo blakusrūtiņu. Ja tas iespējams (uz malas nav šķēršļu), pāriet pie komandas ar numuru YesNr, citādi pāriet pie komandas ar numuru NoNr.

4)     nnClean – izsūkt putekļus tajā rūtiņā, kurā robots atrodas.

5)     nnReset – iztīrīt robota atmiņu (piešķirt kopai S tukšu kopu).

6)     nnAdd – pievienot kopai S to rūtiņu, uz kuras atrodas robots. Rūtiņa tiek pievienota kā veselu skaitļu pāris (x,y), kur x – rūtiņas horizontālais kārtas numurs, bet y – rūtiņas vertikālais kārtas numurs. Ja šāds pārītis jau pieder kopai S, šai komandai nav nekāda efekta.

7)     nnBeen(YesNr,NoNr) – pārbaudīt, vai rūtiņa, uz kuras robots atrodas, ietilpst kopā S. Ja ietilpst, pāriet pie komandas ar numuru YesNr, citādi pāriet pie komandas ar numuru NoNr.

 

Zināms, ka šajā rūtiņu režģī iespējams no jebkuras rūtiņas nokļūt līdz jebkurai citai rūtiņai (neeksistē telpas apgabali, kas mazāki par pašu telpu un norobežoti no pārējās telpas ar šķēršļiem).

 

Ko tad īsti vajag izdarīt – panākt, lai robots, sākot darbu patvaļīgas telpas patvaļīgā rūtiņā ar patvaļīgu atmiņas stāvokli un izpildot pēc kārtas visas komandas, sākot ar pirmo, beigās (pēc visu komandu izpildes) būtu izsūcis putekļus visā telpā jeb, formālāk runājot, lai kopa S beigās būtu vienāda ar kopu {0..n-1} un {0..m-1} Dekarta reizinājumu (pieņemot, ka kopa tiek veidota ar semantiku – iekļaut pārīti kopā drīkst tikai tad, ja attiecīgā rūtiņa ir „izsūkta”). Robota atrašanās vieta istabā darba beigās nav svarīga.

 

Piemērs derīgai komandu virknei, kas liek robotam pāriet uz blakusrūtiņu, ja tas iespējams, bet atstāj robotu aktuālajā rūtiņā, ja uz šīs malas ir šķērslis:

00Can(01,02)

01Go

02Turn

 

Tas arī viss! Uzdevums pietiekami interesants – uzrakstīt komandu virkni, kuru izpildot robots izsūks putekļus visā istabā. Tā kā ķerieties nu pie lietas, nekas cits kā papīrs un pildspalva nav vajadzīgs. Jāteic, ka pats šobrīd esmu uzdevumu tikai izdomājis, bet risināt vēl sācis neesmu, tā kā, iespējams, kaut ko neesmu piefiksējis – varbūt robotam ar šīm komandām nepietiek, varbūt istabu ne vienmēr var izsūkt pilnībā, varbūt vēl kaut kas. Komentāros gaidīšu jūsu domas par šo visu (arī gatavās programmas).

 

Komandu saraksta papildinājums un risinājuma variants izlasāms šeit.