Ich arbeite in einer Bäckerei, die Weizen, Roggen, Gerste, Getreide und französisches Brot serviert, aber der Bäcker ist etwas komisch - er stapelt die Brote in zufälliger Reihenfolge und lässt manchmal am Ende nur einige Regale leer.

Jeden Tag kommt derselbe Kunde herein und fragt nach einem Brot, aber das Schwierige ist, dass er keimtötend ist. Wenn ich also seine Tasche fülle, kann ich keine Brote aus zwei benachbarten Regalen in aufeinanderfolgender Auswahl nehmen.

Es dauert eine Sekunde, um zwischen benachbarten Regalen zu gehen. Es ist ein geschäftiger Laden; Für jede zufällige Konfiguration von Broten möchte ich die Zeit minimieren, die erforderlich ist, um eines von jedem einzelnen Brot zu erhalten. Ich kann an jedem Regal beginnen und enden.

Wenn die heutige Bestellung lautet W B W G F R W, ist ein möglicher Pfad 0, 3, 5, 1, 4für insgesamt 12 Sekunden:abs(3-0) + abs(5-3) + abs(1-5) + abs(4-1) = 12

( 1, 2, 3, 4, 5funktioniert nicht, weil Brot nacheinander aus benachbarten Regalen gepflückt wird.)

Wenn ja B W B G B F B R B W B F, ist ein möglicher Pfad 1, 3, 5, 7, 10für insgesamt 9 Sekunden.

Der Manager stellt immer sicher, dass es eine mögliche Lösung gibt, sodass ich mir keine Sorgen machen muss, schlechte Eingaben zu erhalten. Normalerweise sendet er mir die Bestellung in einer Datei, aber wenn ich möchte, kann ich sie in STDIN eingeben oder anders lesen. Ich möchte, dass das Programm die Indizes des besten Pfads sowie seine Zeit gemäß den Standard-E / A-Regeln druckt .

Zusamenfassend:

1. 5 Brotsorten.
2. Laibreihenfolgen werden als Zeichenfolgen in zufälliger Reihenfolge und Länge angezeigt.
3. Muss eines von jedem einzelnen Brot auswählen.
4. Aufeinanderfolgende aufeinanderfolgende Auswahlen können nicht getroffen werden.
5. Minimieren Sie den Abstand zwischen Auswahlindizes.
6. Sie müssen sich keine Sorgen über ungültige Eingaben machen.
7. Es gelten die Standard-E / A-Regeln .

Dies ist Code-Golf , kürzeste Byte-Anzahl gewinnt.

JavaScript (ES6), 114 Byte

1 Byte dank @Oliver gespeichert

Nimmt die Eingabe als Array von Zeichen auf. Gibt eine durch Kommas getrennte Zeichenfolge aus, wobei der erste Wert die Gesamtzeit ist und die nächsten den Pfad beschreiben.

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

Probieren Sie es online aus!

Kommentiert

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*

Probieren Sie es online aus!

2 Bytes danke an Jonathan Frech .