I've been ranked #112 out of 1167 at the november contest, not bad, although I didn't complete the "Docteur Who - Partitions" exercise.
This exercise was about being able to translate music notes from a partition picture.
I've choosen an original approach : instead of going for purely geometrical method (detecting staff, then looking for the round shape), I went for a statistical approach which proved risky.
I would build the horizontal and vertical histograms, then I would try to find values that would looks like notes signatures. In a hurry, I've tied detection to reading a single value from histograms which is far insufficient to detect correctly all the notes.
After the contest, I've added a solution that checks for pattern signatures in the horizontal and vertica histograms.
This solution still is not complete : It doesn't work on scaled graphics, which appears in part of the mandatories unit tests.
// Read inputs from stdin. Write outputs to stdout.
#include <stdlib.h>
#include <stdio.h>
char output[255];
int ouput_count=0;
#define H_MARGIN 5
#define V_MARGIN 2
static int s_noire_interligne_tab[] = {149, 145, 143, 139, 139, 137, 136, 136, 136, 136, 136,
136, 136, 136, 136, 136, 137, 139, 139, 143, 108, 110};
static int s_noire_interligne_length = sizeof(s_noire_interligne_tab)/sizeof(int);
static int s_vnoire_interligne_tab[] = {10, 8, 4, 4, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 2,
2, 4, 6, 6, 10};
static int s_vnoire_interligne_length = sizeof(s_vnoire_interligne_tab)/sizeof(int);
static int s_noire_ligne_tab[] = {153, 149, 147, 143, 143, 141, 139, 139, 139,
139, 139, 139, 139, 139, 139, 139, 141, 143, 143, 147, 112, 114};
static int s_noire_ligne_length = sizeof(s_noire_ligne_tab)/sizeof(int);
static int s_vnoire_ligne_tab[] = {10, 8, 4, 4, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 2, 2,
4, 6, 6, 10, 12};
static int s_vnoire_ligne_length = sizeof(s_vnoire_ligne_tab)/sizeof(int);
static int s_blanche_interligne_tab[] = {149, 145, 148, 148, 152, 152, 151, 153, 153,
153, 153, 153, 153, 153, 153, 151, 152, 152, 148, 148, 108, 110};
static int s_blanche_interligne_length = sizeof(s_blanche_interligne_tab)/sizeof(int);
static int s_vblanche_interligne_tab[] = {10, 8, 12, 16, 16, 15, 17, 16, 18, 18, 18, 18,
18, 16, 18, 16, 18, 18, 14, 10};
static int s_vblanche_interligne_length = sizeof(s_vblanche_interligne_tab)/sizeof(int);
static int s_blanche_ligne_tab[] = {153, 149, 152, 152, 156, 156, 154, 156, 156,
156, 156, 156, 156, 156, 156, 154, 156, 156, 152, 152, 112, 114};
static int s_blanche_ligne_length = sizeof(s_blanche_ligne_tab)/sizeof(int);
static int s_vblanche_ligne_tab[] = {10, 8, 12, 16, 16, 15, 17, 16, 18, 18, 18, 18,
18, 16, 18, 16, 18, 18, 14, 10, 12};
static int s_vblanche_ligne_length = sizeof(s_vblanche_ligne_tab)/sizeof(int);
static int const c_porteuse = 156;
static int s_porteuse_detection = 156;
void v_buffer_scan(char * pbuff,int w,int h,int h_start,int h_end, int q_flag);
int detect_pattern(int * tab,int tab_length, int offset, int * pattern, int p_length, int margin) {
for (int i = offset;i < tab_length - p_length + 1;i++) {
if ( abs( (tab[i]-s_porteuse_detection) - (pattern[0] - c_porteuse)) <= margin) {
int exit = 0;
for(int k = 1;(!exit) && (k < p_length);k++) {
if (abs ( (tab[i+k]-s_porteuse_detection) - (pattern[k]- c_porteuse)) > margin) {
exit = 1;
}
}
if (exit != 1) {
return i;
}
}
}
return -1;
}
int detect_inverted_pattern(int * tab,int tab_length, int offset, int * pattern, int p_length, int margin) {
for (int i = offset;i < tab_length - p_length + 1;i++) {
if ( abs((tab[i]-s_porteuse_detection) - (pattern[p_length-1] - c_porteuse)) <= margin) {
int exit = 0;
for(int k = 1;(!exit) && (k < p_length);k++) {
if (abs ((tab[i+k]-s_porteuse_detection) - (pattern[p_length-1-k] - c_porteuse)) > margin) {
exit = 1;
}
}
if (exit != 1) {
return i;
}
}
}
return -1;
}
void add_output(char note, char color){
if (ouput_count > 0) {
output[ouput_count]=' ';
ouput_count++;
}
output[ouput_count]=note;
ouput_count ++;
output[ouput_count]=color;
ouput_count++;
output[ouput_count] = 0;
}
void fill_buffer(char * pbuff, int w,int h,char col,int length,int offset) {
for (int i = offset;i < offset+length;i++) {
pbuff[i] = col;
}
}
char getpixel(char * pbuff,int w,int h,int i,int j) {
return pbuff[j*w+i];
}
void h_buffer_scan(char * pbuff,int w,int h) {
int * wBuff = (int*)malloc(sizeof(int)*w);
for (int i = 0;i < w;i++) {
wBuff[i] = 0;
for(int j = 0;j < h;j++) {
wBuff[i] += getpixel(pbuff,w,h,i,j);
}
}
/*
int val = 0;
val = wBuff[0];
for (int i = 0;i < w;i++) {
if (s_porteuse_detection == 0 && wBuff[i] != wBuff[0] ) {
s_porteuse_detection = wBuff[i];
}
}
*/
for (int i = 0;i < w;i++) {
printf("%d ",wBuff[i] - s_porteuse_detection);
}
for (int i = 0;i < w;i++) {
int a = detect_pattern(wBuff,w, i, s_noire_ligne_tab, s_noire_ligne_length, H_MARGIN);
if (a == i) {
v_buffer_scan(pbuff,w,h,i,a+s_noire_ligne_length,1);
i += s_noire_ligne_length;
continue;
}
a = detect_inverted_pattern(wBuff,w, i, s_noire_ligne_tab, s_noire_ligne_length, H_MARGIN);
if (a == i) {
v_buffer_scan(pbuff,w,h,i,a+s_noire_ligne_length,1);
i += s_noire_ligne_length;
continue;
}
int b = detect_pattern(wBuff,w, i, s_noire_interligne_tab, s_noire_interligne_length, H_MARGIN);
if (b == i) {
v_buffer_scan(pbuff,w,h,i,b+s_noire_interligne_length,1);
i += s_noire_interligne_length;
continue;
}
b = detect_inverted_pattern(wBuff,w, i, s_noire_interligne_tab, s_noire_interligne_length, H_MARGIN);
if (b == i) {
v_buffer_scan(pbuff,w,h,i,b+s_noire_interligne_length,1);
i += s_noire_interligne_length;
continue;
}
int c = detect_pattern(wBuff,w, i, s_blanche_ligne_tab, s_blanche_ligne_length, H_MARGIN);
if (c == i) {
v_buffer_scan(pbuff,w,h,i,c+s_blanche_ligne_length,0);
i += s_blanche_ligne_length;
continue;
}
c = detect_inverted_pattern(wBuff,w, i, s_blanche_ligne_tab, s_blanche_ligne_length, H_MARGIN);
if (c == i) {
v_buffer_scan(pbuff,w,h,i,c+s_blanche_ligne_length,0);
i += s_blanche_ligne_length;
continue;
}
int d = detect_pattern(wBuff,w, i, s_blanche_interligne_tab, s_blanche_interligne_length, H_MARGIN);
if (d == i) {
v_buffer_scan(pbuff,w,h,i,d+s_blanche_interligne_length,0);
i += s_blanche_interligne_length;
continue;
}
d = detect_inverted_pattern(wBuff,w, i, s_blanche_interligne_tab, s_blanche_interligne_length, H_MARGIN);
if (d == i) {
v_buffer_scan(pbuff,w,h,i,d+s_blanche_interligne_length,0);
i += s_blanche_interligne_length;
continue;
}
}
free(wBuff);
}
void v_buffer_scan(char * pbuff,int w,int h,int h_start,int h_end, int q_flag) {
printf("\nvertical scan at: %d\n",h_start);
int * hBuff = (int*)malloc(sizeof(int)*h);
int col = 'H';
if (q_flag == 1) {
col = 'Q';
}
for (int j = 0;j < h;j++) {
hBuff[j] = 0;
for(int i = h_start;i < h_end;i++) {
hBuff[j] += getpixel(pbuff,w,h,i,j);
}
}
/*
for (int i = 0;i < h;i++) {
printf("%d ",hBuff[i]);
}
puts("");
*/
for (int i = 0;i < h;i++) {
int a = detect_pattern(hBuff,h, i, s_vnoire_ligne_tab, s_vnoire_ligne_length, V_MARGIN);
if (a == i) {
//printf("noire ligne dected at %d\n",i);
char cout = 'A' + 6 - ((a/12) - 1)%7;
add_output(cout, col);
i += s_vnoire_ligne_length;
continue;
}
int b = detect_pattern(hBuff,h, i, s_vnoire_interligne_tab, s_vnoire_interligne_length, V_MARGIN);
if (b == i) {
//printf("noire interligne dected at %d\n",i);
char cout = 'A' + 6 - ((b/12) - 1)%7;
add_output(cout, col);
i += s_vnoire_interligne_length;
continue;
}
int c = detect_pattern(hBuff,h, i, s_vblanche_ligne_tab, s_vblanche_ligne_length, V_MARGIN);
if (c == i) {
//printf("blanche ligne dected at %d\n",i);
char cout = 'A' + 6 - ((c/12) - 1)%7;
add_output(cout, col);
i += s_vblanche_ligne_length;
continue;
}
int d = detect_pattern(hBuff,h, i, s_vblanche_interligne_tab, s_vblanche_interligne_length, V_MARGIN);
if (d == i) {
//printf("blanche interligne dected at %d\n",i);
char cout = 'A' + 6 - ((d/12) - 1)%7;
add_output(cout, col);
i += s_vblanche_interligne_length;
continue;
}
}
free(hBuff);
}
int main()
{
int w, h;
scanf("%d %d", &w, &h);
printf("w=%d h=%d\n",w,h);
char str_num[10];
int ind = 0;
char * pbuf = (char*)malloc(sizeof(char)*w*h);
int offset = 0;
char curr_c = 0;
int cr = getchar();
while ((cr != EOF)) {
//printf("%c",cr);
cr = getchar();
if (cr == 'W' || cr == 'B') {
if (curr_c != 0) {
str_num[ind] = 0;
int length = atoi(str_num);
//printf("l=%d %d\n",length,offset);
int col;
if (curr_c == 'W'){
col = 1;
} else {
col = 0;
}
fill_buffer(pbuf, w,h,col,length,offset);
offset += length;
}
curr_c = cr;
ind = 0;
} else {
if (cr != ' ') {
str_num[ind]=cr;
ind++;
}
}
}
str_num[ind] = 0;
int length = atoi(str_num);
int col;
if (curr_c == 'W'){
col = 1;
} else {
col = 0;
}
fill_buffer(pbuf, w,h,col,length,offset);
offset += length;
h_buffer_scan(pbuf, w, h);
free(pbuf);
printf("%s\n",output);
return 0;
}