CodinGame November: Note Writing from Doctor Who

On Saturday (11/23/2013) the next competition from CodinGame was held . And since on the same day it turned exactly 50 years from the day of the first release of the series “Doctor Who”, all the tasks in the competition were related to this topic. In my note, I will analyze one of the tasks, describe the solution and point out its shortcomings.

About competition

I take part in the CodinGame contest for the second time. Last time it was a competition from oDesk . There I took the 65th place, although the tasks were subjectively easier. This time the format of the competition has not changed: two tasks, fifteen languages ​​to choose from , four hours and more than a thousand participants. The code can be typed directly in the built-in editor, carefully prepared tests are also sent there.

The first task was easier, so to speak, "to warm up." But from my second, as an unsophisticated person in sports programming, my hair stood on end. I spent half an hour trying to make out the task, understand it and convince myself that this is not a joke and I can write it in the remaining two and a half hours. It is with this task that I want to acquaint you.

Task short

Recognize the sequence of notes from a black and white image, presented in the format of blocks of black and white pixels.

')

Task detail

The picture shows a five-ruled music staff. Notes can be located on the ruler, between the rulers or on an additional ruler. The head of the note can be empty or filled, which means different lengths of sound (empty is half the note, filled - quarter). The notes located in the lower half of the bearer are recorded calmly upwards, in the upper part - calmly downwards. The calm of the note “B” can be directed both up and down.

The data comes from STDIN, the answer must be given to STDOUT. Two lines come to the input of the script: the first is the width and height of the image separated by a space, the second is the encoded image. The image is transmitted using run-length encoding. The sequence of pixels of one color is encoded with one letter (B for black pixels, W for white), followed by a space after the number indicating the number of pixels of that color. For example: W 5 B 20 W 16 means 5 white pixels, after which there are 20 black pixels and another 16 white pixels. The image is encoded from top to bottom, from left to right. One block can continue on the next line. At the exit you need to issue a line indicating the notes (and their duration) separated by a space. According to the assignment, there is no difference between the notes in the upper and lower halves of the noble bearer. Only the length, which is represented by the letters H (for a half note) or Q (for a quarter note), has a value.

Image parameters:

100 <Width <5000
70 <Height <300
Minimum width of note lines and calms 1 pixel
The minimum distance between two notes is 1 pixel.
The distance between two rulers is at least 8 pixels and at least 4 times the width of the ruler.

Example

Entrance:

120 176 W 4090 B 100 W 20 B 100 W 20 B 100 W 20 B 100 W 1020 B 2 W 118 B 2 W 118 B 2 W 118 B 2 W 118 B 2 W 26 B 10 W 82 B 2 W 25 B 12 W 81 B 2 W 23 B 4 W 8 B 4 W 79 B 2 W 23 B 2 W 12 B 2 W 79 B 2 W 22 B 2 W 14 B 2 W 78 B 2 W 21 B 3 W 14 B 3 W 77 B 2 W 21 B 2 W 16 B 2 W 77 B 2 W 20 B 3 W 16 B 3 W 36 B 64 W 18 B 18 W 20 B 64 W 18 B 18 W 20 B 64 W 18 B 18 W 20 B 64 W 18 B 18 W 60 B 2 W 20 B 2 W 18 B 2 W 76 B 2 W 20 B 3 W 16 B 3 W 76 B 2 W 20 B 3 W 16 B 2 W 77 B 2 W 20 B 4 W 14 B 3 W 77 B 2 W 20 B 4 W 14 B 2 W 78 B 2 W 20 B 2 W 1 B 2 W 12 B 2 W 79 B 2 W 20 B 2 W 1 B 4 W 8 B 4 W 79 B 2 W 20 B 2 W 3 B 12 W 81 B 2 W 20 B 2 W 4 B 10 W 82 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 96 B 2 W 20 B 2 W 56 B 100 W 20 B 100 W 20 B 100 W 20 B 100 W 46 B 10 W 4 B 2 W 20 B 2 W 81 B 12 W 3 B 2 W 20 B 2 W 79 B 16 W 1 B 2 W 20 B 2 W 79 B 16 W 1 B 2 W 20 B 2 W 78 B 20 W 20 B 2 W 77 B 21 W 20 B 2 W 77 B 21 W 20 B 2 W 76 B 22 W 20 B 2 W 76 B 22 W 20 B 2 W 76 B 22 W 20 B 2 W 76 B 22 W 20 B 2 W 76 B 22 W 20 B 2 W 76 B 22 W 20 B 2 W 76 B 22 W 20 B 2 W 77 B 20 W 21 B 2 W 77 B 20 W 21 B 2 W 78 B 18 W 22 B 2 W 79 B 16 W 23 B 2 W 79 B 16 W 23 B 2 W 81 B 12 W 25 B 2 W 56 B 100 W 20 B 100 W 20 B 100 W 20 B 100 W 2420 B 100 W 20 B 100 W 20 B 100 W 20 B 100 W 5050 

Output:

 AQ DH 

A list of all the tests that the script must pass can be found here .

Decision

I will describe the basic algorithm, but I will not give the code. To whom it is interesting - you can look here (perl). The decisions of other participants can be found on the results page . If you want to solve this problem on your own, then in a couple of weeks it will most likely be available in training .

Disadvantages of the solution

During the decision, I made several assumptions regarding the image. Obviously, this is not specified in the condition, but for all tests these assumptions were fulfilled. If any of the conditions are violated, the picture will be processed with an error.

Assumptions:
1) the first non-empty column is the delimiter, not the beginning of the note;
2) the width of the rulers and the distance between them does not change throughout the picture;
3) the note takes all the space between the two lines.

Results

The solution to this problem took me 2 hours and 40 minutes. The problem is solved in full, all tests passed. According to the results of the competition, I took 23rd place.