This year's contest task is simple: make money in

International Car and Fuel Production


Table of Contents


The Market for Cars and Fuels

You are in the automobile business and you are manufacturing cars and fuels. Each car has subtly different specifications, so some fuels may suit its engine, and others may not. Given a car and a fuel, it is easy to check whether the fuel fits the car, and that is what the contest server will be doing. Given only the car, it may not be easy to design a fuel that fits. This will be part of your task. Cars are open-sourced (anyone can read their specification), but fuels are closed-sourced (so you cannot copy others' fuels).

During the contest, you will execute two types of actions:

  • compute and upload fuel for a car;
  • upload a new car, with matching fuel.

This is your source of income, and we will compute and display your score (in short intervals).

Each car on the market is a constant source of profit. For each car, the profit is shared among all manufacturers of fuels for that car. This includes the creator of the car. Shares are unequal, and the distribution of profits favors those suppliers with efficient fuel factories.

So your aim is to design fuels that fit others' cars, and to design cars for which you can supply fuel, but others cannot.

Initially, some cars are already on the market. During the contest, more will be added, by participants, and possibly by the organizers.

At any time during the contest, the number of cars submitted by you cannot be larger that number of others' cars for which you did supply fuels.

During the contest, you may submit at most 72 cars (seventy-two, the number of hours of the contest duration).

This bound is independent of whether you take part in the lightning division, or the main division. In particular, if you used up your car submission quota during the lightning division, you may continue to take part in the contest, but only by submitting fuels.


Scoring

For each car, shares are paid out to each team that has provided fuel for that car. Fuels are sorted by size, and (for equal size) time of submission. So, smaller and earlier is better, and smaller is more important. If there are n teams for one car, then they get 1/n, 1/(n+1), ... 1/(2*n-1) points, respectively.

The fuel that was initially provided by the team that built the car, does also take part in this evaluation. This is the way to ensure that the car's designer gets some profit.

Shares pay dividends at regular intervals. The payments will be accumulated on the team's account. Sadly, there will be a tax: in each period, you have to pay a fixed percentage, in such a way that you will lose 50 percent over the course of one day.

When you submit a new car, it will be published immediately. It will start producing profit only after one full time period.

The teams' scores will be published (updated after each period) - but we will hide the top five entries from this highscore list. The top teams will be asked to send in their source code for examination, and the winners of the contest will only be announced at the ICFP conference this September.


Technical Specification of Cars

A car's engine is given by a list of reaction chambers. Each chamber contains two pipes (called the upper and the lower pipe). Each pipe is a sequence of sections. Both pipes suck in air, which is freely available, and is in fact a mixture of several ingredients.

In each section, a chemical reaction combines ingredients coming from the neighboring section on the left, and of fuel that is fed directly to the section from a fuel tank, and the output ingredients are fed to the next section on the right. Finally, the output of the upper and lower pipe are joined to the Difference Engine that actually produces mechanical energy. The connections from tanks to sections are hard-wired by the car manufacturer.

For example, a car may have two fuel tanks, numbered 0 and 1, respectively. Its engine may consist of just one chamber. There are two pipes. The upper pipe consists of two sections, both fed from tank 0, and the lower pipe consists of three sections, where the first and last are fed from tank 0, while the middle section is fed from tank 1.


      upper pipe:  -> section -> section ------------.

    /                   /          /                  \

   /         fuel 0  --<----------'--------.      difference      positive

 air                    \                   \       engine  --->  energy

   \                     \                   \        /

    \ lower pipe:  -> section -> section -> section -'

                                    /

             fuel 1 ---------------'

                        

Proper Cars

A car is only allowed for street traffic if it

  • uses at most 6 (six) different fuel tanks,
  • is normalized,
  • is connected.

Two cars will be considered equivalent if we can transform one to the other by swapping the order of chambers, duplicating chambers, and swapping the order of tanks. A car is normalized if its ternary encoding (see below) is lexicographically smallest among those of its equivalents.

Connectedness is defined via the following: We say that tank t depends on tank s directly, if there is a chamber c such that tank s feeds some section of c's upper pipe, and tank t feeds some section of c's lower pipe. We then say that tank t depends on tank s indirectly, if there is a sequence of dependencies leading from s to t. A car is connected if for each pair of tanks (s,t), tank t depends on tank s. Note that the example car is not connected, since there is no dependency from tank 1 to tank 0.


Fuels

In each section of a pipe, fuel reacts with air. This changes the composition of air that is fed into the next section. The change is linear, in the sense that the amount of ingredient k in the output of a section fuelled with c is given by


out(k) = c(1,k) * in(1) + .. + c(n,k) * in(n)

where in(i) is the amount of ingredient i in the incoming air.

To provide fuel for a car, a manufacturer has to give, for each tank c, the values c(i,k) that characterize its fuel. For physical reasons, c(i,k) must be non-negative.

Air contains many ingredients, but you may choose the number n of ingredients to work with.

The difference engine only works if for each ingredient k, the amount of ingredient k in the upper pipe's output is at least as large as the amount of ingredient k in the output from the lower pipe. This condition must hold for all air conditions, that is, independent of the consistency of incoming air.

The first ingredient of air plays a special role: the incoming air will always contain it, the fuels may never remove it (the coefficient c(1,1) must always be positive), and the difference engine needs it.

Some of reaction chambers are declared as Main chambers, and here the amount of the first ingredient in the upper pipe's output must be strictly larger than the amount of this ingredient in the lower pipe's output. Other chambers are Auxiliary. The car manufacturer declares whether a chamber is Main or Auxiliary. A car must have at least one Main chamber.


Ternary Streams

This wasn't the ICFP contest if it was that easy.

Both cars and fuel descriptions are given as structured data, in fact, lists and tuples of ... of lists and tuples of natural numbers.

The data for both cars and fuel will be encoded by a stream of trits (ternary bits) and, you guessed it, we won't tell you more about the encoding here, so you just have to make some educated guesses, based on the error messages of the stream parser on our server.

Some hints are: the code can handle natural numbers of any size, and lists of any length. The code is self-delimiting, and indeed the parser will ignore trailing garbage after data for fuel, but not for cars. The code has some redundancy (not each trit string is a code word), but not much.

For instance, this is the ternary code of some car:


221022000022010112201010022001122011110220010

                        

Circuits

Does it still sound easy? Fear not, here's another obstacle: you cannot give the streams for the fuel description literally, but have to write a description for a factory that produces the stream you want from some input stream given by us.

The factory is a circuit, built from gates and wires. Each gate has two inputs and two outputs. Each wire connects an output to an input. Each input and output must have exactly one wire. A wire that "goes forward" transports information immediately, and a wire that "goes backward" has a delay of one.

To handle interaction with the world outside the circuit, we stipulate that each circuit contains a special "external" gate that has one input and one output. The circuit's input stream appears at the output of the external gate, and the circuit's output stream is fed to the external gate's input.

So, the factory is producing a stream that describes fuel. The size of the factory is the number of its gates, and smaller factories are more efficient. (This is important for scoring.)

You guessed it, we do not give the semantics of the gates here, and neither the syntax of circuits. Instead, we refer to an example key circuit


19L:

12R13R0#1R12R,

14R0L0#4R9L,

9R10R0#3L8L,

2L17R0#5L9R,

15R1L0#10R13R,

3L18R0#6L15L,

5L11R0#13L12L,

19R16R0#11R8R,

2R7R0#11L10L,

1R3R0#18L2L,

8R4L0#16L2R,

8L7L0#15R6R,

6R0R0#14L0L,

6L4R0#14R0R,

12L13L0#17L1L,

5R11L0#16R4L,

10L15L0#17R7R,

14L16L0#18R3R,

9L17L0#19R5R,

X18L0#X7L:

19L

                        

and its input


[0,2,2,2,2,2,2,0,2,1,0,1,1,0,0,1,1]

                        

You need to find its output on your own. The first seventeen output trits, called "the key", have to be prefixed to any ternary stream that encodes a solution.

You submit to our server any circuit you want and see the first trits of their output.

It is of no direct use to submit the "key circuit" there because our server uses a different input stream.


Remarks on Strategy

For the initial part of the contest, submit your circuits as solution attempts to Car #219 (with ternary code "0"). This is an extraordinary car that has no chambers, and needs no specific fuel. Its only purpose is to serve as a test case for computing the key prefix.

The moment you submit a circuit that produces the key prefix on our server, you will get your first share of profit. Of course if you're late, this may be a small share.

After you have submitted 72 cars, you still can make nice profit by fuelling others' cars.

The results of the lightning division are scored after exactly 24 hours.