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.
- 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.
Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
Want more info? How to link or
or How to display code and escape characters
are good places to start.