Programmare un incontro

[Gianfranco]

Two robots are to be parachuted onto random locations on an infinite line. When they land, their parachutes detach and remain where they are. The robots may be programmed from the following instruction set:

Go left one unit
Go right one unit
Skip next instruction unless there is a parachute here
Go to label
Each instruction takes one cycle to execute. Program the robots to collide.

Due robot stanno per essere paracadutati in due punti a caso su una retta (infinita).
Quando atterrano, i loro paracadute si staccano e rimangono nel punto di atterraggio.
I robot possono essere programmati con il seguente insieme di istruzioni (etichettate o numerate):

Vai a sinistra di una unità
Vai a destra di una unità
Salta la prossima istruzione a meno che lì non ci sia un paradute (nel punto dove si trova il robot)
Salta all'istruzione numero ... (oppure salta all'istruzione avente l'etichetta ...)

Ciascuna istruzione richiede un ciclo per essere eseguita.
Programmate i robot in modo da farli incontrare.

Chi non desidera scrivere un programma usando le istruzioni date, può descrivere una strategia con parole sue.

Tratto da Wu-riddles - Computer Science
http://www.ocf.berkeley.edu/~wwu/riddles/cs.shtml


Gianfranco

[Quelo]

Ecco una possibile soluzione:

1. Vai a sinistra di una unità
2. Vai a sinistra di una unità
3. Vai a destra di una unità
4. Salta la prossima istruzione a meno che lì non ci sia un paradute
5. Salta all'istruzione numero 7
6. Salta all'istruzione numero 1
7. Vai a sinistra di una unità
8. Salta all'istruzione numero 7

I robot sono programmati nello stesso modo e si muovono nella stessa direzione (sinistra) alla velocità di una unità ogni 5 cicli, quando uno dei robot trova il paracadute dell'altro accelera alla velocità di 1 unità ogni 2 cicli e raggiunge l'altro.

SE&O

[Quelo]

[Pasquale]

Si, complimenti a Quelo. In effetti non v'è altro modo: finché non si incontra un paracadute, i due robot procedono nella stessa direzione, alla stessa velocità, mantenendo fra loro la stessa distanza iniziale.
Quello che incontra il paracadute accelera, mentre l'altro continua a procedere alla stessa iniziale velocità.
Riporto di seguito una riscrittura del programma di Quelo con variazioni alle velocità dei robot:

01 ) vai a sinistra
02 ) salta la prossima istruzione, ammenocché non hai già raggiunto il paracadute con l'istruzione precedente
03 ) vai alla 5
04 ) vai alla 1
05 ) vai a sinistra
06 ) vai a sinistra
07 ) vai a sinistra
08 ) vai a sinistra
09 ) vai a sinistra
.
.
.
.
n) vai alla 5

[Gianfranco]

Quelo, complimenti, bella soluzione!

Pasquale, ho visto in questo momento anche la tua, mi sembra che funzioni, ma la devo ancora esaminare bene.

Mi stavo chiedendo se il problema si può risolvere anche se i robot non sanno dov'è la sinistra e dov'é la destra.
In effetti in questo programma "sinistra" e "destra" sono quelle di un osservatore esterno non quelle di un robot che si trova su una strada.
Cioè: i due robot atterrano su una retta, posano i paracadute, e possono scegliere di muoversi in un verso oppure nell'altro.
Si può programmarli in modo che si incontrino?
Oppure non si può?

Gianfranco Bo

[delfo52]

quello che non capisco è come fanno a liberarsi del paracadute....
devono lasciarlo sulla retta per consentire l'evolversi della situazione, ma quando atterrano si trovano "sotto" il paracadute, mentre quando uno dei due incontrerà quello del compagno dovrà passarci sopra (o no?)
e se uno dei due, tornando un poco indietro, incontra il proprio attrezzo ?

[Pasquale]

Secondo me è necessario che procedano nella stessa direzione, altrimenti l'incontro sarà casuale: se si spostano in direzioni opposte divergenti, non incontreranno mai un paracadute e non si incontreranno mai; se si spostano in direzioni opposte convergenti, è ovvio che si incontreranno, prima ancora di inciampare in un paracadute.
In conclusione, sinistra o destra che siano gli ordini, non importa; che i robot sappiano distinguere la sinistra dalla destra non ha importanza; importa solo che ad un certo comando prendano la stessa direzione e che al comando contrario prendano la direzione opposta.

[Admin]

Per far prendere ai due robot la stessa direzione, dal punto di vista di un osservatore esterno, vale il ragionamento di Quelo; ma dal punto di vista dei robot, tale algoritmo non vale;
e penso che le istruzioni "vai a sinistra di un'unità" e "vai a destra di un'unità" si rifereriscano al punto di vista del robot;
cioè se noi dobbiamo fisicamente programmare un robot per spostarsi verso sinistra di una unità, associamo l'istruzione "vai a sinistra di un'unità" con lo spostamento del robot di una unità sulla sua sinistra.
Per programmarlo in modo che si sposti verso la sinistra di un osservatore esterno, il robot dovrebbe sapere dove si trova l'osservatore esterno per poter capire quale sia la sua sinistra.

Il problema penso sia più complesso.

Ciao
Admin

[Admin]

In effetti, le istruzioni coincidono con le istruzioni possibili in una macchina di Turing;
per cui si tratta di capire se il problema sia risolvibile da una macchina di Turing.

