ICFP 2004, version #19 ( #18 < #20 > ... #36)

Created by georg. Last edited by georg, one year and 74 days ago.. Viewed 427 times. #19

General

ICFP stands for International Conference on Functional Programming. They organise an anual interational programming contest. See the

ICFP 2004 Contest Website

Jörg, Allan and me attended the contest. Our team name was Formicoideas and we used primary haskell. Sorry, but we used also java to implement a graphical user frontend to be able to test our solutions.

Why Formicoideas?

Well the contest was about ants and the biological name for family is Formicoidea.

Teamwork

Because Allan lives in Edinburgh and we live in Leipzig we have been forced to program territorial distributed. This worked great since we used CVS,

Teamspeak and ICQ. I would say the productivity was larger than if we all would have worked together in the labs of the university or somewhere else. The reason is that you know you computer and the enviroment and it is calm if you need it.

The Task

The task description and some maps can be downloaded from the ICFP contest webpage or from the panel beside (

task.tgz).

Here a rough decription what it was about: The task was to write a program that controls an ant. It was basicly a finite state machine (FSM) that had to be developed. The programming language was very low level with absolute jumps and so on. Please note that there is no memory in a FSM, so cannot store anything.

There are two teams the red and the black colony. Every colony has an anthill of the same size and the world consists of hexogonal cells. There are rocky cells where you can't go on and there are cells with food. The overall goal was to bring as many food as possible to your anthill. In order to perform that the ant can mark a cell with 6 different markers and is able to sense the own cell and the ahead, left and right cell.

Our Approach

In order to simplify this task we decided to build a translator from a slightly higher level language than that of the ant finite state machine language. This language is called pheromone and the compiler is phec for pheromone compiler. We also built a Simulator as described in the task description to evaluate our ant programs, and a Java front end to visually deploy the simulator in order to aid debugging of the ant programs.

Here the modules we have written:

Formicoideas strategy

Usage

You can type make all in the tools directory to compile everything. The other option you have is to compile modules (Phec, Simulator and Frontend) seperatly be typeing make inside their directories. You will need ghc (haskell compiler) version 6.2 and the java sdk installed. Note that the java sdk is just needed if you want to recompile the frontend. Because the class files are included a java runtime is sufficient.

In the tools directory is a ./run.sh shell script to run the simulator with the graphical front end, this can be used with

./run.sh task/sample0.world --red=source2/initial.phec 
        --black=Simulator/test.prog

Please note that the world files have to be downloaded sperately (

task.tgz).

In the above example the file source2/initial.phec is compiled first whereas the Simulator/test.prog is allready compiled and is used just as it is. There are a plenty of commandline switches of the main program. Start run -h for a usage information.

For example there is a console front end included. The following call makes the simulator run for 100 steps:

./run --world=task/sample0.world --red=testing/initial.phec 
      --black=Simulator/test.prog --console -s100

To run the simulator without any frontend use:

./run --world=task/sample0.world --red=testing/initial.phec 
      --black=Simulator/test.prog

In any case you will get a final result, who as won and so on.

Submission

We submitted our submission 3 minutes before the deadline and - how to say - I was really nervous. It is every year a last minute hack!

The submission can be downloaded from the panel beside (formicoideas.tgz).

A bit Statistic

I let

sloccount run over out code, we produced in the 3 days. Here the results:

SLOC    Directory       SLOC-by-Language (Sorted)
747     Simulator       haskell=747
677     Phec            haskell=677
440     Frontend        java=438,sh=2
209     top_dir         haskell=187,perl=16,sh=6
Totals grouped by language (dominant language first):
haskell:       1706 (78.69%)
java:           438 (20.20%)
perl:            16 (0.74%)
sh:               8 (0.37%)
Total Physical Source Lines of Code (SLOC)                = 2,168
Development Effort Estimate, Person-Years (Person-Months) = 0.45 (5.41)
 (Basic COCOMO model, Person-Months = 2.4 * (KSLOC**1.05))
Schedule Estimate, Years (Months)                         = 0.40 (4.75)
 (Basic COCOMO model, Months = 2.5 * (person-months**0.38))
Estimated Average Number of Developers (Effort/Schedule)  = 1.14
Total Estimated Cost to Develop                           = $ 60,884
 (average salary = $56,286/year, overhead = 2.40).