10
1
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?
3There is no reasonable way to show that you actually found the "optimal output" since this is essentially a traveling salesman(men) problem and is NP complete. – Wally – 2014-03-04T01:16:01.103
@Wally Hmm, it is? Perhaps someone should find the minimum steps for the test case provided, and then all answers can be based upon that. – Doorknob – 2014-03-04T01:18:39.607
2The test case is probably small enough to brute force a minimum - if someone wanted to do that. And/or everyone who answers could tell what they got for the test case and you could require other answers to at least match that minimum. – Wally – 2014-03-04T01:25:49.140
Sorry, I downvoted temporarily. Perhaps you could change the goal to something better (ie. clearly provable) – Dr. belisarius – 2014-03-04T01:43:24.300
@belisarius Alright, edited the goal. – Doorknob – 2014-03-04T01:57:24.957
So, downvote removed :) – Dr. belisarius – 2014-03-04T01:59:04.447
"[I am in a pickle]. Literally". *Pictures a doorknob stuck in a pickle*. Thanks for misusing the word. It gave me a chance to think of something funny (the best way to counter misuse of the word is to assume it is meant literally; it makes the sentence very funny). – Justin – 2014-03-04T04:49:40.120
3Can robots pass through each other? If not, what are the timing restrictions on interpreting the paths? – Peter Taylor – 2014-03-04T07:38:08.033
How to calculate the score when I'm using random numbers in the algorithm? Should I just hardcode a seed? – SztupY – 2014-03-04T10:20:14.293
To stop people coding to your tests, maybe you could have a couple of other tests used for scoring which you don't reveal in the question. I realise you can't really do that now that the question is posted, but maybe for future reference? – Gareth – 2014-03-04T10:44:09.047
@PeterTaylor Yes, robots can pass through each other. I shall edit for clarification. – Doorknob – 2014-03-05T03:19:03.803
@SztupY Your answer must be deterministic. Therefore, hardcoding a seed would work. Edited to clarify – Doorknob – 2014-03-05T03:19:24.623
1@Gareth The problem with that is that scores will not be known until the testcases are revealed, and then submissions after that will already see the testcases. – Doorknob – 2014-03-05T03:19:51.730
There are 20 pickles in the first test case, 20 in the second, 22 in the third, 19 in the fourth and 22 in the fifth. So, we can forget about using brute-force. (Calculated using
prompt().split('').filter(function(a){return a==='P'}).length
.) – user2428118 – 2014-03-31T14:22:34.870