Re^2: Challenge: Ricochet Robots (updated)

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.

Comment on Re^2: Challenge: Ricochet Robots (updated)

Replies are listed 'Best First'.
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]

Replies are listed 'Best First'.

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]