And here's how to get them (they're printed in reversed order). The code is ugly, but works:

Yep you solved it and it took 6 min on my machine

here a (handmade) visualization from my solutions (some steps are in another order)

<Reveal this spoiler or all in this thread>

> The code is ugly, but works:

well mine is uglier (but I was at the start of my Perl career ;-)

I didn't analyze your code yet.

But I think yours is swapping much less than mine.°

Want a harder challenge? =)

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

PS: did you have fun? :)

UPDATE

°) nope, you need 2GB RAM mine only 0.5GB

> Want a harder challenge?

Rather not. This was still manageable, but a harder one would be less fun. I have enough of them at work.

> did you have fun?

Yes, especially when I finished it! ;-)

> you need 2GB RAM

The original version that didn't produce the moves was less memory hungry. But the initial solution that stored the configuration as a string ate all my machine's memory and wasn't able to finish, so I had to introduce pack to make it more compact. I'd be interested in seeing an alternative solution.

map{substr$_->[0],$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]

Hmmm...

#!/usr/bin/perl

use strict; # https://perlmonks.org/?node_id=11128527
use warnings;

local $_ = <<END;
 --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---.
|                   |                 R |                       |
    .   .---.   .   .   .   .   .   .   .   .   .   .   .---.   .
|       |                                               |       |
    .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
|                                           |                   |
    .   .   .   .   .   .   .   .   .   .   .---.   .   .   .   .
|                       |                                       |
    .   .   .   .   .   .---.   .   .   .   .   .   .   .   .---.
|                                                               |
 ---.   .   .   .---.   .   .   .   .   .   .   .   .   .   .   .
|                   |                                           |
    .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
|       |                                               |       |
    .---.   .   .   .   .   .---.---.   .---.   .   .---.   .   .
|         *                 |       |       |                   |
    .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
|                           |       |                           |
    .   .   .   .   .   .   .---.---.   .   .   .---.   .   .   .
|               |                                 B |           |
    .   .   .   .---.   .---.   .   .   .   .   .   .   .   .---.
|                       |                                       |
 ---.   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
|                                                               |
    .   .   .   .   .   .   .---.   .---.   .   .   .   .   .   .
|                               |   |                           |
    .---.   .   .   .   .   .   .   .   .   .   .   .   .   .   .
|     Y |                                               |       |
    .   .   .   .   .   .   .   .   .   .   .   .   .   .---.   .
|               |                               |               |
    .   .   .---.   .   .   .   .   .   .   .---.   .   .   .   .
|                   | G                                 |       |
 --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---.
END

my $starpos = /\*/ && $-[0];
my $w = /\n/ && $-[0];
my $gap = qr/.{$w}/s;
my @queue = "$_= ";
my %seen;

while( @queue )
  {
  (local $_, my $moves) = split /=/, shift @queue;
  $seen{$_}++ and next;
  if( 'Y' eq substr $_, $starpos, 1 )
    {
    my $numoves = $moves =~ tr/lrud//;
    print "\n$_\ncompleted in $numoves moves $moves\n";
    exit;
    }
  print "$_=$moves\n";
  for my $robot ( qw( Y G ) )
    {
    /(?:\| |\w   )\K[ *]([ *]+)$robot/ and push @queue,
      (s/(?:\| |\w   )\K[ *]([ *]+)$robot/$robot$1 /r)
      . "=$moves ${robot}l";
    /$robot([ *]+)([ *])(?=   \w| \|)/ and push @queue,
      (s/$robot([ *]+)[ *](?=   \w| \|)/ $1$robot/r)
      . "=$moves ${robot}r";
    /$robot((?:$gap[ *])*$gap)([ *])(?=${gap}-|$gap $gap\w)/ and push 
+@queue,
      (s/$robot((?:$gap[ *])+$gap)[ *](?=${gap}-|$gap $gap\w)/ $1$robo
+t/r)
      . "=$moves ${robot}d";
    /(?:-$gap|\w$gap $gap)\K[ *]((?:$gap[ *])*$gap)$robot/ and push @q
+ueue,
      (s/(?:-$gap|\w$gap $gap)\K[ *]((?:$gap[ *])*$gap)$robot/$robot$1
+ /r)
      . "=$moves ${robot}u";
    }
  }
[download]

Hmmm...

False input.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

EDIT: nice try,though :-)

UPDATE

for my $robot ( qw( Y G ) )

Cough ... yeah sure...

Just a litle tweaking :)

<Reveal this spoiler or all in this thread>

#!/usr/bin/perl

use strict; # https://perlmonks.org/?node_id=11128527
use warnings;

local $_ = <<END;
 --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---.
|                   |                 R |                       |
    .   .---.   .   .   .   .   .   .   .   .   .   .   .---.   .
|       |                                               |       |
    .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
|                                           |                   |
    .   .   .   .   .   .   .   .   .   .   .---.   .   .   .   .
|                       |                                       |
    .   .   .   .   .   .---.   .   .   .   .   .   .   .   .---.
|                                                               |
 ---.   .   .   .---.   .   .   .   .   .   .   .   .   .   .   .
|                   |                                           |
    .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
|       |                                               |       |
    .---.   .   .   .   .   .---.---.   .---.   .   .---.   .   .
|                           |       |       |                   |
    .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
|         *                 |       |                           |
    .   .   .   .   .   .   .---.---.   .   .   .---.   .   .   .
