Welcome to the CodexCodingEvent! In this file, you will find all information about this event.
The main challenge is to write an algorithm solving a certain problem described in detail in chapter Challenge. The basic idea is to find out the layout of labyrinths.
There is a server with some example labyrinths. You can test your algorithm by letting it solve one of the labyrinths on that server. (Details on how to communicate with the server are in chapter Network protocol, but there is a template relieving you of implementing the protocol yourself; see next paragraph.)
If you want to begin with implementing your algorithm right away, and want to use Java for this challenge, you can download a template containing all code neccessary for communicating with the server. Details are in chapter Template.
There also is a scoreboard on which you will show up when solving one of the labyrinth on the server. (You don't actually have to have solved an example to show up; it is enough to try.) The scoreboard will compare how good your algorithm was, based on how many steps it took. Details are in chapter Scoring.
This challenge is heavily inspired by the game Codex by Daniel Linssen, see https://managore.itch.io/codex. How the colors work and how the player can interact with the labyrinth is his idea. Also, the labyrinths the server tests clients with are the levels from his game.
Note that this also means reading the following challenge description will take much of the fun out of his game.
The only personal information the downloadable template sends to the challenge server
are the username and password entered in LabyrinthSolver
(see chapter Template).
Apart from that, only challenge-related actions are sent; concretely:
starting a challenge, looking, moving, and reporting a solution.
For more details, see chapter Network protocol.
This can be verified by reading the tmeplate's source code; specificially the classes
net.haspamelodica.codex.codingevent.session.SessionOverSocket
and codexcodingevent.MainSolveOne
.
The server keeps logs about all performed actions.
Communication happens via the Zulip channel #Codex-Codingevent, and via the BBB room https://bbb.rbg.tum.de/dan-st1-tz9-kvj.
Feel free to ask questions there! If you have a question while I am not in the BBB room, ask in Zulip. If you have a question others shouldn't be able to see, write to me (Daniel Kirschten / ge49ret).
The event happens from April 7th to 10th.
Starting on the second day, the BBB room and the challenge server will be open from 10:00 to 22:00. On the first day, the BBB room will be opened shortly before the challenge is explained, and the challenge server will be started when I am finished explaining.
Other programming languages (than Java) are allowed, but you will have to reimplement the network protocol yourself. Still, reading chapter Template could be useful.
Solving this challenge in a team is allowed, but please use only one shared username (and password) and begin your username with "(Team)".
You are allowed to work on your labyrinth solver if the server is not running (at night between event days), but you will have to implement the labyrinth logic yourself.
You control a player inside a labyrinth. The labyrinth is a two-dimensional, infinitely big, periodic field of blocks.
Periodic means the labyrinth repeats after width
blocks horizontally and after height
blocks vertically.
Because of this, one width
×height
tile is enough to describe the entire labyrinth.
In other words, the labyrinth is a width
×height
torus.
The x axis goes from left to right, with smaller coordinates left. The y axis goes from up to down, with smaller coordinates up.
The width
and height
of the labyrinth are known.
Every block is colored either black or red. When a challenge starts, your player will start standing on a randomly-chosen red block. As we will see later, the player will always stand on red blocks, never on black ones.
There are two ways of interacting with the labyrinth: looking and moving. The player can look and move in any direction. (Possible directions are horizontal, vertical, and diagonal: up, up right, right, down right, ..., up left)
When looking in a direction, the player will see the color of the block next to the player in that direction.
When moving in a direction, the player will not neccessarily end up on the block next to the player. Instead, the player will continue moving in that direction until a red block is reached. (This is why the player will always stand on red blocks.) In other words, black blocks are covered in slippery oil.
The player does not know how many black blocks were moved over.
The goal is to find out what the labyrinth looks like.
More formally, you have to find out the color of every block of one width
×height
tile of the labyrinth.
There are many different ways to divide a labyrinth into repeating tiles. All tilings are counted as correct.
It is guaranteed that there exists a unique solution (except for different tiling possibilities).
An example labyrinth (with width
7 and height
7) may look like the following:
(To keep this file smaller than ∞ gigabytes, only a portion of the labyrinth is shown.)
Let's say the player stands on the block marked with a black dot. Then the player can see the blocks marked green (by looking), and move to the blocks marked blue:
This labyrinth can be tiled in 49 ways. Here are two of them, along with a single tile in the form it should be returned to the server:
The template contains everything you need to quickly get started solving this challenge, if you want to solve it using Java. Compiling the template requires at least Java 10.
The only class you need to modify is codexcodingevent.LabyrinthSolver
.
Modifying other classes from the template is allowed, but is neither reccommended nor neccessary for solving the challenge.
First, you should enter your username and a password.
You will be shown to other participants by your username. Once you choose a username, you can no longer change it.
Do not reuse a password you use elsewhere! Passwords are stored and transmitted as unencrypted plaintext. The password doesn't have to be very secure. It exists just to avoid other participants from deliberately logging in with your username to degrade your score.
Write your algorithm in LabyrinthSolver.solve
. The width and height of one tile are accessible as field members.
Move and look by calling move
and look
on the field member labyrinthPlayer
.
Return your solution as an instance of LabyrinthTile
.
You can also put code into the constructor of LabyrinthSolver
.
It is guaranteed a new instance of LabyrinthSolver
is created for each solution attempt.
If your code gets too long, consider splitting it into multiple classes. Keep in mind that in order for the provided main classes to work,
the entry point for your algorithm needs to stay in LabyrinthSolver.solve
,
and the signatures of solve
and the constructor of LabyrinthSolver
need to stay unchanged.
Your algorithm must perform at least one action (moving or looking) every 30 seconds, otherwise the attempt counts as canceled. (The server uses a timeout of 30 seconds for incoming messages to detect lost connections.)
There are two main classes: codexcodingevent.MainSolveOne
and codexcodingevent.MainSolveUntilCancel
.
Running MainSolveOne
will call your labyrinth solving algorithm once with a randomly chosen labyrinth.
When your algorithm is finished, an evaluation of your solution is printed to the console.
The evaluation will also show up on the scoreboard.
See chapter Scoring for a description of what the evaluation contains and how it shows up on the scoreboard.
If you stop the program (in Eclipse by pressing the red square) before it is finished, the attempt will show up as a canceled attempt in the scoreboard.
Running MainSolveUntilCancel
will solve challenges using your algorithm (and print the resulting evaluations) in an endless loop.
This loop can be interrupted by sending any input to the program. (In Eclipse this can be done by pressing Enter in the Console view.) The current attempt will be finished. Therefore, interrupting the loop this way won't cause a canceled attempt in the scoreboard.
Stopping the program is not reccommended as it will show up as a canceled attempt in the scoreboard.
The classes in net.haspamelodica.codex.codingevent.labyrinth
correspond to the concepts explained
in chapter Challenge.
You will need to use them for interacting with the labyrinth and returning your solution.
The classes in net.haspamelodica.codex.codingevent.session
and ...codingevent.challenge
are used
by the main classes for communicating with the server. They are not important for solving the challenge.
The evaluation of a solution consists of some statistics about how well your algorithm performed.
If the solution your algorithm returned does not match the real labyrinth, the solution counts as incorrect.
If your algorithm found the real labyrinth, but the path (sequence of moves and looks) your algorithm took also would have been possible for a different labyrinth, the solution also counts as incorrect. In other words, this means your algorithm thought it has unambiguously determined the labyrinth when it hasn't.
Correct means your solution matches the real labyrinth (except if the case described above occurs).
The number of moves your algorithm performed where the player did not step over a black block. In the example image in chapter Example these are up left, up, down left, down, down right.
The number of moves your algorithm performed where the player stepped over at least one black block. In the example image in chapter Example these are left, up right, right.
The number of look operations your algorithm performed, independent of whether the seen block was black or red.
A weighted sum of the move over red count, move over black count, and look count. Moves over red cost 30, moves over black cost 400, and looks cost 30.
The current scoreboard can be viewed under http://139.59.215.82:1338/. At the end of each day the final scoreboard is posted to the Zulip channel as a CSV file.
The main function of the scoreboard is to assign to each participant a score for every labyrinth as well as a summarized score. A score of 1.0 is defined to be the average; lower scores are better, higher scores are worse. How these scores are calculated is described in detail in chapter Score calculation.
The scoreboard is displayed as a table where rows are participants and columns are labyrinths. The first column (labeled "summary") does not correspond to a labyrinth, but is used for displaying summarized statistics.
For the numbers displayed in each cell, only statistics applying to the participant of that cell's row and the labyrinth of that cell's column are counted.
- In the top left corner of each cell, the score is shown.
- In the top right corner, the number of attempts is shown as two or three integers: The first integer is the number of correct attempts, the second one the number of incorrect attempts, the third one the number of canceled attempts. If there are no canceled attempts, the third integer is hidden.
- In the bottom, the minimum cost for a single attempt (see chapter Total cost is shown left; the maximum cost right. These values are not calculated for the summary column, because they wouldn't be meaningful as different labyrinths differ in diffculty.
-
First, an average cost is calculated for each labyrinth for each participant as the average mean of all attempts of that participant for that labyrinth resulting in a correct evaluation.
-
Then, an average cost is calculated for each labyrinth as the arithmetic mean of all average costs for that labyrinth (from step 1). If a participant has no (correct) attempt for a labyrinth, that participant's mean cost naturally is not included here as it doesn't exist. The mean costs of all participants are counted with equal weight, even if one participant has multiple (correct) attempts for a labyrinth. This is to avoid participants with more attempts having a greater effect on the scores than participants with fewer attempts.
-
Next, a score is calculated for each attempt of every participant by dividing each attempt's cost by the mean cost for that attempt's labyrinth (from step 2).
-
Next, the scores for each participant for each labyrinth are calculated as the arithmetic mean of all (correct) attempts of that participant for that labyrinth.
-
Similarily, the summarized scores for each participant are calculated as the arithmetic mean of all (correct) attempts of that participant. Note that, unlike in step 2, multiple attempts for the same labyrinth are counted as multiple attempts here.
You only need to read this chapter if you don't want to use the template.
The server is reachable via a TCP socket over IPv4 on port 1337. Its address is 139.59.215.82.
Communication between client and server consists of messages. Every message consists of a request from the client to the server and a response from the server to the client.
A request consists of a single message type byte and optionally some data.
A response consists of a single status byte and, if the status is SUCCESS
, optionally some data.
If the status is an error status (anything except SUCCESS
), the response doesn't contain data even if the message type requires data.
Also, the server never sends anything after an error response.
A request is always followed by exactly one response. Also, the server never sends a response of status SUCCESS
to the client
without the client sending a request first. (The server does sometimes send error responses without a request, for example TIMEOUT
.)
If any message type is used when the server does not expect it, INCORRECT_STATE
is responded.
If no request arrives within 30 seconds after the last response was sent, the server sends a TIMEOUT
response.
- The first message has to be
LOGIN_OR_REGISTER
.
The server responds withSUCCESS
only if the login was successful or the participant was registered successfully. Otherwise, it responds with an appropriate error response. - The next message has to be
START_CHALLENGE
.
The server randomly chooses a labyrinth and responds with its width and height. Internally, a start position is chosen randomly as well. - Now,
MOVE
andLOOK
can be used any number of times (including zero).
MOVE
causes the server to to move the current attempt's player in the specified direction, according to the rules from chapter Challenge.
LOOK
causes it to let the player look in the specified direction according to chapter Challenge, and to respond with the seen color. - When the client has unambiguously (except for different tilings, see chapter Challenge) determined the colors of a tile,
it should send
REPORT_SOLUTION
. The server evaluates the solution and responds with the evaluation. For details about the fields included in the evaluation, see chapter Evaluation. - The client can now safely terminate the connection, or proceed with step 2.
The server terminates the connection only if and as soon as it has sent an error response.
The client can terminate the connection whenever it wants to, but if the connection is terminated after a challenge was started but before a solution was reported the attempt counts as canceled.
Directions are transmitted as a single byte. Starting with 0x00
meaning up, directions are numbered clockwise:
0x00
for up, 0x01
for up right, 0x02
for right etc. until 0x07
for up left.
Colors are transmitted as a single byte, 'B'
/ 0x42
for black and 'R'
/ 0x52
for red.
All other data types are transmitted according to Java's DataInput class. For clarity, the used data types are repeated below.
There are two number types: integers and longs. Integers are 4 byte, longs are 8 byte, both are signed, and both are transmitted in big-endian, meaning high byte first.
Booleans are transmitted as one byte: 0x01
for true and 0x00
for false.
Strings are transmitted in Java's modified UTF-8 format.
LOGIN_OR_REGISTER
('R'
/0x52
)- Request data:
username
:String
password
:String
- Response data: none
- Request data:
START_CHALLENGE
('C'
/0x43
)- Request data: none
- Response data:
width
:integer
height
:integer
MOVE
('M'
/0x4D
)- Request data:
dir
:Direction
- Response data: none
- Request data:
LOOK
('L'
/0x4C
)- Request data:
dir
:Direction
- Response data:
seenColor
:Color
- Request data:
REPORT_SOLUTION
('S'
/0x53
)- Request data:
width
:integer
height
:integer
- blocks:
width
×height
Color
s. These are the blocks of the reported tile, in row-major format. (When iterating over width and height, the outer loop should iterate over width and the inner one over height.)
- Response data:
correct
:boolean
moveOverRedCount
:integer
moveOverBlackCount
:integer
lookCount
:integer
totalCost
:long
- Request data:
SUCCESS
is 'S'
/ 0x53
.
For error statuses, see net.haspamelodica.codex.codingevent.session.ServerException.Type
.
The Type
s in that file having -1
as the char are only used by the client implementation and never reported by the server.