ICFP programming contest 2017
Lambda punter (1.2)
ICFP programming contest organisers
4th August 2017

1

Introduction

This year’s task is to efficiently transport lambdas around the world by punt. A punt is a kind offlat-bottomed boat propelled by a long pole.

As the picture illustrates, punts are ideal for transporting lambdas. This particular punt happens to be
in Cambridge, but they are also the preferred form of transport in Oxford, where ICFP will be held thisyear.
Five years ago ICFP contest participants alleviated the worldwide shortage of lambdas by optimising the lifting of lambdas from the lambda mines of Fife:
https://icfpcontest2012.wordpress.com/
With the continued popularity of functional programming and the increasing demand for lambdas inimperative as well as functional programming languages the bottleneck has now moved from the minesto the transport network. As a punter, your job is to set up punting routes to transport lambdas fromthe lambda mines to programmers around the world. You will be competing with other punters. May
the best lambda punter win!

1.1

Refinements

As the contest progresses the specification will be refined. We will make at most one refinement during
the first 24 hours, and at most four refinements during the contest overall. We will make no refinements
1

in the 12 hours before either the lightning or full deadline.
Details of any refinements will be posted in the following ways:• via the contest web site http://icfpcontest.org/• by email on the mailing list icfp-contest2017@inf.ed.ac.uk

2

Games

A lambda punter game is contested by n punters, for some n ≥ 2, on a fixed map G. A map is anundirected graph given by a collection of sites (nodes) and rivers (edges) between them. Some sites aredesignated as mines. They are lambda producers. All sites are lambda consumers (lambdas make theworld go round!). The goal is to build punting routes from the mines across as much of the map as
possible.
Here is an example map.

Sites 1 and 5 are mines.
Punters take it in turns to claim a river or to pass. Once a river has been claimed by punter P , only
punter P may use that river for transporting lambdas and no other punter can claim that river. The
game ends when R moves have been made, where R is the total number of rivers on the map (not all
rivers may have been claimed, as some punters may have passed).
We have provided a selection of sample maps, along with a simple visualiser. You can access thesehere:
http://punter.inf.ed.ac.uk/graph-viewer/

3

Scoring

Let the set of mines be {M0 , . . . , Mm−1 } and the set of sites be {S0 , . . . , Ss−1 }. Each punter P is assigned
a score at the end of the game, score(P ), computed as the sum of the scores for P at mine M , score(P, M ),for all mines M .
score(P ) = score(P, M0 ) + · · · + score(P, Mm−1 )The score for punter P at mine M , score(P, M ), is computed as the sum of the scores for P for thejourney from M to each S, for every site S.
score(P, M ) = score(P, M, S0 ) + · · · + score(P, M, Ss−1 )The score for punter P for the journey from M to S, score(P, M, S), is2

• 0 if there is no route from M to S along P ’s rivers; or• d × d, if there is a route along P ’s rivers, and d is the length of the shortest route between M andS along any rivers (whether or not they have been claimed by P or any other punter).

3.1

ExamplesThe following examples are based on the simple map in Section 2.
• If Alonso has rivers 1–2–3–4 (highlighted in yellow below), then Alonso’s score for the journeyfrom 1 to 4 is 2 × 2 = 4, as the shortest route (1–3–4, highlighted in red) has length 2.

• If Alonso has rivers 1–7–5 (highlighted in yellow below), then Alonso’s total score is (1+4)+(1+4)
as he scores for the routes starting from each mine (1–7, 1–5, 5–7, 5–1).

3.2

Timeouts

Punters will be given a limited amount of time to respond to the server. The timeout timer begins
immediately before the server sends a message to the punter and is stopped immediately after theserver receives the response from the punter. Details are given in Section 4.
If a punter fails to move within the specified time, then they will be made to pass for that turn. The
server will send a notification to a punter on each occasion that they time out.

3.3

Zombie punters

If a punter times out for 10 moves in a row then they become a zombie punter. The punter will be
disconnected and all their remaining moves in the game will be forfeit.

34

The lambda punter protocol

The lambda punter protocol exchanges data using the JSON format. Lambda punter supports twomodes: online mode and offline mode.
Online mode
Online mode supports concurrent punters running on different machines. Communication is via
TCP/IP sockets.
Offline mode
Offline mode supports only one punter running at once. Thus the game state must be serialised
between moves. The lambda punter server coordinates the punters, running each in turn andkeeping hold of the game state for each punter alongside each message. Communication is via
unix pipes.
After the contest has finished, the final evaluation will be performed exclusively in offline mode.
This will allow us to ensure that every punter has access to equal resources and teams cannot gain an
unfair advantage by buying up large amounts of cloud compute time. During the evaluation punterswill have no external internet access.

