FUN Team / ICFP Programming Contest : 2009 : index

1001

• score : 67.7723971246
• fuel : 6050.57841675
• steps : 19779
• solution : src/1001.bin

For this problem you can also download the video in MPEG format: 1001.mpeg.

1002

• score : 75.1250406346
• fuel : 4638.87985897
• steps : 7395
• solution : src/1002.bin

1003

• score : 64.0130816965
• fuel : 7108.20406745
• steps : 13126
• solution : src/1003.bin

1004

• score : 67.6606784949
• fuel : 6075.40477892
• steps : 17540
• solution : src/1004.bin

2001

• score : 188.399889449
• fuel : 49111.0496937
• steps : 20021
• solution : src/2001.bin

2002

The following binaries do not have the last EOF frame. The server accepted them. Our Python VM will decode them.

• score : 181.838154538
• fuel : 46576.7525214
• steps : 43632
• solution : src/2002.bin

For this problem you can download the video in MPEG format : 2002.mpeg.

2004

• score : 186.288427722
• fuel : 49049.1265121
• steps : 33132
• solution : src/2004.bin

Python Benchmark

Now let's test Psyco in a 32-bit installation (Pentium® D CPU 2.66GHz). Python 2.5.4. This is just out of curiosity because we did not use this VM much in the contest.

On this machine we got a 3X speedup with Psyco.

Without Psyco in an Intel Core 2 Duo CPU (T5750) at 2.00GHz.

• We get 1022 iter/sec executing problem 1001.
• We get 596 iter/sec executing problem 2001.
• We get 127 iter/sec executing problem 4002.

C world

We decided to encode the doubles as integers in order to avoid losing precision. We should have stripped the trailing zeros but we decided not to do it during the contest.

static int data[32768] = {
    0, 1072693248, 0, 0, 0, 1077805056, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1083129856, 0, 0, 0, 0, 0,
    1073741824,
    /* ... a lot of numbers */
} 

void problem_initial_data(double *d)
{
    memcpy(d, data, sizeof(double) * 16384);
}

And this the C code for the problem binary (1001 in this case) as the VM would execute it.

