CodinGame Spring Challenge 2020 - Day 2

08 May 2020

Today is day 2 of the CodinGame Spring Challenge 2020 which means yesterday was day 1. Where is the post from Day 1? Well I did nothing on day one. I didn’t even read the contest description. I was too busy with my RL job to get started during the day, and by the time I got around to checking the site it was 23:30 and I was ready for bed. It’s actually late in the day for day 2 as well, but this thing is only 10 days long and I’ve effectively wasted 10% of my time already.

Problem Description

It’s a PacMan game. PacMan eats pellets. The pellets are worth points. You need to finish the game with more points than your opponent. Seems pretty straight forward so far.

Today’s Goals

I actually have several goals to accomplish today:

1. Pick a programming language for this project.

2. Beat the Wood League Boss

Programming Language Selection

It’s a grid based game, and I’ve written clients for grid based games in multiple languages. I’ve got grid based game clients written in Go, Kotlin, C#, and Python. If I wanted to not worry about language being a hurdle I would select one of these languages.

On the other hand I could use this as an opportunity to get my C++ skills back in order. I haven’t written anything of consequence in C++ for over decade.

Well, I think since I’ve already pissed away an entire day I don’t think this is a good time to start this project with and unfamiliar language, so C++ is out. Kotlin and Python are out for similar reasons. I haven’t written a thing in either of these languages in 2020.

This leaves C# and Go.

C# Pros

• I use it every day
• I have several good IDEs for C#
• I already have a PacMan project setup for C# from HackerRank

Go Pros

• I was just reading the Go Programming Language book, and I love Go
• Goland

C# wins

Beat the Wood League Bosses

There are two levels of the Wood League and so two bosses to best. This is usually not a feat of great skill, but you don’t want to start the project off in the wrong direction either. It would be nice if everything I write today will be useful in the Bronze league. In this case I control a single PacMan and have to have more points than my opponent after 200 moves.

The important data structures for this task are

• Grid - a good representation of a 2D playing grid. This is just a guess, but I am assuming we are going to be doing some path finding so an adjacency list representation may be needed, maybe and adjacency matrix will be sufficient.

• PacMan - The player that inhabits the Grid.

• BotBrain - This is component that communicates with the game engine. It gets the input from the engine, initiates the big think, and then provides an output string to communicate to the engine. It does not directly use standard in/out or err, the data streams are initialized before use. This accommodate testing. I can stream in a string for testing purposes, and use stdin for the game.

Wood 2 League Strategy

If I am reading the rules for the wood 2 league right I don’t actually have to do anything with the grid data. I can just give the x y coordinate of where I want the pacman to go. Does this mean that the game does the path finding for me?

Lets find out.

My strategy is to order the list of pellets by value and then by Manhattan distance from my PacMan and then simply pick the first in the line.

The code for this is two lines:

var l = Pellets.OrderByDescending(p => p.Value).ThenBy(p => p.Loc.Distance(MyPacs[0].Loc)).First().Loc;

return $"MOVE 0 {l.Column} {l.Row}";

The results was, Blinky was defeated! Promotion to League 1 complete. Interesting that I don’t have to determine the best path between point A and point B. I bet this will change later.

Wood 1 League Strategy

The only difference I can tell is from the last league is this one gives me multiple PacMen to control.

Lets see if simply doing the same thing for each of my PacMen will works.

The logic for the code submitted looks like this:

var response = new List<string>();
foreach (var pacMan in MyPacs)
{
    var l = Pellets.OrderByDescending(p => p.Value).ThenBy(p => p.Loc.Distance(pacMan.Loc)).First().Loc;
    response.Add($"MOVE {pacMan.PacId} {l.Column} {l.Row}");
}

return string.Join("|", response);

I defeated Pinky, the bastard boss of Wood League 1. Watch the replay here.

If you watch the replay you will see that my PacMen are still pretty stupid, but as I expected it was enough to beat the Boss and get promoted to the Bronze league.

Defeating the Bronze league boss is where I will pick up tomorrow.