gistfile1.txt

Rules of the ICFP Contest 2013
==============================


Prologue
~~~~~~~~

Game:    I have a program A, and I want you to guess it.
Player:  Can you tell me what is A(16), A(42) and A(128)?
Game:    Sure, A(16) = 17, A(42) = 43, and A(128) = 129.
Player:  Is the program B0, where B0(x) = x + 1?
Game:    No dice, A(9) = 9, but B0(9) = 10.
Player:  What is A(11), A(12) then?
Game:    Since you ask so nicely: A(11) = 11, A(12) = 13.
Player:  Is the program B1, where 
         B1(x) = if ((x & 1) ^ 1) = 0 then x else x + 1
Game:    That's right! You score one point. 
         I have a program A', and want you to guess it.
Player:  Argh!!!

We want you to guess a few thousand such programs, some slightly
smaller, many a bit bigger. You will have 5 minutes to guess each
one. You will most likely want to program a computer to do this.


Summary of the task
~~~~~~~~~~~~~~~~~~~

The role of the "Game" will be played by a web service that we (the
contest organizers) have programmed. You, the "Player", have to guess
a sequence of secret functions over 64-bit vectors programmed in a
small language called \BV (defined below). 

There are three kinds of requests you can make to the Game server:

    0. myproblems: In response to this request, the Game makes known
          to the Player the IDs of a set of secret programs. These 
          are all the problems assigned to you for the duration of the 
          contest. Additionally, some meta-data about each secret 
          program is revealed, e.g., its size and the operators it 
          contains.  
         

    1. eval: The Player supplies an ID of a secret program, and an
          array of up to 256 input 64-bit vectors, each an argument to
          the secret program. The Game responds by revealing the value
          on the inputs of the secret function corresponding to ID.

    2. guess: The Player supplies the ID of the secret program and a
          guessed program. If the Game decides that the Player's guess
          computes the same function as the secret program, the Player
          scores one point. Otherwise, the Game responds with a
          counter-example, an input bit-vector and the differing
          outputs of the secret and guessed programs on that input.

    Once you begin to eval or guess a problem with a particular ID,
    you will have 5 minutes to score one point. After 5 minutes, the
    problem ID expires; you will have to start over with a fresh
    problem ID.

    The team with the highest score after 72 hours wins.
    
    The team with the highest score after 24 hours wins the lightning
    division.

Additionally, the Game server provides a training mode. By making a
"train" request to the server, the Player can obtain a training
program ID as well as the text of program. Thereafter, the Player can
make eval and guess requests with respect to this training program ID
for an unlimited time period. Of course, successfully guessing a
training program does not contribute to your score.

--------------------------------------------------------------------------------
Details    
--------------------------------------------------------------------------------

Definition of \BV
~~~~~~~~~~~~~~~~~

0. Syntax

 program    P ::= "(" "lambda" "(" id ")" e ")"
 expression e ::= "0" | "1" | id
               | "(" "if0" e e e ")"
               | "(" "fold" e e "(" "lambda" "(" id id ")" e ")" ")"
               | "(" op1 e ")"
               | "(" op2 e e ")"
          op1 ::= "not" | "shl1" | "shr1" | "shr4" | "shr16"
          op2 ::= "and" | "or" | "xor" | "plus" 
          id  ::= [a-z][a-z_0-9]*

A valid program P contains at most one occurrence of "fold".
The only constants in a source program are 0 and 1.
However, \BV programs can be evaluated on arbitrary 64-bit values.

1. Semantics

All programs are functions from 64-bit vectors to 64-bit vectors.
     
The expression "(fold e0 e1 (lambda (x y) e2))" uses the lambda-term
to fold over each byte of e0 bound to x (starting from the least
significant), and with the accumulator y initially bound to e1.

For example, given P = (lambda (x) (fold x 0 (lambda (y z) (or y z)))), 

   P(0x1122334455667788) 

   reduces to 

   (or 0x0000000000000011 
   (or 0x0000000000000022 
   (or 0x0000000000000033 
   (or 0x0000000000000044 
   (or 0x0000000000000055 
   (or 0x0000000000000066 
   (or 0x0000000000000077 
   (or 0x0000000000000088 
       0x0000000000000000))))))))

