SW V : Programmation d'un sondbot

Le défi de Vader

Contrairement à une idée reçue, les sondbots de l'empire ne sont pas autonomes. Ces sondes d'exploration sont en fait programmées en utilisant 8 ordres distincts : N, S, E, O, n, s, e, o qui permettent de se déplacer au nord, au sud, à l'est ou à l'ouest, de 5km (NSEO) ou 3 km (nseo).

Ainsi, un sondbot programmé avec les ordres NsEeO se déplacera de 5 km au nord, puis 3 km au sud (il revient sur ses pas), puis 5km vers l'est, puis 3 km vers l'est, et enfin 5 km vers l'ouest.

Les ordres sont insérés dans le sondbot à l'aide de capsules. Pour programmer un sondbot, on insère donc des capsules de type N, S, E, O, n, s, e ou o dans l'ordre souhaité. Pour les soldats de l'empire, la difficulté est de savoir dans quel ordre insérer les capsules disponibles pour que les sondbots passent là où ils le souhaitent.

Imaginons que vous ne disposez que des 5 capsules suivantes pour programmer un sondbot :

  • une capsule N
  • deux capsules e
  • une capsule s
  • une capsule o

Le plan ci-dessous représente une planète quelconque, le point de départ du sondbot (rond bleu), et les points de passage qu'il doit visiter (carrés verts) :

Dans quel ordre ordonner les 5 capsules pour que tous les points de passage soient visités (et si ce n'est pas possible, comment en visiter le maximum) ? Pour cette exemple, la solution est assez simple, et même un stormtrooper de seconde zone la trouverait : oseNe, ce qui donne le périple suivant :

Vous êtes un stormtrooper de seconde zone.... et Vader vous a fait remettre un lot de capsules en ordonnant de programmer un sondbot pour qu'il visite la surface de Chandrilla. Vous disposez d'une carte de la zone habitée de Chandrilla, indiquant la position des différents villages et le seul point d'atterrissage possible pour le sondbot.

Voici la carte en question. Le nord est vers le haut, et l'ouest sur la gauche. Le point d'atterrissage du sondbot est matérialisé par le pixel blanc. Le passage d'un pixel au pixel voisin représente une distance de 250 m. Les différents villages sont les pixels verts :

Quelle est, dans l'ordre, la séquence de capsules à donner au sondbot pour qu'il visite un maximum de villages ? Vous ne pourrez pas les visiter tous, mais il faut en voir un maximum (sans quoi vous devinez sur qui Vader va passer ses nerfs...). Vous avez à votre disposition 15 capsules :

  • 1 capsules N
  • 3 capsules S
  • 1 capsules E
  • 2 capsules O
  • 2 capsules n
  • 2 capsules s
  • 1 capsules e
  • 3 capsules o

Notez qu'il est possible que le sondbot sorte de la carte durant son trajet. Peu importe que vous utilisiez toutes les capsules ou non. La seule chose qui importe est de visiter le maximum de villages. Donnez votre réponse sous la forme de la séquence des capsules à utiliser. Par exemple :

oseNe
Ce problème est tiré de c0d1ng UP 2018

Type de retour

une chaîne de caractères

Entrée du problème

Pas de donnée d'entrée

Formulaire de réponse

Vous devez être connecté pour pouvoir répondre aux défis

Tags : récursivité optimisation cup18