Catch up on stories from the past week (and beyond) at the Slashdot story archive

 


Forgot your password?
Close
typodupeerror
×
Programming Technology

Mars Rescue Mission Programming Challenge 37

Posted by michael from the call-a-towtruck dept.
Frank Buss writes "A new challenge: Mars Rescue Mission. Have fun! Now you can win real prizes."
This discussion has been archived. No new comments can be posted.

Mars Rescue Mission Programming Challenge More

Mars Rescue Mission Programming Challenge

Comments Filter:
  • This is a somewhat easy problem, no? It's the shortest path problem if you make each square of space a connected vertex. Or did I miss something here...
    • Not quite the shortest path problem because velocity is not constant.
    • You can only control acceleration left, right, and up, with thrusters = 1/5 cell / (time^2). Gravity is -1/10 cell/(time^2). If you could move in any direction and control velocity, shortest-path would work. You've got to work with thrusters, though.

      • Re:Easy problem (Score:1, Interesting)

        by Anonymous Coward
        No, the problem is discretized. Plus there's only one test case. It's an easy problem.

        Shortest path will work (your possible moves are the 7 thruster configurations, not NSEW.. but still shortest path). And because you can precaculate it, you don't even have to use a very efficient shortest path.
        • You're talking about a 4 dimensional graph (position x velocity) with maybe less than 100 million nodes. I guess that sounds reasonable with some of today's desktop pc's.
    • You'd have to make a point on your graph for every possible pixel/velocity combination and link them together by each possible thrust value. You'd end up with on the order of 200,000 points and 600,000 or so links.
      • I didn't take into account the velocities. For the much simpler test problem, there would be about 10 million possible points, and about 5 times that many links (6 possible thrust values, but many of the points will already be at maximum thrust or will result in the same point).
  • They give you all the rules, so why not write it as a simple video game and record the output? In other words, use the human instinct for pattern matching and story telling as a part of your solution. Once you play it out to a successfull solution, then it's a simple matter to go back and program the virtual robot to do it with the same string.

  • RTFA (Score:5, Funny)

    by Anonymous Coward on Friday November 19, 2004 @08:00PM (#10871284)
    Jees, with a summary like that I guess I have no choice but to RTFA. I hate it when I have to do that!
  • So if a move would make you hit a block, then both your x and y velocities are divided by 2? What actually happens in the movement? Let's say your ship is travelling at +10 x velocity and 0 y velocity and you hit a vertical wall, but your box would be 9/10 way inside the wall (you were 1 pixels away). Would you stay 1 pixel away and then have you're velocity cut in 1/2 and stay at the same vertical position? The next round the same thing would happen and your x velocity would go down to 2. The next tim

    • If a stone is hit, the speed vectors are devided by 2 (integer devision without fraction) as long as no stone is hit (which can result in a speed vector of (0, 0)). Hitting a stone is calulated by checking if one or more of the four corners of the robot lies within a stone. Moving to coordinates = the size of the map counts as a hit.

      That made me scratch my head, too. Here's what I think they mean:

      • Calculate vector
      • While position + vector is inside a stone or out of bounds, divide the vector (both x a

      • I think I've got it right. I checked the Lisp code [frank-buss.de] (my doc says I can Lisp, but dad says the other kids may make fun of me). I'd post the exerpt here, but /. thinks that Lisp is pretty lame. Look for method update-robot.

      • That's right. That lets you slide along the ground by continually thrusting sideways. You will always be moving at only 1 speed though. Initially your horizontal velocity gets set to 2, but because of gravity setting your vertical velocity to -1, you hit the ground. Your velocity is halved so you end up with 1 horizontal and 0 vertical velocity, letting you move one pixel. The next round your velocities are 3 and -1, then get cut in 1/2 to 1 and 0. I wondered why they put that path in the map that is
    • you almost have it, except the 1/2 iterations happen all during one turn until you can move (or until your velocity is 0). so if youre 3 pixels from the wall and your velocity is +10 then youll get halved to +5 then halved to +2 then youll move and the turn ends. then youll move +2 and the turn ends. then youll get halved to +1 and the turn ends. then youll get halved to +0 and the turn ends.

      of course gravity is still affecting you, but its getting halved too until you stop moving into the wall. yes,
      • and when i said "then youll move +2 and the turn ends. then youll get halved to +1 and the turn ends." i meant "then youll get halved to +1 then youll move and the turn ends.". i have no idea why i put the extra +2 in there.

  • Genetic Algorithm (Score:2, Informative)

    by Samus ( 1382 )
    Sounds like a pretty simple application for a genetic algorithm. I read a book that showed how to do path finding using a GA. You just need the right number and type of censors and the outputs would correspond to what jet to fire. After a while your NN would learn how to fly to any objective on the map. Sounds like a fun little problem.

  • FYI - Programming contest tonight (Score:3, Informative)

    by Anonymous Coward on Friday November 19, 2004 @08:51PM (#10871574)
    In case anyone's interested, there's a programming contest late tonight/early tomorrow morning, starting at 08:30 UTC on Nov. 20th (5:30am EST, I believe). It's hosted through the University of Valladolid [acm.uva.es]. Contest details and the problemset will be at http://online-judge.uva.es/contest/ [online-judge.uva.es]when the contest begins. All you need to do is register an account [acm.uva.es] on the UVA system, and submit your answers through the on-line submit-o-matic [acm.uva.es].

    There are no prizes, the problems are not terribly hard (they are aimed at college-level participants), but you get geek points (whatever those are) and it's fun (in my opinion, at least).

  • Cool. (Score:5, Insightful)

    by St. Arbirix ( 218306 ) <matthew.townsendNO@SPAMgmail.com> on Friday November 19, 2004 @09:44PM (#10871793) Homepage Journal
    This is the first time I can recall Slashdot reporting on a reasonably interesting (YMMV) programming contest that didn't end yesterday. This sets a real good standard. Keep it up!

  • 2001 (Score:2, Funny)

    by Tablizer ( 95088 )
    "My God, it's full of ASCII!"
  • so, I submitted a soluton (Clarence Risher) but I do not see any others being submitted? lots of comments here, is anyone actually trying to solve it?

    • Well I did start off by looking at the problem, but then decided investigation into making SWF animations using the javaswf2 [anotherbigidea.com] program that they use on the website seemed like a less taxing thing to do on a Saturday morning.

      The problem solving, being more fun, is obviously something to save for the Saturday night;-)

  • http://www.frank-buss.de/marsrescue/list.php [frank-buss.de]

    The optimal solutions for both fewest steps and least fuel usage appear to have been found, which would make Jeremie Allard and Randy Sargent the winners for each finding both solutions. Allen Noe also deserves notice for being the first to find a fewest steps solution.

    It appears most contestants required only about 3-4 hours of programming time and 2-20 minutes of cpu time. The problem was simple enough to apply a traditional shortest path algorithm, solvable

Slashdot Top Deals

Last yeer I kudn't spel Engineer. Now I are won.

Close