Mars Rescue Mission Programming Challenge

Frank Buss writes "A new challenge: Mars Rescue Mission. Have fun! Now you can win real prizes."

Easy problem

[sporty]

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

Re:Easy problem

[El]

Not quite the shortest path problem because velocity is not constant.

Re:Easy problem

[Geoffreyerffoeg]

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

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

Re:Easy problem

[dtfinch]

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 can MAKE it into a shortest path problem.

[jgoemat]

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.

Numbers were way off

[jgoemat]

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

Why not write it as a video game?

[Marxist Hacker 42]

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.

Re:Why not write it as a video game?

[NaturePhotog]

They've already done that. Scroll down and look for "Java and Common Lisp reference implementations". It allows you to play the game, and outputs the command string.

Re:You call yourself Marxist? Then read Marx!

[Marxist Hacker 42]

http://www.technocrat.org/~President4242/Journal [technocrat.org]

I call myself a Marxist HACKER- that is to me, Marx is no different to me than any other economic system, and systems deserve to be hacked until they work for the largest number of lusers. I do support the Revolution- in my own way- and as you can see from the URL below, I hope to bring economic and social engineering to the United States in the 2008 election.

RTFA

[Anonymous Coward]

Jees, with a summary like that I guess I have no choice but to RTFA. I hate it when I have to do that!

Don't get hitting a block

[jgoemat]

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

Re:Don't get hitting a block

[WayneConrad]

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

Re:Don't get hitting a block

[WayneConrad]

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.

Figured it out by looking at code

[jgoemat]

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

Re:Figured it out by looking at code

[Frank Buss]

I wondered why they put that path in the map that is just big enough for your ship to get through.

Are you sure, that the maximum speed in this path is 1? :-)

Re:Figured it out by looking at code

[jgoemat]

I see, you could hit that square at -4x, 0y, then your speed would get cut in 1/2 to -2x, then each round you would add 2 to be -4 and it would get cut in 1/2 to -2 again. I was just thinking before that hitting any block would stop it for some reason.

Re:Don't get hitting a block

[Sparr0]

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,

Re:Don't get hitting a block

[Sparr0]

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

[Samus]

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.

Re:Genetic Algorithm

[p3d0]

You would probably benefit from learning the difference between a genetic algorithm and a neural net.

Re:Genetic Algorithm

[Samus]

Sorry you're right. I was a bit tired when I wrote that. A GA would be used to train the NN.

Re:Genetic Algorithm

[p3d0]

Regarding your sig, why are you trying to dork with the system? Just metamod fair mods as fair, and unfair mods as unfair. If others disgree with you, so what?

Re:Genetic Algorithm

[Frank Buss]

A genetic algorithm is a good idea and would be a candidate for one of the exceptional solution prizes. Currently all solutions are manual solutions or brute force C/C++ programs.

FYI - Programming contest tonight

[Anonymous Coward]

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.

[St. Arbirix]

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

[Tablizer]

"My God, it's full of ASCII!"

anyone actually trying?

[Sparr0]

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?

Re:anyone actually trying?

[rishistar]

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;-)

First results are in

[dtfinch]

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

Re:First results are in

[dtfinch]

Suppose you had a 10x10 map, and didn't have to track velocity. Then N would be max of 10x10=100, but your path length could be 10-20 steps, depending on how you treat diagonal movement. An exponential solution starts looking very bad very quickly. In a discrete problem such as this, N is not the number of possible paths, but at most the product of all the dimensions. In this case the upper limit based on dimensions is 790*350*21*21*2. The actual N is less because much of the map is unreachable.