Wiskundemeisjes

Ionica & Jeanine
 
Slik Internetbureau Rotterdam Internetbureau Rotterdam



  • Laatste Reacties

Categorieën

Archief

Robot puzzel


In Puzzels, door Ionica

Het is weer eens tijd voor een fijne puzzel!

robotje

robotje

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

  1. Doe een stap naar links.
  2. 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...

23 reacties op “Robot puzzel”

  1. henk:

    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?

  2. Michiel Kosters:

    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).

  3. koen:

    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

  4. koen:

    Mijn oplossing hierboven is voor de cirkel ...

  5. Alexander van Hoorn:

    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.

  6. Jos:

    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.

  7. Tim:

    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

  8. Tim:

    Dit is ook al door 4 gezegd, laat dus maar.

  9. michel:

    @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 ;-)

  10. Ricardo:

    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.

  11. Ricardo:

    Regel 5 kan ook nog weg en dan vervangen worden door regel 6.

  12. HJ:

    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.

  13. Gerhard:

    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.)

  14. Bram:

    Prachtige puzzel, maar mag ik jullie toch ook even op http://www.spatiegebruik.nl wijzen? :)

  15. Tim:

    nee...
    nu terug naar de puzzel.

  16. Fokko:

    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.

  17. Wim:

    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?

  18. Tim:

    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.

  19. Wim:

    Klopt, maar er komt altijd een moment dat ze precies tegelijk bij de dezelfde parachute uitkomen. Toch?

  20. Fokko:

    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.

  21. Enigma Online Weblog » Blog Archive » Programmeerpuzzel:

    [...] vond een leuke programmeerpuzzel op wiskundemeisjes.nl: http://www.wiskundemeisjes.nl/20080614/robot-puzzel. Wellicht te gebruiken als introductie op het hoofdstuk [...]

  22. anja campmans:

    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?

  23. philippe:

    erg leuk raadsel, kijk voor onze raadsels eens op http://www.raadsels.net

Plaats een reactie


Je kunt LaTeX gebruiken in je reactie.
Gelieve antwoorden op puzzels tussen [SPOILER] en [/SPOILER] te plaatsen.