CodinGame Contests Meet F# Part 1

Code 4 Life Wood League 2 to Wood League 1

Introduction

If you know me, it’s no secret that I’m a big fan of the CodinGame.com site. I even devoted quite a bit of time in my 100 days of code challenge to completing challenges and the Botters of the Galaxy contest. In this blog post, I’d like to try to encourage you to try out one of the contests. They really are a lot of fun and a nice challenge. Don’t be intimidated, because getting started is easier than you might think!

Unfortunately there is no active contest while I am writing this post (I missed my window by a couple weeks), but have no fear! Every contest eventually becomes a continuous multiplayer competition. There are only a few differences between the two:

• Contests usually happen over a 10 day span (often a week including the surrounding weekends). Continuous multiplayer is ongoing.
• Contests force you to code quickly (and usually dirty). This makes them more challenging in some ways. However, continuous multiplayer can be more challenging since people have had time to work on their strategy longer.
• Contests can have the odd bug or minor bot glitches (which can be exploited!). These are cleaned up once or twice during the contest at specific times. Continuous multiplayer will already have these bugs cleaned up and may have ongoing enhancements, if required.

For this blog post, I’m going to show you the Code 4 Life bot programming multiplayer competition. In addition, I’m going to use F# as my programming language to show how it can be great language for the contests (added bonus: not many people use F# in the competitions, so you can easily place in the top 5 and earn yourself some cool badges). I love that F# has an awesome static typing system, is functional-first, has algebraic types (domain modelling is so awesome in F#) and a sweet REPL so you can test out your functions as you build them!

Getting Started

First off, for the contests, you can do pretty decent by putting in less than an hour a day on average over the 10 day period. I’ve finished in the Gold League a couple times (one league away from the top Legends League) spending no more than 6 total hours during the contest. I keep telling myself that one of these days I’ll spend more time at it and try to compete with the top people… one day.

For this blog post, I’ll show you how you can make it from Wood League 2 (the introduction league) up to Wood League 1 in about an hour. I did intend to walk you through to the Bronze League, but this blog post will be lengthy as it is. I will do a follow up post to go from Wood League 1 to Bronze.

I prefer to spend a little more time at the beginning building domain models, so I don’t have to work directly with console input, arrays etc., which pays off later. As you progress from Wood League X (sometimes they start anywhere as high as 6 and move towards 1), to Bronze League and then Silver League, new rules/abilities etc. are added. Adding these changes in are much simpler when you have spent time on the domain model up front. Once you reach the Gold and Legend Leagues there are no more changes to the game; you are just competing with the top people and strategies.

Code 4 Life – Introduction

Let’s get rolling with the multiplayer competition. I apologize ahead of time, but I’ll be using screenshots to show you the rules. Hopefully they are not too difficult to read. I wanted to preserve the formatting, since they do such a good job in the internal IDE that CodinGame uses. Oh, speaking of the internal IDE, I still prefer to actually code in Visual Studio/Visual Studio Code. There is a cool plugin called CodinGame Sync – Ext that you can get (for Chrome, but it may be available for other browsers). It allows you to select a file, edit it in your favourite editor and have the IDE on the website automatically sync your code. Sometimes it does get out of sync and requires you to manually start it up again, but rarely enough that I still prefer it to copy-pasta from one IDE to the other.

Enough babble, let’s begin!

That sums up the gist of the competition. Now let’s move on to the rules for Wood League 2.

Code 4 Life – Wood League 2 Rules

The rules are a bit lengthy, so I had to split them into multiple screen shots.

The nice thing is that they make certain words stand out, which is great for domain modelling. Things like Diagnosis, Molecules, Laboratory, Collect, Gather, Produce, Robots, Sample Data, Goto, Connect etc. all seem to be candidates as part of our domain. We’ll cover some of that when we start coding.

There are still a few more rules.

And now on to the input and required output for each turn.

Here you can see that we are given some initialization input from the console, followed by input for each turn (note: some input should be ignored for this league and becomes relevant in later leagues). The input comes in string lines, which we’ll need to parse, apply our strategy voodoo and then provide one of three commands as our output for each turn.

When you first begin and choose your given programming language in the CodinGame IDE, you’ll be given some default code that gives you a better idea of what the input looks like. Here is the code provided for F# for Code 4 Life.

As you can see, the default code just grabs all the strings, tokenizes them and binds the values to some variables, which don’t get used for anything (it’s our job to figure that part out!). The code is also not very idiomatic for F# (I consider a more functional style with pipelines to be F#-ish, but F# is a multi-paradigm language so really there is no wrong way).

