Challenge: Ricochet Robots

Ricochet Robots is a board game about optimizing moves. (see wikipedia description)

The 4 pieces represent the "robots" Blue, Yellow, Red and Green on a board with 16x16 cells and some walls.

Rules: Each round one of the robots can be moved horizontally or vertically, and does not stop until it reaches an obstacle - either a wall or another robot.

E.G. in this example the Yellow on B14 can only reach A14 or B16 in one move, and nothing in between. You can only move one robot per round.

The object of the game is to bring one specific robot to an indicated target (here C9 marked with * ) using as few moves as possible.

(Since the goal has no neighboring wall you'll need to position other robots as obstacles nearby to reach it)

    A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P
   --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---
 1|                   |                 R |                       |1
      .   .---.   .   .   .   .   .   .   .   .   .   .   .---.   .
 2|       |                                               |       |2
      .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
 3|                                           |                   |3
      .   .   .   .   .   .   .   .   .   .   .---.   .   .   .   .
 4|                       |                                       |4
      .   .   .   .   .   .---.   .   .   .   .   .   .   .   .---.
 5|                                                               |5
   ---.   .   .   .---.   .   .   .   .   .   .   .   .   .   .   .
 6|                   |                                           |6
      .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
 7|       |                                               |       |7
      .---.   .   .   .   .   .---.---.   .---.   .   .---.   .   .
 8|                           |       |       |                   |8
      .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
 9|         *                 |       |                           |9
      .   .   .   .   .   .   .---.---.   .   .   .---.   .   .   .
10|               |                                 B |           |10
      .   .   .   .---.   .---.   .   .   .   .   .   .   .   .---.
11|                       |                                       |11
   ---.   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
12|                                                               |12
      .   .   .   .   .   .   .---.   .---.   .   .   .   .   .   .
13|                               |   |                           |13
      .---.   .   .   .   .   .   .   .   .   .   .   .   .   .   .
14|    (Y)|                                               |       |14
      .   .   .   .   .   .   .   .   .   .   .   .   .   .---.   .
15|               |                               |               |15
      .   .   .---.   .   .   .   .   .   .   .---.   .   .   .   .
16|                   | G                                 |       |16
   --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---
    A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P
[download]

Question:

Whats the shortest solution (in number of rounds) to bring Yellow on target? Please display the moves for each round at the end.

Provide a runnable Perl script solving it in under 15 min on a current home PC.

Bonus question:

If you are still bored...

How many rounds do you need at most to reach any field?
How many rounds to you need if the goal has to be reached by any of the robots, like the Blue?

Careful

I do have a script I wrote 16 years ago.

It needed over an hour back than and runs today in 1:30 min on my laptop, so it's solvable within the given margin. :)

But it took me two days to write it, and you might run into memory problems.

FUN

I had a lot back then, and learned a lot. Hope you too ... :)

Cheers Rolf
_{(addicted to the Perl Programming Language :)

Wikisyntax for the Monastery}

Edits

added some clarifications and links

UPDATE

here the positions of the walls (yes strings as non-strict barewords, this script is old)

@vwalls=(A5,A11,B7,B13,C1,D15,E5,E10,G4,G10,H7,H9,H12,I7,I9,J12,K7,L3,
+L15,M9,N7,O1,O14,P4,P10);  # below cell

@hwalls=(B2,B7,B14,D10,D15,E1,E6,E16,F4,F11,G8,G9,H13,I8,I9,I13,J1,K3,
+K8,L15,M10,N2,N7,N14,N16); # to the right 

$Target="C9";
$Y="B14";
$R="J1";
$G="F16";
$B="M10";
[download]

UPDATE

It's specifically requested to bring Yellow on target, the first version was misleading, sorry.

removed (updated) marker in title again, to avoid "inheritance" to replies

Comment on Challenge: Ricochet Robots Select or Download Code