Other operators have the usual (bitwise) interpretation.

You are most welcome to figure out the details by experimenting with
the game system :-)

2. Metadata

The function |.| determines the size of an \BV expression or program.

                             |0| = 1
                             |1| = 1
                             |x| = 1
                |(if0 e0 e1 e2)| = 1 + |e0| + |e1| + |e2|
|(fold e0 e1 (lambda (x y) e2))| = 2 + |e0| + |e1| + |e2|
                      |(op1 e0)| = 1 + |e0|
                   |(op2 e0 e1)| = 1 + |e0| + |e1|
                |(lambda (x) e)| = 1 + |e|

The function "Op" determines the set of operators in an expression,
where "U" is set union.

                             Op 0 = {}
                             Op 1 = {}
                             Op x = {}
                Op (if0 e0 e1 e2) = {"if0"}  U Op e0 U Op e1 U Op e2
Op (fold e0 e1 (lambda (x y) e2)) = {"fold"} U Op e0 U Op e1 U Op e2
                      Op (op1 e0) = {op1}    U Op e0
                   Op (op2 e0 e1) = {op2}    U Op e0 U Op e1

The binary relation "Operators" relates a program to a set ranging over
the set "ops", defined below:

       ops ::= op1 | op2 | "if0" | "tfold" | "fold"
       Operators (lambda (x) (fold x 0 (lambda (x y) e))) ({"tfold"} U Op e)
       Operators (lambda (x) e) (Op e)

The Web API
~~~~~~~~~~~

All interactions with the Game should use GET or POST requests
directed to:

     http://icfpc2013.cloudapp.net/

0. Authorization

Your submission to EasyChair, and more precisely its abstract, now
contains a user_id that you will use to authorize with the server
running the game.

Throughout this document, we assume that your user_id is
0000abcdefghijklmnopqrstuvwxyz0123456789. You should substitute it for
your secret authorization token.

All requests need to be directed to the URL below (note the "vpsH1H"
suffix):

http://icfpc2013.cloudapp.net/path?auth=0000abcdefghijklmnopqrstuvwxyz0123456789vpsH1H

where path is "myproblems", "train", "eval", or "guess".

You can start to experiment by pointing your browser to:

http://icfpc2013.cloudapp.net/play.html?auth=0000abcdefghijklmnopqrstuvwxyz0123456789vpsH1H

Type "myproblems" or "status" into the url field, and click on the
POST button. There is also a bit more user friendly playground
interface at:

https://www.touchdevelop.com/users/MichalMoskal/icfpc2013

Enter "0000abcdefghijklmnopqrstuvwxyz0123456789vpsH1H" as the "auth key",
then click on [new] to get a new training problem, try to evaluate it
on some inputs, try to guess it.

Each authorization token grants you the privilege of making up to 5
requests to the game server in any 20 second window. Depending on
load, you may be rate-limited further.

