Publi

#tuentiContest Solución al Challenge 15 . Reto del artista en C

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.

También podría interesarte...

There are 10 comments left Ir a comentario

  1. Pingback: Bitacoras.com /

  2. Ñbrevu /
    Usando Mozilla Firefox Mozilla Firefox 3.6 en Windows Windows XP

    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.

  3. Gaspar Fernández / Post Author
    Usando Mozilla Firefox Mozilla Firefox 4.0.1 en Linux Linux

    @Ñ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 🙂

  4. Ñbrevu /
    Usando Mozilla Firefox Mozilla Firefox 3.6 en Windows Windows XP

    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!).

  5. Gaspar Fernández / Post Author
    Usando Mozilla Firefox Mozilla Firefox 4.0.1 en Linux Linux

    @Ñ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.

  6. Pingback: Poesía binaria » Recopilación de soluciones para los retos de #tuentiContest . Challenge #15 /

  7. Ñbrevu /
    Usando Mozilla Firefox Mozilla Firefox 3.6 en Windows Windows XP

    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.

  8. Gaspar Fernández / Post Author
    Usando Mozilla Firefox Mozilla Firefox 4.0.1 en Linux Linux

    @Ñ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.

  9. Ñbrevu /
    Usando Mozilla Firefox Mozilla Firefox 3.6 en Windows Windows XP

    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.

  10. Gaspar Fernández / Post Author
    Usando Mozilla Firefox Mozilla Firefox 4.0.1 en Linux Linux

    @Ñ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.

Leave a Reply