4.1

Messages

Messages between the server and punter are encoded using the JSON format.
http://www.json.org/
Every message takes the form n:json, where n is a natural number and json is a JSON string of exactly
n bytes in size. n must be an integer with not more than 9-digits, thus limiting the size of the json string
to 999999999 bytes (just under 1 GB). In the descriptions below we omit the n: prefix.

4.2

Online mode

We write P → S for a message sent from the punter to the server and S → P for a message sent fromthe server to the punter.
There are four phases to the protocol: handshake, setup, gameplay, and scoring.
0. Handshake

P →S
S→P

{"me" : name}{"you" : name}name : String(punter name)

The punter initiates the conversation by supplying a name, e.g., {"me" : "Alonso"}. The server
responds by repeating the name, e.g. {"you" : "Alonso"}. All subsequent interactions will be
driven by the server.
1. Setup(setup timeout timer begins here)
S → P {"punter" : p, "punters" : n, "map" : map}
P → S {"ready" : p}
(setup timeout timer ends here)(punter id)(total number of punters)(the map)

p : PunterIdn : Nat
map : Map
Pid = Nat
Map = {"sites" : [Site], "rivers" : [River], "mines" : [SiteId]}
Site = {"id" : SiteId}
River = {"source" : SiteId, "target" : SiteId}
SiteId = Nat
4

Once all punters are connected, the server broadcasts the initial game state to all of the punters.
The initial game state consists of a unique punter id (p), the total number of punters (n), and themap (map). The punter ids are assigned sequentially from 0 up to n − 1. The map consists ofa list of sites, a list of rivers, and a list of sites which are designated as mines. The map may
also contain additional meta data (e.g., coordinates of sites, but any such meta data can be safely
ignored). Each punter responds with a ready message containing their punter id.
2. Gameplay(gameplay timeout timer begins here)
S → P {"move" : {"moves" : moves}}
P → S move(gameplay timeout timer ends here)
moves : [Move] (moves from previous turn)move : Move
(P ’s chosen move)
Move = {"claim" : {"punter" : PunterId, "source" : SiteId, "target" : SiteId}}| {"pass" : {"punter" : PunterId}}
In each turn each punter must make a single move. The server communicates with the punters inascending order of punter id.
For each such interaction, punter P is prompted to move by the server, who sends a list of all
moves made in the previous turn. This list will always contain one entry per punter. At the
beginning of the game the previous move for each punter is initialised to a pass.
Having been prompted, the punter must now make a move: either claim a single river or pass.
(For this communication, the "punter" field is technically redundant. The server will record
when a punter is confused about their identity, but otherwise ignore this confusion. If the puntermakes an illegal claim the server will treat the move like a pass.)
Gameplay continues until r moves have been made, where r is the total number of rivers on themap. (If some punters pass during the game then at the end of the game not all rivers will beclaimed.)3. Scoring
S→P{"stop" : {"moves" : moves, "scores" : scores}}moves : [Move] (collection of moves)scores : [Score] (collection of scores)
Score = {"punter" : PunterId, "score" : Nat}The server notifies the punters that gameplay has ended by sending each in turn a "stop" message. This is accompanied by the final collection of moves as well as the final score for each punter.
For convenience, any moves that have already been reported to P are converted into passes. Thismeans that P can safely apply all of the reported moves to their internal game state without worrying about accidentally applying the same move twice.

4.3

Offline mode

In offline mode an encoding of the game state is passed in the "ready" message and then threaded
through the gameplay messages. In addition, rather than having a single handshake, one is performed
each time the punter binary is invoked.

51. Setup
P → S {"me" : name}
S → P {"you" : name}(setup timeout timer begins here)
S → P {"punter" : p, "punters" : n, "map" : map}
P → S {"ready" : p, "state" : state}(setup timeout timer ends here)
state : GameState(initial game state)

The variable state can be used to encode whatever game state the punter chooses using. At aminimum it should probably include an encoding of p, n, and map, otherwise it will be rather
difficult to play the game!
2. Gameplay
P → S {"me" : name}
S → P {"you" : name}(gameplay timeout timer begins here)
S → P {"move" : {"moves" : moves}, "state" : state}
P → S move ] {"state" : state 0 }(gameplay timeout timer ends here)
state : GameState
state 0 : GameState(game state before this move)(game state after this move)

The protocol for making a move is as in the online protocol, except the previous state is input by
the punter alongside the move request and the updated state is output by the punter alongside
the move. We write ] for the binary disjoint union operator on JSON objects: move must be a
JSON object that doesn’t contain a "state" field and move ] {"state" : state 0 } is move with an
extra "state" field whose value is state 0 .
3. Scoring
P →S
S→P
S→P

