Movimento di un robot

O.I.I.

O.P.S.

OII 30-11-2012 – Numero 13

Il pirata Barbagianni trova un’antica mappa che spiega come raggiungere un favoloso tesoro.
La mappa ha la forma di una matrice di celle; le celle possono essere vuote, contenere ostacoli che impediscono a Barbagianni di attraversarle (le bandiere della Corona inglese), oppure premi (costituiti da un certo numero di monete d’oro); una cella contiene il tesoro.

Trovare il numero N di percorsi diversi disponibili a Barbagialla per raggiungere il tesoro, e il numero massimo MAX e il numero minimo MIN di ghinee d’oro che Barbagialla potrà raccogliere percorrendo questi percorsi.

SOLUZIONE

Osserva tutti i percorsi

Soluzione: N = 5, SMAX = 50, SMIN = 29

OII 21-11-2013 – Numero 17

Un campo di gara per robot ha la forma di un foglio a quadretti o celle; le celle possono contenere ostacoli che impediscono al robot di attraversarle, oppure dei premi; una cella contiene un tesoro.

Con riferimento alla figura, il robot (indicato con una sagoma umana) si trova nella cella individuata dalle coordinate di riga e di colonna (1,1).
Il tesoro, rappresentato da una coppa, è nella cella (8,8).
Il campo contiene ostacoli, individuati da quadrati neri posti in 13 celle.
Altre celle contengono dei premi: ad esempio 8 nella cella di coordinate (4,2) e 10 nella cella (6,4).
Il robot può spostarsi di una cella verso destra o verso l’alto, cioè ad ogni passo solo una delle sue coordinate può aumentare di una unità.

Trovare il numero N di percorsi diversi disponibili al robot per raggiungere il tesoro, la somma massima SMAX e la somma minima SMIN di premi raccoglibili percorrendo questi percorsi.

SOLUZIONE

Osserva tutti i percorsi

Soluzione: N = 5, SMAX = 50, SMIN = 29

OII 2017 – Numero 15

Con riferimento alla figura, il pirata Barbagianni si trova nella cella individuata dalle coordinate (1,1), il tesoro, rappresentato da un forziere, è nella cella (6,6), gli ostacoli, rappresentati dalle bandiere, si trovano, ad esempio in posizione (6,4) e (3,4).
Barbagianni può spostarsi solo di una cella verso destra o verso l’alto, cioè ad ogni passo solo una delle sue coordinate può aumentare di una unità.
Trovare il numero N di percorsi diversi disponibili a Barbagianni per raggiungere il tesoro, e il numero massimo MAX e il numero minimo MIN di monete d’oro che Barbagianni potrà raccogliere percorrendo questi percorsi.

SOLUZIONE

…

OII 21-11-2021 – Numero 20

Il pirata Barbagialla trova un’antica mappa che spiega come raggiungere un favoloso tesoro.
La mappa ha la forma di una matrice di celle; le celle possono essere vuote, contenere ostacoli che impediscono a Barbagialla di attraversarle, oppure premi (costituiti da un certo numero di ghinee d’oro); una cella contiene il tesoro.

Con riferimento alla figura, il pirata Barbagialla (la sagoma umana) si trova nella cella individuata dalle coordinate (1,1).
Il tesoro, rappresentato da una coppa, è nella cella (8,8); il campo contiene ostacoli, individuati da quadrati neri posti in 13 celle.
Nove celle contengono dei premi: ad esempio 8 ghinee d’oro nella cella di coordinate (4,2) e 13 nella cella (6,4).
Barbagialla però può spostarsi solo di una cella verso destra o verso l’alto, cioè ad ogni passo solo una delle sue coordinate può aumentare di una unità.
Esistono diversi percorsi disponibili per Barbagialla per raggiungere il tesoro; siano, rispettivamente, MAX il numero massimo e MIN il numero minimo di ghinee d’oro che Barbagialla potrà raccogliere percorrendo questi percorsi.

Quanto vale MAX+MIN?

SOLUZIONE

Osserva tutti i percorsi

Premi corrispondenti raccolti: 55, 50, 30, 29, 31

Soluzione:

MAX = 55
MIN = 29
MAX+MIN = 84

OPS e Movimento di un robot

In un foglio a quadretti è disegnato un “campo di gara”, per esempio di 14 quadretti in orizzontale e 5 in verticale (vedi figura).

