Trabajo en una panadería que sirve trigo, centeno, cebada, grano y pan francés, pero el panadero es un poco extraño: apila los panes en orden aleatorio y, a veces, deja algunos estantes vacíos al final.

Cada día, el mismo cliente entra y pide una de cada barra de pan, pero lo complicado es que es un germófobo, por lo que cuando lleno su bolsa, no puedo tomar barras de dos estantes adyacentes en selecciones consecutivas.

Se tarda un segundo en caminar entre los estantes adyacentes. Es una tienda ocupada; para cualquier configuración aleatoria de panes, me gustaría minimizar el tiempo que lleva obtener uno de cada pan único. Puedo comenzar y terminar en cualquier estante.

Si el pedido de hoy es W B W G F R W, una posible ruta es 0, 3, 5, 1, 4, por un total de 12 segundos:abs(3-0) + abs(5-3) + abs(1-5) + abs(4-1) = 12

( 1, 2, 3, 4, 5no funciona, porque el pan se recoge consecutivamente de los estantes adyacentes).

Si es así B W B G B F B R B W B F, una posible ruta es 1, 3, 5, 7, 10, por un total de 9 segundos.

El gerente siempre se asegura de que haya una solución posible, por lo que no tengo que preocuparme por detectar entradas malas. Por lo general, me envía el pedido en un archivo, pero si lo deseo, puedo escribirlo en STDIN o leerlo de otra manera. Me gustaría que el programa imprima los índices de la mejor ruta, así como su tiempo, de acuerdo con las reglas de E / S predeterminadas .

En breve:

1. 5 tipos de pan.
2. Las órdenes de pan aparecen como cadenas de orden y longitud aleatorios.
3. Debe seleccionar uno de cada pan único.
4. No se pueden hacer selecciones consecutivas adyacentes.
5. Minimice la distancia entre los índices de selección.
6. No necesita preocuparse por entradas no válidas.
7. Se aplican las reglas de E / S predeterminadas .

Este es el código de golf , el conteo de bytes más corto gana.

JavaScript (ES6), 114 bytes

Guardado 1 byte gracias a @Oliver

Toma entrada como una matriz de caracteres. Emite una cadena separada por comas donde el primer valor es el tiempo total y los siguientes describen la ruta.

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

Pruébalo en línea!

Comentado

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 bytes

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*

Pruébalo en línea!

2 bytes gracias a Jonathan Frech .