Saya bekerja di toko roti yang menyajikan roti gandum, gandum hitam, gandum, gandum, dan Perancis, tetapi tukang roti itu agak aneh - ia menumpuk roti secara acak, dan kadang-kadang hanya meninggalkan beberapa rak di ujung kosong.

Setiap hari, pelanggan yang sama masuk dan meminta satu roti untuk setiap roti, tetapi masalahnya adalah, dia germophobe, jadi ketika saya mengisi tasnya, saya tidak bisa mengambil roti dari dua rak yang berdekatan dalam pemilihan berurutan.

Dibutuhkan satu detik untuk berjalan di antara rak-rak yang berdekatan. Ini toko yang sibuk; untuk setiap konfigurasi acak roti, saya ingin meminimalkan waktu yang diperlukan untuk mendapatkan satu dari setiap roti yang unik. Saya bisa mulai dan berakhir di rak mana pun.

Jika pemesanan hari ini adalah W B W G F R W, jalur yang mungkin adalah 0, 3, 5, 1, 4, selama total 12 detik:abs(3-0) + abs(5-3) + abs(1-5) + abs(4-1) = 12

( 1, 2, 3, 4, 5Tidak berfungsi, karena roti diambil secara berurutan dari rak yang berdekatan.)

Jika itu B W B G B F B R B W B F, jalan yang mungkin adalah 1, 3, 5, 7, 10, untuk total 9 detik.

Manajer selalu memastikan ada solusi yang memungkinkan, jadi saya tidak perlu khawatir tentang mendapatkan input yang buruk. Dia biasanya mengirim saya pesanan dalam file, tetapi jika saya mau, saya bisa mengetiknya ke STDIN atau membacanya dengan cara yang berbeda. Saya ingin program untuk mencetak indeks jalur terbaik, serta waktunya, sesuai dengan aturan I / O default .

Pendeknya:

1. 5 jenis roti.
2. Pesanan roti muncul sebagai string pesanan acak dan panjang.
3. Harus memilih salah satu dari setiap roti unik.
4. Tidak dapat membuat pilihan berurutan yang berdekatan.
5. Minimalkan jarak antara indeks pemilihan.
6. Tidak perlu khawatir tentang input yang tidak valid.
7. Aturan I / O standar berlaku.

Ini adalah kode-golf , kemenangan jumlah byte terpendek.

JavaScript (ES6), 114 byte

Disimpan 1 byte berkat @Oliver

Mengambil input sebagai array karakter. Menghasilkan string yang dipisahkan koma di mana nilai pertama adalah total waktu dan yang berikutnya menggambarkan 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)``

Cobalah online!

Berkomentar

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 byte

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*

Cobalah online!

2 byte thx ke Jonathan Frech .