Ogni casella può essere individuata da due numeri (interi); per esempio la casella contenente P è individuata da essere nella sesta colonna (da sinistra) e nella terza riga (dal basso): brevemente si dice che ha coordinate [6, 3]; la prima coordinata (in questo caso 6) si dice ascissa e la seconda (in questo caso 3) si dice ordinata. Le coordinate della casella contenente S sono [10, 4] e di quella contenente la freccia sono [1, 1].
La freccia può essere pensata come un robot, in questo caso rivolto verso destra; lo stato del robot può quindi essere individuato da tre “valori”: due per le coordinate della casella che occupa e uno per indicare il suo orientamento.
Per quest’ultimo si possono usare i simboli della stella dei venti: E, S, W, N: per indicare che il robot è rivolto, rispettivamente, a destra, in basso, a sinistra, in alto (con riferimento a chi guarda il foglio); lo stato del robot, rappresentato dalla freccia nella figura è [1, 1, E].

Il robot può eseguire tre tipi di comandi:

girarsi di 90 gradi in senso orario: comando o;
girarsi di 90 gradi in senso antiorario: comando a;
avanzare di una casella (nel senso della freccia, mantenendo l’orientamento): comando f.

Questi comandi possono essere concatenati in sequenze in modo da permettere al robot di compiere vari percorsi; per esempio la sequenza di comandi descritta dalla lista [f, f, f, f, f, a, f, f] fa spostare il robot dalla posizione e orientamento iniziali mostrati in figura fino alla casella P; le caselle via via occupate (quella di partenza e quella di arrivo comprese) sono quelle della lista:

[[1, 1], [2, 1], [3, 1], [4, 1], [5, 1], [6, 1], [6, 2], [6, 3]].

Stessa casella di arrivo si raggiunge con la lista di comandi [a, f, f, o, f, f, f, f, f], ma il percorso è diverso ed è descritto dalla lista

[[1, 1], [1, 2], [1, 3], [2, 3], [3, 3], [4, 3], [5, 3], [6, 3]].

Inoltre, nel primo caso l’orientamento finale del robot è verso l’alto (stato [6, 3, N]), mentre nel secondo caso l’orientamento finale è verso destra (stato [6, 3, E]).

In un foglio a quadretti è disegnato un campo di gara, per esempio di dimensioni 14×5 (cioè 14 quadretti in orizzontale e 5 in verticale, vedi figura).
Ogni casella può essere individuata da due numeri (interi); per esempio la casella contenente la lettera P è individuata spostandosi di cinque colonne da sinistra e di tre righe dal basso: brevemente si dice che ha coordinate [5, 3]; la prima coordinata (in questo caso 5) si dice ascissa e la seconda (in questo caso 3) si dice ordinata.
Le coordinate della casella contenente la lettera S sono [10, 4] e di quella contenente il robot sono [1, 1].

Il campo di gara può contenere caselle, segnate da un quadrato nero nella prima figura, interdette al robot: cioè il robot non può essere collocato in quelle caselle (che quindi si comportano come se fossero occupate da un pezzo dello stesso colore del cavallo, nel gioco degli scacchi); quindi, tenuto conto anche dei bordi del campo di gara, la mobilità del robot può essere limitata; ad esempio se il robot si trovasse nella casella in cui c’è Q si potrebbe spostare solo in 3 caselle: non può andare in [5, 4] perché è interdetta; se fosse nella casella in cui c’è P avrebbe 7 mosse possibili; dalla casella [1, 1] ha solo 2 mosse possibili: in [2, 3] e in [3, 2].

In alcuni casi il robot può spostarsi solo in una delle caselle contenenti il cavallo come illustrato nella seguente figura (allo stesso modo del cavallo nel gioco degli scacchi).

Un percorso è descritto dalla lista delle coordinate delle caselle attraversate; un possibile percorso da P (coordinate [5, 3]) a Q (coordinate [3, 5]) è descritto dalla lista

[[5, 3], [3, 2], [5, 1], [4, 3], [3, 5]].

In alcune caselle sono posti dei premi che il robot può raccogliere lungo un percorso.
Ogni premio è descritto fornendo le coordinate della casella che lo contiene e il valore del premio: i premi riportati nella prima figura sono descritti dalla seguente lista

[[3, 2, 3], [4, 3, 7], [3, 4, 5]].

Nel percorso da P a Q, sopra descritto, il totale di premi raccolti è pari a 10.

ESERCIZIO 1

In un campo di gara, sufficientemente ampio, il robot (come descritto nella prima parte della premessa) è nella casella [8,8] con orientamento verso l’alto; deve eseguire il percorso descritto dalla seguente lista di comandi:

[f, f, o, f, f, a, f, f, f, o, f].

Trovare l’ascissa X e l’ordinata Y della casella in cui finisce il percorso del robot.

SOLUZIONE

Dopo l’esecuzione della lista dei comandi

Risposte

X = 11
Y = 13

ESERCIZIO 2

