Skip to content
/ icfpc09 Public

Source code for my team's entry in the 2009 ICFP Programming Competition

Notifications You must be signed in to change notification settings

jld/icfpc09

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.

About

Source code for my team's entry in the 2009 ICFP Programming Competition

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published