Music Scores puzzle discussion

Puzzles
#1

Feel free to send your feedback or ask some help here!

#2

C’est mon puzzle prĂ©fĂ©rĂ©. Il est vraiment original par rapport aux autres problĂšmes.

4 Likes
#3

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 ~1-2 ms in test 11th. This is the power of optimalization! :smiley:

2 Likes
#4

Typo dans la VF de l’énoncĂ© : “dans le continuum espace-temp” => il faut mettre un “s” Ă  “temp”

#5

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

#6

Thanks for the puzzle @FredTreg, I’m a proud owner of 100% music score! :musical_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.

#7

Same thing for the C code, it doesn’t read the entire line.

#8

Done. We just found out about this forum page not being correctly linked. Better now than never.

#9

In constraints it says that notes are separated by at least 1 pixel, but in test case 11 thats not case.

Screenshot_2.png1168×887 2.26 KB

#10

That’s not a note, that’s a ledger line.

#11

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.

#13

No. Test 1 contains only AQ. The example has AQ and DH

#14

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.

#15

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.

1 Like
#16

What noise? :slight_smile:

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 @chr-m’s post above, finding the position and dimensions of the staff is possible with much lower time complexity by, for instance, applying a run-length 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 LP-LW 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.)

#17

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

  2. 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.

#18

Impressive! :smiley:

#19

Nice task :slight_smile: I used columns scanner, checking each column, one by one, extracting the columns with notes and then analyse the middle column for each note.

1 Like
#20

What does the statement “Encoding is done from top to bottom” mean?
Does it mean that:

  • encoding is done starting from the top row (left to right), followed by the second row from the top, etc. till we reach the bottom row,
    or
  • encoding is done by column (top to bottom), starting with the left column, followed by the second column from the left, etc.?
    Thanks!
#21

It means “encoding is done starting from the top row (left to right), followed by the second row from the top, etc. till we reach the bottom row”. You may refer to the images (link in the puzzle statement) and compare them with the test case inputs to have a better idea.

1 Like