CodinGame – There is no spoon

I’ve been relocating to Guildford, UK in the past two weeks, and was away from coding in that time. As I’ll start at Lionhead Studios on Monday I planned to grab the keyboard over the weekend to get back in typing. There are programming contests at a regular interval on the CodInGame site, which I usually participate in whenever I have the time for it. This time it was only a four hours competition with two tasks.

The first was quite easy, you were given a grid with several nodes, some of them empty, others don’t. The task was to travel every node from the left hand corner and tell the neighbours of every node. If you’ve missed out a node, processed one twice or finished too slow, you failed. There were couple of test run against each participant’s code and a score were given out based on how many of them have passed.

The second one was more trickier. You were given a grid with several nodes, some of them empty, others don’t. Each non-empty node had a number, which indicated how many links it should have with it’s neighbouring nodes. Every node should have the exact number of links, there can be a maximum of two links between two nodes, and the links can not cross each other. I went with a simple solution first, reusing my code from the first task; simply running through all the nodes from the upper left corner and set every possible link for first, then repeat until all is found. It quickly turned out that there are several setups where you need to weight which ones to process first, as certain situations can only be solved one way. I then started on creating a weighted list of nodes based on the demand nearby. To be able to tune the system even more I also added the number of links the node itself should have to the calculations. It then produced a quite fine weighted list, which I could use to set the links between the nodes, and was able to pass about half of the tests. As three hours have gone already, I had to consider my options. So far the program only added, and took into calculation the bottom and right nodes, not the ones on the left and above. Later on this became a major obstacle, as without generating cross-links, some tests couldn’t been handled properly. After thinking for a few minutes I decided to submit my code in its current state, as adding the missing features would exceed the time limit, and I didn’t want to risk of submitting a code that performs even worse.

My results: