jld/icfpc09
Folders and files
| Name | Name | Last commit date | ||
|---|---|---|---|---|
Repository files navigation
Stuff in order of being written:
orb*.[hc]: an interpretive virtual machine in C
other *.c: ...and associated utilities.
icomp/ideco: translate input traces from/to a text format; invoke like cat
sim: the simulator; "./sim foo.obf bar.osf" or "./sim foo.obf < bar.osf";
prints outputs changed at each time step
disas: disassembles scenario binaries (requires input on stdin)
hohmann.zsh: Yes, I did the Wikipedia-cribbed math in zsh. Why not.
meetgreet.zsh: Likewise. (Note the variable "fudge" in this and the above.)
orbit_caml.c, orbit.ml: OCaml bindings for the interpreter &c
orbutil.ml: attempts at doing physics on my own; never quite worked right
pretty.pl: takes output of disas and makes it prettier
disas.ml: Now I can disassemble VM programs in ML...
ncmplr.ml: ...and compile them to C.
The VM-to-C compiler is noteworthy in that it can cause a subset of
the inputs to be vector-valued, thus running several instances of the
machine in parallel. In particular, values and computations which are
not influenced by the vectorized inputs remain scalar. Thus, for
example, bin4.obf vectorized on the delta-v input but not the scenario
input will compute the target satellite positions only once, while at
the same time simulating arbitrarily many spaceships. Aside from
cutting down on reduntant computation, the vectorization should allow
gains from data parallelism (to whatever extent it can be juiced out
of the C compiler; there is likely room for improvement here).
Also, it is possible to have multiple simulations living in the same C
namespace, and have one initialize its state to that of another.
This, for example, could be used for efficiently simulating many
flight plans with a common prefix.
gridtrace.(ml|c): a failed attempt at finding a path to some satellite
by casting a parallelogram-grid of delta-v's and, in theory,
proceeding recursively into grid cells which wind up somewhere
useful. (The set of parallelograms is closed under the action of
the group generated by rotations and scalings, which seems to go
not entirely badly with orbital mechanics.) In practice, for
cells of large enough size to be useful in the initial stages of
such a search, the grid bends too far out of shape to be useful.
Oh well.
scattertrace.(ml|c): oddly like my 2008 strategy; cast a bunch of
rays at random, and repeatedly focus the dispersion around the
"best" ray. This is where I finally got something working enough
to make the common-prefix stuff happen. Became piled high with
dodgy heuristics in the later hours, but I've tried to more or
less keep compatibility, and record the flags I used (on a new
OCaml process, which has a deterministic random seed).
Building/Using:
Assumes that a subdirectory "specs" has been created and the
scenario files are within.
Applying GNU make to the default target should take care of building.
Note that the scenario number to use in scattertrace is hard-coded
into the C file; it shouldn't be hard to find.
(Requires GCC, OCaml with dynamic library support, and zsh for the
section 1/2 stuff. Assumes a little-endian machine with IEEE
floating point; AMD64 is one such. (A static-only OCaml can be
accomodated without much work, as probably could a generic C99
compiler.) Also perl for the pretty-printer.)
Near the bottom of scattertrace.ml are my notes on the arguments I
gave the function there for the various problems. Basically, inside
"ocaml scattertrace.cma", "let at = Scattertrace.moreauto [the
arguments];;", hope it eventually terminates, "print_string
(printout [scenario#] at);;", copy that text, then in a shell
"./icomp > whatever.osf" and paste the text. If done first thing in
a new OCaml process, that should get the same random seed as I did.