1. Getting problems
  
  Use the following API to initiate a new problem instance:
   
  POST /myproblems
    response 200 body Problem []
    response 403 authorization required
    response 429 try again later

  A succesful response (response 200) from the Game server will return
  in the response body an array of Problem structures (defined
  below), formatted using JSON (http://www.json.org).

  interface Problem {
    id: string;
    size: number;
    operators: string[];
    solved?: boolean;
    timeLeft?: number
  }

  In response to a /myproblems request, each problem p in response
  array has the following properties:

    -- p.id is a problem ID corresponding to some program P.

    -- p.size is in the range [3,30], and |P| = p.size

    -- When interpreted as a set, the relation 
       (Operators P p.operators) is valid.

    -- The field "solved" may or may not be present. If present,
       p.solved indicates whether or not a point has been scored on
       this problem.

    -- The field "timeLeft" may or may not be present. If present,
       p.timeLeft records the time in seconds remaining to solve the
       problem. If absent, you have 300 seconds to solve the
       problem---the clock starts ticking as soon as you make an /eval
       or /guess request for that problem.

   For example, a valid response may be:

    [
     {"id":"dKdeIAoZMyb5y3a74iTcLXyr",
      "size":30,
      "operators":["shr16","if0","xor","plus","not","fold"]},
     {"id":"hx2XLtS756IvDv9ZNuILizxJ",
      "size":3,
      "operators":["not"],
      "solved":true,
      "timeLeft":0},
     {"id":"af82718a7fhla74cal8faf7a",
      "size":3,
      "operators":["not"],
      "timeLeft":192.61}
    ]

2. Evaluating programs

   Use the following API to evaluate a program on some inputs:

   POST /eval
     request body EvalRequest
     response 200 body EvalResponse
     response 400 Bad Request   (some input is not well-formed)
     response 401 Unauthorized  problem was not requested by the current user
     response 404 Not Found     no such challenge
     response 410 Gone          problem requested more than 5 minutes ago
     response 412               problem was already solved (by current user)
     response 413               request too big

   The request body is a JSON-formatted EvalRequest:

   interface EvalRequest {
    id?: string;
    program?: string;
    arguments: string[];
   }

   An EvalRequest must contain either an id field or a program field,
   but not both.

   -- id: A program ID obtained previously from the Game server.

   -- program: A \BV program P formatted as a string. The program must
               be 1024 characters or less, and |P| is less than or
               equal to 100

   -- arguments: Up to 256 64-bit unsigned numbers encoded in
                 hexadecimal notation.

   An example of a valid EvalRequest:

     {"program":"(lambda (x) (shl1 x))",
      "arguments":["0x00000000000001", 
                   "0xEFFFFFFFFFFFFF"]}

   A successful request produces an EvalResponse in the response body:

   interface EvalResponse {
     status: string; 
     outputs?: string[];  
     message?: string;    
   }

   Given an EvalRequest r, an EvalResponse s to r has the following
   properties:

   -- s.status is either "ok" or "error"

   -- If s.status is "error", s.outputs is not present.

   -- If s.status is "ok", then s.outputs is an array of hexadecimal
      formatted 64-bit unsigned numbers, in 1-1 correspondence with
      r.arguments, such that, if P is the program corresponding to
      r.id or r.program, s.outputs[i] = P (r.arguments[i]).

   -- If s.status is "error", s.message is an error message; otherwise
      s.message is not present.

3. Submitting guesses

   Use the following API to submit guesses (and test if they are valid
   solutions to the challenge):

   POST /guess
    request body Guess
    response 200 body GuessResponse
    response 400 Bad Request   (some input is not well-formed)
    response 401 Unauthorized  problem was not requested by the current user
    response 404 Not Found     no such challenge
    response 410 Gone          problem requested more than 5 minutes ago
    response 412               problem was already solved (by current user)
    response 413               request too big

   The request body is a Guess (formatted as JSON):

   interface Guess {
    id: string;
    program: string;
   }

   -- id is a problem ID obtained from the Game server

   -- program is a \BV program, guessed to be equivalent to the secret 

   An example Guess is:

    {"id":"afa696afglajf696af",
     "program":"(lambda (x) (plus x 1))"}

   A valid guess request g produces a GuessResponse r:

   interface GuessResponse {
     status: string;
     values?: string[];
     message?: string;
     lightning?: bool;
   }

   -- r.status is either "win", "mismatch" or "error"

   -- If r.status is "win" if you guessed correctly. The other fields
      are absent. You score one point if g.id is not a training ID.

   -- If r.status is "mismatch", then values contains three 64-bit
      unsigned integers encoded as hexadecimal strings: the first is
      an input argument; the second is the result of the challenge;
      and the third is the result of your guessed program.

   -- If r.status is "error", then the message field contains an
      explanation. Note, if the Game server is unable to prove that
      your guess is functionally equivalent to the secret program,
      then you do NOT score a point. You can either try another guess,
      or move on to another problem. If you make reasonable guesses,
      we do not expect this to happen.

   -- If r.lightning is present and true, then your guess was counted
      for the lightning division.

4. Training 

   Use the following API to obtain training programs:

   POST /train
     request body TrainRequest
     response 200 body TrainingProblem
     response 400 bad request
     response 403 authorization required
     response 429 try again later

   The request body is a JSON-formatted TrainRequest:

   interface TrainRequest {
    size?: number;
    operators?: string[];
   }

   The request body contains two optional fields:

   -- size: The size of the problem requested, in the range [3,30].

   -- operators: Is either [], ["tfold"], or ["fold"]

   In response to a valid TrainRequest t, the server returns a
   TrainingProblem p:

   interface TrainingProblem {
     challenge: string;
     id: string;
     size: number;
     operators: string[];
   }

   The response p to a valid request t has the following properties:

   -- p.challenge is some \BV program P.

   -- p.id is a training problem ID associated with P.

   -- p.size = |P| and if t.size is defined then t.size = p.size

   -- (Operators P p.operators) is valid, and 
      if t.operators is []
      then "fold" and "tfold" do not occur in p.operators
      else if t.operators is defined
      then t.operators is included in p.operators
      
5. Status

   The following API displays various statistics about your team:

   POST /status
   response 200 body Status
   response 400 bad request
   response 403 authorization required
   response 429 try again later

   A valid request produces a JSON-formatted Status as a response.

   interface Status {
     easyChairId: string;
     contestScore: number;
     lightningScore: number;
     trainingScore: number;
     mismatches: number;
     numRequests: number;
     requestWindow: {
       resetsIn: number;
       amount: number;
       limit: number
     };
     cpuWindow: {
       resetsIn: number;
       amount: number;
       limit: number
     };
     cpuTotalTime:number;
   }

   Most of the fields in a Status object are self-explanatory.

   The requestWindow object shows how many requests you are currently
   allocated in each 20-second window.

      -- resetsIn is the time in seconds until the current 20-second
         window expires and your allocation is reset.

      -- amount is the number of requests you have already made in the
         current window.

      -- limit is maximum number of requests you are allowed to make
         in the current window.

   The cpuWindow object is similar, except it shows you how much CPU
   time you have allocated to you on the server in the current 60
   second window.

      -- resetsIn is the time in seconds until the current 60-second
         window expires and your allocation is reset.

      -- amount is the amount of CPU time you have already consumed in
         the current window.

      -- limit is maximum number of CPU time you have available to you
         in the current window.

   Depending on load, we may change the window sizes and number of
   requests/cpu time allotted to you.
   
Rules, regulations, and other notes
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
0. Do not cheat.

1. Please do not attempt to attack the Game server. That will spoil
   the fun for the other 500+ teams and us, the game administrators.

2. Each team should compete independently of other teams. Do not
   collude.

3. Each team is assigned a unique authorization token which grants
   them the ability to make a fixed number of requests to the Game
   server. Do not attempt to obtain or use more than one such
   token. If you attempt to use the token of another team, both you
   and the other team could be disqualified.
   
4. Remember, you only have up to 5 requests every 20 seconds.
   So, make your requests wisely. In particular,
   /train, /status and /myproblems requests also count.

5. At most one hour after the contest closes, you should complete the
   submission form at the URL below. This involves providing answers
   to a few simple questions about your team. Additionally, if you
   want to be considered for the judges' prize, you should provide a
   SHA-256 hash of your code.

   Submission form:

   https://www.touchdevelop.com/users/MichalMoskal/icfpc2013

   (first provide your auth token and then click on [survey] button)

6. At the end of 72 hours, if your team's score is among the top 20,
   you will be contacted (at the email address you provided in
   EasyChair) and asked to submit a two-page abstract describing your
   solution. Thereafter, you will have 48 hours to respond, if you
   wish to be considered for the judges' prize. Based on your
   abstract, you may be requested to make your code available for
   further review, under some mutually acceptable license.

7. All decisions made by the organizers are final.