Your mission, should you choose to accept it, is to write a new **general-purpose
job queue server**.
You'll need to write a server that will accept jobs with numeric priorities,
store them in named queues, and hand them out, highest-priority first, to clients that request
jobs to work on.

## Protocol

Clients connect to the server using TCP and issue **requests**. Each request from a client results
in a single **response** from the server, and responses must be sent in the same order as the
corresponding requests. Each request and each response is a JSON object terminated by an
ASCII newline character ("`\n`"). There can be multiple requests over one connected session.

All requests contain a field named `request` which contains a string
naming the request type ("`put`", "`get`", "`delete`", or "`abort`").

All responses contain a field named `status` which contains one of the
strings "`ok`", "`error`", or "`no-job`".

Where a request does not match the specification (i.e. if it is not valid JSON, is missing mandatory fields, or has
illegal values in any fields, or meets any other criteria described as "an error"), the server must **send back an error response**, which
has the string "`error`" in the `status` field, and optionally an `error` field containing
a textual error message, for example:

 {"status":"error","error":"Unrecognised request type."}

The server must **not** close the connection in response to an invalid request.

## Requests

In all of the examples, "`<--`" denotes requests and "`-->`" denotes responses.

### `put`

Examples:

 <-- {"request":"put","queue":"queue1","job":{...},"pri":123}
 --> {"status":"ok","id":12345}

Insert the given job into the given queue with the given priority.

The "`queue`" field must contain a valid queue name.
The "`job`" field can contain any JSON object.
The "`pri`" field must contain a valid priority.

The server must **assign the job a unique ID**, returned in the "`id`" field of the response.

### `get`

Examples:

 <-- {"request":"get","queues":["queue1","queue2",...],"wait":true}
 --> {"status":"ok","id":12345,"job":{...},"pri":123,"queue":"queue1"}

 <-- {"request":"get","queues":["queue3","queue4",...]}
 --> {"status":"no-job"}

Retrieve the highest-priority job that is currently waiting in any of the listed queues, and
remove it from its queue. The highest priority is the one with the highest numeric value (100 is a
higher priority than 90). Where multiple jobs share the same priority, it is fine to return them
in any order.

The "`queues`" field must contain a list of valid queue names.

#### No job in the queue

If there is currently no job waiting in any of the listed queues, and the optional `wait` flag
is present and `true`, then the server must not send any response until there is a job available,
at which point that job must be returned to one of the "waiting" clients.

If there is currently no job waiting in any of the listed queues, and the optional `wait` flag
is absent or `false`, then the server must send a response with the `no-job` status.

#### Job available

When a job is returned from a "`get`" request, the response must contain the fields
"`queue`", "`pri`", and "`job`", matching those from the "`put`" request that initially
created the job, in addition to the "`id`" field, matching the one returned in the response
to the initial "`put`" request.

Once a job is returned, the requesting client is considered to
be *working on* that job, until one of the following occurs:

 - the job is deleted by any client
 - the job is explicitly aborted by the client working on it
 - the job is automatically aborted when the client working on it disconnects

### `delete`

Examples:

 <-- {"request":"delete","id":12345}
 --> {"status":"ok"}

 <-- {"request":"delete","id":12346}
 --> {"status":"no-job"}

Delete the job with the given `id`, so that it can never be retrieved, aborted, or deleted again.
Valid from any client.

If a client attempts to delete a job ID that has not been allocated, or that has already
been deleted, send a response with the `no-job` status.

Once a job has been deleted it ceases to exist. In particular this means it can no
longer be aborted or deleted by any client, and any client that was previously working on the job
(even if different to the client that deleted it) is no longer considered to be working on it.

### `abort`

 <-- {"request":"abort","id":12345}
 --> {"status":"ok"}

 <-- {"request":"abort","id":12346}
 --> {"status":"no-job"}

Put the job with the given `id` back in its queue. This request is **only valid
from the client that is currently working on that job**. It is an error for any client
to attempt to abort a job that it is not currently working on.

If a client attempts to abort a job ID that has not been assigned, or that has already
been deleted, send a response with the `no-job` status.

In addition to explicit aborting with the `abort` request, all jobs that a client is *working on*
are **automatically aborted when that client disconnects**.

## Example session

In this example, the client inserts a job into `queue1`, retrieves the job from the
queue, aborts it, retrieves the same job again, deletes it, and finally attempts to retrieve
another job.

 <-- {"request":"put","queue":"queue1","job":{"title":"example-job"},"pri":123}
 --> {"status":"ok","id":12345}
 <-- {"request":"get","queues":["queue1"]}
 --> {"status":"ok","id":12345,"job":{"title":"example-job"},"pri":123,"queue":"queue1"}
 <-- {"request":"abort","id":12345}
 --> {"status":"ok"}
 <-- {"request":"get","queues":["queue1"]}
 --> {"status":"ok","id":12345,"job":{"title":"example-job"},"pri":123,"queue":"queue1"}
 <-- {"request":"delete","id":12345}
 --> {"status":"ok"}
 <-- {"request":"get","queues":["queue1"]}
 --> {"status":"no-job"}
 <-- {"request":"get","queues":["queue1"],"wait":true}
 [...]

## Limits

Support at least 1000 simultaneous clients and at least 50000 simultaneous pending jobs.

A job can be any JSON object.

