Re^2: Challenge: Ricochet Robots (updated)

[LanX]

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.

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.

[LanX]

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