void
problem_timestep(double data[], double input[],
                 double output[], int *status_p)
{
    int status = *status_p;


    data[1] = data[265];


    data[4] = data[248];
    data[5] = data[4] - data[3];
    status = data[5] == 0;
    data[7] = status ? data[2] : data[1];
    data[8] = data[7] - data[0];
    data[9] = data[263];
    status = data[5] == 0;
    data[11] = status ? data[0] : data[9];
    data[12] = data[11] - data[0];
    status = data[12] == 0;
    data[14] = status ? data[8] : data[7];
    data[15] = data[264];

    status = data[5] == 0;
    data[18] = status ? data[16] : data[15];

    ...

This file is linked with each solution (code and data) in order to make a shared library. Note that we make in-place copies to C arrays here in the iterate function that is called from Python.

#include <string.h>
#include <assert.h>

/* functions you should care about, these could be called from python */
void init(double *data, double *input, double *output);
void iterate(double *data, double *input, double *output, int *status, int nsteps);

/* different for each problem */
void problem_initial_data(double *d);
/* different for each problem */
void problem_timestep(double data[], double input[], double output[], int *status_p);

#define mem_size 16384

void init(double *data, double *input, double *output)
{
  assert(data);
  assert(input);
  assert(output);

  problem_initial_data(data);

  memset(input, 0, sizeof(double) * mem_size);
  memset(output, 0, sizeof(double) * mem_size);
}

void copy_data(double *orig, double *dest) {
    memcpy(dest, orig, mem_size);
}

void iterate(double *data, double *input, double *output, int *status, int nsteps)
{
  assert(input);
  assert(output);
  assert(status);
  assert(nsteps > 0);

  while (nsteps--)
    problem_timestep(data, input, output, status);

}

We compiled the shared libraries for all the problems with this shell script:

test -d lib || mkdir lib
for i in  $(seq 1 4); do 
  python vm_compiler.py ../../input/bin$i.obf > lib/prob$i.c
  gcc -fPIC -Wall -O2 lib/prob$i.c -c -o lib/prob$i.o
  gcc -fPIC -Wall -O2 problem-common.c -c -o lib/common.o
  gcc -lc -shared -Wl,-soname,libprob$i.so -fPIC -Wall -O2 lib/prob$i.o lib/common.o -o lib/libprob$i.so 
done

Python world

The first interface in the python world is the c_vm.py file, which makes the interface with the C code for the simulator (we cannot longer call it a VM when it's in C).

We use the ctypes module in order to create native © arrays from python. This saves us a lot of time.

Note that we can save the state of the simulation. We started with a stack (that's why we have push and pop methods) but then we optimized for the hill climbing and replaced with a simple copy to native arrays.

#!/usr/bin/python

# the interfaces for this program could be improved a lot.

import ctypes
from ctypes import byref, c_int

MEM_SIZE = 2**14

# Create proxy object.
# Call as data = MEM() to create a native array of size MEM_SIZE
MEM = ctypes.c_double * MEM_SIZE
SCN_CFG = 0x3E80

# Hohmann
def get_output_1(output):
    """
    score, fuel_remaining, sx, sy, orbit_radio
    """
    return output[:5]

def set_input_1(input, *vals):
    input[0x2] = vals[0]
    input[0x3] = vals[1]
    input[0x3E80] = vals[2] # Ahh, this should not be  here.

# Meet and greet
def get_output_2(output):
    """
    score, fuel_remaining, sx, sy, orbit_radio
    """
    return output[:6]

# Clear Skyes
def get_output_4(output):
    """
    score, fuel_remaining, sx, sy, sx_fuel, sy_fuel, fuel_remain
    [sx, sy, touched?] ... (for 11 satellites)
    """
    return output[:7], output[7:7 + 3 * 11]

SG = dict() # setters and getters
SG[1] = (get_output_1, set_input_1)
SG[2] = (get_output_2, set_input_1)
SG[3] = (get_output_2, set_input_1)
SG[4] = (get_output_4, set_input_1)

class C_VM:
    def __init__(self, pr_id):
        global SG
        pr_id = int(pr_id)
        self.real_data = MEM()
        self.real_input = MEM()
        self.real_output = MEM()
        self.sim_data = MEM()
        self.sim_input = MEM()
        self.sim_output = MEM()
        self.status = ctypes.c_int(0)

        # we'll go for real initially
        self.data = self.real_data
        self.input = self.real_input
        self.output = self.real_output

        self.vm = ctypes.CDLL('../vm/lib/libprob%d.so' % pr_id)
        self.get_output, self.set_input = SG[pr_id]
        self.vm.init(byref(self.data), byref(self.input), byref(self.output))
        self.input[SCN_CFG] = -1 # Do not rely on this.
        self.iteration = 0
        self.fuel = 0

        self.savestack = list()

    def push(self):
        """ Save the state of the simulation """
        self.vm.copy_data(self.real_input, self.sim_input)
        self.vm.copy_data(self.real_output, self.sim_output)
        self.vm.copy_data(self.real_data, self.sim_data)
        self.data = self.sim_data
        self.input = self.sim_input
        self.output = self.sim_output
        self.savestack.append((self.status, self.iteration, self.fuel))

    def pop(self):
        """ Restore the state of the simulation """
        (self.status, self.iteration, self.fuel) = self.savestack.pop()
        self.data = self.real_data
        self.input = self.real_input
        self.output = self.real_output


    def iterate(self, *args):
        self.iteration += 1
        self.set_input(self.input, *args)
        self.vm.iterate(byref(self.data), byref(self.input),
                        byref(self.output), byref(self.status), c_int(1))
        rv = self.get_output(self.output)
        self.fuel = rv[1]
        return rv

Running the program

This is a skeleton of an optimizer. This was coded for the 4th problem that we didn't manage to solve.

from visualizer import CSVisualizer
from constants import EARTH_RADIUS
import v_utils

# This is an skeleton (slighty edited, it might not run)
# of how we started with a solver.

def solve_clear_skyes(sim, scn, impulse_a, angle, visualize=True):

    if visualize:
        vis = CSVisualizer(scale = 22, speed = 30)
    else:
        vis = None

    result, targets = sim.iterate(0, 0, scn) # initial impulse here, do nothing
    score, fuel, sx, sy, gasx, gasy, gas_left = result

    print 'fuel0', fuel

    old_sx = sx
    old_sy = sy

    time_solved = 0

    closest = 1e1000

    while score == 0.0:
        result, targets = sim.iterate(0.0, 0.0, scn)
        score, fuel, sx, sy, gasx, gasy, gas_left = result

        closest = min(closest, v_utils.v_norm((gasx, gasy)))

        old_sx = sx
        old_sy = sy
        if visualize:
            result.append(targets)
            result.append(sim.sim_data[0x64]) # moon_x
            result.append(sim.sim_data[0x65]) # moon_y
            vis.set_data(*result) # We don't display first timestep.
            vis.draw_map()
        if sim.iteration % 100000 == 0:
          print 'iter:', sim.iteration
          print 'closest to gas:', closest / 1000.0, ' gas left', gas_left
          print 'fuel', fuel
    else:
        print "Score", score
        print "Fuel", fuel

    return score

if __name__ == '__main__':
    import sys
    from c_vm import C_VM

    sys.path.append('../vm') # duh?

    def solve(scn):
        sim = C_VM(4)
        impulse_a = float(sys.argv[2])
        angle =  float(sys.argv[3])
        solve_clear_skyes(sim, scn, impulse_a, angle, len(sys.argv) < 5)

    solve(int(sys.argv[1]))

And this is how we would run the program with no GUI.

$ PYTHONPATH=../vm python solvercs.py 4001 0 0 nogui
fuel0 10000.0
iter: 100000
closest to gas: 100.000624888  gas left 75000.0
fuel 10000.0
iter: 200000
closest to gas: 100.000624888  gas left 75000.0
fuel 10000.0
iter: 300000
closest to gas: 99.7776569966  gas left 75000.0
fuel 10000.0
...

With GUI it would show a simple representation of the problem. The colors are not the best but we did this an hour before the contest and we didn't really use it.

Computing Environment

• Python 2.5
• C
  • We used GCC to compile the problem specification as a Python module.
  • We used ctypes.
  • We stored the state in C vectors and used them in-place (ctypes.c_double arrays).
• GNU/Linux
  • Debian and Ubuntu (32 and 64 bits)

Contest resources

• http://fxkr.net/icfp09/chatlog.txt
• #icfp-contest and #oasis @ Freenode

Writeups

There is a Subreddit for the contest now. You might want to check it.

• http://john.freml.in/icfp-contest-2009 (Score > 4000)
• http://subvert-the-dominant-paradigm.net/blog/?p=46 (Score 2000)
• http://www.stanford.edu/~vkl/icfpc2009/ (Interesting read)
• http://www.lshift.net/blog/2009/06/29/icfp-contest-2009
• http://bedevere.bohrarper.se/
• http://grammerjack.blogspot.com/2009/06/icfp-2009-contest-blog.html
• http://nibot-lab.livejournal.com/tag/icfp
• http://byorgey.wordpress.com/2009/06/29/2009-icfp-programming-contest-reflections/
• http://www.reddit.com/r/programming/comments/8wmhs/icfp_contest_2009_diary/c0aob0c
• http://kingsrook.com/sas.artifact/icfp/2009/index.vtl
• http://www.fatvat.co.uk/2009/06/icfp-contest-2009-2.html
• http://icfp2009.codeslower.com
• http://rmathew.blogspot.com/2009/06/icfpc-2009.html
• http://igor.rumiha.net/2009/06/icfp-contest-clojure-solution/
• http://www.reddit.com/r/icfpcontest/comments/8xlyk/blakes_writeup_2009/

Code

• http://adept.homeunix.net/icfpc2009/
• http://github.com/vii/dysfunkycom/tree/master
• http://redmine.stbuehler.de/projects/icfp12/repository
• http://github.com/darius/icfp09/tree/master