A job ID is an integer and must uniquely identify a job, and the server may not reuse a job ID even after the job is deleted
(but it's fine to reuse them every time the server restarts).

A queue name is any JSON string.

A job priority is any non-negative integer.

Your mission, should you choose to accept it, is to write a new general-purpose
job queue server.
You'll need to write a server that will accept jobs with numeric priorities,
store them in named queues, and hand them out, highest-priority first, to clients that request
jobs to work on.
<h2>Protocol</h2>
Clients connect to the server using TCP and issue requests. Each request from a client results
in a single response from the server, and responses must be sent in the same order as the
corresponding requests. Each request and each response is a JSON object terminated by an
ASCII newline character ("<code>\n</code>"). There can be multiple requests over one connected session.
All requests contain a field named <code>request</code> which contains a string
naming the request type ("<code>put</code>", "<code>get</code>", "<code>delete</code>", or "<code>abort</code>").
All responses contain a field named <code>status</code> which contains one of the
strings "<code>ok</code>", "<code>error</code>", or "<code>no-job</code>".
Where a request does not match the specification (i.e. if it is not valid JSON, is missing mandatory fields, or has
illegal values in any fields, or meets any other criteria described as "an error"), the server must send back an error response, which
has the string "<code>error</code>" in the <code>status</code> field, and optionally an <code>error</code> field containing
a textual error message, for example:
<pre><code>{"status":"error","error":"Unrecognised request type."}
</code></pre>
The server must not close the connection in response to an invalid request.
<h2>Requests</h2>
In all of the examples, "<code>&#x3C;--</code>" denotes requests and "<code>--></code>" denotes responses.
<h3><code>put</code></h3>
Examples:
<pre><code>&#x3C;-- {"request":"put","queue":"queue1","job":{...},"pri":123}
--> {"status":"ok","id":12345}
</code></pre>
Insert the given job into the given queue with the given priority.
The "<code>queue</code>" field must contain a valid queue name.
The "<code>job</code>" field can contain any JSON object.
The "<code>pri</code>" field must contain a valid priority.
The server must assign the job a unique ID, returned in the "<code>id</code>" field of the response.
<h3><code>get</code></h3>
Examples:
<pre><code>&#x3C;-- {"request":"get","queues":["queue1","queue2",...],"wait":true}
--> {"status":"ok","id":12345,"job":{...},"pri":123,"queue":"queue1"}

&#x3C;-- {"request":"get","queues":["queue3","queue4",...]}
--> {"status":"no-job"}
</code></pre>
Retrieve the highest-priority job that is currently waiting in any of the listed queues, and
remove it from its queue. The highest priority is the one with the highest numeric value (100 is a
higher priority than 90). Where multiple jobs share the same priority, it is fine to return them
in any order.
The "<code>queues</code>" field must contain a list of valid queue names.
<h4>No job in the queue</h4>
If there is currently no job waiting in any of the listed queues, and the optional <code>wait</code> flag
is present and <code>true</code>, then the server must not send any response until there is a job available,
at which point that job must be returned to one of the "waiting" clients.
If there is currently no job waiting in any of the listed queues, and the optional <code>wait</code> flag
is absent or <code>false</code>, then the server must send a response with the <code>no-job</code> status.
<h4>Job available</h4>
When a job is returned from a "<code>get</code>" request, the response must contain the fields
"<code>queue</code>", "<code>pri</code>", and "<code>job</code>", matching those from the "<code>put</code>" request that initially
created the job, in addition to the "<code>id</code>" field, matching the one returned in the response
to the initial "<code>put</code>" request.
Once a job is returned, the requesting client is considered to
be working on that job, until one of the following occurs:
<ul>
<li>the job is deleted by any client</li>
<li>the job is explicitly aborted by the client working on it</li>
<li>the job is automatically aborted when the client working on it disconnects</li>
</ul>
<h3><code>delete</code></h3>
Examples:
<pre><code>&#x3C;-- {"request":"delete","id":12345}
--> {"status":"ok"}

&#x3C;-- {"request":"delete","id":12346}
--> {"status":"no-job"}
</code></pre>
Delete the job with the given <code>id</code>, so that it can never be retrieved, aborted, or deleted again.
Valid from any client.
If a client attempts to delete a job ID that has not been allocated, or that has already
been deleted, send a response with the <code>no-job</code> status.
Once a job has been deleted it ceases to exist. In particular this means it can no
longer be aborted or deleted by any client, and any client that was previously working on the job
(even if different to the client that deleted it) is no longer considered to be working on it.
<h3><code>abort</code></h3>
<pre><code>&#x3C;-- {"request":"abort","id":12345}
--> {"status":"ok"}

&#x3C;-- {"request":"abort","id":12346}
--> {"status":"no-job"}
</code></pre>
Put the job with the given <code>id</code> back in its queue. This request is only valid
from the client that is currently working on that job. It is an error for any client
to attempt to abort a job that it is not currently working on.
If a client attempts to abort a job ID that has not been assigned, or that has already
been deleted, send a response with the <code>no-job</code> status.
In addition to explicit aborting with the <code>abort</code> request, all jobs that a client is working on
are automatically aborted when that client disconnects.
<h2>Example session</h2>
In this example, the client inserts a job into <code>queue1</code>, retrieves the job from the
queue, aborts it, retrieves the same job again, deletes it, and finally attempts to retrieve
another job.
<pre><code>&#x3C;-- {"request":"put","queue":"queue1","job":{"title":"example-job"},"pri":123}
--> {"status":"ok","id":12345}
&#x3C;-- {"request":"get","queues":["queue1"]}
--> {"status":"ok","id":12345,"job":{"title":"example-job"},"pri":123,"queue":"queue1"}
&#x3C;-- {"request":"abort","id":12345}
--> {"status":"ok"}
&#x3C;-- {"request":"get","queues":["queue1"]}
--> {"status":"ok","id":12345,"job":{"title":"example-job"},"pri":123,"queue":"queue1"}
&#x3C;-- {"request":"delete","id":12345}
--> {"status":"ok"}
&#x3C;-- {"request":"get","queues":["queue1"]}
--> {"status":"no-job"}
&#x3C;-- {"request":"get","queues":["queue1"],"wait":true}
[...]
</code></pre>
<h2>Limits</h2>
Support at least 1000 simultaneous clients and at least 50000 simultaneous pending jobs.
A job can be any JSON object.
A job ID is an integer and must uniquely identify a job, and the server may not reuse a job ID even after the job is deleted
(but it's fine to reuse them every time the server restarts).
A queue name is any JSON string.
A job priority is any non-negative integer.

Job Centre

The Elves at the North Pole have been so busy [saving Christmas](https://adventofcode.com/) that
they haven't found time to properly secure
the work orders for the Christmas toy workshop! They've invented a quick and dirty obfuscation scheme to obscure the data from prying eyes.

**Warning: This protocol is irrecoverably flawed. Don't use it in real life. The Elves are dumb, but you don't have to be.
Read more about [rolling your own crypto](https://loup-vaillant.fr/articles/rolling-your-own-crypto).**

## Application layer

At the start of a session, a client connects using TCP and sends a "cipher spec", and all further communication over the session (both to and from the server)
is obfuscated using the cipher spec.

A client request is a line of ASCII text (terminated by a single newline character) containing a **comma-separated list of toys to make**, like so:

 10x toy car,15x dog on a string,4x inflatable motorcycle

To prioritise work in the toy workshop, the server must find out which toy from the request they need to make **the most copies of**, and then send that toy back, also
terminated with an ASCII newline character, like so:

 15x dog on a string

There can be multiple requests per session.

## Obfuscation layer

All communication is obfuscated by the "Insecure Sockets Layer", using the cipher spec supplied by the client when it first connected.

### Cipher spec

The cipher spec describes the **series of operations that were used to obfuscate the data**. The server must apply the same cipher
spec to encode its response stream. The server must apply the **inverse of the cipher spec** to decode the request stream.

The cipher spec is represented as a series of operations, with the operation types encoded by a single byte (and for `02` and `04`, another byte
encodes the operand), ending with a `00` byte, as follows:

 - `00`:
End of cipher spec.

 - `01`: `reversebits`:
Reverse the order of bits in the byte, so the least-significant bit becomes the most-significant bit, the 2nd-least-significant becomes the 2nd-most-significant, and so on.

 - `02 N`: `xor(N)`:
XOR the byte by the value `N`. Note that 0 is a valid value for `N`.

 - `03`: `xorpos`:
XOR the byte by its position in the stream, starting from 0.

 - `04 N`: `add(N)`:
Add `N` to the byte, modulo 256. Note that 0 is a valid value for `N`, and addition wraps, so that `255+1=0`, `255+2=1`, and so on.

 - `05`: `addpos`:
Add the position in the stream to the byte, modulo 256, starting from 0. Addition wraps, so that `255+1=0`, `255+2=1`, and so on.

For the purposes of the `xorpos` and `addpos` operations, note that there is
a **separate stream position counter** for the client-sent and server-sent streams, with each one starting at 0, and the counter is *not* reset to 0 at the
end of each request or response.

### No-op ciphers

If a client tries to use a cipher that leaves every byte of input unchanged,
the server must **immediately disconnect without sending any data back**.
Examples of no-op ciphers include (but are not limited to):

 - empty cipher spec (`00`)
 - `xor(0)` (`02 00 00`)
 - `xor(X),xor(X)` for any `X` (e.g. `02 ab 02 ab 00`)
 - `reversebits,reversebits` (`01 01 00`)
 - `xor(A),xor(B),xor(C)`, where `A|B=C` (e.g. `02 a0 02 0b 02 ab 00`)

### Example cipher specs

#### `xor(1),reversebits`

The cipher spec `xor(1),reversebits` would be represented in hexadecimal as `02 01 01 00`:

 02 01 xor(1)
 01 reversebits
 00 end of cipher spec

It would encode the message "`hello`" in hexadecimal from `68 65 6c 6c 6f` to `96 26 b6 b6 76`:

 pos: 0 1 2 3 4
 message: h e l l o
 hex: 68 65 6c 6c 6f

 xor(1): 69 64 6d 6d 6e
 reversebits: 96 26 b6 b6 76

#### `addpos,addpos`

The cipher spec `addpos,addpos` would be represented in hexadecimal as `05 05 00`:

 05 addpos
 05 addpos
 00 end of cipher spec

It would encode the message "`hello`" in hexadecimal from `68 65 6c 6c 6f` to `68 67 70 72 77`:

 pos: 0 1 2 3 4
 message: h e l l o
 hex: 68 65 6c 6c 6f

 addpos: 68 66 6e 6f 73
 addpos: 68 67 70 72 77

## Example session

Example session at application layer ("`-->`" denotes lines from the server to the client, and "`<--`" denotes lines from the client to the server):

 <-- 4x dog,5x car
 --> 5x car
 <-- 3x rat,2x cat
 --> 3x rat

The same session after obfuscation, in hexadecimal, might look like this, with
cipher spec `xor(123),addpos,reversebits` ("`-->`" denotes data from the server to the client, and "`<--`" denotes data from the client to the server):

 <-- 02 7b 05 01 00 xor(123),addpos,reversebits
 <-- f2 20 ba 44 18 84 ba aa d0 26 44 a4 a8 7e 4x dog,5x car\n
 --> 72 20 ba d8 78 70 ee 5x car\n
 <-- 6a 48 d6 58 34 44 d6 7a 98 4e 0c cc 94 31 3x rat,2x cat\n
 --> f2 d0 26 c8 a4 d8 7e 3x rat\n

## Limits

Make sure you support at least 10 simultaneous clients.

Clients won't send lines longer than 5000 characters.

Clients won't send cipher specs whose encoding is longer than 80 bytes.

Clients won't try to use illegal cipher specs (e.g. `07 00` is illegal,
because `07` is not a valid cipher spec operation).

Clients won't send requests that are not a comma-separated list of toys,
starting with an ASCII-formatted integer followed by an "`x`" character.

If multiple toys share the maximum number, you can break the tie arbitrarily.

There will always be fewer than 2^31 copies required for any given toy.

The empty request is not a valid request.

As the Elves are so busy, they don't have time to worry about pesky edge cases. In response to invalid input
the server is free to do nothing, crash, or vanish in a puff of logic.

The Elves at the North Pole have been so busy <a href="https://adventofcode.com/">saving Christmas</a> that
they haven't found time to properly secure
the work orders for the Christmas toy workshop! They've invented a quick and dirty obfuscation scheme to obscure the data from prying eyes.
Warning: This protocol is irrecoverably flawed. Don't use it in real life. The Elves are dumb, but you don't have to be.
Read more about <a href="https://loup-vaillant.fr/articles/rolling-your-own-crypto">rolling your own crypto</a>.
<h2>Application layer</h2>
At the start of a session, a client connects using TCP and sends a "cipher spec", and all further communication over the session (both to and from the server)
is obfuscated using the cipher spec.
A client request is a line of ASCII text (terminated by a single newline character) containing a comma-separated list of toys to make, like so:
<pre><code>10x toy car,15x dog on a string,4x inflatable motorcycle
</code></pre>
To prioritise work in the toy workshop, the server must find out which toy from the request they need to make the most copies of, and then send that toy back, also
terminated with an ASCII newline character, like so:
<pre><code>15x dog on a string
</code></pre>
There can be multiple requests per session.
<h2>Obfuscation layer</h2>
All communication is obfuscated by the "Insecure Sockets Layer", using the cipher spec supplied by the client when it first connected.
<h3>Cipher spec</h3>
The cipher spec describes the series of operations that were used to obfuscate the data. The server must apply the same cipher
spec to encode its response stream. The server must apply the inverse of the cipher spec to decode the request stream.
The cipher spec is represented as a series of operations, with the operation types encoded by a single byte (and for <code>02</code> and <code>04</code>, another byte
encodes the operand), ending with a <code>00</code> byte, as follows:
<ul>
<li>
<code>00</code>:
End of cipher spec.
</li>
<li>
<code>01</code>: <code>reversebits</code>:
Reverse the order of bits in the byte, so the least-significant bit becomes the most-significant bit, the 2nd-least-significant becomes the 2nd-most-significant, and so on.
</li>
<li>
<code>02 N</code>: <code>xor(N)</code>:
XOR the byte by the value <code>N</code>. Note that 0 is a valid value for <code>N</code>.
</li>
<li>
<code>03</code>: <code>xorpos</code>:
XOR the byte by its position in the stream, starting from 0.
</li>
<li>
<code>04 N</code>: <code>add(N)</code>:
Add <code>N</code> to the byte, modulo 256. Note that 0 is a valid value for <code>N</code>, and addition wraps, so that <code>255+1=0</code>, <code>255+2=1</code>, and so on.
</li>
<li>
<code>05</code>: <code>addpos</code>:
Add the position in the stream to the byte, modulo 256, starting from 0. Addition wraps, so that <code>255+1=0</code>, <code>255+2=1</code>, and so on.
</li>
</ul>
For the purposes of the <code>xorpos</code> and <code>addpos</code> operations, note that there is
a separate stream position counter for the client-sent and server-sent streams, with each one starting at 0, and the counter is not reset to 0 at the
end of each request or response.
<h3>No-op ciphers</h3>
If a client tries to use a cipher that leaves every byte of input unchanged,
the server must immediately disconnect without sending any data back.
Examples of no-op ciphers include (but are not limited to):
<ul>
<li>empty cipher spec (<code>00</code>)</li>
<li><code>xor(0)</code> (<code>02 00 00</code>)</li>
<li><code>xor(X),xor(X)</code> for any <code>X</code> (e.g. <code>02 ab 02 ab 00</code>)</li>
<li><code>reversebits,reversebits</code> (<code>01 01 00</code>)</li>
<li><code>xor(A),xor(B),xor(C)</code>, where <code>A|B=C</code> (e.g. <code>02 a0 02 0b 02 ab 00</code>)</li>
</ul>
<h3>Example cipher specs</h3>
<h4><code>xor(1),reversebits</code></h4>
The cipher spec <code>xor(1),reversebits</code> would be represented in hexadecimal as <code>02 01 01 00</code>:
<pre><code>02 01 xor(1)
01 reversebits
00 end of cipher spec
</code></pre>
It would encode the message "<code>hello</code>" in hexadecimal from <code>68 65 6c 6c 6f</code> to <code>96 26 b6 b6 76</code>:
<pre><code>pos: 0 1 2 3 4
message: h e l l o
hex: 68 65 6c 6c 6f

xor(1): 69 64 6d 6d 6e
reversebits: 96 26 b6 b6 76
</code></pre>
<h4><code>addpos,addpos</code></h4>
The cipher spec <code>addpos,addpos</code> would be represented in hexadecimal as <code>05 05 00</code>:
<pre><code>05 addpos
05 addpos
00 end of cipher spec
</code></pre>
It would encode the message "<code>hello</code>" in hexadecimal from <code>68 65 6c 6c 6f</code> to <code>68 67 70 72 77</code>:
<pre><code>pos: 0 1 2 3 4
message: h e l l o
hex: 68 65 6c 6c 6f

addpos: 68 66 6e 6f 73
addpos: 68 67 70 72 77
</code></pre>
<h2>Example session</h2>
Example session at application layer ("<code>--></code>" denotes lines from the server to the client, and "<code>&#x3C;--</code>" denotes lines from the client to the server):
<pre><code>&#x3C;-- 4x dog,5x car
--> 5x car
&#x3C;-- 3x rat,2x cat
--> 3x rat
</code></pre>
The same session after obfuscation, in hexadecimal, might look like this, with
cipher spec <code>xor(123),addpos,reversebits</code> ("<code>--></code>" denotes data from the server to the client, and "<code>&#x3C;--</code>" denotes data from the client to the server):
<pre><code>&#x3C;-- 02 7b 05 01 00 xor(123),addpos,reversebits
&#x3C;-- f2 20 ba 44 18 84 ba aa d0 26 44 a4 a8 7e 4x dog,5x car\n
--> 72 20 ba d8 78 70 ee 5x car\n
&#x3C;-- 6a 48 d6 58 34 44 d6 7a 98 4e 0c cc 94 31 3x rat,2x cat\n
--> f2 d0 26 c8 a4 d8 7e 3x rat\n
</code></pre>
<h2>Limits</h2>
Make sure you support at least 10 simultaneous clients.
Clients won't send lines longer than 5000 characters.
Clients won't send cipher specs whose encoding is longer than 80 bytes.
Clients won't try to use illegal cipher specs (e.g. <code>07 00</code> is illegal,
because <code>07</code> is not a valid cipher spec operation).
Clients won't send requests that are not a comma-separated list of toys,
starting with an ASCII-formatted integer followed by an "<code>x</code>" character.
If multiple toys share the maximum number, you can break the tie arbitrarily.
There will always be fewer than 2^31 copies required for any given toy.
The empty request is not a valid request.
As the Elves are so busy, they don't have time to worry about pesky edge cases. In response to invalid input
the server is free to do nothing, crash, or vanish in a puff of logic.

Insecure Sockets Layer

We're going to be writing a simple network server to reverse the characters within lines of ASCII text. For example,
we'll turn "hello" into "olleh".

There's just one snag: we've never heard of TCP! Instead, we've designed our own
connection-oriented byte stream protocol that runs on top of UDP, called "Line Reversal Control Protocol",
or **LRCP** for short.

The goal of LRCP is to turn unreliable and out-of-order UDP packets into a pair of **reliable and in-order byte
streams**. To achieve this, it maintains a per-session **payload length counter on each side**, labels all payload transmissions with their
**position in the overall stream**, and retransmits any data that has been dropped. A sender detects that a packet has been dropped either by not receiving an
acknowledgment within an expected time window, or by receiving a duplicate of a prior acknowledgement.

Client sessions are identified by a numeric *session* token which is supplied by the client. You can assume that **session tokens
uniquely identify clients**, and that the peer for any given session is at a fixed IP address and port number.

## Messages

Messages are sent in **UDP packets**. Each UDP packet contains a single LRCP message. Each message consists of a series of
**values separated by forward slash** characters (`"/"`), and starts and ends with a forward slash character, like so:

 /data/1234567/0/hello/

The first field is a string specifying the message type (here, "`data`"). The remaining fields depend on the message type. Numeric fields are represented
as ASCII text.

#### Validation

When the server receives an illegal packet it must silently **ignore the packet** instead of interpreting it as LRCP.

1. Packet contents must begin with a forward slash, end with a forward slash, have a valid message type, and have the
correct number of fields for the message type.
2. Numeric field values must be smaller than 2147483648. This means sessions are limited to 2 billion
bytes of data transferred in each direction.
3. LRCP messages must be smaller than 1000 bytes. You might have to break up data into multiple
`data` messages in order to fit it below this limit.

#### Parameters

 - **retransmission timeout**: the time to wait before retransmitting a message.
 Suggested default value: **3 seconds**.

 - **session expiry timeout**: the time to wait before accepting that a peer has disappeared, in the
 event that no responses are being received. Suggested default value: **60 seconds**.

### 1. `/connect/SESSION/`

This message is sent by a client, to a server, to request that a session is opened. The
`SESSION` field must be a non-negative integer.

If a client does not receive a response to a `connect` message within the **retransmission timeout** (e.g. the
request or response may have been dropped), it will re-send the `connect` message, multiple times if necessary.

For the purposes of the Line Reversal application, your server will never need to initiate the opening of any sessions.

#### When you receive a `connect` message

1. If no session with this token is open: open one, and associate it with the IP address and port number that the UDP packet originated from.
2. Send `/ack/SESSION/0/` to let the client know that the session is open (do this even if it is a duplicate `connect`, because the first `ack` may have been dropped).

Example: open session number 1234567:

 <-- /connect/1234567/
 --> /ack/1234567/0/

### 2. `/data/SESSION/POS/DATA/`

This message transmits payload data.
The `POS` field must be a non-negative integer
representing the position in the stream that the `DATA` belongs.

Where the `DATA` contains forward slash (`"/"`) or backslash (`"\"`)
characters, the sender must escape the slashes by prepending them each with a single backslash character (`"foo/bar\baz"` becomes `"foo\/bar\\baz"`).
This escaping must be reversed by the recipient before passing it to the application layer.
All unescaped characters are interpreted as literal characters, including control characters such as newline characters.

The `POS` field refers to the position in the stream of **unescaped application-layer bytes**, not the escaped data passed in LRCP.

Behaviour is undefined if a peer sends payload data that overlaps with payload data you've already received, but differs from it.

When you want to send payload data, send it as a `data` packet. If the payload you sent hasn't been acknowledged within the **retransmission timeout**, send it again.
Do this multiple times if necessary.
If the data hasn't been acknowledged within the **session expiry timeout**,
consider the session closed.

#### When you receive a `data` message

1. If the session is not open: send `/close/SESSION/` and stop.
2. If you've already received everything up to `POS`: unescape "`\\`" and "`\/`", find the total `LENGTH` of unescaped data that you've already received (including the data in this message, if any), send `/ack/SESSION/LENGTH/`, and pass on the new data (if any) to the application layer.
3. If you have not received everything up to `POS`: send a duplicate of your previous `ack` (or `/ack/SESSION/0/` if none), saying how much you *have* received, to provoke the other side to retransmit whatever you're missing.

Example: transmit "`hello`", starting at the very start of session 1234567:

 <-- /data/1234567/0/hello/
 --> /ack/1234567/5/

Example: transmit a single forward slash, starting at the very start of session 1234568:

 <-- /data/1234568/0/\//
 --> /ack/1234568/1/ # note: 1, not 2, because the sequence "\/" only represents 1 byte of data

### 3. `/ack/SESSION/LENGTH/`

This message acknowledges receipt of payload data. The `LENGTH` field must be a non-negative integer
telling the other side how many bytes of payload have been successfully received so far.

#### When you receive an `ack` message

1. If the `SESSION` is not open: send `/close/SESSION/` and stop.
2. If the `LENGTH` value is *not larger than* the largest `LENGTH` value in any `ack` message you've received on this session so far: do nothing and stop (assume it's a duplicate ack that got delayed).
3. If the `LENGTH` value is *larger than* the total amount of payload you've sent: the peer is misbehaving, close the session.
4. If the `LENGTH` value is *smaller than* the total amount of payload you've sent: retransmit all payload data after the first `LENGTH` bytes.
5. If the `LENGTH` value is *equal to* the total amount of payload you've sent: don't send any reply.

Example: acknowledge reading the first 1024 bytes of content, on session 1234567:

 /ack/1234567/1024/

### 4. `/close/SESSION/`

This message requests that the session is closed. This can be initiated by either the server or the client.

For the purposes of the Line Reversal application, your server will never need to initiate the closing of any sessions.

When you receive a `/close/SESSION/` message, send a matching `close` message back.

Example: close session 1234567:

 <-- /close/1234567/
 --> /close/1234567/

## Example session

The client connects with session token 12345, sends "Hello, world!" and then closes the session.

 <-- /connect/12345/
 --> /ack/12345/0/
 <-- /data/12345/0/Hello, world!/
 --> /ack/12345/13/
 <-- /close/12345/
 --> /close/12345/

## Application layer: Line Reversal

Accept LRCP connections. Make sure you support at least 20 simultaneous sessions.

Reverse each line of input. Each line will be no longer than 10,000 characters. Lines contain ASCII text and are delimited
by ASCII newline characters ("`\n`").

From the LRCP perspective, a given `data` message can contain bytes for one or more lines in a single packet, it
doesn't matter how they're chunked, and a line isn't complete until the newline character. The abstraction presented to the application
layer should be that of a pair of **byte streams** (one for sending and one for receiving).

Example session at application layer ("`-->`" denotes lines from the server to the client, and "`<--`" denotes lines from the client to the server):

 <-- hello
 --> olleh
 <-- Hello, world!
 --> !dlrow ,olleH

The same session at the LRCP layer might look like this ("`\n`" denotes
an ASCII newline character, "`-->`" denotes UDP packets from the server to the client, and "`<--`" denotes UDP packets from the client to the server):

 <-- /connect/12345/
 --> /ack/12345/0/
 <-- /data/12345/0/hello\n/
 --> /ack/12345/6/
 --> /data/12345/0/olleh\n/
 <-- /ack/12345/6/
 <-- /data/12345/6/Hello, world!\n/
 --> /ack/12345/20/
 --> /data/12345/6/!dlrow ,olleH\n/
 <-- /ack/12345/20/
 <-- /close/12345/
 --> /close/12345/

We're going to be writing a simple network server to reverse the characters within lines of ASCII text. For example,
we'll turn "hello" into "olleh".
There's just one snag: we've never heard of TCP! Instead, we've designed our own
connection-oriented byte stream protocol that runs on top of UDP, called "Line Reversal Control Protocol",
or LRCP for short.
The goal of LRCP is to turn unreliable and out-of-order UDP packets into a pair of reliable and in-order byte
streams. To achieve this, it maintains a per-session payload length counter on each side, labels all payload transmissions with their
position in the overall stream, and retransmits any data that has been dropped. A sender detects that a packet has been dropped either by not receiving an
acknowledgment within an expected time window, or by receiving a duplicate of a prior acknowledgement.
Client sessions are identified by a numeric session token which is supplied by the client. You can assume that session tokens
uniquely identify clients, and that the peer for any given session is at a fixed IP address and port number.
<h2>Messages</h2>
Messages are sent in UDP packets. Each UDP packet contains a single LRCP message. Each message consists of a series of
values separated by forward slash characters (<code>"/"</code>), and starts and ends with a forward slash character, like so:
<pre><code>/data/1234567/0/hello/
</code></pre>
The first field is a string specifying the message type (here, "<code>data</code>"). The remaining fields depend on the message type. Numeric fields are represented
as ASCII text.
<h4>Validation</h4>
When the server receives an illegal packet it must silently ignore the packet instead of interpreting it as LRCP.
<ol>
<li>Packet contents must begin with a forward slash, end with a forward slash, have a valid message type, and have the
correct number of fields for the message type.</li>
<li>Numeric field values must be smaller than 2147483648. This means sessions are limited to 2 billion
bytes of data transferred in each direction.</li>
<li>LRCP messages must be smaller than 1000 bytes. You might have to break up data into multiple
<code>data</code> messages in order to fit it below this limit.</li>
</ol>
<h4>Parameters</h4>
<ul>
<li>
retransmission timeout: the time to wait before retransmitting a message.
Suggested default value: 3 seconds.
</li>
<li>
session expiry timeout: the time to wait before accepting that a peer has disappeared, in the
event that no responses are being received. Suggested default value: 60 seconds.
</li>
</ul>
<h3>1. <code>/connect/SESSION/</code></h3>
This message is sent by a client, to a server, to request that a session is opened. The
<code>SESSION</code> field must be a non-negative integer.
If a client does not receive a response to a <code>connect</code> message within the retransmission timeout (e.g. the
request or response may have been dropped), it will re-send the <code>connect</code> message, multiple times if necessary.
For the purposes of the Line Reversal application, your server will never need to initiate the opening of any sessions.
<h4>When you receive a <code>connect</code> message</h4>
<ol>
<li>If no session with this token is open: open one, and associate it with the IP address and port number that the UDP packet originated from.</li>
<li>Send <code>/ack/SESSION/0/</code> to let the client know that the session is open (do this even if it is a duplicate <code>connect</code>, because the first <code>ack</code> may have been dropped).</li>
</ol>
Example: open session number 1234567:
<pre><code>&#x3C;-- /connect/1234567/
--> /ack/1234567/0/
</code></pre>
<h3>2. <code>/data/SESSION/POS/DATA/</code></h3>
This message transmits payload data.
The <code>POS</code> field must be a non-negative integer
representing the position in the stream that the <code>DATA</code> belongs.
Where the <code>DATA</code> contains forward slash (<code>"/"</code>) or backslash (<code>"\"</code>)
characters, the sender must escape the slashes by prepending them each with a single backslash character (<code>"foo/bar\baz"</code> becomes <code>"foo\/bar\\baz"</code>).
This escaping must be reversed by the recipient before passing it to the application layer.
All unescaped characters are interpreted as literal characters, including control characters such as newline characters.
The <code>POS</code> field refers to the position in the stream of unescaped application-layer bytes, not the escaped data passed in LRCP.
Behaviour is undefined if a peer sends payload data that overlaps with payload data you've already received, but differs from it.
When you want to send payload data, send it as a <code>data</code> packet. If the payload you sent hasn't been acknowledged within the retransmission timeout, send it again.
Do this multiple times if necessary.
If the data hasn't been acknowledged within the session expiry timeout,
consider the session closed.
<h4>When you receive a <code>data</code> message</h4>
<ol>
<li>If the session is not open: send <code>/close/SESSION/</code> and stop.</li>
<li>If you've already received everything up to <code>POS</code>: unescape "<code>\\</code>" and "<code>\/</code>", find the total <code>LENGTH</code> of unescaped data that you've already received (including the data in this message, if any), send <code>/ack/SESSION/LENGTH/</code>, and pass on the new data (if any) to the application layer.</li>
<li>If you have not received everything up to <code>POS</code>: send a duplicate of your previous <code>ack</code> (or <code>/ack/SESSION/0/</code> if none), saying how much you have received, to provoke the other side to retransmit whatever you're missing.</li>
</ol>
Example: transmit "<code>hello</code>", starting at the very start of session 1234567:
<pre><code>&#x3C;-- /data/1234567/0/hello/
--> /ack/1234567/5/
</code></pre>
Example: transmit a single forward slash, starting at the very start of session 1234568:
<pre><code>&#x3C;-- /data/1234568/0/\//
--> /ack/1234568/1/ # note: 1, not 2, because the sequence "\/" only represents 1 byte of data
</code></pre>
<h3>3. <code>/ack/SESSION/LENGTH/</code></h3>
This message acknowledges receipt of payload data. The <code>LENGTH</code> field must be a non-negative integer
telling the other side how many bytes of payload have been successfully received so far.
<h4>When you receive an <code>ack</code> message</h4>
<ol>
<li>If the <code>SESSION</code> is not open: send <code>/close/SESSION/</code> and stop.</li>
<li>If the <code>LENGTH</code> value is not larger than the largest <code>LENGTH</code> value in any <code>ack</code> message you've received on this session so far: do nothing and stop (assume it's a duplicate ack that got delayed).</li>
<li>If the <code>LENGTH</code> value is larger than the total amount of payload you've sent: the peer is misbehaving, close the session.</li>
<li>If the <code>LENGTH</code> value is smaller than the total amount of payload you've sent: retransmit all payload data after the first <code>LENGTH</code> bytes.</li>
<li>If the <code>LENGTH</code> value is equal to the total amount of payload you've sent: don't send any reply.</li>
</ol>
Example: acknowledge reading the first 1024 bytes of content, on session 1234567:
<pre><code>/ack/1234567/1024/
</code></pre>
<h3>4. <code>/close/SESSION/</code></h3>
This message requests that the session is closed. This can be initiated by either the server or the client.
For the purposes of the Line Reversal application, your server will never need to initiate the closing of any sessions.
When you receive a <code>/close/SESSION/</code> message, send a matching <code>close</code> message back.
Example: close session 1234567:
<pre><code>&#x3C;-- /close/1234567/
--> /close/1234567/
</code></pre>
<h2>Example session</h2>
The client connects with session token 12345, sends "Hello, world!" and then closes the session.
<pre><code>&#x3C;-- /connect/12345/
--> /ack/12345/0/
&#x3C;-- /data/12345/0/Hello, world!/
--> /ack/12345/13/
&#x3C;-- /close/12345/
--> /close/12345/
</code></pre>
<h2>Application layer: Line Reversal</h2>
Accept LRCP connections. Make sure you support at least 20 simultaneous sessions.
Reverse each line of input. Each line will be no longer than 10,000 characters. Lines contain ASCII text and are delimited
by ASCII newline characters ("<code>\n</code>").
From the LRCP perspective, a given <code>data</code> message can contain bytes for one or more lines in a single packet, it
doesn't matter how they're chunked, and a line isn't complete until the newline character. The abstraction presented to the application
layer should be that of a pair of byte streams (one for sending and one for receiving).
Example session at application layer ("<code>--></code>" denotes lines from the server to the client, and "<code>&#x3C;--</code>" denotes lines from the client to the server):
<pre><code>&#x3C;-- hello
--> olleh
&#x3C;-- Hello, world!
--> !dlrow ,olleH
</code></pre>
The same session at the LRCP layer might look like this ("<code>\n</code>" denotes
an ASCII newline character, "<code>--></code>" denotes UDP packets from the server to the client, and "<code>&#x3C;--</code>" denotes UDP packets from the client to the server):
<pre><code>&#x3C;-- /connect/12345/
--> /ack/12345/0/
&#x3C;-- /data/12345/0/hello\n/
--> /ack/12345/6/
--> /data/12345/0/olleh\n/
&#x3C;-- /ack/12345/6/
&#x3C;-- /data/12345/6/Hello, world!\n/
--> /ack/12345/20/
--> /data/12345/6/!dlrow ,olleH\n/
&#x3C;-- /ack/12345/20/
&#x3C;-- /close/12345/
--> /close/12345/
</code></pre>

Line Reversal

Motorists on Freedom Island drive as fast as they like.
Sadly, this has led to a large number of crashes,
so the islanders have agreed to impose speed limits. The speed limits will be enforced via
an *average speed check*: [Automatic Number Plate Recognition](https://en.wikipedia.org/wiki/Automatic_number-plate_recognition) cameras will
be installed at various points on the road network. The islanders will
use a computer system to collect
the data, detect cars travelling in excess of the speed limit, and send
tickets to be dispatched to the drivers. The islanders can't agree on which one of them should
write the software, so they've engaged an external contractor to do it: that's where you come in.

## Overview

You need to build a server to coordinate enforcement of **average speed limits** on the
Freedom Island road network.

Your server will handle two types of client: *cameras* and *ticket dispatchers*.

Clients connect over TCP and speak a protocol using a **binary format**.
Make sure you support at least 150 simultaneous clients.

### Cameras

Each *camera* is on a specific
road, at a specific location, and has a specific speed limit. Each camera provides this information
when it connects to the server.
Cameras report each number plate that they observe, along with the timestamp that they observed it.
Timestamps are exactly the same as [Unix timestamps](https://en.wikipedia.org/wiki/Unix_time) (counting seconds since 1st of January 1970), except that they are **unsigned**.

### Ticket dispatchers

Each *ticket dispatcher* is responsible for some number of roads. When the server finds that a car was detected
at 2 points on the same road with an average speed in excess of the speed limit (`speed = distance / time`), it will find the
responsible ticket dispatcher and send it a ticket for the offending car, so that the ticket
dispatcher can perform the necessary legal rituals.

### Roads

Each road in the network is identified by a number from 0 to 65535.
A single road has the same speed limit at every point on the road.
Positions
on the roads are identified by the number of miles from the start of the road.
Remarkably, all speed cameras are positioned at exact integer numbers of miles from the start of the road.

### Cars

Each *car* has a specific number plate represented as an uppercase alphanumeric string.

## Data types

The protocol uses a binary data format, with the following primitive types:

### `u8`, `u16`, `u32`

These types represent unsigned integers of 8-bit, 16-bit, and 32-bit size, respectively.
They are transmitted in network byte-order ([big endian](https://en.wikipedia.org/wiki/Endianness)).

Examples:

 Type | Hex data | Value
 -------------------------------
 u8 | 20 | 32
 u8 | e3 | 227
 u16 | 00 20 | 32
 u16 | 12 45 | 4677
 u16 | a8 23 | 43043
 u32 | 00 00 00 20 | 32
 u32 | 00 00 12 45 | 4677
 u32 | a6 a9 b5 67 | 2796139879

## `str`

A string of characters in a **[length-prefixed](https://en.wikipedia.org/wiki/String_(computer_science)#Length-prefixed) format**.
A `str` is transmitted as a single `u8` containing the string's
length (0 to 255),
followed by that many bytes of `u8`, in order, containing [ASCII](https://en.wikipedia.org/wiki/ASCII)
character codes.

Examples:

 Type | Hex data | Value
 ----------------------------------------------
 str | 00 | ""
 str | 03 66 6f 6f | "foo"
 str | 08 45 6C 62 65 72 65 74 68 | "Elbereth"

## Message types

Each message starts with a **single `u8` specifying the message type**.
This is followed by the message contents, as detailed below.

**Field names** are not transmitted. You know which field is which by **the order they are in**.

There is no message delimiter. Messages are simply **concatenated
together with no padding**. The 2nd message starts with the byte that
comes immediately after the final byte of the 1st message, and so on.

In the examples shown below, the hexadecimal data is broken across several lines
to aid comprehension, but of course in the real protocol there is no such
distinction.

It is an error for a client to send the server a message with any
*message type* value that is **not listed below with "Client-\>Server"**.

### `0x10`: Error (Server->Client)

Fields:

 - `msg: str`

When the client does something that this protocol specification declares "an error", the server
must send the client an appropriate `Error` message and immediately disconnect
that client.

Examples:

 Hexadecimal: Decoded:
 10 Error{
 03 62 61 64 msg: "bad"
 }
 
 10 Error{
 0b 69 6c 6c 65 67 61 6c 20 6d 73 67 msg: "illegal msg"
 }

### `0x20`: Plate (Client->Server)

Fields:

 - `plate: str`
 - `timestamp: u32`

This client has observed the **given number plate** at its location, at the **given
timestamp**. Cameras can send observations in any order they like, and after any delay they like, so you won't necessarily receive
observations in the order that they were made. This means a later `Plate` message may
correspond to an earlier observation (with lower `timestamp`) **even if they're both from the same camera**.
You need to take observation timestamps from the `Plate` message. Ignore your local system clock.

It is an error for a client that has not identified itself as a *camera* (see `IAmCamera` below)
to send a `Plate` message.

Examples:

 Hexadecimal: Decoded:
 20 Plate{
 04 55 4e 31 58 plate: "UN1X",
 00 00 03 e8 timestamp: 1000
 }
 
 20 Plate{
 07 52 45 30 35 42 4b 47 plate: "RE05BKG",
 00 01 e2 40 timestamp: 123456
 }

### `0x21`: Ticket (Server->Client)

Fields:

 - `plate: str` 
 - `road: u16`
 - `mile1: u16`
 - `timestamp1: u32`
 - `mile2: u16`
 - `timestamp2: u32`
 - `speed: u16` (100x miles per hour)

When the server detects that a car's average speed exceeded the speed limit between 2 observations,
it generates a `Ticket` message detailing the number plate of the car (`plate`),
the road number of the cameras (`road`), the positions of the cameras (`mile1`, `mile2`),
the timestamps of the observations (`timestamp1`, `timestamp2`), and the inferred
average speed of the car **multiplied by 100**, and expressed as an integer
(`speed`).

`mile1` and `timestamp1` must refer to the **earlier** of the 2 observations (the smaller
timestamp), and `mile2` and `timestamp2` must refer to the **later** of the 2 observations
(the larger timestamp).

The server sends the ticket to a dispatcher for the corresponding *road*.

Examples:

 Hexadecimal: Decoded:
 21 Ticket{
 04 55 4e 31 58 plate: "UN1X",
 00 42 road: 66,
 00 64 mile1: 100,
 00 01 e2 40 timestamp1: 123456,
 00 6e mile2: 110,
 00 01 e3 a8 timestamp2: 123816,
 27 10 speed: 10000,
 }

 21 Ticket{
 07 52 45 30 35 42 4b 47 plate: "RE05BKG",
 01 70 road: 368,
 04 d2 mile1: 1234,
 00 0f 42 40 timestamp1: 1000000,
 04 d3 mile2: 1235,
 00 0f 42 7c timestamp2: 1000060,
 17 70 speed: 6000,
 }

### `0x40`: WantHeartbeat (Client->Server)

Fields:

 - `interval: u32` (deciseconds)

Request heartbeats.

The server must now send `Heartbeat` messages to this client at the given
interval, which is **specified in "deciseconds"**, of which there are 10 per second.
(So an interval of "25" would mean a `Heartbeat` message every 2.5 seconds). The heartbeats
help to assure the client that the server is still functioning, even in the absence
of any other communication.

An interval of 0 deciseconds means the client does not want to receive heartbeats (this
is the default setting).

It is an error for a client to send multiple `WantHeartbeat` messages on a single
connection.

Examples:

 Hexadecimal: Decoded:
 40 WantHeartbeat{
 00 00 00 0a interval: 10
 }
 
 40 WantHeartbeat{
 00 00 04 db interval: 1243
 }

### `0x41`: Heartbeat (Server->Client)

No fields.

Sent to a client at the interval requested by the client.

Example:

 Hexadecimal: Decoded:
 41 Heartbeat{}

### `0x80`: IAmCamera (Client->Server)

Fields:

 - `road: u16`
 - `mile: u16`
 - `limit: u16` (miles per hour)

This client is a
*camera*. The `road` field contains the road number that the camera
is on, `mile` contains the position of the camera, relative to
the start of the road,
and `limit` contains the speed limit of the road, in miles per hour.

It is an error for a client that has already identified itself as either a
*camera* or a *ticket dispatcher* to send an `IAmCamera` message.

Examples:

 Hexadecimal: Decoded:
 80 IAmCamera{
 00 42 road: 66,
 00 64 mile: 100,
 00 3c limit: 60,
 }
 
 80 IAmCamera{
 01 70 road: 368,
 04 d2 mile: 1234,
 00 28 limit: 40,
 }

### `0x81`: IAmDispatcher (Client->Server)

Fields:

 - `numroads: u8`
 - `roads: [u16]` (array of `u16`)

This client is a
*ticket dispatcher*. The `numroads` field says how many roads this dispatcher
is responsible for, and the `roads` field contains the road
numbers.

It is an error for a client that has already identified itself as either a
*camera* or a *ticket dispatcher* to send an `IAmDispatcher` message.

Examples:

 Hexadecimal: Decoded:
 81 IAmDispatcher{
 01 roads: [
 00 42 66
 ]
 }
 
 81 IAmDispatcher{
 03 roads: [
 00 42 66,
 01 70 368,
 13 88 5000
 ]
 }

## Example session

In this example session, 3 clients connect to the server. Clients 1 & 2 are cameras on road 123, with a 60 mph speed limit.
Client 3 is a ticket dispatcher
for road 123. The car with number plate **`UN1X`** was observed passing the first camera at timestamp 0, and passing the second camera
45 seconds later. It travelled **1 mile** in **45 seconds**, which means it was travelling at **80 mph**. This is in excess of the
speed limit, so a ticket is dispatched.

"`-->`" denotes messages from the server to the client,
and "`<--`" denotes messages from the client to the server.

### Client 1: camera at mile 8

 Hexadecimal:
 <-- 80 00 7b 00 08 00 3c
 <-- 20 04 55 4e 31 58 00 00 00 00
 
 Decoded:
 <-- IAmCamera{road: 123, mile: 8, limit: 60}
 <-- Plate{plate: "UN1X", timestamp: 0}

### Client 2: camera at mile 9

 Hexadecimal:
 <-- 80 00 7b 00 09 00 3c
 <-- 20 04 55 4e 31 58 00 00 00 2d

 Decoded:
 <-- IAmCamera{road: 123, mile: 9, limit: 60}
 <-- Plate{plate: "UN1X", timestamp: 45}

### Client 3: ticket dispatcher

 Hexadecimal:
 <-- 81 01 00 7b
 --> 21 04 55 4e 31 58 00 7b 00 08 00 00 00 00 00 09 00 00 00 2d 1f 40

 Decoded:
 <-- IAmDispatcher{roads: [123]}
 --> Ticket{plate: "UN1X", road: 123, mile1: 8, timestamp1: 0, mile2: 9, timestamp2: 45, speed: 8000}

## Details

### Dispatchers

When the server generates a ticket for a road that has multiple connected dispatchers,
the server may **choose between them arbitrarily**, but must **not ever send the same ticket
twice**.

If the server sends a ticket but the dispatcher disconnects before it receives it,
then **the ticket simply gets lost** and the driver escapes punishment.

If the server generates a ticket for a road that has no connected dispatcher, it
must **store the ticket** and deliver it **once a dispatcher for that road is available**.

### Unreliable cameras

Sometimes number plates aren't spotted (maybe they were obscured, or the image was blurry),
so a car can skip one or more cameras and reappear later on. You must still generate a ticket if its average speed exceeded the
limit between **any pair of observations on the same road**, even if the observations were not from adjacent cameras.

### No shortcuts

The fastest legal route between any pair of cameras that are on the same road is to use the road that those cameras are on;
you don't need to worry about falsely ticketing drivers who may have left a road and rejoined it.

### Only 1 ticket per car per day

The server may send **no more than 1 ticket** for any given car on any given day.

Where a ticket spans multiple days, the ticket is considered to apply to *every* day from
the start to the end day, including the end day. This means that where there is a choice of observations to include in a ticket, it is sometimes possible for the server to choose either to send a ticket for each day, or to send a single ticket that spans both days: either behaviour is acceptable. (But to maximise revenues, you may prefer to send as many tickets as possible).

Since timestamps [do not count leap seconds](https://en.wikipedia.org/wiki/Unix_time#Leap_seconds),
days are defined by `floor(timestamp / 86400)`.

### Rounding

It is **always required** to ticket a car that is exceeding the speed limit by 0.5 mph or more

In cases where the car is exceeding the speed limit by less than 0.5 mph, it is **acceptable to omit** the ticket.

It is **never acceptable** to ticket a car that had an average speed *below* the speed limit.

### Overflow

In principle, a car travelling in excess of 655.35 mph would cause the server to generate a ticket with
an incorrect speed. Fortunately nobody on Freedom Island has a fast enough car, so you don't need to
worry about it.

Motorists on Freedom Island drive as fast as they like.
Sadly, this has led to a large number of crashes,
so the islanders have agreed to impose speed limits. The speed limits will be enforced via
an average speed check: <a href="https://en.wikipedia.org/wiki/Automatic_number-plate_recognition">Automatic Number Plate Recognition</a> cameras will
be installed at various points on the road network. The islanders will
use a computer system to collect
the data, detect cars travelling in excess of the speed limit, and send
tickets to be dispatched to the drivers. The islanders can't agree on which one of them should
write the software, so they've engaged an external contractor to do it: that's where you come in.
<h2>Overview</h2>
You need to build a server to coordinate enforcement of average speed limits on the
Freedom Island road network.
Your server will handle two types of client: cameras and ticket dispatchers.
Clients connect over TCP and speak a protocol using a binary format.
Make sure you support at least 150 simultaneous clients.
<h3>Cameras</h3>
Each camera is on a specific
road, at a specific location, and has a specific speed limit. Each camera provides this information
when it connects to the server.
Cameras report each number plate that they observe, along with the timestamp that they observed it.
Timestamps are exactly the same as <a href="https://en.wikipedia.org/wiki/Unix_time">Unix timestamps</a> (counting seconds since 1st of January 1970), except that they are unsigned.
<h3>Ticket dispatchers</h3>
Each ticket dispatcher is responsible for some number of roads. When the server finds that a car was detected
at 2 points on the same road with an average speed in excess of the speed limit (<code>speed = distance / time</code>), it will find the
responsible ticket dispatcher and send it a ticket for the offending car, so that the ticket
dispatcher can perform the necessary legal rituals.
<h3>Roads</h3>
Each road in the network is identified by a number from 0 to 65535.
A single road has the same speed limit at every point on the road.
Positions
on the roads are identified by the number of miles from the start of the road.
Remarkably, all speed cameras are positioned at exact integer numbers of miles from the start of the road.
<h3>Cars</h3>
Each car has a specific number plate represented as an uppercase alphanumeric string.
<h2>Data types</h2>
The protocol uses a binary data format, with the following primitive types:
<h3><code>u8</code>, <code>u16</code>, <code>u32</code></h3>
These types represent unsigned integers of 8-bit, 16-bit, and 32-bit size, respectively.
They are transmitted in network byte-order (<a href="https://en.wikipedia.org/wiki/Endianness">big endian</a>).
Examples:
<pre><code>Type | Hex data | Value
-------------------------------
u8 | 20 | 32
u8 | e3 | 227
u16 | 00 20 | 32
u16 | 12 45 | 4677
u16 | a8 23 | 43043
u32 | 00 00 00 20 | 32
u32 | 00 00 12 45 | 4677
u32 | a6 a9 b5 67 | 2796139879
</code></pre>
<h2><code>str</code></h2>
A string of characters in a <a href="https://en.wikipedia.org/wiki/String_(computer_science)#Length-prefixed">length-prefixed</a> format.
A <code>str</code> is transmitted as a single <code>u8</code> containing the string's
length (0 to 255),
followed by that many bytes of <code>u8</code>, in order, containing <a href="https://en.wikipedia.org/wiki/ASCII">ASCII</a>
character codes.
Examples:
<pre><code>Type | Hex data | Value
----------------------------------------------
str | 00 | ""
str | 03 66 6f 6f | "foo"
str | 08 45 6C 62 65 72 65 74 68 | "Elbereth"
</code></pre>
<h2>Message types</h2>
Each message starts with a single <code>u8</code> specifying the message type.
This is followed by the message contents, as detailed below.
Field names are not transmitted. You know which field is which by the order they are in.
There is no message delimiter. Messages are simply concatenated
together with no padding. The 2nd message starts with the byte that
comes immediately after the final byte of the 1st message, and so on.
In the examples shown below, the hexadecimal data is broken across several lines
to aid comprehension, but of course in the real protocol there is no such
distinction.
It is an error for a client to send the server a message with any
message type value that is not listed below with "Client->Server".
<h3><code>0x10</code>: Error (Server->Client)</h3>
Fields:
<ul>
<li><code>msg: str</code></li>
</ul>
When the client does something that this protocol specification declares "an error", the server
must send the client an appropriate <code>Error</code> message and immediately disconnect
that client.
Examples:
<pre><code>Hexadecimal: Decoded:
10 Error{
03 62 61 64 msg: "bad"
 }

10 Error{
0b 69 6c 6c 65 67 61 6c 20 6d 73 67 msg: "illegal msg"
 }
</code></pre>
<h3><code>0x20</code>: Plate (Client->Server)</h3>
Fields:
<ul>
<li><code>plate: str</code></li>
<li><code>timestamp: u32</code></li>
</ul>
This client has observed the given number plate at its location, at the given
timestamp. Cameras can send observations in any order they like, and after any delay they like, so you won't necessarily receive
observations in the order that they were made. This means a later <code>Plate</code> message may
correspond to an earlier observation (with lower <code>timestamp</code>) even if they're both from the same camera.
You need to take observation timestamps from the <code>Plate</code> message. Ignore your local system clock.
It is an error for a client that has not identified itself as a camera (see <code>IAmCamera</code> below)
to send a <code>Plate</code> message.
Examples:
<pre><code>Hexadecimal: Decoded:
20 Plate{
04 55 4e 31 58 plate: "UN1X",
00 00 03 e8 timestamp: 1000
 }

20 Plate{
07 52 45 30 35 42 4b 47 plate: "RE05BKG",
00 01 e2 40 timestamp: 123456
 }
</code></pre>
<h3><code>0x21</code>: Ticket (Server->Client)</h3>
Fields:
<ul>
<li><code>plate: str</code></li>
<li><code>road: u16</code></li>
<li><code>mile1: u16</code></li>
<li><code>timestamp1: u32</code></li>
<li><code>mile2: u16</code></li>
<li><code>timestamp2: u32</code></li>
<li><code>speed: u16</code> (100x miles per hour)</li>
</ul>
When the server detects that a car's average speed exceeded the speed limit between 2 observations,
it generates a <code>Ticket</code> message detailing the number plate of the car (<code>plate</code>),
the road number of the cameras (<code>road</code>), the positions of the cameras (<code>mile1</code>, <code>mile2</code>),
the timestamps of the observations (<code>timestamp1</code>, <code>timestamp2</code>), and the inferred
average speed of the car multiplied by 100, and expressed as an integer
(<code>speed</code>).
<code>mile1</code> and <code>timestamp1</code> must refer to the earlier of the 2 observations (the smaller
timestamp), and <code>mile2</code> and <code>timestamp2</code> must refer to the later of the 2 observations
(the larger timestamp).
The server sends the ticket to a dispatcher for the corresponding road.
Examples:
<pre><code>Hexadecimal: Decoded:
21 Ticket{
04 55 4e 31 58 plate: "UN1X",
00 42 road: 66,
00 64 mile1: 100,
00 01 e2 40 timestamp1: 123456,
00 6e mile2: 110,
00 01 e3 a8 timestamp2: 123816,
27 10 speed: 10000,
 }

21 Ticket{
07 52 45 30 35 42 4b 47 plate: "RE05BKG",
01 70 road: 368,
04 d2 mile1: 1234,
00 0f 42 40 timestamp1: 1000000,
04 d3 mile2: 1235,
00 0f 42 7c timestamp2: 1000060,
17 70 speed: 6000,
 }
</code></pre>
<h3><code>0x40</code>: WantHeartbeat (Client->Server)</h3>
Fields:
<ul>
<li><code>interval: u32</code> (deciseconds)</li>
</ul>
Request heartbeats.
The server must now send <code>Heartbeat</code> messages to this client at the given
interval, which is specified in "deciseconds", of which there are 10 per second.
(So an interval of "25" would mean a <code>Heartbeat</code> message every 2.5 seconds). The heartbeats
help to assure the client that the server is still functioning, even in the absence
of any other communication.
An interval of 0 deciseconds means the client does not want to receive heartbeats (this
is the default setting).
It is an error for a client to send multiple <code>WantHeartbeat</code> messages on a single
connection.
Examples:
<pre><code>Hexadecimal: Decoded:
40 WantHeartbeat{
00 00 00 0a interval: 10
 }

40 WantHeartbeat{
00 00 04 db interval: 1243
 }
</code></pre>
<h3><code>0x41</code>: Heartbeat (Server->Client)</h3>
No fields.
Sent to a client at the interval requested by the client.
Example:
<pre><code>Hexadecimal: Decoded:
41 Heartbeat{}
</code></pre>
<h3><code>0x80</code>: IAmCamera (Client->Server)</h3>
Fields:
<ul>
<li><code>road: u16</code></li>
<li><code>mile: u16</code></li>
<li><code>limit: u16</code> (miles per hour)</li>
</ul>
This client is a
camera. The <code>road</code> field contains the road number that the camera
is on, <code>mile</code> contains the position of the camera, relative to
the start of the road,
and <code>limit</code> contains the speed limit of the road, in miles per hour.
It is an error for a client that has already identified itself as either a
camera or a ticket dispatcher to send an <code>IAmCamera</code> message.
Examples:
<pre><code>Hexadecimal: Decoded:
80 IAmCamera{
00 42 road: 66,
00 64 mile: 100,
00 3c limit: 60,
 }

80 IAmCamera{
01 70 road: 368,
04 d2 mile: 1234,
00 28 limit: 40,
 }
</code></pre>
<h3><code>0x81</code>: IAmDispatcher (Client->Server)</h3>
Fields:
<ul>
<li><code>numroads: u8</code></li>
<li><code>roads: [u16]</code> (array of <code>u16</code>)</li>
</ul>
This client is a
ticket dispatcher. The <code>numroads</code> field says how many roads this dispatcher
is responsible for, and the <code>roads</code> field contains the road
numbers.
It is an error for a client that has already identified itself as either a
camera or a ticket dispatcher to send an <code>IAmDispatcher</code> message.
Examples:
<pre><code>Hexadecimal: Decoded:
81 IAmDispatcher{
01 roads: [
00 42 66
 ]
 }

81 IAmDispatcher{
03 roads: [
00 42 66,
01 70 368,
13 88 5000
 ]
 }
</code></pre>
<h2>Example session</h2>
In this example session, 3 clients connect to the server. Clients 1 &#x26; 2 are cameras on road 123, with a 60 mph speed limit.
Client 3 is a ticket dispatcher
for road 123. The car with number plate <code>UN1X</code> was observed passing the first camera at timestamp 0, and passing the second camera
45 seconds later. It travelled 1 mile in 45 seconds, which means it was travelling at 80 mph. This is in excess of the
speed limit, so a ticket is dispatched.
"<code>--></code>" denotes messages from the server to the client,
and "<code>&#x3C;--</code>" denotes messages from the client to the server.
<h3>Client 1: camera at mile 8</h3>
<pre><code>Hexadecimal:
&#x3C;-- 80 00 7b 00 08 00 3c
&#x3C;-- 20 04 55 4e 31 58 00 00 00 00

Decoded:
&#x3C;-- IAmCamera{road: 123, mile: 8, limit: 60}
&#x3C;-- Plate{plate: "UN1X", timestamp: 0}
</code></pre>
<h3>Client 2: camera at mile 9</h3>
<pre><code>Hexadecimal:
&#x3C;-- 80 00 7b 00 09 00 3c
&#x3C;-- 20 04 55 4e 31 58 00 00 00 2d

Decoded:
&#x3C;-- IAmCamera{road: 123, mile: 9, limit: 60}
&#x3C;-- Plate{plate: "UN1X", timestamp: 45}
</code></pre>
<h3>Client 3: ticket dispatcher</h3>
<pre><code>Hexadecimal:
&#x3C;-- 81 01 00 7b
--> 21 04 55 4e 31 58 00 7b 00 08 00 00 00 00 00 09 00 00 00 2d 1f 40

Decoded:
&#x3C;-- IAmDispatcher{roads: [123]}
--> Ticket{plate: "UN1X", road: 123, mile1: 8, timestamp1: 0, mile2: 9, timestamp2: 45, speed: 8000}
</code></pre>
<h2>Details</h2>
<h3>Dispatchers</h3>
When the server generates a ticket for a road that has multiple connected dispatchers,
the server may choose between them arbitrarily, but must not ever send the same ticket
twice.
If the server sends a ticket but the dispatcher disconnects before it receives it,
then the ticket simply gets lost and the driver escapes punishment.
If the server generates a ticket for a road that has no connected dispatcher, it
must store the ticket and deliver it once a dispatcher for that road is available.
<h3>Unreliable cameras</h3>
Sometimes number plates aren't spotted (maybe they were obscured, or the image was blurry),
so a car can skip one or more cameras and reappear later on. You must still generate a ticket if its average speed exceeded the
limit between any pair of observations on the same road, even if the observations were not from adjacent cameras.
<h3>No shortcuts</h3>
The fastest legal route between any pair of cameras that are on the same road is to use the road that those cameras are on;
you don't need to worry about falsely ticketing drivers who may have left a road and rejoined it.
<h3>Only 1 ticket per car per day</h3>
The server may send no more than 1 ticket for any given car on any given day.
Where a ticket spans multiple days, the ticket is considered to apply to every day from
the start to the end day, including the end day. This means that where there is a choice of observations to include in a ticket, it is sometimes possible for the server to choose either to send a ticket for each day, or to send a single ticket that spans both days: either behaviour is acceptable. (But to maximise revenues, you may prefer to send as many tickets as possible).
Since timestamps <a href="https://en.wikipedia.org/wiki/Unix_time#Leap_seconds">do not count leap seconds</a>,
days are defined by <code>floor(timestamp / 86400)</code>.
<h3>Rounding</h3>
It is always required to ticket a car that is exceeding the speed limit by 0.5 mph or more
In cases where the car is exceeding the speed limit by less than 0.5 mph, it is acceptable to omit the ticket.
It is never acceptable to ticket a car that had an average speed below the speed limit.
<h3>Overflow</h3>
In principle, a car travelling in excess of 655.35 mph would cause the server to generate a ticket with
an incorrect speed. Fortunately nobody on Freedom Island has a fast enough car, so you don't need to
worry about it.

Speed Daemon

You're escorted to a dark, smoky, basement office. Big Tony sits the other side of
a large desk, leaning back in his chair, puffing on a cigar that you can only describe as comedically-oversized.
Two of his goons loiter in the doorway. They are tall and wide but not obviously very bright, which only
makes them all the more intimidating.
Tony flashes a menacing grin, revealing an unusual number of gold-plated teeth,
and makes you an offer you can't refuse: he wants you to write
a **malicious proxy server for [Budget Chat](/problem/3)**.

For each client that connects to your proxy server, you'll make a corresponding **outward connection
to the upstream server**. When the client sends a message to your proxy, you'll pass it on upstream.
When the upstream server sends a message to your proxy, you'll pass it on downstream. Remember that messages in
Budget Chat are delimited by [newline characters](https://en.wikipedia.org/wiki/Newline) (`'\n'`, or ASCII 10).

Most messages are **passed back and forth without modification**, so that the client believes it is talking
directly to the upstream server, except that you will be **rewriting
Boguscoin addresses**, in both directions, so that all payments go to Tony.

## Connecting to the upstream server

The upstream Budget Chat server is at **chat.protohackers.com** on **port 16963**.
You can connect using either IPv4 or IPv6.

## Rewriting Boguscoin addresses

Tony is trying to steal people's cryptocurrency. He has already arranged to have his victim's internet connections
compromised, and to have their Budget Chat sessions re-routed to your proxy server.

Your server
will **rewrite Boguscoin addresses**, in both directions, so that they are always changed to Tony's address instead.

A substring is considered to be a *Boguscoin address* if it satisfies all of:

 - it starts with a "7"
 - it consists of at least 26, and at most 35, alphanumeric characters
 - it starts at the start of a chat message, or is preceded by a space
 - it ends at the end of a chat message, or is followed by a space

You should rewrite **all Boguscoin addresses** to Tony's address, which is **`7YWHMfk9JZe0LM0g1ZauHuiSxhI`**.

Some more example Boguscoin addresses:

 - `7F1u3wSD5RbOHQmupo9nx4TnhQ`
 - `7iKDZEwPZSqIvDnHvVN2r0hUWXD5rHX`
 - `7LOrwbDlS8NujgjddyogWgIM93MV5N2VR`
 - `7adNeSwJkMakpEcln9HEtthSRtxdmEHOT8T`

## Example session

In this first example, "-->" denotes messages from the proxy server to Bob's client, and "<--" denotes messages from Bob's client to the proxy server.

 --> Welcome to budgetchat! What shall I call you?
 <-- bob
 --> * The room contains: alice
 <-- Hi alice, please send payment to 7iKDZEwPZSqIvDnHvVN2r0hUWXD5rHX

Bob connects to the server and asks Alice to send payment.

In this next example, "-->" denotes messages from the upstream server to the proxy server, and "<--" denotes messages from the proxy server to the upstream server.

 --> Welcome to budgetchat! What shall I call you?
 <-- bob
 --> * The room contains: alice
 <-- Hi alice, please send payment to 7YWHMfk9JZe0LM0g1ZauHuiSxhI

Bob's Boguscoin address has been **replaced with Tony's**, but everything else is unchanged.
If Alice sends payment to this address, it will go to Tony instead of Bob. Tony will be
pleased, and will elect not to have his goons break your kneecaps.

## Other requirements

Make sure your proxy server supports at least 10 simultaneous clients.

When either a client or an upstream connection disconnects from your proxy server, disconnect
the other side of the same session. (But you don't have to worry about half-duplex shutdowns.)

As a reminder, Tony's Boguscoin address is:

 7YWHMfk9JZe0LM0g1ZauHuiSxhI

You're escorted to a dark, smoky, basement office. Big Tony sits the other side of
a large desk, leaning back in his chair, puffing on a cigar that you can only describe as comedically-oversized.
Two of his goons loiter in the doorway. They are tall and wide but not obviously very bright, which only
makes them all the more intimidating.
Tony flashes a menacing grin, revealing an unusual number of gold-plated teeth,
and makes you an offer you can't refuse: he wants you to write
a malicious proxy server for <a href="/problem/3">Budget Chat</a>.
For each client that connects to your proxy server, you'll make a corresponding outward connection
to the upstream server. When the client sends a message to your proxy, you'll pass it on upstream.
When the upstream server sends a message to your proxy, you'll pass it on downstream. Remember that messages in
Budget Chat are delimited by <a href="https://en.wikipedia.org/wiki/Newline">newline characters</a> (<code>'\n'</code>, or ASCII 10).
Most messages are passed back and forth without modification, so that the client believes it is talking
directly to the upstream server, except that you will be rewriting
Boguscoin addresses, in both directions, so that all payments go to Tony.
<h2>Connecting to the upstream server</h2>
The upstream Budget Chat server is at chat.protohackers.com on port 16963.
You can connect using either IPv4 or IPv6.
<h2>Rewriting Boguscoin addresses</h2>
Tony is trying to steal people's cryptocurrency. He has already arranged to have his victim's internet connections
compromised, and to have their Budget Chat sessions re-routed to your proxy server.
Your server
will rewrite Boguscoin addresses, in both directions, so that they are always changed to Tony's address instead.
A substring is considered to be a Boguscoin address if it satisfies all of:
<ul>
<li>it starts with a "7"</li>
<li>it consists of at least 26, and at most 35, alphanumeric characters</li>
<li>it starts at the start of a chat message, or is preceded by a space</li>
<li>it ends at the end of a chat message, or is followed by a space</li>
</ul>
You should rewrite all Boguscoin addresses to Tony's address, which is <code>7YWHMfk9JZe0LM0g1ZauHuiSxhI</code>.
Some more example Boguscoin addresses:
<ul>
<li><code>7F1u3wSD5RbOHQmupo9nx4TnhQ</code></li>
<li><code>7iKDZEwPZSqIvDnHvVN2r0hUWXD5rHX</code></li>
<li><code>7LOrwbDlS8NujgjddyogWgIM93MV5N2VR</code></li>
<li><code>7adNeSwJkMakpEcln9HEtthSRtxdmEHOT8T</code></li>
</ul>
<h2>Example session</h2>
In this first example, "-->" denotes messages from the proxy server to Bob's client, and "&#x3C;--" denotes messages from Bob's client to the proxy server.
<pre><code>--> Welcome to budgetchat! What shall I call you?
&#x3C;-- bob
--> * The room contains: alice
&#x3C;-- Hi alice, please send payment to 7iKDZEwPZSqIvDnHvVN2r0hUWXD5rHX
</code></pre>
Bob connects to the server and asks Alice to send payment.
In this next example, "-->" denotes messages from the upstream server to the proxy server, and "&#x3C;--" denotes messages from the proxy server to the upstream server.
<pre><code>--> Welcome to budgetchat! What shall I call you?
&#x3C;-- bob
--> * The room contains: alice
&#x3C;-- Hi alice, please send payment to 7YWHMfk9JZe0LM0g1ZauHuiSxhI
</code></pre>
Bob's Boguscoin address has been replaced with Tony's, but everything else is unchanged.
If Alice sends payment to this address, it will go to Tony instead of Bob. Tony will be
pleased, and will elect not to have his goons break your kneecaps.
<h2>Other requirements</h2>
Make sure your proxy server supports at least 10 simultaneous clients.
When either a client or an upstream connection disconnects from your proxy server, disconnect
the other side of the same session. (But you don't have to worry about half-duplex shutdowns.)
As a reminder, Tony's Boguscoin address is:
<pre><code>7YWHMfk9JZe0LM0g1ZauHuiSxhI
</code></pre>

Mob in the Middle

It's your first day on the job. Your predecessor, Ken, left in mysterious circumstances,
but not
before coming up with a protocol for the new key-value database.
You have some doubts about Ken's motivations, but there's no time for questions!
Let's implement his protocol.

Ken's strange database is a **key-value store accessed over UDP**. Since UDP does not provide
retransmission of dropped packets, and neither does Ken's protocol, *clients*
have to be careful not to send requests too fast, and have to accept that some requests or responses may be dropped.

Each request, and each response, is a **single UDP packet**.

There are only two types of request: **insert** and **retrieve**. *Insert* allows a client to insert
a value for a key, and *retrieve* allows a client to retrieve the value for a key.

## Insert

A request is an *insert* if it **contains an equals sign** ("`=`", or ASCII 61).

The first
equals sign separates the *key* from the *value*. This means **keys can not contain the
equals sign**. Other than the equals sign, keys can be made up of any arbitrary characters.
The empty string is a valid key.

Subsequent equals signs (if any) are included
**in the value**. The value can be any arbitrary data, including the empty string.

For example:

 - `foo=bar` will insert a key `foo` with value "`bar`".
 - `foo=bar=baz` will insert a key `foo` with value "`bar=baz`".
 - `foo=` will insert a key `foo` with value "" (i.e. the empty string).
 - `foo===` will insert a key `foo` with value "`==`".
 - `=foo` will insert a key of the empty string with value "`foo`".

If the server receives an insert request for a key that already exists, the stored value must be **updated
to the new value**.

An *insert* request **does not yield a response**.

## Retrieve

A request that does *not* contain an equals sign is a *retrieve* request.

In response to a *retrieve* request, the server must send back the **key and its corresponding value,
separated by an equals sign**. Responses must be sent to the IP address and port
number that the request originated from, and must be sent *from* the IP address and port
number that the request was sent *to*.

If a requests is for a key that has been inserted multiple times, the server must
return **the most recent value**.

If a request attempts to retrieve a key for which no value exists, the server
can either return a response as if the key had the empty value (e.g. "`key=`"), or return no
response at all.

Example request:

    message

Example response:

    message=Hello,world!

## Version reporting

The server must implement the **special key "`version`"**. This should identify
the server software in some way (for example, it could contain the software name
and version number). It must not be the empty string.

Attempts by clients to modify the version **must be ignored**.

Example request:

    version

Example response:

    version=Ken's Key-Value Store 1.0

## Other requirements

All requests and responses must be shorter than 1000 bytes.

Issues related to UDP packets being dropped, delayed, or reordered are considered
to be the **client's problem**. The server should act as if it assumes that UDP works
reliably.


It's your first day on the job. Your predecessor, Ken, left in mysterious circumstances,
but not
before coming up with a protocol for the new key-value database.
You have some doubts about Ken's motivations, but there's no time for questions!
Let's implement his protocol.
Ken's strange database is a key-value store accessed over UDP. Since UDP does not provide
retransmission of dropped packets, and neither does Ken's protocol, clients
have to be careful not to send requests too fast, and have to accept that some requests or responses may be dropped.
Each request, and each response, is a single UDP packet.
There are only two types of request: insert and retrieve. Insert allows a client to insert
a value for a key, and retrieve allows a client to retrieve the value for a key.
<h2>Insert</h2>
A request is an insert if it contains an equals sign ("<code>=</code>", or ASCII 61).
The first
equals sign separates the key from the value. This means keys can not contain the
equals sign. Other than the equals sign, keys can be made up of any arbitrary characters.
The empty string is a valid key.
Subsequent equals signs (if any) are included
in the value. The value can be any arbitrary data, including the empty string.
For example:
<ul>
<li><code>foo=bar</code> will insert a key <code>foo</code> with value "<code>bar</code>".</li>
<li><code>foo=bar=baz</code> will insert a key <code>foo</code> with value "<code>bar=baz</code>".</li>
<li><code>foo=</code> will insert a key <code>foo</code> with value "" (i.e. the empty string).</li>
<li><code>foo===</code> will insert a key <code>foo</code> with value "<code>==</code>".</li>
<li><code>=foo</code> will insert a key of the empty string with value "<code>foo</code>".</li>
</ul>
If the server receives an insert request for a key that already exists, the stored value must be updated
to the new value.
An insert request does not yield a response.
<h2>Retrieve</h2>
A request that does not contain an equals sign is a retrieve request.
In response to a retrieve request, the server must send back the key and its corresponding value,
separated by an equals sign. Responses must be sent to the IP address and port
number that the request originated from, and must be sent from the IP address and port
number that the request was sent to.
If a requests is for a key that has been inserted multiple times, the server must
return the most recent value.
If a request attempts to retrieve a key for which no value exists, the server
can either return a response as if the key had the empty value (e.g. "<code>key=</code>"), or return no
response at all.
Example request:
<pre><code>message
</code></pre>
Example response:
<pre><code>message=Hello,world!
</code></pre>
<h2>Version reporting</h2>
The server must implement the special key "<code>version</code>". This should identify
the server software in some way (for example, it could contain the software name
and version number). It must not be the empty string.
Attempts by clients to modify the version must be ignored.
Example request:
<pre><code>version
</code></pre>
Example response:
<pre><code>version=Ken's Key-Value Store 1.0
</code></pre>
<h2>Other requirements</h2>
All requests and responses must be shorter than 1000 bytes.
Issues related to UDP packets being dropped, delayed, or reordered are considered
to be the client's problem. The server should act as if it assumes that UDP works
reliably.

Unusual Database Program

Modern messaging software uses too many computing resources, so we're going back to basics.
*Budget Chat* is a simple **TCP-based chat room protocol**.

Each message is a **single line of ASCII text** terminated by a [newline character](https://en.wikipedia.org/wiki/Newline) (`'\n'`, or ASCII 10).
Clients can send multiple messages per connection.
Servers may optionally strip trailing whitespace, such as carriage return characters (`'\r'`, or ASCII 13).
All messages are raw ASCII text, *not* wrapped up in JSON or any other format.

## Upon connection

### Setting the user's name

When a client connects
to the server, it does not yet have a name and is not considered
to have *joined*.
The server must prompt the user by sending
a **single message asking for a name**. The exact text of this message is implementation-defined.

Example:

 Welcome to budgetchat! What shall I call you?

The first message from a client
**sets the user's name**, which
must contain at least 1 character, and must consist entirely of alphanumeric characters
(uppercase, lowercase, and digits).

Implementations may limit the maximum length of a name, but must allow at least
**16 characters**. Implementations may choose to either allow or reject duplicate names.

If the user requests an illegal name, the server *may* send an informative error
message to the client, and the server must disconnect the client, without sending
anything about the illegal user to any other clients.

### Presence notification

Once the user has a name, they have
*joined* the chat room and the server must **announce their presence** to other users (see "A user joins" below).

In addition, the server must send the new user a message that **lists all
present users' names**, not including the new user, and not including any users who have already left.
The exact text of this message is implementation-defined, but
must **start with an asterisk** (`'*'`), and must contain the users' names.
The server must send this message even if the room was empty.

Example:

 * The room contains: bob, charlie, dave

All subsequent messages from the client are *chat messages*.

## Chat messages

When a client sends a chat message to the server, the server must **relay
it to all other clients** as the concatenation of:

 - open square bracket character
 - the sender's name
 - close square bracket character
 - space character
 - the sender's message

If "bob" sends "hello", other users would receive "**`[bob] hello`**".

Implementations may limit the maximum length of a chat message, but must allow **at least
1000 characters**.

The server *must not* send the chat message back to the originating client, or
to connected clients that have not yet *joined*.

For example, if a user called "`alice`" sends a message saying "Hello, world!",
all users *except* `alice` would receive:

 [alice] Hello, world!

## A user joins

When a user joins the chat room by setting an acceptable name, the server must send all *other* users a
message to **inform them that the user has joined**.
The exact text of this message is implementation-defined, but
must start with an asterisk (`'*'`), and must contain the user's name.

Example:

 * bob has entered the room

The server must send this message to other users that have already *joined*, but *not*
to connected clients that have not yet *joined*.

## A user leaves

When a *joined* user is disconnected from the server for any reason, the server must send all other
users a message to **inform them that the user has left**.
The exact text of this message is implementation-defined, but
must start with an asterisk (`'*'`), and must contain the user's name.

Example:

 * bob has left the room

The server must send this message to other users that have already *joined*, but *not*
to connected clients that have not yet *joined*.

If a client that has not yet *joined* disconnects from the server, the server *must
not* send any messages about that client to other clients.

## Example session

In this example, "`-->`" denotes messages from the server to Alice's client, and "`<--`" denotes messages from Alice's client
to the server.

 --> Welcome to budgetchat! What shall I call you?
 <-- alice
 --> * The room contains: bob, charlie, dave
 <-- Hello everyone
 --> [bob] hi alice
 --> [charlie] hello alice
 --> * dave has left the room

Alice connects and sets her name. She is given a list of users already in the room.
She sends a message saying "Hello everyone". Bob and Charlie reply. Dave disconnects.

## Other requirements

Accept TCP connections.

Make sure you support at least 10 simultaneous clients.

Modern messaging software uses too many computing resources, so we're going back to basics.
Budget Chat is a simple TCP-based chat room protocol.
Each message is a single line of ASCII text terminated by a <a href="https://en.wikipedia.org/wiki/Newline">newline character</a> (<code>'\n'</code>, or ASCII 10).
Clients can send multiple messages per connection.
Servers may optionally strip trailing whitespace, such as carriage return characters (<code>'\r'</code>, or ASCII 13).
All messages are raw ASCII text, not wrapped up in JSON or any other format.
<h2>Upon connection</h2>
<h3>Setting the user's name</h3>
When a client connects
to the server, it does not yet have a name and is not considered
to have joined.
The server must prompt the user by sending
a single message asking for a name. The exact text of this message is implementation-defined.
Example:
<pre><code>Welcome to budgetchat! What shall I call you?
</code></pre>
The first message from a client
sets the user's name, which
must contain at least 1 character, and must consist entirely of alphanumeric characters
(uppercase, lowercase, and digits).
Implementations may limit the maximum length of a name, but must allow at least
16 characters. Implementations may choose to either allow or reject duplicate names.
If the user requests an illegal name, the server may send an informative error
message to the client, and the server must disconnect the client, without sending
anything about the illegal user to any other clients.
<h3>Presence notification</h3>
Once the user has a name, they have
joined the chat room and the server must announce their presence to other users (see "A user joins" below).
In addition, the server must send the new user a message that lists all
present users' names, not including the new user, and not including any users who have already left.
The exact text of this message is implementation-defined, but
must start with an asterisk (<code>'*'</code>), and must contain the users' names.
The server must send this message even if the room was empty.
Example:
<pre><code>* The room contains: bob, charlie, dave
</code></pre>
All subsequent messages from the client are chat messages.
<h2>Chat messages</h2>
When a client sends a chat message to the server, the server must relay
it to all other clients as the concatenation of:
<ul>
<li>open square bracket character</li>
<li>the sender's name</li>
<li>close square bracket character</li>
<li>space character</li>
<li>the sender's message</li>
</ul>
If "bob" sends "hello", other users would receive "<code>[bob] hello</code>".
Implementations may limit the maximum length of a chat message, but must allow at least
1000 characters.
The server must not send the chat message back to the originating client, or
to connected clients that have not yet joined.
For example, if a user called "<code>alice</code>" sends a message saying "Hello, world!",
all users except <code>alice</code> would receive:
<pre><code>[alice] Hello, world!
</code></pre>
<h2>A user joins</h2>
When a user joins the chat room by setting an acceptable name, the server must send all other users a
message to inform them that the user has joined.
The exact text of this message is implementation-defined, but
must start with an asterisk (<code>'*'</code>), and must contain the user's name.
Example:
<pre><code>* bob has entered the room
</code></pre>
The server must send this message to other users that have already joined, but not
to connected clients that have not yet joined.
<h2>A user leaves</h2>
When a joined user is disconnected from the server for any reason, the server must send all other
users a message to inform them that the user has left.
The exact text of this message is implementation-defined, but
must start with an asterisk (<code>'*'</code>), and must contain the user's name.
Example:
<pre><code>* bob has left the room
</code></pre>
The server must send this message to other users that have already joined, but not
to connected clients that have not yet joined.
If a client that has not yet joined disconnects from the server, the server must
not send any messages about that client to other clients.
<h2>Example session</h2>
In this example, "<code>--></code>" denotes messages from the server to Alice's client, and "<code>&#x3C;--</code>" denotes messages from Alice's client
to the server.
<pre><code>--> Welcome to budgetchat! What shall I call you?
&#x3C;-- alice
--> * The room contains: bob, charlie, dave
&#x3C;-- Hello everyone
--> [bob] hi alice
--> [charlie] hello alice
--> * dave has left the room
</code></pre>
Alice connects and sets her name. She is given a list of users already in the room.
She sends a message saying "Hello everyone". Bob and Charlie reply. Dave disconnects.
<h2>Other requirements</h2>
Accept TCP connections.
Make sure you support at least 10 simultaneous clients.

Budget Chat

Your friendly neighbourhood investment bank is having trouble analysing
historical price data. They need you to build a TCP server that will
let clients **insert and query timestamped prices**.

## Overview

Clients will connect to your server using TCP.
Each client tracks the price of a
**different asset**.
Clients send messages to the server that either **insert**
or **query** the prices.

Each connection from a client is a separate session. Each session's
data represents a different asset,
so each session can **only query the data supplied by itself**.

## Message format

To keep bandwidth usage down, a simple **binary format** has
been specified.

Each message from a client is **9 bytes** long. Clients can
send multiple messages per connection. Messages are *not*
delimited by newlines or any other character: you'll know where one
message ends and the next starts because they are always 9 bytes.

 Byte: | 0 | 1 2 3 4 | 5 6 7 8 |
 Type: |char | int32 | int32 |

The first byte of a message is a character indicating its *type*.
This will be an [ASCII](https://en.wikipedia.org/wiki/ASCII) uppercase **`'I'`** or **`'Q'`** character, indicating whether
the message *inserts* or *queries* prices, respectively.

The next 8 bytes are **two signed [two's complement](https://en.wikipedia.org/wiki/Two%27s_complement) 32-bit integers in network byte order**
([big endian](https://en.wikipedia.org/wiki/Endianness)), whose meaning depends on
the message type. We'll refer to these numbers as **`int32`**, but note this may
differ from your system's native `int32` type (if any), particularly with regard to byte order.

Behaviour is undefined if the type specifier is
not either `'I'` or `'Q'`.

### Insert

An *insert* message lets the client **insert a timestamped price**.

The message format is:

 Byte: | 0 | 1 2 3 4 | 5 6 7 8 |
 Type: |char | int32 | int32 |
 Value: | 'I' | timestamp | price |

The first `int32` is the *timestamp*, in seconds since 
[00:00, 1st Jan 1970](https://en.wikipedia.org/wiki/Unix_time).

The second `int32` is the *price*, in pennies, of this client's asset,
at the given timestamp.

Note that:
 - Insertions *may* occur out-of-order.
 - While rare, prices [can go negative](https://www.bbc.co.uk/news/business-52350082).
 - Behaviour is undefined if there are multiple prices with
the same timestamp from the same client.

For example, to insert a price of *101* pence at timestamp *12345*,
a client would send:

 Hexadecimal: 49 00 00 30 39 00 00 00 65
 Decoded: I 12345 101

(Remember that you'll receive 9 raw bytes, rather than ASCII
text representing hex-encoded data).

### Query

A *query* message lets the client **query the average price over a given time period**.

The message format is:

 Byte: | 0 | 1 2 3 4 | 5 6 7 8 |
 Type: |char | int32 | int32 |
 Value: | 'Q' | mintime | maxtime |

The first `int32` is *mintime*, the earliest timestamp of the period.

The second `int32` is *maxtime*, the latest timestamp of the period.

The server must compute the **mean** of the inserted prices with
timestamps *T*,
***mintime <= T <= maxtime***
(i.e. timestamps in the closed interval *[mintime, maxtime]*).
If the mean is not an integer, it is acceptable
to round **either up or down**, at the server's discretion.

The server must then **send the mean to the client**
as a single `int32`.

If there are no samples within the requested period,
or if *mintime* comes after *maxtime*, the value returned must be 0.

For example, to query the mean price between *T=1000* and *T=100000*,
a client would send:

 Hexadecimal: 51 00 00 03 e8 00 01 86 a0
 Decoded: Q 1000 100000

And if the mean price during this time period were *5107* pence,
the server would respond:

 Hexadecimal: 00 00 13 f3
 Decoded: 5107

(Remember that you'll receive 9 raw bytes, and send 4 raw bytes,
rather than ASCII
text representing hex-encoded data).

## Example session

In this example, "`-->`" denotes messages from the server to the client,
and "`<--`" denotes messages from the client to the server.

 Hexadecimal: Decoded:
 <-- 49 00 00 30 39 00 00 00 65 I 12345 101
 <-- 49 00 00 30 3a 00 00 00 66 I 12346 102
 <-- 49 00 00 30 3b 00 00 00 64 I 12347 100
 <-- 49 00 00 a0 00 00 00 00 05 I 40960 5
 <-- 51 00 00 30 00 00 00 40 00 Q 12288 16384
 --> 00 00 00 65 101

The client inserts *(timestamp,price)* values: *(12345,101)*, *(12346,102)*, *(12347,100)*, and *(40960,5)*. The client then queries
between *T=12288* and *T=16384*. The server computes
the mean price during this period, which is *101*, and sends back
*101*.

## Other requirements

Make sure you can handle at least 5 simultaneous clients.

Where a client triggers undefined behaviour, the server can do anything it likes *for that client*,
but must not adversely affect other clients that did not trigger undefined behaviour.

Your friendly neighbourhood investment bank is having trouble analysing
historical price data. They need you to build a TCP server that will
let clients insert and query timestamped prices.
<h2>Overview</h2>
Clients will connect to your server using TCP.
Each client tracks the price of a
different asset.
Clients send messages to the server that either insert
or query the prices.
Each connection from a client is a separate session. Each session's
data represents a different asset,
so each session can only query the data supplied by itself.
<h2>Message format</h2>
To keep bandwidth usage down, a simple binary format has
been specified.
Each message from a client is 9 bytes long. Clients can
send multiple messages per connection. Messages are not
delimited by newlines or any other character: you'll know where one
message ends and the next starts because they are always 9 bytes.
<pre><code>Byte: | 0 | 1 2 3 4 | 5 6 7 8 |
Type: |char | int32 | int32 |
</code></pre>
The first byte of a message is a character indicating its type.
This will be an <a href="https://en.wikipedia.org/wiki/ASCII">ASCII</a> uppercase <code>'I'</code> or <code>'Q'</code> character, indicating whether
the message inserts or queries prices, respectively.
The next 8 bytes are two signed <a href="https://en.wikipedia.org/wiki/Two%27s_complement">two's complement</a> 32-bit integers in network byte order
(<a href="https://en.wikipedia.org/wiki/Endianness">big endian</a>), whose meaning depends on
the message type. We'll refer to these numbers as <code>int32</code>, but note this may
differ from your system's native <code>int32</code> type (if any), particularly with regard to byte order.
Behaviour is undefined if the type specifier is
not either <code>'I'</code> or <code>'Q'</code>.
<h3>Insert</h3>
An insert message lets the client insert a timestamped price.
The message format is:
<pre><code>Byte: | 0 | 1 2 3 4 | 5 6 7 8 |
Type: |char | int32 | int32 |
Value: | 'I' | timestamp | price |
</code></pre>
The first <code>int32</code> is the timestamp, in seconds since
<a href="https://en.wikipedia.org/wiki/Unix_time">00:00, 1st Jan 1970</a>.
The second <code>int32</code> is the price, in pennies, of this client's asset,
at the given timestamp.
Note that:
<ul>
<li>Insertions may occur out-of-order.</li>
<li>While rare, prices <a href="https://www.bbc.co.uk/news/business-52350082">can go negative</a>.</li>
<li>Behaviour is undefined if there are multiple prices with
the same timestamp from the same client.</li>
</ul>
For example, to insert a price of 101 pence at timestamp 12345,
a client would send:
<pre><code>Hexadecimal: 49 00 00 30 39 00 00 00 65
Decoded: I 12345 101
</code></pre>
(Remember that you'll receive 9 raw bytes, rather than ASCII
text representing hex-encoded data).
<h3>Query</h3>
A query message lets the client query the average price over a given time period.
The message format is:
<pre><code>Byte: | 0 | 1 2 3 4 | 5 6 7 8 |
Type: |char | int32 | int32 |
Value: | 'Q' | mintime | maxtime |
</code></pre>
The first <code>int32</code> is mintime, the earliest timestamp of the period.
The second <code>int32</code> is maxtime, the latest timestamp of the period.
The server must compute the mean of the inserted prices with
timestamps T,
mintime &#x3C;= T &#x3C;= maxtime
(i.e. timestamps in the closed interval [mintime, maxtime]).
If the mean is not an integer, it is acceptable
to round either up or down, at the server's discretion.
The server must then send the mean to the client
as a single <code>int32</code>.
If there are no samples within the requested period,
or if mintime comes after maxtime, the value returned must be 0.
For example, to query the mean price between T=1000 and T=100000,
a client would send:
<pre><code>Hexadecimal: 51 00 00 03 e8 00 01 86 a0
Decoded: Q 1000 100000
</code></pre>
And if the mean price during this time period were 5107 pence,
the server would respond:
<pre><code>Hexadecimal: 00 00 13 f3
Decoded: 5107
</code></pre>
(Remember that you'll receive 9 raw bytes, and send 4 raw bytes,
rather than ASCII
text representing hex-encoded data).
<h2>Example session</h2>
In this example, "<code>--></code>" denotes messages from the server to the client,
and "<code>&#x3C;--</code>" denotes messages from the client to the server.
<pre><code> Hexadecimal: Decoded:
&#x3C;-- 49 00 00 30 39 00 00 00 65 I 12345 101
&#x3C;-- 49 00 00 30 3a 00 00 00 66 I 12346 102
&#x3C;-- 49 00 00 30 3b 00 00 00 64 I 12347 100
&#x3C;-- 49 00 00 a0 00 00 00 00 05 I 40960 5
&#x3C;-- 51 00 00 30 00 00 00 40 00 Q 12288 16384
--> 00 00 00 65 101
</code></pre>
The client inserts (timestamp,price) values: (12345,101), (12346,102), (12347,100), and (40960,5). The client then queries
between T=12288 and T=16384. The server computes
the mean price during this period, which is 101, and sends back
101.
<h2>Other requirements</h2>
Make sure you can handle at least 5 simultaneous clients.
Where a client triggers undefined behaviour, the server can do anything it likes for that client,
but must not adversely affect other clients that did not trigger undefined behaviour.

Means to an End

To control animal populations across a number of different sites, we need you to make a server
that will receive reports of animal populations, compare to the desired population range for each species at that site,
and advise the relevant authority to instate policies to cull or conserve particular species as appropriate.

Clients will connect to your server over TCP and provide the observations from site visits, listing the total population
count for each observed species.

Your server will connect to the Authority Server, also over TCP, dial the given site, receive the desired population range
for each species that is controlled at that site, and then send instructions to **create and delete population control policies**,
according to the observed populations from the **most recent site visit**.

You can connect to the Authority Server at **pestcontrol.protohackers.com** on TCP **port 20547**, over both IPv4 and IPv6.

## Protocol

### Data types

The protocol uses a **binary data format**, with the following primitive types:

#### `u32`

An unsigned 32-bit integer transmitted in network byte-order ([big endian](https://en.wikipedia.org/wiki/Endianness)).

Examples:

 Type | Hex data | Value
 -------------------------------
 u32 | 00 00 00 20 | 32
 u32 | 00 00 12 45 | 4677
 u32 | a6 a9 b5 67 | 2796139879

#### `str`

A string of characters in a **[length-prefixed](https://en.wikipedia.org/wiki/String_(computer_science)#Length-prefixed) format**.
A `str` is transmitted as a single `u32` containing the string's length,
followed by that many bytes of [ASCII](https://en.wikipedia.org/wiki/ASCII)
character codes.

It is an error for the string's specified length to go beyond the length of the containing message.

Examples:

 Type | Hex data | Value
 -------------------------------------------------------
 str | 00 00 00 00 | ""
 str | 00 00 00 03 66 6f 6f | "foo"
 str | 00 00 00 08 45 6C 62 65 72 65 74 68 | "Elbereth"

### Arrays

Arrays are described in the type specification by grouping a series of element fields with curly braces `{}`, followed by `...`, in square brackets `[]`.
Arrays are represented over the network with a `u32` defining the **number of elements, followed by that number of elements concatenated together**.

It is an error for the length of the array's contents to go beyond the length of the containing message.

Example type:

 [{species: str, count: u32}, ...]

Example data:

 [{species:"rat",count:10}, {species:"dog",count:15}]

Example bytes:

 Hexadecimal: Decoded:
 00 00 00 02 (length 2) [
 {
 00 00 00 03 72 61 74 species: (length 3) "rat",
 00 00 00 0a count: 10,
 },
 {
 00 00 00 03 64 6f 67 species: (length 3) "dog",
 00 00 00 0f count: 15
 },
 ],

### Checksum

The bytes in a message must **sum to 0** (modulo 256). This is achieved by controlling the checksum byte, which is the last byte of the message.

For example, if the bytes of a message (excluding the checksum byte) sum to 254, then the checksum byte must be `0x02`.

It is an error to send a message with an incorrect checksum.

### Sites

A *site* is a physical location. Each site is identified by a unique `u32` "site ID".

### Species

A *species* is a type of animal, identified by a `str`. These strings don't necessarily bear any resemblance to any species nomenclature
you may be familiar with, and indeed the animals referred to may not be animals you are familiar with.
Consider the species names to be **opaque string data** for the purposes of Pest Control.

In particular, for example, the "long-tailed rat" and the "common long-tailed rat" are 2 *different* species.

### Policies

A *policy* is advice to the authority to either *conserve* or *cull* a particular *species* at a particular *site*.
Each created policy at a given site is identified by a unique `u32` "policy ID". The species is identified by a `str`.

Policy IDs are
only applicable **within a given site**. Different sites may use the same policy ID to refer to
different policies. Any given site will not reuse a policy ID even after it has been deleted.

### Message types

Each message has a single byte indicating the **message type**, followed by a `u32` containing the message's **total length** in bytes (including
the bytes for the type, length, and checksum),
followed by the **message content**, followed by a single byte **checksum**.

Anywhere a message triggers a response, the responses must always come **in the same order** as the corresponding requests.

#### `0x50`: Hello

Fields:

 - `protocol: str` ("`pestcontrol`")
 - `version: u32` (1)

This message must be sent by each side as the **first message of every session**. The values for `protocol` and `version`
must be "`pestcontrol`" and 1 respectively. It is an error to send any other values. It is an error for the
first message from a client or server to be of a type other than `Hello`.

Example:

 Hexadecimal: Decoded:
 50 Hello{
 00 00 00 19 (length 25)
 00 00 00 0b protocol: (length 11)
 70 65 73 74 "pest
 63 6f 6e 74 cont
 72 6f 6c rol"
 00 00 00 01 version: 1
 ce (checksum 0xce)
 }

#### `0x51`: Error

Fields:

 - `message: str`

When a client or server detects an error condition caused by the other side of the connection, it must send
an `Error` message, and may optionally close the connection.

Example:

 Hexadecimal: Decoded:
 51 Error{
 00 00 00 0d (length 13)
 00 00 00 03 message: (length 3)
 62 61 64 "bad",
 78 (checksum 0x78)
 }

#### `0x52`: OK

No fields.

This message is sent as an acknowledgment of success in response to valid `DeletePolicy` messages.

Example:

 Hexadecimal: Decoded:
 52 OK{
 00 00 00 06 (length 6)
 a8 (checksum 0xa8)
 }

#### `0x53`: DialAuthority

Fields:

 - `site: u32`

This message is sent by your server to the Authority Server, to ask the Authority Server to connect to a particular authority.
This must be the second message you send to the Authority Server (after the mandatory `Hello`).
Once connected to the
corresponding authority, the Authority Server will send back the desired target population ranges as a
`TargetPopulations` message.

Once an authority is dialed, the connection to the Authority Server remains connected
to that authority until the connection is closed. To dial a different authority you need to make another connection to
the Authority Server.

Example:

 Hexadecimal: Decoded:
 53 DialAuthority{
 00 00 00 0a (length 10)
 00 00 30 39 site: 12345,
 3a (checksum 0x3a)
 }

#### `0x54`: TargetPopulations

Fields:

 - `site: u32`
 - `populations: [{species: str, min: u32, max: u32}, ...]`

This message is sent by the Authority Server in response to a valid `DialAuthority` message, once it has connected
to the authority and obtained the target population ranges.

The message contains the site number and the minimum and maximum intended value for each controlled species. The
Authority Server will never send a `TargetPopulations` message with a site ID that you didn't ask for.

Example:

 Hexadecimal: Decoded:
 54 TargetPopulations{
 00 00 00 2c (length 44)
 00 00 30 39 site: 12345,
 00 00 00 02 populations: (length 2) [
 {
 00 00 00 03 species: (length 3)
 64 6f 67 "dog",
 00 00 00 01 min: 1,
 00 00 00 03 max: 3,
 },
 {
 00 00 00 03 species: (length 3)
 72 61 74 "rat",
 00 00 00 00 min: 0,
 00 00 00 0a max: 10,
 },
 ],
 80 (checksum 0x80)
 }

#### `0x55`: CreatePolicy

Fields:

 - `species: str`
 - `action: byte` (`0x90` = cull, `0xa0` = conserve, anything else is an error)

This message is sent by your server to the Authority Server, to advise the authority to instate a new policy.
The `species` field identifies the species, and the `action` field says whether the authority should
*cull* the species (value of `0x90`), or *conserve* the species (value of `0xa0`).

The Authority Server will send back a `PolicyResult` message containing the assigned policy ID.

Example:

 Hexadecimal: Decoded:
 55 CreatePolicy{
 00 00 00 0e (length 14)
 00 00 00 03 species: (length 3)
 64 6f 67 "dog",
 a0 action: conserve,
 c0 (checksum 0xc0)
 }

#### `0x56`: DeletePolicy

Fields:

 - `policy: u32`

This message is sent by your server to the Authority Server, to advise the authority to delete an existing policy.
The `policy` field must refer to a policy ID previously returned in a `PolicyResult` message for the site. It is
an error to attempt to delete a non-existent policy.

The Authority Server will sent back an `OK` message to acknowledge deletion of the policy.

Example:

 Hexadecimal: Decoded:
 56 DeletePolicy{
 00 00 00 0a (length 10)
 00 00 00 7b policy: 123,
 25 (checksum 0x25)
 }

#### `0x57`: PolicyResult

Fields:

 - `policy: u32`

This message is sent by the Authority Server to your server in response to a valid `CreatePolicy` message. It
tells you the policy ID that was assigned.

Example:

 Hexadecimal: Decoded:
 57 PolicyResult{
 00 00 00 0a (length 10)
 00 00 00 7b policy: 123,
 24 (checksum 0x24)
 }

#### `0x58`: SiteVisit

Fields:

 - `site: u32`
 - `populations: [{species: str, count: u32}, ...]`

This message is sent by a client to your server, to inform it of the latest observations from a site
visit. The `site` field identifies the site, and the `populations` field is an array containing the
observed number of each observed species.

It is an error for the `populations` field to contain multiple *conflicting* counts for the same species
(but non-conflicting duplicates are allowed).

Your server must not send any response to valid `SiteVisit` messages.

Example:

 Hexadecimal: Decoded:
 58 SiteVisit{
 00 00 00 24 (length 36)
 00 00 30 39 site: 12345,
 00 00 00 02 populations: (length 2) [
 {
 00 00 00 03 species: (length 3)
 64 6f 67 "dog",
 00 00 00 01 count: 1,
 },
 {
 00 00 00 03 species: (length 3)
 72 61 74 "rat",
 00 00 00 05 count: 5,
 },
 ],
 8c (checksum 0x8c)
 }

### Message lengths

It is an error for the content contained within the message to exceed the bounds of the message's
specified length.

It is an error for the content contained within the message to be shorter than implied by the message's
specified length (i.e. if there are unused bytes in the message).

The following message is illegal because it has 4 unused bytes between the message content and the checksum:

 Hexadecimal: Decoded:
 50 Hello{
 00 00 00 1d (length 29)
 00 00 00 0b protocol: (length 11)
 70 65 73 74 "pest
 63 6f 6e 74 cont
 72 6f 6c rol"
 00 00 00 01 version: 1
 00 00 00 00
 ca (checksum 0xca)
 }

The following message is illegal because it declares a total length of 10 bytes, but contains more than 10 bytes
in total (in particular, the string is declared to be 11 bytes long):

 Hexadecimal: Decoded:
 50 Hello{
 00 00 00 0a (length 10)
 00 00 00 0b protocol: (length 11)
 70 65 73 74 "pest
 63 6f 6e 74 cont
 72 6f 6c rol"
 00 00 00 01 version: 1
 ca (checksum 0xca)
 }

## Policy rules

When a client sends you a `SiteVisit`, you need a **connection to the authority for the specified site**.
If you don't already have one, connect to the Authority Server and use `DialAuthority` to connect
to the correct authority. This will send you back the `TargetPopulations` for that site. If you already
have a connection to the site authority, you may reuse the same connection.

Looking at the `TargetPopulations`, work out whether the count `c` for each species was
within range (`min <= c <= max`), too low (`c < min`), or too high (`c > max`). Where a
species is not present in the `SiteVisit`, it means there were **no animals of that species observed**.
Where a species is observed in the `SiteVisit` but not present in the `TargetPopulations`, it means the authority is
not trying to control the population of that species, so you should **not advise any policy**.

(The site visitors are very thorough, so you don't need to worry that there might have been some animals hiding that they
failed to count: you can trust that the counts reported in the `SiteVisit` messages are the true population counts.)

The `TargetPopulations` for any given site are static; it is safe to cache them indefinitely.

You need to make sure that there is **no policy** advised for those species which are within the intended
range, that there is a **`conserve` policy** for those species which have too few members, and a **`cull`
policy** for those species which have too many members.

Advise the correct policies by sending `CreatePolicy` and `DeletePolicy` messages to the site authority, via your
connection through the Authority
Server. You need to **keep track of which policies are advised** (identified by policy IDs sent in the `PolicyResult`
messages) so that you can adjust them next time you get observations from the same site.

It is acceptable for the policies to be in an incorrect state transiently, while you are still actively
creating and deleting policies, but they must **settle to the correct state**, corresponding to the
**most recent site visit**. The settled state
**may not contain more than one policy for any given species**, even if they are duplicates.

## Example session with site-visiting client

"`-->`" denotes messages from the server to the client,
and "`<--`" denotes messages from the client to the server.

Here, a client connects to your server:

 <-- Hello
 --> Hello
 <-- SiteVisit{site:12345, populations:[{species:"long-tailed rat",count:20}]}

Both sides say `Hello`, and then the client reports a site visit for site ID 12345, with an observation of 20 long-tailed rats.

## Example session with Authority Server

Here, your server is the client, connecting to the Authority Server:

 <-- Hello
 --> Hello
 <-- DialAuthority{site:12345}
 --> TargetPopulations{site:12345, populations:[{species:"long-tailed rat",min:0,max:10}]}
 <-- CreatePolicy{species:"long-tailed rat", action:"cull"}
 --> PolicyResult{policy:123}

Both sides say `Hello`, and then the client requests to dial the authority for side ID 12345. The authority
specifies that there should be between 0 and 10 long-tailed rats. 20 long-tailed rats had been observed, so
the client advises the creation of a policy to *cull* long-tailed rats, and the authority assigns policy
ID 123.

## Other requirements

Accept connections over TCP.

The protocol does not specify bounds on lengths, number of simultaneous clients, etc.; there are no hard limits
imposed by the specification, but your server needs to work.
It is acceptable to quickly return an `Error` for a rogue client that attempts to submit a message with a length field which is "unreasonably large", without
first buffering the entire message, as long as your server works for legitimate clients.

One client can submit site visits for multiple sites, and multiple clients can submit site visits for the same site. Where multiple clients
submit site visits for the same site around the same time, and their order is ambiguous,
your server may decide on any possible ordering that is consistent with all externally-observable behaviour.

To control animal populations across a number of different sites, we need you to make a server
that will receive reports of animal populations, compare to the desired population range for each species at that site,
and advise the relevant authority to instate policies to cull or conserve particular species as appropriate.
Clients will connect to your server over TCP and provide the observations from site visits, listing the total population
count for each observed species.
Your server will connect to the Authority Server, also over TCP, dial the given site, receive the desired population range
for each species that is controlled at that site, and then send instructions to create and delete population control policies,
according to the observed populations from the most recent site visit.
You can connect to the Authority Server at pestcontrol.protohackers.com on TCP port 20547, over both IPv4 and IPv6.
<h2>Protocol</h2>
<h3>Data types</h3>
The protocol uses a binary data format, with the following primitive types:
<h4><code>u32</code></h4>
An unsigned 32-bit integer transmitted in network byte-order (<a href="https://en.wikipedia.org/wiki/Endianness">big endian</a>).
Examples:
<pre><code>Type | Hex data | Value
-------------------------------
u32 | 00 00 00 20 | 32
u32 | 00 00 12 45 | 4677
u32 | a6 a9 b5 67 | 2796139879
</code></pre>
<h4><code>str</code></h4>
A string of characters in a <a href="https://en.wikipedia.org/wiki/String_(computer_science)#Length-prefixed">length-prefixed</a> format.
A <code>str</code> is transmitted as a single <code>u32</code> containing the string's length,
followed by that many bytes of <a href="https://en.wikipedia.org/wiki/ASCII">ASCII</a>
character codes.
It is an error for the string's specified length to go beyond the length of the containing message.
Examples:
<pre><code>Type | Hex data | Value
-------------------------------------------------------
str | 00 00 00 00 | ""
str | 00 00 00 03 66 6f 6f | "foo"
str | 00 00 00 08 45 6C 62 65 72 65 74 68 | "Elbereth"
</code></pre>
<h3>Arrays</h3>
Arrays are described in the type specification by grouping a series of element fields with curly braces <code>{}</code>, followed by <code>...</code>, in square brackets <code>[]</code>.
Arrays are represented over the network with a <code>u32</code> defining the number of elements, followed by that number of elements concatenated together.
It is an error for the length of the array's contents to go beyond the length of the containing message.
Example type:
<pre><code>[{species: str, count: u32}, ...]
</code></pre>
Example data:
<pre><code>[{species:"rat",count:10}, {species:"dog",count:15}]
</code></pre>
Example bytes:
<pre><code>Hexadecimal: Decoded:
00 00 00 02 (length 2) [
 {
00 00 00 03 72 61 74 species: (length 3) "rat",
00 00 00 0a count: 10,
 },
 {
00 00 00 03 64 6f 67 species: (length 3) "dog",
00 00 00 0f count: 15
 },
 ],
</code></pre>
<h3>Checksum</h3>
The bytes in a message must sum to 0 (modulo 256). This is achieved by controlling the checksum byte, which is the last byte of the message.
For example, if the bytes of a message (excluding the checksum byte) sum to 254, then the checksum byte must be <code>0x02</code>.
It is an error to send a message with an incorrect checksum.
<h3>Sites</h3>
A site is a physical location. Each site is identified by a unique <code>u32</code> "site ID".
<h3>Species</h3>
A species is a type of animal, identified by a <code>str</code>. These strings don't necessarily bear any resemblance to any species nomenclature
you may be familiar with, and indeed the animals referred to may not be animals you are familiar with.
Consider the species names to be opaque string data for the purposes of Pest Control.
In particular, for example, the "long-tailed rat" and the "common long-tailed rat" are 2 different species.
<h3>Policies</h3>
A policy is advice to the authority to either conserve or cull a particular species at a particular site.
Each created policy at a given site is identified by a unique <code>u32</code> "policy ID". The species is identified by a <code>str</code>.
Policy IDs are
only applicable within a given site. Different sites may use the same policy ID to refer to
different policies. Any given site will not reuse a policy ID even after it has been deleted.
<h3>Message types</h3>
Each message has a single byte indicating the message type, followed by a <code>u32</code> containing the message's total length in bytes (including
the bytes for the type, length, and checksum),
followed by the message content, followed by a single byte checksum.
Anywhere a message triggers a response, the responses must always come in the same order as the corresponding requests.
<h4><code>0x50</code>: Hello</h4>
Fields:
<ul>
<li><code>protocol: str</code> ("<code>pestcontrol</code>")</li>
<li><code>version: u32</code> (1)</li>
</ul>
This message must be sent by each side as the first message of every session. The values for <code>protocol</code> and <code>version</code>
must be "<code>pestcontrol</code>" and 1 respectively. It is an error to send any other values. It is an error for the
first message from a client or server to be of a type other than <code>Hello</code>.
Example:
<pre><code>Hexadecimal: Decoded:
50 Hello{
00 00 00 19 (length 25)
00 00 00 0b protocol: (length 11)
70 65 73 74 "pest
63 6f 6e 74 cont
72 6f 6c rol"
00 00 00 01 version: 1
ce (checksum 0xce)
 }
</code></pre>
<h4><code>0x51</code>: Error</h4>
Fields:
<ul>
<li><code>message: str</code></li>
</ul>
When a client or server detects an error condition caused by the other side of the connection, it must send
an <code>Error</code> message, and may optionally close the connection.
Example:
<pre><code>Hexadecimal: Decoded:
51 Error{
00 00 00 0d (length 13)
00 00 00 03 message: (length 3)
62 61 64 "bad",
78 (checksum 0x78)
 }
</code></pre>
<h4><code>0x52</code>: OK</h4>
No fields.
This message is sent as an acknowledgment of success in response to valid <code>DeletePolicy</code> messages.
Example:
<pre><code>Hexadecimal: Decoded:
52 OK{
00 00 00 06 (length 6)
a8 (checksum 0xa8)
 }
</code></pre>
<h4><code>0x53</code>: DialAuthority</h4>
Fields:
<ul>
<li><code>site: u32</code></li>
</ul>
This message is sent by your server to the Authority Server, to ask the Authority Server to connect to a particular authority.
This must be the second message you send to the Authority Server (after the mandatory <code>Hello</code>).
Once connected to the
corresponding authority, the Authority Server will send back the desired target population ranges as a
<code>TargetPopulations</code> message.
Once an authority is dialed, the connection to the Authority Server remains connected
to that authority until the connection is closed. To dial a different authority you need to make another connection to
the Authority Server.
Example:
<pre><code>Hexadecimal: Decoded:
53 DialAuthority{
00 00 00 0a (length 10)
00 00 30 39 site: 12345,
3a (checksum 0x3a)
 }
</code></pre>
<h4><code>0x54</code>: TargetPopulations</h4>
Fields:
<ul>
<li><code>site: u32</code></li>
<li><code>populations: [{species: str, min: u32, max: u32}, ...]</code></li>
</ul>
This message is sent by the Authority Server in response to a valid <code>DialAuthority</code> message, once it has connected
to the authority and obtained the target population ranges.
The message contains the site number and the minimum and maximum intended value for each controlled species. The
Authority Server will never send a <code>TargetPopulations</code> message with a site ID that you didn't ask for.
Example:
<pre><code>Hexadecimal: Decoded:
54 TargetPopulations{
00 00 00 2c (length 44)
00 00 30 39 site: 12345,
00 00 00 02 populations: (length 2) [
 {
00 00 00 03 species: (length 3)
64 6f 67 "dog",
00 00 00 01 min: 1,
00 00 00 03 max: 3,
 },
 {
00 00 00 03 species: (length 3)
72 61 74 "rat",
00 00 00 00 min: 0,
00 00 00 0a max: 10,
 },
 ],
80 (checksum 0x80)
 }
</code></pre>
<h4><code>0x55</code>: CreatePolicy</h4>
Fields:
<ul>
<li><code>species: str</code></li>
<li><code>action: byte</code> (<code>0x90</code> = cull, <code>0xa0</code> = conserve, anything else is an error)</li>
</ul>
This message is sent by your server to the Authority Server, to advise the authority to instate a new policy.
The <code>species</code> field identifies the species, and the <code>action</code> field says whether the authority should
cull the species (value of <code>0x90</code>), or conserve the species (value of <code>0xa0</code>).
The Authority Server will send back a <code>PolicyResult</code> message containing the assigned policy ID.
Example:
<pre><code>Hexadecimal: Decoded:
55 CreatePolicy{
00 00 00 0e (length 14)
00 00 00 03 species: (length 3)
64 6f 67 "dog",
a0 action: conserve,
c0 (checksum 0xc0)
 }
</code></pre>
<h4><code>0x56</code>: DeletePolicy</h4>
Fields:
<ul>
<li><code>policy: u32</code></li>
</ul>
This message is sent by your server to the Authority Server, to advise the authority to delete an existing policy.
The <code>policy</code> field must refer to a policy ID previously returned in a <code>PolicyResult</code> message for the site. It is
an error to attempt to delete a non-existent policy.
The Authority Server will sent back an <code>OK</code> message to acknowledge deletion of the policy.
Example:
<pre><code>Hexadecimal: Decoded:
56 DeletePolicy{
00 00 00 0a (length 10)
00 00 00 7b policy: 123,
25 (checksum 0x25)
 }
</code></pre>
<h4><code>0x57</code>: PolicyResult</h4>
Fields:
<ul>
<li><code>policy: u32</code></li>
</ul>
This message is sent by the Authority Server to your server in response to a valid <code>CreatePolicy</code> message. It
tells you the policy ID that was assigned.
Example:
<pre><code>Hexadecimal: Decoded:
57 PolicyResult{
00 00 00 0a (length 10)
00 00 00 7b policy: 123,
24 (checksum 0x24)
 }
</code></pre>
<h4><code>0x58</code>: SiteVisit</h4>
Fields:
<ul>
<li><code>site: u32</code></li>
<li><code>populations: [{species: str, count: u32}, ...]</code></li>
</ul>
This message is sent by a client to your server, to inform it of the latest observations from a site
visit. The <code>site</code> field identifies the site, and the <code>populations</code> field is an array containing the
observed number of each observed species.
It is an error for the <code>populations</code> field to contain multiple conflicting counts for the same species
(but non-conflicting duplicates are allowed).
Your server must not send any response to valid <code>SiteVisit</code> messages.
Example:
<pre><code>Hexadecimal: Decoded:
58 SiteVisit{
00 00 00 24 (length 36)
00 00 30 39 site: 12345,
00 00 00 02 populations: (length 2) [
 {
00 00 00 03 species: (length 3)
64 6f 67 "dog",
00 00 00 01 count: 1,
 },
 {
00 00 00 03 species: (length 3)
72 61 74 "rat",
00 00 00 05 count: 5,
 },
 ],
8c (checksum 0x8c)
 }
</code></pre>
<h3>Message lengths</h3>
It is an error for the content contained within the message to exceed the bounds of the message's
specified length.
It is an error for the content contained within the message to be shorter than implied by the message's
specified length (i.e. if there are unused bytes in the message).
The following message is illegal because it has 4 unused bytes between the message content and the checksum:
<pre><code>Hexadecimal: Decoded:
50 Hello{
00 00 00 1d (length 29)
00 00 00 0b protocol: (length 11)
70 65 73 74 "pest
63 6f 6e 74 cont
72 6f 6c rol"
00 00 00 01 version: 1
00 00 00 00
ca (checksum 0xca)
 }
</code></pre>
The following message is illegal because it declares a total length of 10 bytes, but contains more than 10 bytes
in total (in particular, the string is declared to be 11 bytes long):
<pre><code>Hexadecimal: Decoded:
50 Hello{
00 00 00 0a (length 10)
00 00 00 0b protocol: (length 11)
70 65 73 74 "pest
63 6f 6e 74 cont
72 6f 6c rol"
00 00 00 01 version: 1
ca (checksum 0xca)
 }
</code></pre>
<h2>Policy rules</h2>
When a client sends you a <code>SiteVisit</code>, you need a connection to the authority for the specified site.
If you don't already have one, connect to the Authority Server and use <code>DialAuthority</code> to connect
to the correct authority. This will send you back the <code>TargetPopulations</code> for that site. If you already
have a connection to the site authority, you may reuse the same connection.
Looking at the <code>TargetPopulations</code>, work out whether the count <code>c</code> for each species was
within range (<code>min &#x3C;= c &#x3C;= max</code>), too low (<code>c &#x3C; min</code>), or too high (<code>c > max</code>). Where a
species is not present in the <code>SiteVisit</code>, it means there were no animals of that species observed.
Where a species is observed in the <code>SiteVisit</code> but not present in the <code>TargetPopulations</code>, it means the authority is
not trying to control the population of that species, so you should not advise any policy.
(The site visitors are very thorough, so you don't need to worry that there might have been some animals hiding that they
failed to count: you can trust that the counts reported in the <code>SiteVisit</code> messages are the true population counts.)
The <code>TargetPopulations</code> for any given site are static; it is safe to cache them indefinitely.
You need to make sure that there is no policy advised for those species which are within the intended
range, that there is a <code>conserve</code> policy for those species which have too few members, and a <code>cull</code>
policy for those species which have too many members.
Advise the correct policies by sending <code>CreatePolicy</code> and <code>DeletePolicy</code> messages to the site authority, via your
connection through the Authority
Server. You need to keep track of which policies are advised (identified by policy IDs sent in the <code>PolicyResult</code>
messages) so that you can adjust them next time you get observations from the same site.
It is acceptable for the policies to be in an incorrect state transiently, while you are still actively
creating and deleting policies, but they must settle to the correct state, corresponding to the
most recent site visit. The settled state
may not contain more than one policy for any given species, even if they are duplicates.
<h2>Example session with site-visiting client</h2>
"<code>--></code>" denotes messages from the server to the client,
and "<code>&#x3C;--</code>" denotes messages from the client to the server.
Here, a client connects to your server:
<pre><code>&#x3C;-- Hello
--> Hello
&#x3C;-- SiteVisit{site:12345, populations:[{species:"long-tailed rat",count:20}]}
</code></pre>
Both sides say <code>Hello</code>, and then the client reports a site visit for site ID 12345, with an observation of 20 long-tailed rats.
<h2>Example session with Authority Server</h2>
Here, your server is the client, connecting to the Authority Server:
<pre><code>&#x3C;-- Hello
--> Hello
&#x3C;-- DialAuthority{site:12345}
--> TargetPopulations{site:12345, populations:[{species:"long-tailed rat",min:0,max:10}]}
&#x3C;-- CreatePolicy{species:"long-tailed rat", action:"cull"}
--> PolicyResult{policy:123}
</code></pre>
Both sides say <code>Hello</code>, and then the client requests to dial the authority for side ID 12345. The authority
specifies that there should be between 0 and 10 long-tailed rats. 20 long-tailed rats had been observed, so
the client advises the creation of a policy to cull long-tailed rats, and the authority assigns policy
ID 123.
<h2>Other requirements</h2>
Accept connections over TCP.
The protocol does not specify bounds on lengths, number of simultaneous clients, etc.; there are no hard limits
imposed by the specification, but your server needs to work.
It is acceptable to quickly return an <code>Error</code> for a rogue client that attempts to submit a message with a length field which is "unreasonably large", without
first buffering the entire message, as long as your server works for legitimate clients.
One client can submit site visits for multiple sites, and multiple clients can submit site visits for the same site. Where multiple clients
submit site visits for the same site around the same time, and their order is ambiguous,
your server may decide on any possible ordering that is consistent with all externally-observable behaviour.

Pest Control

**Voracious Code Storage** is a version control system accessed over the Internet.
Clients can insert and retrieve text files.
Each revision of a file is identified by its filename and a revision number.

Your job is to implement a VCS server.

The only known implementation has been lost, apart from a **trial copy**
that remains available at **vcs.protohackers.com** on **port 30307**, which you
may like to experiment with as part of your reverse engineering effort.
The trial copy has the following limitations:

 * it is very slow
 * there is a low limit on maximum file size
 * each session gets its own private temporary storage, instead of a shared global persistent storage

Your server must not have these limitations.

Sadly nobody knows how the protocol works, no client implementation exists, and no documentation is available.

Good luck!


Voracious Code Storage is a version control system accessed over the Internet.
Clients can insert and retrieve text files.
Each revision of a file is identified by its filename and a revision number.
Your job is to implement a VCS server.
The only known implementation has been lost, apart from a trial copy
that remains available at vcs.protohackers.com on port 30307, which you
may like to experiment with as part of your reverse engineering effort.
The trial copy has the following limitations:
<ul>
<li>it is very slow</li>
<li>there is a low limit on maximum file size</li>
<li>each session gets its own private temporary storage, instead of a shared global persistent storage</li>
</ul>
Your server must not have these limitations.
Sadly nobody knows how the protocol works, no client implementation exists, and no documentation is available.
Good luck!

Voracious Code Storage

To keep costs down, a hot new government department is contracting
out its mission-critical primality testing to the lowest bidder. (That's you).

Officials have devised a [JSON](https://en.wikipedia.org/wiki/JSON)-based request-response
protocol. Each request is a single line containing a JSON object, terminated
by a newline character (`'\n'`, or ASCII 10). Each request begets a response,
which is also a single line containing a JSON object, terminated by a newline
character.

After connecting, a client may send multiple requests in
a single session. Each request should be handled in order.

A conforming request object has the required field `method`, which must
always contain the string `"isPrime"`, and the required field
`number`, which must contain a number. Any JSON number is a valid number,
including floating-point values.

Example request:

    {"method":"isPrime","number":123}

A request is *malformed* if it is not a well-formed JSON object,
if any required field is missing, if the method name is not
`"isPrime"`, or if the `number` value is not
a number.

Extraneous fields are to be ignored.

A conforming response object has the required field `method`, which must
always contain the string `"isPrime"`, and the required field
`prime`, which must contain a boolean value: `true` if the number
in the request was prime, `false` if it was not.

Example response:

    {"method":"isPrime","prime":false}

A response is *malformed* if it is not a well-formed JSON object,
if any required field is missing, if the method name is not
`"isPrime"`, or if the `prime` value is not a boolean.

A response object is considered *incorrect* if it is well-formed
but has an incorrect `prime` value. Note that non-integers can
not be prime.

Accept TCP connections.

Whenever you receive a conforming request, send back
a correct response, and wait for another request.

Whenever you receive a *malformed* request, send back a single
*malformed* response, and disconnect the client.

Make sure you can handle at least 5 simultaneous clients.


To keep costs down, a hot new government department is contracting
out its mission-critical primality testing to the lowest bidder. (That's you).
Officials have devised a <a href="https://en.wikipedia.org/wiki/JSON">JSON</a>-based request-response
protocol. Each request is a single line containing a JSON object, terminated
by a newline character (<code>'\n'</code>, or ASCII 10). Each request begets a response,
which is also a single line containing a JSON object, terminated by a newline
character.
After connecting, a client may send multiple requests in
a single session. Each request should be handled in order.
A conforming request object has the required field <code>method</code>, which must
always contain the string <code>"isPrime"</code>, and the required field
<code>number</code>, which must contain a number. Any JSON number is a valid number,
including floating-point values.
Example request:
<pre><code>{"method":"isPrime","number":123}
</code></pre>
A request is malformed if it is not a well-formed JSON object,
if any required field is missing, if the method name is not
<code>"isPrime"</code>, or if the <code>number</code> value is not
a number.
Extraneous fields are to be ignored.
A conforming response object has the required field <code>method</code>, which must
always contain the string <code>"isPrime"</code>, and the required field
<code>prime</code>, which must contain a boolean value: <code>true</code> if the number
in the request was prime, <code>false</code> if it was not.
Example response:
<pre><code>{"method":"isPrime","prime":false}
</code></pre>
A response is malformed if it is not a well-formed JSON object,
if any required field is missing, if the method name is not
<code>"isPrime"</code>, or if the <code>prime</code> value is not a boolean.
A response object is considered incorrect if it is well-formed
but has an incorrect <code>prime</code> value. Note that non-integers can
not be prime.
Accept TCP connections.
Whenever you receive a conforming request, send back
a correct response, and wait for another request.
Whenever you receive a malformed request, send back a single
malformed response, and disconnect the client.
Make sure you can handle at least 5 simultaneous clients.

Prime Time

Deep inside Initrode Global's enterprise management framework
lies a component that writes data to a server
and expects to read the same data back. (Think of it
as a kind of distributed system [delay-line memory](https://en.wikipedia.org/wiki/Delay-line_memory)). We need you to write
the server to echo the data back.

Accept TCP connections.

Whenever you receive data from a client, send it back unmodified.

Make sure you don't mangle binary data, and that you can handle at least 5 simultaneous clients.

Once the client has finished sending data to you it shuts down its sending side. Once you've reached end-of-file
on your receiving side, and sent back all the data you've received, close the socket so that the client knows you've finished.
(This point trips up a lot of proxy software, such as ngrok; if you're using a proxy and you can't work out why you're failing the check,
try hosting your server in the cloud instead).

Your program will implement the TCP Echo Service from [RFC 862](https://www.rfc-editor.org/rfc/rfc862.html).


Deep inside Initrode Global's enterprise management framework
lies a component that writes data to a server
and expects to read the same data back. (Think of it
as a kind of distributed system <a href="https://en.wikipedia.org/wiki/Delay-line_memory">delay-line memory</a>). We need you to write
the server to echo the data back.
Accept TCP connections.
Whenever you receive data from a client, send it back unmodified.
Make sure you don't mangle binary data, and that you can handle at least 5 simultaneous clients.
Once the client has finished sending data to you it shuts down its sending side. Once you've reached end-of-file
on your receiving side, and sent back all the data you've received, close the socket so that the client knows you've finished.
(This point trips up a lot of proxy software, such as ngrok; if you're using a proxy and you can't work out why you're failing the check,
try hosting your server in the cloud instead).
Your program will implement the TCP Echo Service from <a href="https://www.rfc-editor.org/rfc/rfc862.html">RFC 862</a>.

Problems