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

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

Bonus question:

If you are still bored...

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";

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
  • Replies are listed 'Best First'.
    Re: Challenge: Ricochet Robots (updated)
    by choroba (Archbishop) 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
      map{substr$_->[0],$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]
    Re: Challenge: Ricochet Robots
    by choroba (Archbishop) on Feb 19, 2021 at 09:30 UTC
      So, here are the moves:

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

      map{substr$_->[0],$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]
        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)

        > 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]
    Re: Challenge: Ricochet Robots
    by tybalt89 (Prior) on Feb 19, 2021 at 16:43 UTC

      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"; } }
        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 :)

          #!/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"; } }

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

    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...

        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

    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.
        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.

    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
        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