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.)
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.
- 5 types of bread.
- Loaf orders appears as strings of random order and length.
- Must select one of each unique loaf.
- Cannot make adjacent consecutive selections.
- Minimize the distance between selection indices.
- Don't need to worry about invalid inputs.
- Default I/O rules apply.
This is code-golf, shortest byte count wins.