Feel free to send your feedback or ask some help here!
Doctor Who  Music Scores puzzle discussion
Câest mon puzzle prĂ©fĂ©rĂ©. Il est vraiment original par rapport aux autres problĂšmes.
Very original and fun one. At first I was like âOCR? Itâs impossible that I will complete it!â but in fact itâs pretty simple in realisation. At first I came up with solution that timed out at 11th test with only ~30% notes recognised (somewhere about 800ms). By converting input image to more convenient format and using operations on raw memory I reduced execution time to ~12 ms in test 11th. This is the power of optimalization!
Typo dans la VF de lâĂ©noncĂ© : âdans le continuum espacetempâ => il faut mettre un âsâ Ă âtempâ
The base PHP code for reading data is wrong :
$IMAGE = stream_get_line(STDIN, 256, â\nâ);
=> doenât read the entire line but only Â first 256 chars and thatâs not enough.
Also the button âI need helpâ doesnât link to this page
Thanks for the puzzle @FredTreg, Iâm a proud owner of 100% music score!
This puzzle is a lot of fun (in contrast to each and every other puzzle in the very hard section), original, and relaxing. Algorithm is simple to find but hard to pinpoint which variable you need in the first place, but once you figured it out, it all comes together like a good jigsaw.
Done. We just found out about this forum page not being correctly linked. Better now than never.
In constraints it says that notes are separated by at least 1 pixel, but in test case 11 thats not case.
They mean it this way.
The epsilon area is at least one pixel wide. In other words, between every two nodes is a slice that is at least one pixel wide and contains only lines. I hope thatâs not too much of a spoiler.
very interesting challenge, not easy to solve without the good data structures. My original algorithm was slow but resistant tonoise, while the last one was fast but very sensitive to noise.
Just a remark about 2 mistakes on the french version:
2 unit tests (and corresponding images) have a wrong name: âQue des noires sans doâ and âQue des blanches sans doâ. That imply there isnât any âDOâ (=C in anglosaxon notation) but they both have some DOs. First one has 5 DOs.
What noise?
My solution is 100% deterministic and guaranteed to find the correct answer, as long as the notes are not (much) taller than the line period. Noise is not an issue at all. I did at a time have some problems trying to fit my circle aliasing to the one in the tasks, but in the end I did not depend on that at all.
I do wonder, however, whether anyone has found a completely waterproof method for determining the position and dimensions of the staff with less than O(H^4) time complexity, where H is the height of the image. The time usage is well within the acceptable range for the images in the puzzle, but for a more general case, a more efficient method may be needed. I understand that approximate methods can solve the problem in a short time, but I demand a bulletproof method that can be proven to handle correctly every problem instance that adheres to the specification. Edit: When I think about it, considering @chrmâs post above, finding the position and dimensions of the staff is possible with much lower time complexity by, for instance, applying a runlength encoding to each column and looking for patterns that consist of a long white space followed by 4 or 5 cycles of LW Bâs and LPLW Wâs, then 0 or 1 LW B, then a white space.
Now I would like to propose an additional challenge (which I personally will try to avoid): Make a solution that runs through the input once, stores an amount of information that scales only with the width and not with the height, and outputs the answer in O(W*H) time. (I have not analyzed the published solutions to see if any of them qualify.)

by ânoiseâ I meant the random presence of white and black pixels, which xwould change dramatically the difficulty of the problem.

FYI, my code is in O(W*H) in time and space, with a small constant, but it has to run twice on the data, the first pass is to identify where are the lines, and the second to extract the notes. I also implemented an algorithm based on morphological analysis that could do this in one pass and with noise, it was running effectively on my PC, but was too slow for the coding game.
Nice task I used columns scanner, checking each column, one by one, extracting the columns with notes and then analyse the middle column for each note.