A Lazy Bag of Bread

Question

I work at a bakery that serves Wheat, Rye, Barley, Grain, and French bread, but the baker's a little weird - he stacks the loaves in random order, and sometimes just leaves some shelves at the end empty.

Each day, the same customer comes in and asks for one of each loaf of bread, but the tricky thing is, he's a germophobe, so when I fill his bag, I can't take loaves from two adjacent shelves in consecutive selections.

It takes one second to walk between adjacent shelves. It's a busy store; for any random configuration of loaves, I'd like to minimize the time it takes to get one of each unique loaf. I can start and end at any shelf.

If today's ordering is W B W G F R W, a possible path is 0, 3, 5, 1, 4, for a total of 12 seconds: abs(3-0) + abs(5-3) + abs(1-5) + abs(4-1) = 12

(1, 2, 3, 4, 5 doesn't work, because bread is picked consecutively from adjacent shelves.)

If it's B W B G B F B R B W B F, a possible path is 1, 3, 5, 7, 10, for a total of 9 seconds.

The manager always makes sure there is a possible solution, so I don't need to worry about catching bad inputs. He usually sends me the order in a file, but if I want, I can type it to STDIN or read it a different way. I'd like the program to print out the indices of the best path, as well as its time, according to default I/O rules.

In short:

1. 5 types of bread.
2. Loaf orders appears as strings of random order and length.
3. Must select one of each unique loaf.
4. Cannot make adjacent consecutive selections.
5. Minimize the distance between selection indices.
6. Don't need to worry about invalid inputs.
7. Default I/O rules apply.

This is code-golf, shortest byte count wins.

Answer 1

JavaScript (ES6), 114 bytes

Saved 1 byte thanks to @Oliver

Takes input as an array of characters. Outputs a comma-separated string where the first value is the total time and the next ones describe the path.

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

Try it online!

Commented

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 = [""]

Answer 2

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*

Try it online!

2 bytes thx to Jonathan Frech.