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...
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
by
Anonymous Coward
·
· Score: 1, Interesting
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.
Why not write it as a video game?
by
Marxist+Hacker+42
·
· Score: 0, Redundant
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.
-- SJW: a person who perceives an injustice, and while correcting it, commits a greater injustice.
Re:Why not write it as a video game?
by
NaturePhotog
·
· Score: 3, Informative
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.
RTFA
by
Anonymous Coward
·
· Score: 5, Funny
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 time your x velocity would go down to 1, the next time you would move one pixel over and be touching the wall and would have a -1 y velocity added. The next time you would hit the wall again and you would have a 0,0 velocity, then finally you would start to slide down the wall?
That seems like what the rules imply, but it doesn't make sense naturally to have your ship hover away from the wall for three turns without falling down at all...
Re:Don't get hitting a block
by
WayneConrad
·
· Score: 1
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 and y parts) by 2, discarding any remainder
position = position + vector.
Essentially, hitting something causes your ship to slow down as much as it takes to keep from hitting it, even to the point of stopping completely. Assuming my interpretation is correct.
I could check the reference implementation, but my doctor says I've got to lay off of the Java.
Re:Don't get hitting a block
by
Anonymous Coward
·
· Score: 0
Re:Don't get hitting a block
by
WayneConrad
·
· Score: 1
I think I've got it right. I checked the Lisp code (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.
Re:Don't get hitting a block
by
Sparr0
·
· Score: 1
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, its unrealistic that your vertical velocity slows when you hit a vertical wall, but it makes the simulation so much simpler. not quite the instant stop you envisioned.
Re:Don't get hitting a block
by
Sparr0
·
· Score: 1
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
by
Samus
·
· Score: 2, Informative
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.
-- In Republican America phones tap you.
Re:Genetic Algorithm
by
Anonymous Coward
·
· Score: 0
Heh, you sound exactly like my mate at work who's doing AI as part of a computing degree. For his projects he keeps saying stuff like 'I just have to train a neural net' and 'ill just use a GA for that part' while I keep saying 'its not that easy' to no avail. Without fail he comes in the next day saying its too difficult.
Re:Genetic Algorithm
by
p3d0
·
· Score: 2, Insightful
You would probably benefit from learning the difference between a genetic algorithm and a neural net.
-- Patrick Doyle I mod down every jackass who puts his moderation policy in his sig. Oh, wait a sec....
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?
-- Patrick Doyle I mod down every jackass who puts his moderation policy in his sig. Oh, wait a sec....
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.
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. Contest details and the problemset will be at http://online-judge.uva.es/contest/when the contest begins. All you need to do is register an account on the UVA system, and submit your answers through the on-line submit-o-matic.
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).
Oops - 3:30am EST, not 5:30am EST
by
Anonymous Coward
·
· Score: 0
So it's for the insomniacs, not the morning-people. My mistake.
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!
-- Direct away from face when opening.
Figured it out by looking at code
by
jgoemat
·
· Score: 1
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 just big enough for your ship to get through.
Re:Figured it out by looking at code
by
Frank+Buss
·
· Score: 1
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
by
jgoemat
·
· Score: 1
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.
You can MAKE it into a shortest path problem.
by
jgoemat
·
· Score: 2, Interesting
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).
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?
by
rishistar
·
· Score: 1
Well I did start off by looking at the problem, but then decided investigation into making SWF animations using the javaswf2 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;-)
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 in O(N) time, but with 5 instead of 2 dimensions, which required nearly half a gb or more of ram to store path information for the roughly 115 million possible states.
Three more prizes remain to be given out for exceptional solutions, going above and beyond the scope of the original problem.
Re:First results are in
by
Anonymous Coward
·
· Score: 0
Hmmm... if by O(N) you mean N is the number of possible states, then yes, but pathfinding is generally thought of as taking exponential time, with N being the length of the path. Also, sure, if you use A*, memory is a problem, but IDA* (iterative deepening) would probably be a better idea -- it should take a bit more time but require much less memory, since memory use is proportional to the length of the path, not the size of the search space.
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.
Re:You call yourself Marxist? Then read Marx!
by
Marxist+Hacker+42
·
· Score: 1
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.
-- SJW: a person who perceives an injustice, and while correcting it, commits a greater injustice.
Slashdot Mirror
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...
-
ping -f 255.255.255.255 # if only
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.
SJW: a person who perceives an injustice, and while correcting it, commits a greater injustice.
Jees, with a summary like that I guess I have no choice but to RTFA. I hate it when I have to do that!
That seems like what the rules imply, but it doesn't make sense naturally to have your ship hover away from the wall for three turns without falling down at all...
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.
In Republican America phones tap you.
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).
So it's for the insomniacs, not the morning-people. My mistake.
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!
Direct away from face when opening.
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 just big enough for your ship to get through.
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.
"My God, it's full of ASCII!"
Table-ized A.I.
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).
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?
http://www.frank-buss.de/marsrescue/list.php
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 in O(N) time, but with 5 instead of 2 dimensions, which required nearly half a gb or more of ram to store path information for the roughly 115 million possible states.
Three more prizes remain to be given out for exceptional solutions, going above and beyond the scope of the original problem.
http://www.technocrat.org/~President4242/Journal
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.
SJW: a person who perceives an injustice, and while correcting it, commits a greater injustice.