Let’s start building our domain and some useful helper functions to deal with parsing our values.

Code 4 Life – Wood League 2 Helper Functions

I should mention quickly that the CodinGame IDE only allows you to have a single file, so you can’t break things down into multiple files and modules nicely (although some people have written their own tooling to take multiple files and produce a single file which can then be transferred to the CodinGame IDE). Luckily, we’re not writing C code, so we won’t be writing thousands of lines of code (this is not a dig at C, this is what I’ve heard from people during contests that are using C!).

I may go a little overboard on functions, but they are so easy in F# that I tend to make the following helper functions for all things CodinGame:

These functions should be fairly self-explanatory. They are just convenience functions for code that is needed a lot in CodinGame: reading from the console, reading and parsing integers (I have no error checking, which could be added, but CodinGame will not give you unexpected input, as it is clearly defined in the rules), reading strings that need to be tokenized etc. Speaking of tokens, you’ll notice I slipped in a type alias at the top. This allows me to specify in some of the functions we’ll be using later that we’re expecting a Token instead of a string array. That makes the intention a little clearer, don’t you think?

The last function perhaps needs an explanation. It is a function that I like to use in place of for loops. I can read N number of lines from the console and have it return a string array of those lines. This works much nicer for pipelines, as you will soon see.

Code 4 Life – Wood League 2 Domain

Now it’s time to get on to where F# shines: Domain modelling.

Modules are mentioned in the rules section first, so let’s handle them. We have the following modules: DIAGNOSIS, MOLECULES, LABORATORY. We can only be at one module at a time, so this sounds like the perfect case for a discriminated union.

In addition, these modules are a location where our robot can be (which will be passed as a string as part of our token). So we’ll need a way to create a module from a string. I like to go with static Create methods myself, but there are many ways to do it.

Lastly, we will need to be able to go to these modules. One of the commands listed in the output is GOTO MODULE, so we’ll need a way to convert the discriminated union cases back into a string. This is a good place to override the ToString method.

Here is our Module type:

You’ll notice I’ve also added an unmentioned case for START_POS. This was discovered due to the failwithf call I like to add in case I receive any input I’m not expecting. It turns out that the robots start at a location called START_POS that is not mentioned in the rules.

Next mentioned is Robots. However, it looks like a robot needs to deal with some types we have not yet created, so let’s handle some of those first. It seems a Molecules type would be an important and fairly simple type to model next.

It says a molecule can be one of five types: A, B, C, D or E. Sounds like another discriminated union.

For input we never get a string with the molecule name, but instead receive a count of each type of molecule for different purposes (number of molecules stored by the robot, number of required molecules for each data sample and a couple other scenarios that it says are ignored in this league). So that means we don’t need a string to molecule type creation function.

For output, we do need to convert our molecule into a string in the CONNECT TYPE command. So that means overriding ToString again. Here is our type (let’s call it MoleculeType so it is easy to differentiate from the Molecules module type we created above):

Very simple. Looking even closer at the input section, it appears that we receive single lines of input containing the counts for each molecule type in many scenarios. It makes sense to create a type that holds a collection of the molecule types and counts together. Sounds like a key/value pair to me, or in F# a Map. For lack of a better name, let’s create a MoleculeStorage type. A record type should do us nicely.

The input appears to always provide five integers representing the molecules from A to E in alphabetical order, so our Token passed to a static Create method should do the trick:

We should now have enough to make our Robot type. Robots do carry sample data (for which we have yet to create a type), but looking at the input, the sample data has a property that says who is carrying it, rather than a robot saying what samples it is carrying. In addition, the robots are created first, and I’d like to keep things immutable. So for now we can create our Robot type without the need for a SampleData type.

Let’s check the input section to see what properties our robot should have:

• target (location of the robot): Module type
• eta (ignored)
• score (health points) : integer
• storage counts for the molecule types: StorageLocation type
• expertise counts for the molecule types (ignored)

We have two values we can ignore (they will be in the input string, however). We also have two values already handled by our domain types. Lastly, we have an integer type, which I think should be aliased to our domain (HealthPoints sounds like a good name).

Our Robot type will need to be created from a Token, so (you probably guessed it) we’ll have to make a static Create function that takes our aliased Token type. We’ll use a record type for our robots!