{"me" : name}{"you" : name}{"stop" : {"moves" : moves, "scores" : scores}, "state" : state}state : GameState(game state after P ’s final move)

The protocol for scoring is as in the online protocol except the previous state is input alongside
the stop message. There is no need for the punter to update the state again as this is the end of the
game.

4.4

Timeouts

If a punter is too slow to respond then their move will be forfeit. In online mode, the server sends"timeout" message along with the length of the timeout for this phase.
S→P
t : GameState{"timeout" : t}(length of the timeout)

In offline mode, the server kills the punter, and keeps track of the moves from the current turn so thatthey can be reported to the punter next turn. If a punter times out for several turns in a row then thislist of moves accumulates. Whether in online or offline mode, if a punter times out 10 times then they
become a zombie punter who always passes. The server makes no attempt to communicate with apunter once they have become a zombie.
In offline mode, the setup timeout is 10 seconds and the gameplay timeout is 1. In online mode,timeouts may be more lax in order to accommodate human players.
65Game servers

A collection of lambda punter servers will be made available for the duration of the contest in order toallow teams to test their implementations against one another while they develop their solutions.
You can find a status page detailing the active games at
http://punter.inf.ed.ac.uk/status.html
To connect to a game, open a connection to punter.inf.ed.ac.uk:<port>, where <port> is theport of the game you wish to connect to.
Additionally, if you wish to play a game yourself, you can find a web interface at
http://punter.inf.ed.ac.uk/puntfx/

6

Determining the winner

We will use the same procedure to determine the winner in both the lightning and full divisions.
The result for each game will be determined by ranking the punters by game score (the absolute
game score does not matter). The winner of a game with n punters is awarded n points, the player whocomes second n − 1 points, and so on. If two or more punters are ranked equally they all are awardedn − k points where k is the number of punters having been ranked higher in the game.
For determining the overall winners there will be three rounds:
1. We will run each entry on a collection of small maps. Entries scoring below the median score will
be eliminated.
2. We will then run each remaining entry on a number of larger maps. Again, entries scoring below
the median score will be eliminated.
3. Finally, we will run each remaining entry on a number of fiendish maps. The entry with the largest
score will be the winner.
The selection of punters in any given game will be randomised. In order to ensure that all puntersplay the same number of games in total in each round, some punters may be randomly drafted in to play
extra games, but the results of the extra punters will not be taken into account in the final reckoning.
We will announce the results of the first two elimination rounds in the weeks following the contest, andthe overall winners at the International Conference on Functional Programming in Oxford.
You are free to create your own maps, and submit them to us if you wish. We may even use them tohelp judge the contest.

6.1

The judges’ prize

The judges’ prize will be picked by the judges. All entries in both the full and lightning divisions are
eligible for the judges’ prize.

7

Submission

In order to register your entry go here:
http://punter.inf.ed.ac.uk:9000/register/Your submission must be a single .tar.gz file, named
icfp-XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.tar.gz
where
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

7