In un campo di gara il robot (come descritto nella prima parte della premessa) è nella casella [9, 9] con orientamento verso sinistra: trovare la lista L dei comandi da assegnare al robot per fargli compiere il percorso descritto dalla seguente lista di caselle:

[[9, 9], [8, 9], [7, 9], [6, 9], [6, 8], [6, 7], [6, 6], [6, 5]].

SOLUZIONE

Dopo l’esecuzione della lista dei comandi

Risposta: L = [f, f, f, a, f, f, f, f]

ESERCIZIO 3

Un campo di gara (come descritto nella seconda parte della premessa) ha dimensioni 5×5

le caselle interdette descritte dalla seguente lista:
[[1, 2], [1, 3], [1, 4], [2, 4], [3, 4], [4, 1], [4, 2], [4, 4], [4, 5], [5, 4]];
i premi, invece, sono descritti dalla seguente lista:
[[3, 1, 10], [2, 2, 12], [2, 3, 13]].

Al robot sono vietati i movimenti corrispondenti alle direzioni della rosa dei venti indicate nella seguente lista [oso, nno, ene], cioè le mosse del robot in questo problema si riducono a quelle illustrate (col cavallo) nella seguente figura.

Partendo dalla casella [1, 1], il robot deve raggiungere la casella [5, 5], senza passare più di una volta per una stessa casella.

Trovare:

il percorso L1 in cui si raccoglie il massimo di premi;
il percorso L2 in cui si raccoglie il minimo di premi;
il numero N di percorsi possibili da [1, 1] a [5, 5].

SOLUZIONE

Il campo di gara

e i percorsi possibili

Risposte

L1 = [[1,1], [2,3], [3,1], [4,3], [5,5]]
Premio = 23
L2 = [[1,1], [2,3], [3,5], [4,3], [5,5]]
Premio=13
N = 2

ESERCIZIO 4

In un campo di dimensioni 8×8 un robot si muove come il cavallo nel giuoco degli scacchi; gli sono vietate, però, le mosse nelle direzioni della rosa dei venti comprese nella seguente lista [oso, sso, sse, ese], cioè le mosse del robot in questo problema si riducono a quelle illustrate (col simbolo ♘) nella seguente figura

Nel campo di gara le caselle della seguente lista sono interdette al robot:

[[3, 1], [4, 4], [4, 5], [4, 8], [5, 2], [5, 3], [7, 4], [7, 5]].

N.B. Un elemento della lista descrive una casella indicandone le coordinate a partire dallo spigolo in basso a sinistra del campo di gara.

Inoltre, in certe caselle sono presenti dei premi, descritti dalla seguente lista:

[[3, 2, 5], [1, 3, 6], [2, 5, 7], [4, 6, 8], [5, 5, 9]].

N.B. Un elemento della lista ha la forma:

[<ascissa>, <ordinata>, <premio>].

Partendo dalla casella [1,1], il robot deve raggiungere la casella [8,8], senza passare più di una volta per una stessa casella.

Trovare:

la lista L1 del percorso in cui si raccoglie il minor numero di premi;
la lista L2 del percorso in cui si raccoglie il maggior numero di premi.

SOLUZIONE

Il campo di gara

e i percorsi possibili

con premi 20, 20, 19, 26.

Risposte

L1 = [[1, 1], [3, 2], [1, 3], [3, 4], [4, 6], [6, 7], [8, 8]]
Premio = 19
L2 = [[1, 1], [3, 2], [1, 3], [2, 5], [4, 6], [6, 7], [8, 8]]
Premio = 26

In un campo di gara il robot si trova nella casella (13,29) con direzione verso l’alto e deve eseguire la seguente lista di comandi [f,a,f,a,f,o,f,a,f,a,f,f,a,f,f,o].

Trovare le coordinate [X,Y] della casella in cui ha termine il percorso.

In un campo di gara il robot si trova nella casella [21,19) con direzione verso il basso e deve eseguire la
seguente lista di comandi [f,a,f,f,o,f,a,f,a,f,f,a,f,f,f,o].

Trovare le coordinate [X,Y] della casella in cui ha termine il percorso.

Il robot si trova nella casella [20,20] con direzione verso sinistra (ovest) e deve eseguire il seguente percorso [(20,20),(19,20),(18,20),(18,21),(19,21),(19,20),(19,19),(18,19)].

Trovare la lista L dei comandi da assegnare al robot.

Il robot si trova nella casella [20,20] con direzione verso destra (est) e deve eseguire la seguente lista di comandi [f,f,o,f,o,f,o,f,f,o,f,a,f,f,o,f,f].

Trovare le coordinate [X,Y] della casella in cui ha termine il percorso.