But wait! There is a hidden property we’ll need. It says “For each player, 1 line: 1 string followed by 12 integers (you are always the first player)”. Aha! We need a way to distinguish between us and the enemy robot. The only way to distinguish between them is the order in which the input comes.

And further still, looking at the input details we see that sample data are carried by us (integer 0), the enemy robot (integer 1) or in the cloud (integer -1). I feel like I should make some Azure related joke here, but I’ve got nothin’… So let’s make another type called Player.

Since a player can only be one of the three choices, we’ll use a discriminated union. We’ll also have to code a static Create function for a Player that takes an integer. Let’s not forget to update our Robot Create function to take in a Player since the Token will not contain this information.

No more jibba jabba, show me teh codez:

And now we finally come to the SampleData type:

• sample id: integer
• carried by: Player type
• rank (ignored)
• gain (ignored)
• health: HealthPoints type
• required counts for the molecule types: MoleculeStorage type

Two ignore values again: check. Three values that can make use of our already created domain types: check. Lastly, we need an integer value to represent the id of the sample (based on default code provided way up in the first code sample in this blog post (let sampleId = int(token3.[0])) … even though it doesn’t say so in the input section of the rules). Now, I’m not a fan of storing a straight-up integer as a property for something like an Id, so let’s make an alias type called Id.

Once again, we’ll be receiving a Token that can be passed to a static Create function. Here are the two types, in all of their glory:

We’ve now handled creating all of the domain objects. There is one more type I like to create for convenience. It’s to hold game state and pass it around to my main function so that I have everything I need to decide my move each turn. Let’s make a GameState type! It will hold a list of the robots and a list of the sample data. It’s not much to hold right now, but as each league unlocks new wonders, it’s nice to just add new domain objects to the game state as needed.

No fancy Create function required for this one.

Now, we have our domain objects, but we also need to do some actions. Based on the rules, our robots need to perform the following actions:

• Collect sample data
• Gather molecules
• Produce medicine from sample data
• Go to locations

Each of these actions are what I would call moves, one of which should be performed for each turn. These moves must be output as a command in a string format. Let’s start by modelling the actions as function types with only signatures (I considered using a discriminated union, but decided to take this route instead).

Not too bad. Now let’s implement the functions that are constrained to these types we have just created. Each function must return a string with the proper command:

• Collect: “CONNECT [id]”, where id is the sample data id
• Gather: “CONNECT [type]”, where type is the molecule type
• Produce: “CONNECT [id]”, where id is the sample data id
• Goto: “GOTO [module]”, where module is the target location

That’s it for the domain objects and commands! Now we can move on to our strategy functions to decide each move and the game loop where we populate our game state, decide our move and output our command.

Code 4 Life – Wood League 2 Strategy Functions

So the good news is that a strategy that is good enough to get passed Wood League 2 is very simple. We could even make a fancy state machine, but let’s leave that for another day and stick with some simple pattern matching.

Here is the simple strategy we will use:

• If we have a sample that is ready to make (we have all the required molecules), go to the Laboratory if we are not already there, then produce the medicine from the sample.
• If we have no samples, but there are some available in the cloud, go to the diagnosis machine if we are not already there, then grab a sample (we’ll grab the one with the highest available health points so we look smart).
• This last scenario will be hit if the above two are false. We will have a sample, but not all the required molecules to produce it. If we are not at the molecule station, move there, otherwise, figure out a molecule we need and grab it.

So there it is. A very basic strategy. So what functions do we need? Well, we need to know if we can make a sample for the first scenario. I bring you the canMakeSample function:

This function takes a sample data file, compares all the required molecule counts against the given robot’s molecule counts. If the robot has enough for each molecule type, the robot can make the sample. It’s not rocket science, but it is robotics and medicine!

For scenario two, I don’t think we really need a specialized function. It will be covered in our main getMove function coming up shortly.

Scenario three requires us to identify a molecule type we still need to gather before we can produce medicine from the sample data file:

This function looks at all the molecule counts required for a given sample data file. It then filters out the given robot’s molecule counts to only include molecule types that the robot doesn’t have enough of to produce the sample. We just grab the first one off the list and move along.

So we have two data transformation, pipeline-style F# goodness functions so far. Let’s move on to our main function and make use of F#’s amazing pattern matching (if you need an introduction or refresher on pattern matching, I did a two-part series here). I bring you the getMove function. There is a bit more going on in this function, so I’ll break it down a bit and build it up.

Based on our strategy above and the last two functions we created, we’ll need a few things (we will pull these from our GameState object):

