Internetbureau Rotterdam 
Dit bericht is geplaatst op zaterdag 14 juni 2008 om 13:16 in categorieën Puzzels. Je kunt de reacties volgen via een RSS 2.0 feed. Je kunt een reactie plaatsen, of een trackback van je eigen site plaatsen.
Wiskundemeisjes
Ionica & Jeanine
Robot puzzel
In Puzzels, door Ionica
Het is weer eens tijd voor een fijne puzzel!
Twee robots worden met parachutes gedropt op een lange lijn. De robots laten hun parachute liggen op de plek waar ze landen en kennen maar vier verschillende instructies. Jij moet de robots zo programmeren dat ze elkaar op den duur tegenkomen. Allebei de robots krijgen hetzelfde programma en gaan dat tegelijk uitvoeren. Dit zijn de instructies die de robots kennen:
- Doe een stap naar links.
- Doe een stap naar rechts.
- Ga naar regel [nummer].
- Als je op een parachute staat, doe dan [één van de andere drie instructies].
Een voorbeeld van een programma is
- Doe een stap naar links.
- Ga naar regel 1.
Alleen is dit niet zo'n handig programma, omdat de robots hiermee elkaar niet gaan tegenkomen. Met wat voor programma lukt dat wél? De robotjes landen trouwens precies een geheel aantal stappen van elkaar en het programma moet uit een eindig aantal stappen bestaan.
De echte liefhebbers kunnen zich ook afvragen wat er gebeurt als de robotjes landen op een cirkel in plaats van een lijn...
zaterdag 14 juni 2008 om 14:12
Wat gebeurt er als je programma 'Als je op een parachute staat, ...' wilt uitvoeren maar je staat niet op een parachute? Gaat je programma dan gewoon voort met de volgende lijn code?
zaterdag 14 juni 2008 om 14:20
Dit doet me heel erg denken aan het spel Robocom (http://cyty.com/robocom, maar deze lijkt niet te meer te werken). Een hele leuke 'puzzel' hierover staat op http://www.liacs.nl/home/kosters/AI/robot.html (hier moet je een vlag maken met 'identieke' robots, het is niet heel makkelijk om het werkend te maken).
zaterdag 14 juni 2008 om 14:41
1 Doe een stap naar rechts.
2 Doe een stap naar links.
3 Doe een stap naar rechts.
4 Als je op een parachute staat, Ga naar regel 2
5 Ga naar regel 1
zaterdag 14 juni 2008 om 14:48
Mijn oplossing hierboven is voor de cirkel ...
zaterdag 14 juni 2008 om 14:55
Ik weet niet zeker of dit voldoet aan de gestelde eisen, omdat ik niet weet of de robots elkaar ook mogen tegenkomen terwijl ze allebei een stap aan het doen zijn (in plaats van dat ze allebei een stap eindigen op dezelfde plek).
1. Doe een stap naar links.
2. Doe een stap naar links.
3. Doe een stap naar rechts.
4. Als je op een parachute staat, doe dan Ga naar regel 6..
5. Ga naar regel 1.
6. Doe een stap naar links.
7. Ga naar regel 6.
Het idee is: De robots gaan allebei langzaam naar links lopen (door steeds twee stappen naar links te doen en één stap naar rechts).
Zodra een robot (de meest linkse, moet wel) een parachute tegenkomt (dat kan niet haar eigen zijn, want daar is ze al voorbij) stopt ze hiermee en gaat ze twee keer zo snel (namelijk alleen maar naar links) lopen, dan haalt ze de andere robot dus in.
Als ze allebei op eenzelfde plek moeten uitkomen na een aantal stappen, is het iets ingewikkelder. Maar het is me nu dus onduidelijk of dat ook een eis is.
zaterdag 14 juni 2008 om 15:29
koen, volgens mij eindigen beide robots op de parachute van de ander, en daar gaan ze heen en weer lopen. Dus ze komen elkaar niet tegen op de cirkel.
zaterdag 14 juni 2008 om 18:43
volgens mij staan ze maar 1 keer op de parachute, dus haalt de buitenste de andere maar 1 stap in. Voorbeeld wat dan wel kan:
1. doe een stap naar links
2. Als je op een parachute staat, ga dan naar regel 4
3. doe een stap naar rechts
4. doe een stap naar links
5. doe een stap naar rechts
6. doe een stap naar links
7. ga naar regel 1
8. doe een stap naar links
9. doe een stap naar links
10. doe een stap naar links
11. doe een stap naar links
12. ga naar regel 8
zaterdag 14 juni 2008 om 18:44
Dit is ook al door 4 gezegd, laat dus maar.
zondag 15 juni 2008 om 22:00
@Alexander: volgens mij klopt jouw programma, als de rechter robot een even aantal stappen verder staat. Als de rechter robot een oneven aantal stappen verder staat, dan botsen ze en komen ze niet op dezelfde plek. Maar ja... botsen is ook tegenkomen ;-)
zondag 15 juni 2008 om 22:33
1. doe een stap naar links
2. Als je op een parachute staat, Ga naar regel 4
3. ga naar regel 1
4. doe een stap naar links
5. doe een stap naar links
6. ga naar regel 4
Dit garandeert dat de rechter robot op een gegeven moment samen met de linker robot op één plek staat.
zondag 15 juni 2008 om 22:38
Regel 5 kan ook nog weg en dan vervangen worden door regel 6.
maandag 16 juni 2008 om 01:33
De meisjes weten het misschien niet, maar het 'programmeren' van robotjes die de weg moeten vinden is een hele wetenschap. Stel je hebt een labyrint dat doorzocht moet worden, hoe slim moet de robot zijn? Hoeveel geheugen moet de robot hebben? Wat als we meerdere robots op pad sturen die met elkaar communiceren? Voor een doolhof met een rooster als grondplan (zeg schaakbord met heggen) lieten Blum en Kozen zien dat de robot uitgerust kan worden met een tellertje of met twee kiezels (om plekken te markeren). Met een enkele kiezel schijnt het niet te lukken.
Puzzel gerust verder.
maandag 16 juni 2008 om 11:13
Here is another nice robot navigation puzzle:
It is midnight, and you are standing in front of the Chinese Wall. Somewhere to the left or somewhere to the right of you there is a gate in the wall. You have checked your immediate neighborhood, and you know that the gate is at least 1 meter to the right or at least 1 meter to the left.
You walk along the wall, and keep checking it with your hands. Since it is pitch-dark, you will not see the gate before you hit it. Of course, searching just the right hand side might be a bad idea (if the door is 10m to the left), and also only searching the left hand side is a bad idea (if the door is 10m to the right).
What is the optimal worst-case strategy for this problem?
(Meaning of optimal: Minimize the worst-case ratio between the distance walked by you and the straightline distance from your starting point to the gate.)
maandag 16 juni 2008 om 14:12
Prachtige puzzel, maar mag ik jullie toch ook even op http://www.spatiegebruik.nl wijzen? :)
maandag 16 juni 2008 om 20:57
nee...
nu terug naar de puzzel.
woensdag 18 juni 2008 om 10:11
Voor de cirkel: Als de cirkel een even aantal stappen rond is, en de robots precies tegenover elkaar landen kun je niet ervoor zorgen dat de robots elkaar tegenkomen. Met inductie kun je namelijk bewijzen dat ze altijd een halve cirkel van elkaar vandaan staan, omdat het daar er precies zo uit ziet als aan de overkant doen ze dan hetzelfde.
In andere gevallen werkt het volgende algoritme:
Loop snel naar links totdat je een parachute tegenkomt (i.e. die van de andere robot), loop daarna langzaam naar links totdat je weer een parachute (nu de eigen parachute) tegenkomt en herhaal.
Aangezien de twee afstanden tussen de parachutes bij aanname verschillen zal de ene robot sneller door het rondje gaan dan de andere en haalt hij die andere dus in.
Bij dit algoritme doet het er eigenlijk niet toe of je begint met snel of langzaam te lopen, maar het leuke is dat het algoritme zoals nu opgeschreven, zowel op een cirkel als op een lijn werkt.
woensdag 18 juni 2008 om 10:54
Mooi beredeneerd. Alleen denk ik dat je op een lijn moet beginnen met langzaam lopen, anders wordt de afstand alleen maar groter (=reactie 5).
Op een cirkel kun je ze ook (met constante snelheid) tussen de parachutes heen en weer laten lopen, mits ze niet tegenover elkaar staan komen ze elkaar dan uiteindelijk tegen, toch? Je kunt dan met minder regels toe, en dat vind ik ook wel weer elegant:
1. stap links
2. als parachute ga naar 4
3. ga naar 1
4. stap rechts
5. als parachute ga naar 1
6. ga naar 4
Of zie ik iets over het hoofd?
woensdag 18 juni 2008 om 11:40
ze lopen nu ieder langs een kant tussen de parachutes heen en weer, en ze kunnen elkaar alleen tegenkomen wanneer ze op een parachute staan.
woensdag 18 juni 2008 om 12:27
Klopt, maar er komt altijd een moment dat ze precies tegelijk bij de dezelfde parachute uitkomen. Toch?
woensdag 18 juni 2008 om 14:10
Laten we in het cirkel geval de afstanden tussen de parachutes l en k noemen. In Wim's algoritme bereiken de robots elkaar alleen als een robot een even aantal keer zijn stuk heeft afgelegd en de andere robot een oneven aantal keer zijn stuk. Ofwel als er een oplossing is van l p = k q voor p even en q oneven, of p oneven en q even. Als echter l en k beide oneven zijn is dit onmogelijk. Meer algemeen kan het niet als l en k evenveel factoren 2 bevatten.
woensdag 18 juni 2008 om 21:45
[...] vond een leuke programmeerpuzzel op wiskundemeisjes.nl: http://www.wiskundemeisjes.nl/20080614/robot-puzzel. Wellicht te gebruiken als introductie op het hoofdstuk [...]
dinsdag 28 oktober 2008 om 11:47
als ze in een rechte lijn staan kan je dat niet dit doen:
als op parachut dan naar rechts
doe een stap naar links
en dit zovaak herhalen tot ze bij elkaar zijn?
dinsdag 10 februari 2009 om 11:54
erg leuk raadsel, kijk voor onze raadsels eens op http://www.raadsels.net