I seem to have gotten myself into a bit of a pickle. Literally. I dropped a bunch of pickles on the floor and now they're all scattered about! I need you to help me collect them all. Oh, did I mention I have a bunch of robots at my command? (They're also all scattered all over the place; I'm really bad at organizing things.)
You must take input in the form of:
P.......
..1..2..
.......P
........
P3PP...4
.......P
i.e., multiple lines of either .
, P
(pickle), or a digit (robot's ID). (You may assume that each line is of equal length, padded with .
.) You can input these lines as an array, or slurp from STDIN, or read in a comma-separated single line, or read a file, or do whatever you would like to take the input.
Your output must be in the form of n
lines, where n
is the highest robot ID. (Robot IDs will always be sequantial starting at 1.) Each line will contain the robot's path, formed from the letters L
(left), R
(right), U
(up), and D
(down). For example, here's an example output for that puzzle:
LLU
RDR
LRRR
D
It can also be
LLU RDR LRRR D
Or
["LLU","RDR","LRRR","D"]
Or any format you would like, as long as you can tell what the solution is supposed to be.
Your goal is to find the optimal output, which is the one that has the least steps. The amount of steps is counted as the greatest amount of steps from all of the robots. For example, the above example had 4 steps. Note that there may be multiple solutions, but you only need to output one.
Scoring:
- Your program will be run with each of the 5 (randomly generated) test cases.
- You must add the steps from each run, and that will be your score.
- The lowest total, cumulative score will win.
- You may not hard-code for these specific inputs. Your code should also work for any other input.
- Robots can pass through each other.
- Your program must be deterministic, i.e. same output for every run. You can use a random number generator, as long as it's seeded and consistently produces the same numbers cross-platform.
- Your code must run within 3 minutes for each of the inputs. (Preferrably much less.)
- In case of a tie, most upvotes will win.
Here are the test cases. They were randomly generated with a small Ruby script I wrote up.
P.......1.
..........
P.....P...
..P.......
....P2....
...P.P....
.PP..P....
....P....P
PPPP....3.
.P..P.P..P
....P.....
P....1....
.P.....PP.
.PP....PP.
.2.P.P....
..P....P..
.P........
.....P.P..
P.....P...
.3.P.P....
..P..P..P.
..1....P.P
..........
.......2P.
...P....P3
.P...PP..P
.......P.P
..P..P..PP
..P.4P..P.
.......P..
..P...P...
.....P....
PPPP...P..
..P.......
...P......
.......P.1
.P..P....P
P2PP......
.P..P.....
..........
......PP.P
.P1..P.P..
......PP..
P..P....2.
.P.P3.....
....4..P..
.......PP.
..P5......
P.....P...
....PPP..P
Good luck, and don't let the pickles sit there for too long, or they'll spoil!
Oh, and why pickles, you ask?
Why not?