Ciao
Admin

[Quelo]

i due robot atterrano su una retta, posano i paracadute, e possono scegliere di muoversi in un verso oppure nell'altro.
Si può programmarli in modo che si incontrino?
Oppure non si può?

Con la soluzione proposta in precedenza si ha comunque il 75% delle probabilità (solo nel caso in cui i robot prendono due direzioni divergenti non c'è l'incontro).

Se potessimo ampliare il set istruzioni cme segue:

Vai a sinistra di $n$ unità
Vai a destra di $n$ unità
Incrementa $n$ di una unità
Salta la prossima istruzione a meno che lì non ci sia un paradute (nel punto dove si trova il robot)
Salta all'istruzione numero ... (oppure salta all'istruzione avente l'etichetta ...)

potremmo usare il seguente programma:

ROBOT 1: nessuna programmazione

ROBOT 2:

1. Vai a sinistra di $n$ unità
2. Vai a destra di $n$ unità
3. Vai a destra di $n$ unità
4. Vai a sinistra di $n$ unità
5. Salta la prossima istruzione a meno che lì non ci sia un paradute
6. Incrementa $n$ di una unità
7. Salta all'istruzione numero 1

Il secondo robot si muove intorno al punto di atterraggio con oscillazioni sempre più ampie fino all'incontro con il primo robot (indipendentemente dal valore iniziale di $n$)

[Quelo]

[Gianfranco]

Quelo,
la stategia è buona ma l'implementazione dell'algoritmo potrebbe non funzionare.
Infatti in questo caso non serve testare la presenza del paracadute (mi sembra).
Inoltre è necessaria un'altra istruzione nel set: l'istruzione di assegnazione di una variabile.

Invece di usare i termini "destra", "sinistra" uso "verso+" e "verso-", intendendo i due versi opposti della retta.

1. Poni n = 1
2. Vai nel verso+ di n passi
3. Vai nel verso- di n passi
4. Vai nel verso- di n passi
5. Vai nel verso+ di n passi
6. Incrementa n di 1 unità
7. Salta all'istruzione n. 2

Enrico, hai chiesto:

a) quello che non capisco è come fanno a liberarsi del paracadute....
b) devono lasciarlo sulla retta per consentire l'evolversi della situazione, ma quando atterrano si trovano "sotto" il paracadute, mentre quando uno dei due c) incontrerà quello del compagno dovrà passarci sopra (o no?)
e se uno dei due, tornando un poco indietro, incontra il proprio attrezzo ?

a) non è rilevante ai fini dell'algoritmo
b) in questo modello "sopra" o "sotto" è la stessa cosa
c) qui ci sono vari problemi:
c1) SE ammettiamo che i paracadute cadano nello stesso posto in cui cadono i robot allora l'algoritmo di Quelo funziona.
c2) SE INVECE ammettiamo che i paracadute possano cadere anche in un altro punto lì vicino (come avviene normalmente ai paracadutisti reali) CAVOLO! qui sì che c'é un problema! Ci possono essere dei casi in cui entrambi i robot incontrano esattamente un paracadute e quindi aumentano ugualmente la propria velocità e perciò non si incontrano mai!
Ad esempio: (R = robot, p = paracadute)

<<<<-------------p1---R1-------------R2---p2-----------------<<<<

In questo caso R1 incontra p1 e R2 incontra p1.
c3) inoltre bisogna ammettere che le distanze iniziali di tutti gli oggetti fra di loro siano multiple del passo dei robot.

Pasquale, hai scritto:

che i robot sappiano distinguere la sinistra dalla destra non ha importanza; importa solo che ad un certo comando prendano la stessa direzione e che al comando contrario prendano la direzione opposta.

E' vero, ma per prendere la stessa direzione devono sapere qualcosa: o che hanno una bussola, o che sulla strada ci sono dei segni che indicano i due sensi.

Pietro, hai scritto:

e penso che le istruzioni "vai a sinistra di un'unità" e "vai a destra di un'unità" si rifereriscano al punto di vista del robot;

Beh, devo rifletterci...

Credo che questo problema dovrebbe essere riformulato meglio...
Forse, invece di "sinistra" e "destra", sarebbe meglio "avanti" e "indietro", anche se le cose non cambiano gran che.

Gianfranco

[Quelo]

Ciao Gianfranco,
per quanto riguarda il testare la presenza del paracadute hai ragione tu, non serve, però mi spiaceva risultasse inutilizzata...
L'istruzione di assegnazione di una variabile invece non è necessaria, perché il valore iniziale di n è irrilevante per il funzionamento dell'algoritmo, potrebbe essere 1, nessuno (0) o 100000. Lo stesso dicasi per l'incremento di n.
Infatti se la distanza tra i robot è inferiore al valore iniziale di n il programma sarà eseguito una sola volta, diversamente verrà eseguito più volte (in funzione del valore di incremento).

A questo punto, adottando l'algoritmo di Gianfranco, quali sono i valori di n e incremento di n che minimizzano il numero di passi se la distanza tra i due robot è di x passi ?

[vulneraria]

n = x ?

se i robot invece non sanno quale sia la destra e la sinistra temo sia impossibile da risolvere.

mi pare sia un problema posto da microsoft, percio' servira' per tutta altra cosa...mi chiedo cosa

ottimizzare quel programma per risparmiare cicli mi pare sia arduo.