|               |                                 B |           |
    .   .   .   .---.   .---.   .   .   .   .   .   .   .   .---.
|                       |                                       |
 ---.   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
|                                                               |
    .   .   .   .   .   .   .---.   .---.   .   .   .   .   .   .
|                               |   |                           |
    .---.   .   .   .   .   .   .   .   .   .   .   .   .   .   .
|     Y |                                               |       |
    .   .   .   .   .   .   .   .   .   .   .   .   .   .---.   .
|               |                               |               |
    .   .   .---.   .   .   .   .   .   .   .---.   .   .   .   .
|                   | G                                 |       |
 --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---.
END

my $starpos = /\*/ && $-[0];
my $base = tr/RGBY*/ /r;
my $w = /\n/ && $-[0];
my $gap = qr/.{$w}/s;
my @queue = code($_) . "= ";
my %seen;
my %before;
my $max = 1025;

sub code { lc(shift) =~ tr/rgby/\0/cr =~ s/\0+/length $&/ger }

while( @queue )
  {
  my ($grid, $moves) = split /=/, shift @queue;
  $seen{$grid}++ and next;
  local $_ = $grid =~ s/\d+/"\0" x $&/ger ^ $base;
  if( 'Y' eq substr $_, $starpos, 1 )
    {
    my $numoves = $moves =~ tr/lrud//;
    print "\n$_\ncompleted in $numoves moves $moves\n";
    exit;
    }
  print "$_=$moves\n";
  for my $robot ( qw( Y G R ) )
    {
    /(?:\| |\w   )\K[ *]([ *]+)$robot/
      && $before{$-[0]}++ < $max
      and push @queue,
      code(s/(?:\| |\w   )\K[ *]([ *]+)$robot/$robot$1 /r)
      . "=$moves ${robot}l";
    /$robot([ *]+)([ *])(?=   \w| \|)/
      && $before{$-[2]}++ < $max
      and push @queue,
      code(s/$robot([ *]+)[ *](?=   \w| \|)/ $1$robot/r)
      . "=$moves ${robot}r";
    /$robot((?:$gap[ *])*$gap)([ *])(?=${gap}-|$gap $gap\w)/
      && $before{$-[2]}++ < $max
      and push @queue,
      code(s/$robot((?:$gap[ *])+$gap)[ *](?=${gap}-|$gap $gap\w)/ $1$
+robot/r)
      . "=$moves ${robot}d";
    /(?:-$gap|\w$gap $gap)\K[ *]((?:$gap[ *])*$gap)$robot/
      && $before{$-[0]}++ < $max
      and push @queue,
      code(s/(?:-$gap|\w$gap $gap)\K[ *]((?:$gap[ *])*$gap)$robot/$rob
+ot$1 /r)
      . "=$moves ${robot}u";
    }
  }
[download]

Ah, mucking about with the* and must have put it back wrong :(

Sorry to be late,

it took me two days to write it

I kicked myself (very hard) into motion just yesterday, so I guess this solution still qualifies. It's same brute force, is definitely faster than choroba's and eats a little less RAM. Though tybalt89's uses impressively less memory, but with blue robot excluded from the fun, I don't know how to measure against it.

Edit: added readmore tag. Removed trailing space in one code line for better display in the node ("perfectionism"? never heard of that). Noticed, that lexical $x and $y in subroutine "shadow" variables with same names, used in same scope. Ugly, but won't fix it. Let it stay...

No problem being late, I didn't call it yet. :)

Tybalt89's solution doesn't qualify, knowing beforehand that you don't need one of the robots wasn't part of my game. With such a reduced branch factor brute forcing is easy.

Though it made me think about

• the best way to design challenges
• types of challenges and avoiding misunderstandings

My goal was a general algorithm to solve random robot positions in acceptable time.

And to have a problem hard enough to demonstrate some basic and advanced techniques like branch and bound. The recent triangle challenge was far too lightweight in complexity.

FWIW: The origin of this problem was a game we played at our students union in 2005.

But many people attempted to solve the whole problem class in the meantime and published solutions.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

UPDATE

• Your solution is correct, it's analogous to the other shown yet. (please add spoiler tags though)
• Runtime on my laptop averaged at 75 seconds after 3 runs
• Memory was ~1.3-1.5GB
Disclaimer: I maybe should write a proper test suite for benchmarking under reproducible conditions.

> types of challenges and avoiding misunderstandings

I was once at a regional open source conference - "MRMCD" (kind of the local branch of CCC) which was fun.

And they had a golfing competition, with online submission. You were allowed to choose the language, and at the end of the conference the winners were declared by language.

And I was very confident to win in Perl, since practically nobody there knew Perl.

To my great astonishment I was beaten by large distance, and I was very curious to learn these new advanced techniques.

Now what happened was: the test cases were given in advance, i.e. input on STDIN and expected output on STDOUT and automatically tested for all contributions.

While I tried to process the input did the winner just do something like print "EXPECTED OUTPUT"

Well ...

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

I've only seen discussions/mentions of the A-Star algorithm for Ricochet Robots and no implementation yet.

You're welcome to provide one!°:)

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

°) if that's more than just name-dropping in style of our dearest troll ...

Don't hold your breath. He couldn't implement A* in perl if his life depended on it. Heck, he can't even provide any "help" that isn't a simple regurgitation of "interesting" buzzwords he's heard.

Thanks, but ...

... either the author is using the term "Manhattan distance" wrongly or his solution is far from optimal.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}