13
\$\begingroup\$

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 , shortest byte count wins.

\$\endgroup\$
10
  • \$\begingroup\$ 0+3+5+1+4=13 but 1+3+5+7+10=26, not 9. \$\endgroup\$
    – Shaggy
    Jul 9, 2018 at 14:59
  • 2
    \$\begingroup\$ @LuisfelipeDejesusMunoz Not quite, several of those consecutive indeces are adjacent. \$\endgroup\$
    – Nick Reed
    Jul 9, 2018 at 15:19
  • 4
    \$\begingroup\$ Welcome to PPCG, and nice first challenge! \$\endgroup\$
    – DELETE_ME
    Jul 9, 2018 at 15:33
  • 2
    \$\begingroup\$ It's not important to the actual task, but I'm curious: why does him being a germophobe mean you can't take loaves from two adjacent shelves in consecutive selections? \$\endgroup\$
    – Sundar R
    Jul 9, 2018 at 17:52
  • 1
    \$\begingroup\$ Might there be any empty shelves that are not at the ends? (e.g. is 'WBWG FRW' a valid input too? \$\endgroup\$ Jul 9, 2018 at 19:16

3 Answers 3

3
\$\begingroup\$

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 = [""]
\$\endgroup\$
0
0
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ if len(...)==5and all(...) can be if(len(...)==5)&all(...) to save two bytes. \$\endgroup\$ Jul 12, 2018 at 1:11
0
\$\begingroup\$

Python3, 244

def f(l):
 q=[(0,0,[],[])]
 L,C=0,0
 for a,r,b,c in q:
  if C and r>=C:continue
  if not{*l}-{*c}:L=b;C=r;continue
  for i,A in enumerate(l):
   if i not in b and A not in c and(c==[]or abs(b[-1]-i)!=1):q+=[(i,r+abs(a-i),b+[i],c+[A])]
 return L

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.