Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Re^2: Challenge: Ricochet Robots (updated)

by LanX (Sage)
on Feb 22, 2021 at 19:13 UTC ( #11128661=note: print w/replies, xml ) Need Help??


in reply to Re: Challenge: Ricochet Robots (more edits)
in thread Challenge: Ricochet Robots

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 (Sage) 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

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://11128661]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (5)
As of 2022-05-18 09:23 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Do you prefer to work remotely?



    Results (70 votes). Check out past polls.

    Notices?