?

Log in

No account? Create an account
2001: a vector arithmetic odyssey - Lindsey Kuper [entries|archive|friends|userinfo]
Lindsey Kuper

[ website | composition.al ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

2001: a vector arithmetic odyssey [Jun. 29th, 2009|03:26 am]
Lindsey Kuper
[Tags|]

Alex oniugnip and I solved scenario 2001, the first problem of the second set of ICFP contest problems! Scoreboard-wise, this puts Team K&R in 200th place of 305 registered teams, with ten hours remaining. It took us until just now to catch up with Jesse jes5199!

We're wrecked and probably going to sleep soon, but I want to show off this thing I did by accident. The black line is supposed to plot the path of a satellite that travels around the orbit shown in red, so, really, it should cover the red line instead of looping all over the map. But instead of plotting that satellite's location with respect to the center of the earth, I accidentally plotted its location with respect to another satellite, which is a moving target (in fact, it's orbiting the earth at a lower altitude). What I got was a pretty Spirograph-esque design.

This is not the science you're looking for.

Things like this are one reason why I'm envious of computer graphics people like Andrew pixelherder. Even their bugs end up looking cool!

Edited to add: Okay, maybe we're not going to sleep soon. Six problems solved, which puts us in 186th place at the moment! We came in something like 174th last year, which makes me want to do "better", even though those numbers have nothing to do with each other.

Edited again: It's now 6:06 a.m. and we're in 120th place with eight problems solved! What we have probably isn't general enough to work for the next set of problems, so, with less than eight hours to go, we might not be able to solve any more. I'm incredibly happy with where we are, though.

LinkReply

Comments:
[User Picture]From: royhuggins
2009-06-29 12:59 pm (UTC)
Did your satellite crash into the Earth? I hope it was over some 3rd-world country with no appreciable GDP.
(Reply) (Thread)
[User Picture]From: lindseykuper
2009-07-02 02:33 am (UTC)
Roy, that is a fantastic article. Thanks.
(Reply) (Parent) (Thread)
[User Picture]From: jes5199
2009-06-29 03:20 pm (UTC)
I tried to skip set 2, since set 3 is a generalization of set 2.

I got the math like actually completely working an hour ago ...
but I never land within the 1 kilometer range. Either my ellipse estimator isn't as accurate as I expected, or I need more floating point precision, or maybe it's just necessary to do things more complicated than instant engine burns.

I found this contest to be frustrating in a different sort of way. The programming never really got hard -- it would be nice if my simulator was a little faster, but it didn't seem critical.
I spent something like 36 hours just reading about physics. That seems a little weird.

2 and a half hours till they close, but I'm calling it a night.
(Reply) (Thread)
[User Picture]From: conform
2009-06-29 05:42 pm (UTC)
I didn't tackle the 3s at all, since I wasted most of my working time this weekend trying to figure out why my Hohmann transfers weren't (and aren't, with the exception of 2001) putting me quite close enough to the target satellite. I'm curious, Lindsey, if you're solving 2001-2004 with exactly two boosts, or if you're correcting after you arrive at approximately the right orbit.
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2009-06-29 05:44 pm (UTC)
Exactly two boosts.
(Reply) (Parent) (Thread)
[User Picture]From: conform
2009-06-29 06:23 pm (UTC)
i'd be interested to see you boost timings and vectors for each of the M'n'G problems, to try to figure out where i'm going wrong.
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2009-06-29 08:00 pm (UTC)

Here's what we used for 2001, for instance.

I'll write about our technique later, when I'm less wrecked.

localhost:icfp09 lkuper$ ./pack-osf.py 2001 scratch/meetandgreet.trace solutions/meetandgreet-2001-r2.osf 
frame at timestep 0
has this many inputs: 3
port 16000 val 2001.0
port 2 val 0.0
port 3 val 0.0
frame at timestep 15926
has this many inputs: 2
port 2 val -59.9281428687
port 3 val -454.233039831
frame at timestep 15927
has this many inputs: 2
port 2 val 0.0
port 3 val 0.0
frame at timestep 19117
has this many inputs: 2
port 2 val 56.3957296712
port 3 val 427.458661253
frame at timestep 19118
has this many inputs: 2
port 2 val 0.0
port 3 val 0.0
frame at timestep 27138
has this many inputs: 0

(Reply) (Parent) (Thread)
[User Picture]From: conform
2009-06-29 09:12 pm (UTC)

Re: Here's what we used for 2001, for instance.

interesting. i fire the initial pulse at 15926, but the second pulse is a few seconds later, at 19123. i calculate the time between thrusts ahead of time, with the formula pi * sqrt( (r1 + r2)^3 / 8 * mu ).

my thrust amount appears to agree with yours to a little more than four decimal places, which i'll attribute to rounding error in backcomputing from the thrust vector. i assume we're using the same Rs and the same formula.

the thrust vector was one of the last things i was tinkering with -- i was initially calculating the tangent by subtracting my last position from my current position and normalizing, but tried to get more precise by computing the tangent to the circle i'm on, storing that vector, and reversing that vector for the second thrust. given the quantization of time, that last step might not have been a good idea.
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2009-06-29 05:42 pm (UTC)
Were you on your own? If so, I'm impressed.

We're calling it a...whatever it is, too. We went to bed around 6:30 a.m. today and got up around noon. With 20 minutes or so to go, we're in 128th place -- seems like an auspicious number, and we know we can't solve the generalized meet-and-greet problem in this much time. If we had another day, we might try and do a bi-elliptic transfer.

We're only doing instant engine burns, but we spent a very long time tweaking the tolerances for our solutions for meet-and-greet so that we could stay in the 1-kilometer range for 900 seconds. On a couple of the runs, we're in range for less time than that, but then later we come back in range long enough to get a score. It was just a matter of runnign the simulation long enough.
(Reply) (Parent) (Thread)
[User Picture]From: jes5199
2009-06-29 11:24 pm (UTC)
well, I wrote all the code for my sim and rocket. I, at times, sat in the same room as Kim, Arlo, Seamus, Chad, and Martin.
Between us, we wrote five and a half separate virtual machines, and Seamus and Arlo's cross-pollinated heavily.
I would never had successfully submitted a score at all, if I didn't look at Kim's binary and find that I was rendering "CAFEBABE" backwards.

Chad consulted on my math a fair amount. I got really bogged down on the "where's that target satellite's ellipse?" problem, and I never would have cracked it if Paul hadn't been willing to sketch out some graphs at a party on Sunday night.

My one real victory is that I'm getting some pretty high scores on 1001-1004.

Actually, this deserves its own post.
(Reply) (Parent) (Thread)