Je travaille dans une boulangerie qui sert du blé, du seigle, de l'orge, des céréales et du pain français, mais le boulanger est un peu bizarre - il empile les pains dans un ordre aléatoire et laisse parfois quelques étagères à la fin vides.

Chaque jour, le même client entre et demande une de chaque miche de pain, mais la chose délicate est qu'il est un germophobe, donc quand je remplis son sac, je ne peux pas prendre des pains de deux étagères adjacentes dans des sélections consécutives.

Il faut une seconde pour marcher entre les étagères adjacentes. C'est un magasin très fréquenté; pour toute configuration aléatoire de pains, je voudrais minimiser le temps nécessaire pour obtenir un de chaque pain unique. Je peux commencer et terminer sur n'importe quelle étagère.

Si la commande d'aujourd'hui est W B W G F R W, un chemin possible est 0, 3, 5, 1, 4, pour un total de 12 secondes:abs(3-0) + abs(5-3) + abs(1-5) + abs(4-1) = 12

( 1, 2, 3, 4, 5ne fonctionne pas, car le pain est prélevé consécutivement sur les étagères adjacentes.)

Si c'est le cas B W B G B F B R B W B F, un chemin possible est 1, 3, 5, 7, 10, pour un total de 9 secondes.

Le gestionnaire s'assure toujours qu'il existe une solution possible, donc je n'ai pas besoin de m'inquiéter d'attraper de mauvaises entrées. Il m'envoie généralement la commande dans un fichier, mais si je veux, je peux le taper sur STDIN ou le lire d'une manière différente. J'aimerais que le programme imprime les index du meilleur chemin, ainsi que son heure, selon les règles d'E / S par défaut .

En bref:

1. 5 sortes de pain.
2. Les commandes de pain apparaissent sous la forme de chaînes d'ordre et de longueur aléatoires.
3. Vous devez sélectionner un de chaque pain unique.
4. Impossible d'effectuer des sélections consécutives adjacentes.
5. Minimisez la distance entre les indices de sélection.
6. Ne vous inquiétez pas des entrées invalides.
7. Les règles d'E / S par défaut s'appliquent.

C'est le golf par code , le nombre d'octets le plus court gagne.

JavaScript (ES6), 114 octets

1 octet enregistré grâce à @Oliver

Prend l'entrée comme un tableau de caractères. Génère une chaîne séparée par des virgules où la première valeur est la durée totale et les suivantes décrivent le chemin.

a=>(b=g=(r,s=o='',c,p)=>s[c>b|4]?o=(b=c)+r:a.map((v,i)=>s.match(v)||(d=p<i?i-p:p-i)<2||g([r,i],s+v,~~c+d,i))&&o)``

Essayez-le en ligne!

Commenté

a => (                          // a[] = input array
  b =                           // b = best score so far (initially a non-numeric value)
  g = (                         // g = recursive function taking:
    r,                          //   r = path
    s =                         //   s = string of collected loaves of bread
    o = '',                     //   o = final output
    c,                          //   c = current cost
    p                           //   p = index of the last visited shelf 
  ) =>                          //
    s[c > b                     // if the final cost is not greater than our best score
            | 4] ?              // and we've successfully collected 5 loaves of bread:
      o = (b = c) + r           //   update the current output and the best score
    :                           // else:
      a.map((v, i) =>           //   for each loaf of bread v at shelf i in a[]:
        s.match(v) ||           //     if we've already collected this kind of bread
        (d =                    //     or the distance d
          p < i ? i - p : p - i //     defined as the absolute value of p - i
        ) < 2 ||                //     is less than 2: stop recursion
        g(                      //     otherwise, do a recursive call to g() with:
          [r, i],               //       r updated with the index of the current shelf
          s + v,                //       s updated with the current loaf of bread
          ~~c + d,              //       c updated with the last distance
          i                     //       i as the index of the last shelf
        )                       //     end of recursive call
      )                         //   end of map()
      && o                      //   return the current output
  )``                           // initial call to g() with r = [""]

Python 2 , 212 210 octets

lambda s:min((sum(h(p)),p)for b in combinations(range(len(s)),5)for p in permutations(b)if(len(set(s[i]for i in p))==5)&all(d>1for d in h(p)))
h=lambda p:[abs(y-x)for x,y in zip(p,p[1:])]
from itertools import*

Essayez-le en ligne!

2 octets de thx à Jonathan Frech .