Replies are listed 'Best First'.
Re: Challenge: Ricochet Robots (updated) by choroba (Cardinal) on Feb 19, 2021 at 02:06 UTC
I don't have the moves yet, but I found a solution in 16 moves (almost 5 minutes on my machine). The final position of the robots was <Reveal this spoiler or all in this thread> `map{substr$_->[0],$_->[1]\|\|0,1}[\\|\|{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^ARGV,3]`	[reply] [d/l] [select]
Re: Challenge: Ricochet Robots by choroba (Cardinal) on Feb 19, 2021 at 09:30 UTC
So, here are the moves: `1:Y A14 2:Y A12 3:Y P12 4:R J12 5:G F1 6:G J1 7:R A12 8:G J12 9:G B12 10:Y C12 11:G B8 12:G G8 13:R B12 14:R B8 15:G C8 16:Y C9` [download] And here's how to get them (they're printed in reversed order). The code is ugly, but works: Read more... (7 kB) `map{substr$_->[0],$_->[1]\|\|0,1}[\\|\|{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^ARGV,3]`	[reply] [d/l] [select]
Re^2: Challenge: Ricochet Robots by LanX (Saint) on Feb 19, 2021 at 12:57 UTC
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	[reply] [d/l]
Re^3: Challenge: Ricochet Robots by choroba (Cardinal) on Feb 19, 2021 at 13:40 UTC
> 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]`	[reply] [d/l]
Re^4: Challenge: Ricochet Robots by LanX (Saint) on Feb 19, 2021 at 14:15 UTC
Re: Challenge: Ricochet Robots by tybalt89 (Monsignor) on Feb 19, 2021 at 16:43 UTC
Hmmm... <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 $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]	[reply] [d/l]
Re^2: Challenge: Ricochet Robots by LanX (Saint) on Feb 19, 2021 at 17:03 UTC
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...	[reply] [d/l]
Re^3: Challenge: Ricochet Robots by tybalt89 (Monsignor) on Feb 19, 2021 at 19:06 UTC
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]	[reply] [d/l]
Re^4: Challenge: Ricochet Robots by LanX (Saint) on Feb 19, 2021 at 20:54 UTC
Re^3: Challenge: Ricochet Robots by tybalt89 (Monsignor) on Feb 19, 2021 at 17:22 UTC
Ah, mucking about with the* and must have put it back wrong :(	[reply]
Re^4: Challenge: Ricochet Robots by LanX (Saint) on Feb 19, 2021 at 19:19 UTC
Re^5: Challenge: Ricochet Robots by tybalt89 (Monsignor) on Feb 19, 2021 at 19:28 UTC
Some notes below your chosen depth have not been shown here
Re: Challenge: Ricochet Robots (more edits) by vr (Curate) on Feb 22, 2021 at 18:31 UTC
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... Read more... (10 kB)	[reply] [d/l] [select]
Re^2: Challenge: Ricochet Robots (updated) by LanX (Saint) on Feb 22, 2021 at 19:13 UTC
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.	[reply]
Re^3: Challenge: Ricochet Robots by LanX (Saint) on Feb 22, 2021 at 19:32 UTC
> 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}	[reply] [d/l]
Re: Challenge: Ricochet Robots by Anonymous Monk on Feb 23, 2021 at 17:11 UTC
The most interesting solution I've yet found uses the "A*" algorithm that is commonly used for finding directions in a GPS or for sending bad-guys after you in a video game.	[reply]
Re^2: Challenge: Ricochet Robots by LanX (Saint) on Feb 23, 2021 at 17:15 UTC
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 ...	[reply]
Re^3: Challenge: Ricochet Robots by Anonymous Monk on Feb 23, 2021 at 18:41 UTC
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.	[reply]
Re^4: Challenge: Ricochet Robots by LanX (Saint) on Feb 23, 2021 at 19:24 UTC
Re: Challenge: Ricochet Robots by Anonymous Monk on Feb 23, 2021 at 18:17 UTC
Python implementation using A* to provide optimal solution: github.com/vipinpillai/ricochet-robots	[reply]
Re^2: Challenge: Ricochet Robots by LanX (Saint) on Feb 23, 2021 at 19:29 UTC
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}	[reply]


Keep It Simple, Stupid
	PerlMonks