Robots! Collect these pickles! 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?
Ruby, 15+26+17+26+17 = 101

Robot Finds Pickles!

Okay, here's a baseline to get people started, using the following super-naive algorithm:


Each tick, each robot will act in numeric order, performing the following steps:


Identify the closest (Manhattan distance) pickle that no other robots are targeting.
Figure out which adjacent squares are available to move to.
Choose one of those squares, preferring directions that move it closer to the selected pickle.



Here's what it looks like for Test Case #1:



Obviously this isn't very good but it's a start!

Code:

Tile = Struct.new(:world, :tile, :x, :y) do
    def passable?
        tile =~ /\.|P/
    end

    def manhattan_to other
        (self.x - other.x).abs + (self.y - other.y).abs
    end

    def directions_to other
        directions = []
        directions &lt;&lt; ?U if self.y &gt; other.y
        directions &lt;&lt; ?D if self.y &lt; other.y
        directions &lt;&lt; ?L if self.x &gt; other.x
        directions &lt;&lt; ?R if self.x &lt; other.x
        directions
    end

    def one_step direction
        nx,ny = case direction
            when ?U then [self.x, self.y - 1]
            when ?D then [self.x, self.y + 1]
            when ?L then [self.x - 1, self.y]
            when ?R then [self.x + 1, self.y]
        end

        self.world[nx,ny]
    end

    def move direction
        destination = one_step(direction)
        raise "can't move there" unless destination &amp;&amp; destination.passable?

        destination.tile, self.tile = self.tile, ?.
    end
end

class World
    DIRECTIONS = %w(U D L R)

    def initialize s
        @board = s.split.map.with_index { |l,y| l.chars.map.with_index { |c,x| Tile.new(self, c, x, y) }}
        @width = @board[0].length
    end

    def [] x,y
        y &gt;= 0 &amp;&amp; x &gt;= 0 &amp;&amp; y &lt; @board.size &amp;&amp; x &lt; @board[y].size &amp;&amp; @board[y][x]
    end

    def robots
        tiles_of_type(/[0-9]/).sort_by { |t| t.tile }
    end

    def pickles
        tiles_of_type ?P
    end

    def tiles_of_type type
        @board.flatten.select { |t| type === t.tile }
    end

    def inspect
        @board.map { |l| l.map { |t| t.tile }*'' }*?\n
    end
end

gets(nil).split("\n\n").each do |input|
    w = World.new(input)
    steps = Hash[w.robots.map { |r| [r.tile, []] }]
    while (pickles_remaining = w.pickles).size &gt; 0
        current_targets = Hash.new(0)

        w.robots.each do |r|
            target_pickle = pickles_remaining.min_by { |p| [current_targets[p], r.manhattan_to(p)] }

            possible_moves = World::DIRECTIONS.select { |d| t = r.one_step(d); t &amp;&amp; t.passable? }
            raise "can't move anywhere" if possible_moves.empty?

            direction = (r.directions_to(target_pickle) &amp; possible_moves).first || possible_moves[0]

            current_targets[target_pickle] += 1
            steps[r.tile] &lt;&lt; direction
            r.move(direction)
        end
    end

    puts steps.values.map &amp;:join
    p steps.values.map { |v| v.size }.max
end


Takes input on STDIN in exactly the format of the test case code-block in the original question.  Here's what it prints for those test cases:

DDLLDLLLLULLUUD
LDLRRDDLDLLLLDR
URDDLLLLLULLUUL
15
ULDLDDLDRRRURRURDDDDDDDLLL
UUULDDRDRRRURRURDLDDDDLDLL
ULUURURRDDRRRRUUUDDDDLDLLL
26
URRRDRUDDDDLLLDLL
RUUUDLRRDDDLLLDLL
LDRDDLDDLLLLLLLUU
RUUURDRDDLLLLLUUU
17
DULLUUUUULDLDLLLLLDDRUUUUR
UDLRRRURDDLLLUUUUURDRUUUUD
26
LDDLDUUDDDUDDDDDR
ULUULDDDDDRDRDDDR
LULLDUUDDDRDRDDDR
UUUURDUURRRRDDDDD
LDLLUDDRRRRRRUDRR
17