• Our robot.
• The samples carried by our robot.
• The samples carried by our robot that can be created.
• The samples available to grab from the cloud (sorted by highest health points).

Nothing special here. Just taking data and transforming it in a pipeline (another area F# excels in!).

Now we can move on to the pattern matching to decide our move. F# allows you to match on more than one term, so we can easily hit our three strategy points above (there are actually six, because for each strategy branch, we may or may not be at the location/module we want).

There are four things we need to match on for our strategy:

1. How many samples we are carrying.
2. How many samples are ready (we can make).
3. How many samples are available in the cloud.
4. The location of our robot.

Let’s handle strategy from our first point. I’ll reiterate it here so you don’t have to scroll up:

From our four match conditions, we are interested in if we have any samples ready to make and where our robot is located. We can ignore the other two matching options for this scenario.

If we have any samples ready and we are at the laboratory, we produce the first sample that is ready. If we are not at the laboratory, we go to the laboratory.

If we have no samples ready, we move on to our next strategy:

From our four match conditions, we are interested in if our robot is carrying any samples (they will not be ready to make since we didn’t hit the previous match conditions) and where it is located. We also need to ensure that the cloud has a sample we can retrieve (although in this league it should always be the case). We can ignore the other matching option for this scenario.

If we have no samples, the cloud has a sample for us and our robot is at the diagnosis module, we can collect the first sample from the cloud (it will be sorted by highest health points). If we are not at the diagnosis machine, we go to the diagnosis machine.

Finally, we have our last scenario:

From our match conditions, we are only interested in our robot’s location. We’ve already handled the other match conditions and can only be at this code if our robot has a sample and we can’t make it yet. That allows us to ignore the rest of the match conditions.

If we are at the molecule station, grab a molecule we need. Otherwise, go to the molecule station.

And that’s our strategy implemented. It’s very basic, but it does the job for this league. Here is the getMove function in its entirety:

Code 4 Life – Wood League 2 Game Loop

We are nearly done. All that is left now is to actually read the input in the game loop, ask for a move and return a command.

To begin, we need to pull in the project information. According to the rules, this can be ignored for Wood League 2. However, we still need to parse the input. There is a line containing a project count (which will always be 0 for now) and then project count lines of input.

So we don’t forget about it later, we’ll modify the boiler plate code that was provided:

And now on to the final step. The game loop!

The first two lines are our robot and the enemy robot:

This is easy to do because of all the work we’ve already done with our helper functions and our static Create function.

The next line is yet another line that should be ignored in this league, but must be read (it is related to available molecules):

Next, we read a line with the number of samples, along with a line for each sample, which contains all of the details:

Once again, our helper functions and static Create function make this an easy task. We read in the number of samples, pipe that to the readNLines function, tokenize each line and convert it to a SampleData. Then we convert it to a list (I prefer immutable lists over arrays unless I have a specific reason to need an array… in hindsight, I should have just made readNLines return a list instead).

We have two things left to do:

1. Create our game state to hold the robots (even though we don’t do anything with the enemy robot yet, that will come later) and samples.
2. Pass our game state to getMove and print out the move.

And that’s it. All the code is done. Here is the entire game loop code:

Code 4 Life – Wood League 2 Code Submit

Here is a replay, testing the code out against the Wood League 2 boss in the IDE. We owned that robot!

So now we’ll submit our code into the arena and play against other players in the league. If we win enough battles, we’ll move up the leaderboard until we get to the boss.

After 60% of the battles, we have not yet lost and we are ranked above the boss. There is also a detailed leaderboard:

After our battles are complete, we have finished with a better score that the boss. We get a nice notification:

Virtual high-five! About a minute later…

Conclusion

So that’s it. It probably seemed to take a long time, but really it’s only about an hour or less. The strategy was pretty simple once we broke it down. Trust me, spending the time to create a nice domain pays dividends later, when things get more complicated.

If you haven’t used F#, I hope this shows you what a great and easy language it is to use. If you’ve never entered a CodinGame contest, hopefully this seemed like a fun challenge and will inspire you to do so. And bonus points if you decide to do a CodinGame contest with F#!

I’ve pushed the entire fsx file up on GitHub if you want to check it out. Feel free to use it as a starting point for the Code 4 Life multiplayer competition and then improve it in the later leagues so you can blow past me in the rankings!

Stay tuned for the next post, where we will go from Wood League 1 to Bronze League.

Useful Resources

• Domain Modeling Made Functional
• Designing With Types
• F# Pattern Matching