Planteo una solución en C para este reto, en el que nos dan un tamaño de lienzo (ancho, alto) y número de rectángulos de colores que dibujaremos, a continuación nos pasarán por cada color, el número del color y las coordenadas del rectángulo a dibujar. Teniendo en cuenta que el origen está en (0,0), debemos devolver la superficie de cada color, ordenada por color. Eso sí, si hay algún color que no sea visible, no debemos mostrarlo, ese es uno de los detalles de los que no informaban en el reto.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 | /** ************************************************************* * @file artist.c * @brief Challenge 15 * * @author Gaspar Fernández <blakeyed@totaki.com> * @version * @date 17 jun 2011 * Historial de cambios: * *************************************************************/ #include <stdlib.h> #include <stdio.h> #include <string.h> /* Huge string */ #define STRSIZE 1000 /* #define debug */ typedef struct TRect { int lx, ly, ux, uy, color; } TRect; int extrae_argumentos_dd(char *orig, char *delim, char ***args); void fill_image(int *img, int width, int color, int x1, int y1, int x2, int y2); void new_rect(int *img, int width, int height, int color, int lx, int ly, int ux, int uy); void see_image(int *img, int width, int height); char *trim2(char *s, const char *trimChars); void define_rect(TRect *r, int lx, int ly, int ux, int uy, int color); void draw_rect(int *img, int width, int height, const TRect *r); void swap(TRect* a, TRect* b); void quicksort(TRect* izq, TRect* der); int count_color(int *img, int width, int height, int color); int main(int argc, char *argv[]) { char **args; int control; char bigstr[STRSIZE]; int width; int height; int colors; int c; unsigned *img; /* Lots of colors available */ TRect *rectangles; int i; /* Read until EOF in stdin */ while (fgets(bigstr, STRSIZE, stdin)!=NULL) { control=extrae_argumentos_dd(trim2(bigstr,"\n\r "), " ", &args); if (control<=3) continue; width=atoi(args[0]); height=atoi(args[1]); colors=atoi(args[2]); if (control!=colors*5+3) { printf("Wrong number of parameters: %d; colors=%d\n", control, colors); /* for (c=0; c<control; c++) */ /* printf("P%d=%s\n", c, args[c]); */ continue; } /* Everything's ok */ img=malloc(sizeof(int)*height*width); fill_image(img, width, 1, 0,0, width-1, height-1); rectangles=malloc(sizeof(TRect)*colors); /* control=(control-3)/5; */ for (c=3, i=0; c<control; c+=5, i++) { define_rect(&rectangles[i], atoi(args[c+0]),atoi(args[c+1]),atoi(args[c+2]),atoi(args[c+3]),atoi(args[c+4])); } quicksort(&rectangles[0], &rectangles[colors-1]); for (i=0; i<colors; i++) { draw_rect(img, width, height, &rectangles[i]); } #ifdef debug see_image(img, width, height); #endif printf ("%d %d", 1, count_color(img, width, height, 1)); for (i=0; i<colors; i++) { control=count_color(img, width, height, rectangles[i].color); if (control>0) printf (" %d %d", rectangles[i].color, control); } printf("\n"); free(rectangles); free(img); } return EXIT_SUCCESS; } int count_color(int *img, int width, int height, int color) { int i, j; int s=0; for (i=0; i<height; i++) { for (j=0; j<width; j++) { if (img[i*width+j]==color) s++; } } return s; } void define_rect(TRect *r, int lx, int ly, int ux, int uy, int color) { r->lx=lx; r->ly=ly; r->ux=ux; r->uy=uy; r->color=color; } void draw_rect(int *img, int width, int height, const TRect *r) { new_rect(img, width, height, r->color, r->lx, r->ly, r->ux, r->uy); } void new_rect(int *img, int width, int height, int color, int lx, int ly, int ux, int uy) { #ifdef debug printf("LI: %d,%d | UR: %d, %d\n", lx, ly, ux, uy); #endif fill_image(img, width, color, lx, height-uy, ux-1, height-ly-1); } void fill_image(int *img, int width, int color, int x1, int y1, int x2, int y2) { int i, j; #ifdef debug printf("%d,%d -> %d,%d\n", x1,y1, x2,y2); #endif for (i=y1; i<=y2; i++) { for (j=x1; j<=x2; j++) { img[i*width+j]=color; } } } void see_image(int *img, int width, int height) { int i, j; for (i=0; i<height; i++) { for (j=0; j<width; j++) { printf("%2d ", img[i*width+j]); } printf("\n"); } } /* An old function I made */ int extrae_argumentos_dd(char *orig, char *delim, char ***args) { char *tmp; int num=0; /* Reservamos memoria para copiar la candena ... pero la memoria justa */ char *str= malloc(strlen(orig)+1); char **aargs; strcpy(str, orig); aargs=malloc(sizeof(char**)); tmp=strtok(str, delim); do { aargs[num]=malloc(sizeof(char*)); /* strcpy(aargs[num], tmp); */ aargs[num]=tmp; num++; /* Reservamos memoria para una palabra más */ aargs=realloc(aargs, sizeof(char**)*(num+1)); /* Extraemos la siguiente palabra */ tmp=strtok(NULL, delim); } while (tmp!=NULL); *args=aargs; return num; } char *trim2(char *s, const char *trimChars) { char *start = s; /* Nos comemos los caracteres al principio */ while(*start && strpbrk((const char*)start, trimChars)==start) ++start; char *i = start; char *end = start; /* Nos comemos los caracteres al final */ while(*i) { if( strpbrk(i++, trimChars)!=i-1 ) end = i; } /* Coloramos el perminador */ *end = 0; return start; } /* to order colors */ void quicksort(TRect* izq, TRect* der) { if(der<izq) return; TRect pivot=*izq; TRect* ult=der; TRect* pri=izq; while(izq<der) { while(izq->color<=pivot.color && izq<der+1) izq++; while(der->color>pivot.color && der>izq-1) der--; if(izq<der) swap(izq,der); } swap(pri,der); quicksort(pri,der-1); quicksort(der+1,ult); } void swap(TRect* a, TRect* b) { TRect temp=*a; *a=*b; *b=temp; } |
Para el parseo de la cadena, he utilizado las funciones trim2() y extrae_argumentos_dd(), con lo que podremos extraer sin problemas cada uno de los miembros de la cadena inicial.
Para ahorrar parámetros a la hora de pasarlos de un lado a otro (y me refiero a las coordenadas), he hecho el struct TRect, con el que trabajaremos más cómodamente, sólo hay que llamar a define_rect() para insertar en el registro la información. Además de la función draw_rect() que cambiará el origen de coordenadas a la esquina superior izquierda, que es con la que normalmente trabajamos.
También hay una función de depuración see_image(), a la que llamaba en mis pruebas para ver cómo quedaría el lienzo, la verdad es que era de mucha ayuda, ya que visualizando los datos todo es mucho más fácil.
Por último, como la gente de Tuenti nos tenía acostumbrados a datos de entrada totalmente diferentes en las pruebas de los algoritmos, incluí un quicksort de todos los colores, por si nos los daban desordenados, no fue el caso, pero ahí queda.
Pingback: Bitacoras.com /
Me sorprende un montón que casi todo el mundo haya hecho lo de crear un array con la imagen, rellenarlo y después leer pixel a pixel (tal vez el límite de tiempo les impulsó a implementar la primera solución que se les ocurrió). Es una solución que funciona, pero me parece un poco ineficiente, tanto espacial como temporalmente. Se me ocurren dos soluciones alternativas:
1) Eficiencia espacial, pero no temporal. Almacenas los rectángulos según te van llegando (no hace falta almacenar el array entero). Después, para cada pixel, vas leyendo la lista de rectángulos desde el final, y en cuanto encuentras un rectángulo que contiene al píxel, devuelves su color. Devolviendo 1 (lienzo) si ningún rectángulo contiene al pixel.
2) Eficiencia espacial y temporal. Empiezas con una lista que tiene sólo un rectángulo, que ocupa todo el lienzo y es de color 1. Cada vez que llega un rectángulo, compruebas las intersecciones con todos los que tienes, y los vas «partiendo» como haga falta (¡es más fácil de lo que parece!), de manera que en todo momento la lista de rectángulos ocupe exactamente todo el lienzo sin repetir píxeles. Después sólo hay que sumar las áreas de todos los rectángulos. Aquí mi código: http://pastebin.com/cYG8ds4z (observa que además tengo los rectángulos ordenados por color). De todos modos, incluso aunque los métodos de «partir» (substract y fullSubstract) son rápidos, tal vez los lienzos presentados fueran lo suficientemente pequeños como para que el método «bruto» de dibujar el lienzo fuera igual de rápido o incluso más.
También es verdad que yo soy un poco muy obseso de la eficiencia, ¿eh? Luego en la vida real estas cosas no se miran tanto con lupa, y a veces prima la velocidad con la que se programa.
@Ñbrevu
Me gusta tu método, es verdad que los lienzos eran muy pequeños, incluso yo me los esperaba más grandes, con los colores desordenados y con muchos más colores, dada la naturaleza de pruebas como la de las teclas o la de los buses… pero un lienzo tenía que ser muy grande para que no entrara en memoria, y vistos los tests propuestos antes de hacer el reto, todos entraban de sobra.
Por otra parte, es lo que tú dices, con lienzos pequeños, es más rápido almacenarlos enteros que hacer la sustracción como tú la haces, ya en lienzos grandes, tal vez el mío flaquee, es muy soba contando colores y dibujándolos. A ver si hago un benchmark o algo 🙂
Yo después de ver la entrada del 7 pensaba que pondrían, por lo menos, un lienzo de 10000×10000, así que tiré por el método laborioso. La cosa es que al principio tenía un método substract mucho más lioso, con 16 casos diferentes… una tortura, vaya. Luego me di cuenta de que podía generalizar y me salió un método bastante apañado.
El principal problema que le veo a mi método (y acabo de caer, ¿eh?) es que hace intersecciones con todos los rectángulos anteriores, y el número de rectángulos podría crecer mucho. En principio parece que el orden es N^2, con N el número de rectángulos, pero en realidad, como se van dividiendo, el orden creo que puede llegar a ser algo así como N·2^N en el peor caso (que es muy raro, pero puede pasar). En el mejor caso sí es N^2, con N el número de rectángulos (ni idea del caso medio. Es difícil de calcular), mientras que el método de almacenar los píxeles en memoria es como mucho de orden M·N, con M el número de píxeles y M el número de rectángulos. Teniendo en cuenta que M no es demasiado grande, es razonable que el método fácil pueda llegar a ser más rápido, aunque sigue gastando más memoria y desde luego es menos escalable.
El otro método que he propuesto, el que va recorriendo la lista de rectángulos al revés, pinta más interesante cuanto más lo pienso… es de orden M·N y probablemente sea más o menos igual de rápido (o lento) que el método estándar, pero te libras de tener todos los bytes en memoria (¡y de escribirlos hasta N veces!).
@Ñbrevu
Pero mira, sobre todo, la diferencia entre el método laborioso y el de «andar por casa» es que a ti te han llamado los de Tuenti. Tu método seguro que tiene mucho más papel que otra cosa. De todas formas, el número de triángulos en casi todos los casos ni se acercará al número de pixels.
Es difícil hacer que este programa se comporte perfectamente en todos los casos, ya para el segundo concurso, que el programa evalúe la entrada y vea qué método es mejor… pero ya estamos complicando mucho el tema.
Pingback: Poesía binaria » Recopilación de soluciones para los retos de #tuentiContest . Challenge #15 /
Yo creo que lo bueno (?) de mis soluciones es que no son las obvias: me he parado a pensarlas y a intentar hacerlas pensando en otras posibilidades. La mayoría de la gente, como digo, ha optado por la solución obvia de ir pintando el array; igual que en el problema de los relojes, que casi todas las soluciones que miré hacían el cálculo iterativamente, con lo que eran de complejidad lineal (con N muy grande, encima) y no constante. Eso me sorprendió un montón. O el de los emirps, que decía uno que lo había hecho en cinco minutos, pero es casi seguro que no lo había hecho eficiente; yo en ese monté un pollo bastante gordo con reutilización de sumas parciales, que habría estado bien aprovechado si la entrada hubiera sido una ristra bastante larga de números, en vez de 2 ó 3 como al final resultaron ser. Aunque mi método isPrime era muy malo.
@Ñbrevu
Estoy de acuerdo contigo. Tu solución del reloj me pareció buenísima, tanto en la primera como en la segunda. Es verdad que son soluciones más de pararse a pensar antes de ponerse a picar código como un loco.
Con la solución iterativa, no era excesivamente lento, era muy rápido, pero sí es cierto que pongo esto a calcular como un poseso, y has demostrado que no tiene mucho sentido.
Yo para los emirps al principio no fue mal, pero luego cuando vi que eran números enoormes, intenté también aprovechar resultados anteriores, aunque pude haberlo hecho mucho mejor. Sé que en ese sí me lo pude haber currado más, a lo mejor algún día lo hago tranquilamente. Además, me mató en la fase de submit, cuando uno de los números con los que probaban me desbordó el int, tenía que haber usado algo más grande… aunque en test todo fue ok.
Hombre, sí, con los relojes tienes un N muy largo pero cada paso es muy corto. Incluso aunque cojas diez millones de segundos o algo así, el tiempo sería razonable, pero desde luego muy lejos del óptimo. De mi solución al segundo problema del reloj lamento haberlo hecho todo a mano y luego no haberlo explicado, porque mirando el código daba la impresión de que los números estaban a voleo (sobre todo el 8786 y el 1464), cuando todo tenía un sentido y unos cálculos simples detrás.
¿El submit podía fallar? A mí, una vez pasado el test, no recuerdo que me diera ningún fallo nunca.
@Ñbrevu
Cierto, pero vamos echando un ratillo analizando el código seguro que se sacan esos numerajos, pero vamos, aunque lo suyo es ir documentando, es un concurso a contra-reloj prácticamente.
El submit no fallaba, lo que pasa es que en el submit también hacían pruebas al código y eran distintas que las del test, yo tenía en el script del submit un par de echo, del INPUT y del OUTPUT.
Pero aunque no funcionara, el submit se hacía.
Good step you have written of writing content relating to cooperate sense. Better yet good working skills and hope you write more of this soon.A Paris Proposal Alexa PenaVega Coat
Excellent article. I just stumbled across your blog and enjoyed reading your blog posts. I am looking for new articles to get more valuable information. Thanks a lot for the useful information.
You have a good point here! I totally agree with what you have said!! Thanks for sharing your views…hope more people will read this article!!!
Ryan Gosling Drive Jacket