is the 36-character registration code, obtained from registering through the web form.
To submit your entry, share it via Google Docs or Google Drive with one of the following accounts:• icfpcontest2017@gmail.com for full submissions.
• icfpcontest2017lightning@gmail.com for lightning division submissions.
You can do this via the Google Docs web interface (http://docs.google.com/) by uploading thefile, selecting the uploaded file then clicking Share. You may submit in either or both divisions, as you
wish.
The .tar.gz file will be unpacked into a unique user’s home directory, and should contain (atleast) the following:• An executable file ./install, which is executed exactly once.
• An executable file ./punter, which may be generated by ./install, and will be executed oneach test map. It must comply with the offline protocol. The ./punter executable will not haveany access to the network. It should not access the filesystem either, except stdin, stdout, andstderr.
• A file ./PACKAGES listing the names of any non-standard packages required by either your./install or ./punter executables, one per line.
• A directory ./src, containing your source code. We will not try to compile this, but we will use
it to help choose the judges’ prize.
• A file ./README, listing your team members and (optionally) describing how your entry works.
We will use this to help choose the judges’ prize.
Ideally ./install should not need network access. If ./install needs access to the network,
then please explain why in the ./README file.
If ./punter really needs access to the filesystem (e.g. because it uses a system that relies on creating
files at runtime), then please explain why this is necessary in your ./README file and we will decide
whether to enable limited access to the file system for your entry.
Lightning contest deadline: 1200 UTC on Saturday 5th August
Full submission deadline: 1200 UTC on Monday 7th AugustGood luck, and happy lambda punting.

A

Sample play

Final game state after Alice (yellow) and Bob (red) claimed all rivers.

In the following, we write -> as shorthand for P → S and <- as shorthand for S → P .
Punter 0:
8

-> {"me":"Alice"}<- {"you":"Alice"}<- {"punter":0,"punters":2,"map":{"sites":[{"id":4},{"id":1},{"id":3},{"id":6},{"id":5},{"id":0},{"id":7},{"id":2}],"rivers":[{"source":3,"target":4},{"source":0,"target":1},{"source":2,"target":3},{"source":1,"target":3},{"source":5,"target":6},{"source":4,"target":5},{"source":3,"target":5},{"source":6,"target":7},{"source":5,"target":7},{"source":1,"target":7},{"source":0,"target":7},{"source":1,"target":2}],"mines":[1,5]}}-> {"ready":0}<- {"move":{"moves":[{"pass":{"punter":0}},{"pass":{"punter":1}}]}}-> {"claim":{"punter":0,"source":0,"target":1}}<- {"move":{"moves":[{"claim":{"punter":0,"source":0,"target":1}},{"claim":{"punter":1,"source":1,"target":2}}]}}-> {"claim":{"punter":0,"source":2,"target":3}}<- {"move":{"moves":[{"claim":{"punter":0,"source":2,"target":3}},{"claim":{"punter":1,"source":3,"target":4}}]}}-> {"claim":{"punter":0,"source":4,"target":5}}<- {"move":{"moves":[{"claim":{"punter":0,"source":4,"target":5}},{"claim":{"punter":1,"source":5,"target":6}}]}}-> {"claim":{"punter":0,"source":6,"target":7}}<- {"move":{"moves":[{"claim":{"punter":0,"source":6,"target":7}},{"claim":{"punter":1,"source":7,"target":0}}]}}-> {"claim":{"punter":0,"source":1,"target":3}}<- {"move":{"moves":[{"claim":{"punter":0,"source":1,"target":3}},{"claim":{"punter":1,"source":3,"target":5}}]}}-> {"claim":{"punter":0,"source":5,"target":7}}<- {"stop":{"moves":[{"claim":{"punter":0,"source":5,"target":7}},{"claim":{"punter":1,"source":7,"target":1}}],"scores":[{"punter":0,"score":6},{"punter":1,"score":6}]}}
Punter 1:-> {"me":"Bob"}<- {"you":"Bob"}<- {"punter":1,"punters":2,"map":{"sites":[{"id":4},{"id":1},{"id":3},{"id":6},{"id":5},{"id":0},{"id":7},{"id":2}],"rivers":[{"source":3,"target":4},{"source":0,"target":1},{"source":2,"target":3},{"source":1,"target":3},{"source":5,"target":6},{"source":4,"target":5},{"source":3,"target":5},{"source":6,"target":7},{"source":5,"target":7},{"source":1,"target":7},{"source":0,"target":7},{"source":1,"target":2}],"mines":[1,5]}}-> {"ready":1}<- {"move":{"moves":[{"claim":{"punter":0,"source":0,"target":1}},{"pass":{"punter":1}}]}}-> {"claim":{"punter":1,"source":1,"target":2}}<- {"move":{"moves":[{"claim":{"punter":0,"source":2,"target":3}},{"claim":{"punter":1,"source":1,"target":2}}]}}-> {"claim":{"punter":1,"source":3,"target":4}}<- {"move":{"moves":[{"claim":{"punter":0,"source":4,"target":5}},{"claim":{"punter":1,"source":3,"target":4}}]}}-> {"claim":{"punter":1,"source":5,"target":6}}<- {"move":{"moves":[{"claim":{"punter":0,"source":6,"target":7}},{"claim":{"punter":1,"source":5,"target":6}}]}}-> {"claim":{"punter":1,"source":7,"target":0}}<- {"move":{"moves":[{"claim":{"punter":0,"source":1,"target":3}},{"claim":{"punter":1,"source":7,"target":0}}]}}-> {"claim":{"punter":1,"source":3,"target":5}}<- {"move":{"moves":[{"claim":{"punter":0,"source":5,"target":7}},{"claim":{"punter":1,"source":3,"target":5}}]}}-> {"claim":{"punter":1,"source":7,"target":1}}<- {"stop":{"moves":[{"claim":{"punter":0,"source":5,"target":7}},{"claim":{"punter":1,"source":7,"target":1}}],"scores":[{"punter":0,"score":6},{"punter":1,"score":6}]}}

B

Version history• 1.0: Initial task description• 1.1: Added link to registration form. Removed spurious reference to 2012 contest!
• 1.2: Changes made:– Updated protocol to include handshakes in offline mode and to specify more precisely where
timeouts occur.
– Clarification on the game outcome when multiple punters score equally.
– Clarification over the treatment of illegal moves by the server.
– Clarification over the maximum length of messages.
– Clarified meaning of disjoint union operator.

9