Archivo

Entradas Etiquetadas ‘concurso’

#tuentiContest solución del Challenge 14 en C. Colours are beautiful

Lunes, 27 de Junio de 2011 Gaspar Fernández Sin comentarios

Presento aquí mi solución al reto 14, en el que nos pasan una imagen en BMP, y por la stdin nos dan una componente (R, G, B) y un número de línea. Tenemos que hacer la suma de los valores de esa componente a lo largo de la línea especificada, y luego sumar 1.

Para ello, vamos a valernos del post dedicado a la lectura de archivos BMP en C, esta será una de las aplicaciones que vamos a hacer.

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
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

#define STRSIZE 1000

typedef struct bmpFileHeader
{
  uint32_t size;
  uint16_t resv1;
  uint16_t resv2;
  uint32_t offset;
} bmpFileHeader;

typedef struct bmpInfoHeader
{
  uint32_t headersize;      /* DIB header size */
  uint32_t width;
  uint32_t height;
  uint16_t planes;         /* color planes */
  uint16_t bpp;            /* bits per pixel */
  uint32_t compress;
  uint32_t imgsize;    
  uint32_t bpmx;        /* X bits per meter */
  uint32_t bpmy;        /* Y bits per meter */
  uint32_t colors;      /* colors used */
  uint32_t imxtcolors;      /* important colors */
} bmpInfoHeader;

/* old function I made */
unsigned char *LoadBMP(char *filename, bmpInfoHeader *bInfoHeader);
int calculate_sum(bmpInfoHeader *info, unsigned char *img, char rgb, int line);

int main()
{
  bmpInfoHeader info;
  unsigned char *img;
  char bigstr[STRSIZE];
  int line_number;

  img=LoadBMP("trabaja.bmp", &info);

  while (fgets(bigstr, STRSIZE, stdin)!=NULL)
    {
      line_number=info.height-atoi(bigstr+1)-1; /* bmps are inverted. Line 0 is count*/
      printf("%d\n", calculate_sum(&info, img, bigstr[0],line_number));
    }

  return 0;
}

unsigned char *LoadBMP(char *filename, bmpInfoHeader *bInfoHeader)
{

  FILE *f;
  bmpFileHeader header;
  unsigned char *imgdata;
  uint16_t type;
  f=fopen (filename, "r");
  /* handle open error */
  fread(&type, sizeof(uint16_t), 1, f);
  if (type !=0x4D42)
    {
      fclose(f);
      return NULL;
    }
  fread(&header, sizeof(bmpFileHeader), 1, f);

  fread(bInfoHeader, sizeof(bmpInfoHeader), 1, f);
  imgdata=(unsigned char*)malloc(bInfoHeader->imgsize);
  fseek(f, header.offset, SEEK_SET);
  fread(imgdata, bInfoHeader->imgsize,1, f);
  fclose(f);

  return imgdata;
}

int calculate_sum(bmpInfoHeader *info, unsigned char *img, char rgb, int line)
{
  int i;
  int sum=0;
  int comp;
  char *bgr="BGR";
  char *tcomp=strchr(bgr, rgb);
  if (tcomp==NULL)
    return 0;

  comp=tcomp-bgr;

  for (i=0; i<info->width; i++)
    {
      sum+=img[3*(i+line*info->width)+comp];
    }
 
  return sum+1;
}

Ya que las cabeceras y la función LoadBMP() ya están analizadas en el post anterior. Analizaremos las funciones calculate_sum() y la principal.

En calculate_sum(), lo que hacemos es primero, obtener el número de la componente a extraer, ya que B=0, G=1, R=2, hallaremos la posición del carácter en la cadena, y si éste existe (tcomp!=NULL), en la variable comp almacenaremos dicha posición (como strchr devuelve un puntero a la parte de la cadena correspondiente, sólo tenemos que restar con la cadena con la que comparamos.
Luego, hacemos un for para recorrer todos los puntos de la línea, pero sólo leyendo los datos de la componente seleccionada. En cada iteración incrementaremos la variable sum para que nos devuelva la suma total de todos los pixels.

En la función principal, lo único que hacemos es cargar en memoria el BMP, y leer por la stdin la entrada propuesta Wxxx, donde W es la componente a leer (R,G,B) y xxx es el número de línea a leer. Desde main() invertimos la línea (como ya dijimos en los BMP, la imagen está boca abajo), por lo que en lugar de leer la línea Y, debemos leer la línea [ ALTO - Y - 1 ] (restamos 1 porque la primera línea es la 0).

Tal vez para hacer la función calculate_sum() más general, debería haber hecho la conversión de línea dentro de ésta (la conversión es algo interno), y la suma de 1 (es algo que nos pide el problema).

Recopilación de soluciones para los retos de #tuentiContest . Challenge #13

Domingo, 26 de Junio de 2011 Gaspar Fernández Sin comentarios

Últimamente he hablado acerca del I concurso de programación de Tuenti. Un concurso de programación Online que se llevó acabo durante la semana pasada (del 13 al 20 de Junio, muy mala fecha).

Podéis ver los enunciados de todos los problemas, con ejemplos sobre la entrada y salida (aunque a veces no hay que haerles mucho caso) en la web oficial del concurso, pero en Vidas Concurrentes lo encontramos todo en español.

Challenge #13 : The Other Clock

¿ Os acordáis del Challenge #6: The Clock ? En esta ocasión los leds no se apagan todos y se vuelven a encender al cambiar el segundo, ahora sólo se apagarán y se encenderán los leds justos, tendremos que contar cuántos leds se encuenden cada vez.

Soluciones:

Si no estás en la lista y quieres plantear tu solución, deja un comentario con tu link !

Actualización 2011/06/28 08:30 : Añadida solución de @theom3ga
Actualización 2011/06/28 08:35 : Añadida solución de @ricardclau
Actualización 2011/07/03 01:47 : Añadida solución de @frisco82
Actualización 2011/07/03 13:45 : Añadida solución de @Rosapolis
Actualización 2011/07/13 16:10 : Añadida solución de @lagunex

Recopilación de soluciones para los retos de #tuentiContest . Challenge #12

Sábado, 25 de Junio de 2011 Gaspar Fernández 2 comentarios

Últimamente he hablado acerca del I concurso de programación de Tuenti. Un concurso de programación Online que se llevó acabo durante la semana pasada (del 13 al 20 de Junio, muy mala fecha).

Podéis ver los enunciados de todos los problemas, con ejemplos sobre la entrada y salida (aunque a veces no hay que haerles mucho caso) en la web oficial del concurso, pero en Vidas Concurrentes lo encontramos todo en español.

Challenge #12 : The Stargate Problem

Tenemos que dar saltos entre planetas. Llegar de la Tierra a Atlantis, dando saltos entre planetas a través de Stargates, cada salto tendrá un coste en tiempo, empezaremos en la fecha estelas 25000 y si podemos llegar en el pasado mejor. Eso sí, si no podemos determinar la fecha, tendremos que decir: “BAZINGA”

Soluciones:

Si no estás en la lista y quieres plantear tu solución, deja un comentario con tu link !

Actualización 2011/06/25 13:23 : Añadida solución de @enwillyado
Actualización 2011/06/28 08:30 : Añadida solución de @theom3ga
Actualización 2011/07/03 01:45 : Añadida solución de @frisco82
Actualización 2011/07/03 13:45 : Añadida solución de @Rosapolis
Actualización 2011/07/13 02:48 : Añadida solución de @lagunex

Recopilación de soluciones para los retos de #tuentiContest . Challenge #11

Viernes, 24 de Junio de 2011 Gaspar Fernández 3 comentarios

Últimamente he hablado acerca del I concurso de programación de Tuenti. Un concurso de programación Online que se llevó acabo durante la semana pasada (del 13 al 20 de Junio, muy mala fecha).

Podéis ver los enunciados de todos los problemas, con ejemplos sobre la entrada y salida (aunque a veces no hay que haerles mucho caso) en la web oficial del concurso, pero en Vidas Concurrentes lo encontramos todo en español.

Challenge #11 : Gas Stations

Tenemos que planificar un viaje de X kilómetros, sabemos cuántos kilómetros podemos recorrer con el depósito lleno y tenemos localizadas las gasolineras por todo el trayecto, ¿qué paradas tendremos que hacer?

Soluciones:

Si no estás en la lista y quieres plantear tu solución, deja un comentario con tu link !

Actualización: 2011/06/24 20:30: Solución de @enwillyado
Actualización: 2011/06/28 08:30 : Añadida solución de @theom3ga
Actualización: 2011/07/03 01:45 : Añadida solución de @frisco82
Actualización: 2011/07/03 13:45 : Añadida solución de @Rosapolis
Actualización: 2011/07/08 12:42 : Añadida solución de @lagunex

Recopilación de soluciones para los retos de #tuentiContest . Challenge #10

Viernes, 24 de Junio de 2011 Gaspar Fernández 4 comentarios

Últimamente he hablado acerca del I concurso de programación de Tuenti. Un concurso de programación Online que se llevó acabo durante la semana pasada (del 13 al 20 de Junio, muy mala fecha).

Podéis ver los enunciados de todos los problemas, con ejemplos sobre la entrada y salida (aunque a veces no hay que haerles mucho caso) en la web oficial del concurso, pero en Vidas Concurrentes lo encontramos todo en español.

Challenge #10 : Key Combos

Se trata de crear un sistema donde se puedan configurar combinaciones de teclas y asignarles funciones. Más tarde, para probar, se enviarán esas combinaciones y el programa deberá decir la función definida. Las teclas podrán pulsarse en cualquier orden.

Soluciones:

Si no estás en la lista y quieres plantear tu solución, deja un comentario con tu link !

Actualización 2011/06/25 13:22 : Añadida solución de @enwillyado
Actualización 2011/06/28 08:30 : Añadida solución de @theom3ga
Actualización 2011/07/03 01:45 : Añadida solución de @frisco82
Actualización 2011/07/03 13:35 : Añadida solución de @Rosapolis
Actualización 2011/07/04 17:35 : Añadida solución de @lagunex

Recopilación de soluciones para los retos de #tuentiContest . Challenge #9

Viernes, 24 de Junio de 2011 Gaspar Fernández 2 comentarios

Últimamente he hablado acerca del I concurso de programación de Tuenti. Un concurso de programación Online que se llevó acabo durante la semana pasada (del 13 al 20 de Junio, muy mala fecha).

Podéis ver los enunciados de todos los problemas, con ejemplos sobre la entrada y salida (aunque a veces no hay que haerles mucho caso) en la web oficial del concurso, pero en Vidas Concurrentes lo encontramos todo en español.

Challenge #9 : Christmas Lights

Tenemos que implementar un sistema para gestionar luces de navidad con una secuencia especial.

Soluciones:

Si no estás en la lista y quieres plantear tu solución, deja un comentario con tu link !

Actualización 2011/06/28 08:25 : Añadida la solución de theom3ga
Actualización 2011/07/03 01:42 : Añadida solución de @frisco82
Actualización 2011/07/03 13:35 : Añadida solución de @Rosapolis
Actualización 2011/07/04 12:53 : Añadidas soluciones de @lagunex

Números grandes en C usando GMP. Resolución del primer reto de #tuentiContest (Super Hard Sum)

Viernes, 24 de Junio de 2011 Gaspar Fernández Sin comentarios

Aquí llega mi primera aportación a las soluciones de los retos del I concurso de programación de Tuenti. La utilización de números grandes es algo que siempre me llamó la atención, y normalmente utilizo bc cuando necesito algún cálculo. Este reto se podía resolver con bash/sed/bc y, aunque varios lenguajes permiten la utilización de números de precisión arbitraria “de serie”  como python y Java, yo decidí hacerlo en C, utilizando la biblioteca GMP.

En un lenguaje como C, es normal que no podamos utilizar números de precisión arbitraria con los operadores normales (+, -, *,…), en este caso tendremos que hacer llamadas a funciones de la biblioteca para realizar las operaciones, tampoco podremos utilizar un printf() normal para mostrarlos.

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
/**
*************************************************************
* @file hardsum.c
* @brief Tuenti Contest Test Phase
* Sum numbers separated by space line by line
*
* @author Gaspar Fernández <blakeyed@totaki.com>
* @version 0.0.2
* @date 12 jun 2011
*
* http://totaki.com/poesiabinaria
*
*************************************************************/


#include <stdio.h>
#include <string.h>
#include <gmp.h>

/* Huge string */
#define STRSIZE 1000

int main()
{
  char bigstr[STRSIZE];
  mpz_t tmp, sum;
  char * token;

  /* Initialize gmp numbers */
  mpz_init(tmp);
  mpz_init(sum);
 
  /* Read until EOF in stdin */
  while (fgets(bigstr, STRSIZE, stdin)!=NULL)
    {
      /* reset sum */
      mpz_set_si(sum, 0);
      token=strtok(bigstr, " \n");
      while (token!=NULL)
        {
          gmp_sscanf(token, "%Zd", &tmp); /* Extract number from token string */
          mpz_add(sum, sum, tmp);         /* Adds numbers */
          token=strtok(NULL, " \n");
        }
      gmp_printf("%Zd\n", sum);
    }

   return 0;
}

Para compilar, debemos incluir gmp:

$ gcc -o hardsum hardsum.c -lgmp

Para utilizar este tipo de variables numéricas, primero tendremos que inicializarlas con mpz_init(), otras funciones interesantes son:

  • mpz_set_si(): inicializa el número con un valor entero.
  • gmp_sscanf(): igual que scanf(), pero con la posibilidad de utilizar estas nuevas variables.
  • mpz_add(): realiza la suma de dos números
  • gmp_printf(): igual que printf(), pero con la posibilidad de utilizar estas nuevas variables.

GMP tiene muchísimas funciones para realizar gran cantidad de operaciones, se puede consultar la documentación aquí.

Recopilación de soluciones para los retos de #tuentiContest . Challenge #8

Jueves, 23 de Junio de 2011 Gaspar Fernández 2 comentarios

Últimamente he hablado acerca del I concurso de programación de Tuenti. Un concurso de programación Online que se llevó acabo durante la semana pasada (del 13 al 20 de Junio, muy mala fecha).

Podéis ver los enunciados de todos los problemas, con ejemplos sobre la entrada y salida (aunque a veces no hay que haerles mucho caso) en la web oficial del concurso, pero en Vidas Concurrentes lo encontramos todo en español.

Challenge #8 : The Biologist Problem

Eres un biólogo, y tienes que examinar dos cadenas de ADN. Recibimos las cadenas por la entrada estándar como un conjunto ordenado de bases de nucleótidos, hay que hallar el conjunto ordenado más grande entre ambas cadenas de ADN.

Ejemplo:

ATGTCTTCCTCGA
TGCTTCCTATGAC

Soluciones:

Si no estás en la lista y quieres plantear tu solución, deja un comentario con tu link !

Actualización 2011/06/28 08:25 : Añadida la solución de theom3ga
Actualización 2011/07/01 13:50 : Añadida la solución de @lagunex
Actualización 2011/07/03 01:42 : Añadida solución de @frisco82
Actualización 2011/07/03 13:35 : Añadida solución de @Rosapolis

Recopilación de soluciones para los retos de #tuentiContest . Challenge #7

Jueves, 23 de Junio de 2011 Gaspar Fernández 5 comentarios

Últimamente he hablado acerca del I concurso de programación de Tuenti. Un concurso de programación Online que se llevó acabo durante la semana pasada (del 13 al 20 de Junio, muy mala fecha).

Podéis ver los enunciados de todos los problemas, con ejemplos sobre la entrada y salida (aunque a veces no hay que hacerles mucho caso) en la web oficial del concurso, pero en Vidas Concurrentes lo encontramos todo en español.

Challenge #7 : The Tile Game

Tenemos dos series de símbolos y tenemos que transformar la primera serie en la segunda a través de tres tipos de operaciones (sustitución, adición y eliminación). Cada una de las operaciones tiene un coste, también especificado.

Soluciones:

Para más información podéis ver una explicación del algoritmo de Levenshtein.

Si no estás en la lista y quieres plantear tu solución, deja un comentario con tu link !

Actualización 2011/06/28 08:25 : Añadida la solución de @theom3ga
Actualización 2011/06/28 17:35 : Añadida la solución de @lagunex
Actualización 2011/07/03 01:42 : Añadida solución de @frisco82
Actualización 2011/07/03 13:35 : Añadida solución de @Rosapolis

Recopilación de soluciones para los retos de #tuentiContest . Challenge #6

Jueves, 23 de Junio de 2011 Gaspar Fernández 1 comentario

Últimamente he hablado acerca del I concurso de programación de Tuenti. Un concurso de programación Online que se llevó acabo durante la semana pasada (del 13 al 20 de Junio, muy mala fecha).

Podéis ver los enunciados de todos los problemas, con ejemplos sobre la entrada y salida (aunque a veces no hay que haerles mucho caso) en la web oficial del concurso, pero en Vidas Concurrentes lo encontramos todo en español.

Challenge #6 : The Clock

clockUn reto curioso y friki. Tenemos un reloj y nos preguntamos, ¿cuántos leds se encenderán desde las 00:00:00 pasados X segundos? Parece tonto, pero no lo entendí a la primera, me costó un rato, saber qué pedían, tal vez era el sueño. Es importante saber que el reloj es de 7 segmentos, y cada segundo se apagan todos los números y se vuelven a encender con la nueva hora.

Soluciones:

Si no estás en la lista y quieres plantear tu solución, deja un comentario con tu link !

Actualización 2011/06/23 13:54 : Corregido error tipográfico y añadida solución de @javipinero
Actualización 2011/06/24 06:20 : Añadida solución de @lagunex
Actualización 2011/06/28 08:23 : Añadida solución de @theom3ga
Actualización 2011/07/03 01:42 : Añadida solución de @frisco82
Actualización 2011/07/03 13:35 : Añadida solución de @Rosapolis

Visita otras webs de la red