Resolviendo el #TuentiContest: Problema 14 – Colors are beautiful

Volvemos a Java para leer imágenes. Ahota toca el problema 14.

Nuestra tarea ahora consiste en sumar los colores en una fila de una imagen. Un problema bastante sencillo que nos prepararía a los futuros retos que también tendrían imágenes de por medio.

Recuerda que también puedes ver mis soluciones a los otros problemas de la competición.

Si en el problema 12 te sorprendió que al resultado había que sumarle 25000, aquí quedarás loco cuando veas que hay que sumarle 1. ¿Por qué lo hacen?

Análisis del problema

Siguiendo la línea del problema 4, teníamos que volver a trabajar con un archivo de entrada por parámetros. El archivo era una imagen del logo de la competición en formato BMP.

Una vez leída la imagen, nos indicaban una fila y un color y teníamos que sumar los valores de dicho color a lo largo de la fila. Luego de eso, sumar 1.

A pesar de la simpleza del planteamiento, este problema sirve para repasar cosas interesantes sobre las imágenes en las computadores. Cada píxel de una imagen está compuesto por tres colores: rojo, verde y azul (en ese orden). Los 24 bits indican el espacio que ocupa cada píxel, correspondiendo 8 bits a cada color (8bits + 8bits + 8bits = rojo + verde + azul). Por lo tanto, nuestra misión era implementar una máscara que solo viera los bits que nos piden, los transformara a enteros y los sumara.

Solución enviada

Aquí Java hace verdaderamente fácil la lectura de la imagen. Como parte de su API encontramos la clase BufferedImage, que incluye métodos para leer imágenes en varios formatos y luego obtener los píxeles que queramos. Mi algoritmo simplemente parsea la entrada para saber el color y la fila, luego define la máscara que se debe utilizar y finalmente suma los valores recorridos.

import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.Scanner;

import javax.imageio.ImageIO;

public class Colors {
  public static void main(String[] args) {
    try {
      BufferedImage bmp = ImageIO.read(new File(args[0]));

      int dred = 16;
      int red = 255<<dred;

      int dgreen = 8;
      int green = 255<<dgreen;

      int dblue = 0;
      int blue = 255;

      Scanner scan = new Scanner(System.in);
      String query;
      while(scan.hasNext()){
        query = scan.next();
        char color = query.charAt(0);
        int line = Integer.parseInt(query.substring(1));

        int factor = 0;
        int dfactor = 0;
        switch(color){
        case 'R': case 'r':
          factor = red;
          dfactor = dred;
          break;
        case 'G': case 'g':
          factor = green;
          dfactor = dgreen;
          break;
        case 'B': case 'b':
          factor = blue;
          dfactor = dblue;
          break;
        }

        int suma =0;
        for(int i=0;i<bmp.getWidth();i++){
          suma += ((bmp.getRGB(i, line)&factor)>>>dfactor);
        }
        System.out.println(suma+1);
      }
    }catch(IOException e) {
    }
  }
}

El código en general es bastante legible. La línea 48 lee el valor del color deseado y lo convierte en entero. Recuerda que si debo ver el rojo o el verde, los bits que contienen esa información no son los menos significativos (111111110000000000000000 y 000000001111111100000000) y por lo tanto debo moverlos a la derecha para que me den el valor entero que representan.

Solución mejorada

La misma clase BufferedImage tiene un método que devuelve un rectángulo entero de colores. De todas formas se necesitaría una iteración adicional para sumar sus valores pero no deja de ser una variación interesante. Es una lástima que Java no tenga funciones como map o reduce pues nos dejarían el código verdaderamente corto, sin perder legibilidad. Como curiosidad, he implementado dichas funciones para que vean como queda la solución.

import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.Scanner;
import javax.imageio.ImageIO;

public class Colors {
  public static void main(String[] args) {
    try {
      BufferedImage bmp = ImageIO.read(new File(args[0]));

      Scanner scan = new Scanner(System.in);
      String query;
      while(scan.hasNext()){
        query = scan.next();
        char color = query.charAt(0);
        int line = Integer.parseInt(query.substring(1));

        MapReduce functions = new MapReduce(color);
        int[] colors = new int[bmp.getWidth()];
        bmp.getRGB(0, line, bmp.getWidth(), 1,
                     colors, 0, bmp.getWidth());
        int suma = functions.reduce(functions.map(colors));

        System.out.println(suma+1);
      }
    }catch(IOException e) {

    }
  }
}
class MapReduce {
  int factor,dfactor;

  int dred = 16;
  int red = 255<<dred;

  int dgreen = 8;
  int green = 255<<dgreen;

  int dblue = 0;
  int blue = 255;    

  public MapReduce(char color){
    switch(color){
    case 'R': case 'r':
      factor = red;
      dfactor = dred;
      break;
    case 'G': case 'g':
      factor = green;
      dfactor = dgreen;
      break;
    case 'B': case 'b':
      factor = blue;
      dfactor = dblue;
      break;
    }
  }

  public int[] map(int[] colors){
    int[] newColors = new int[colors.length];
    for(int i=0;i<colors.length;i++){
      newColors[i] = ((colors[i]&factor)>>>dfactor);
    }
    return newColors;
  }

  public int reduce(int[] colors) {
    int suma = 0;
    for(int c : colors){
      suma += c;
    }
    return suma;
  }
}

En esta solución he creado la clase MapReduce que se encarga de establecer la máscara y el desplazamiento y además implementa las funciones map y reduce específicas para esta situación. Es una clase amarrada al problema, por lo que no puede reutilizarse, pero funciona para que vean el potencial de este tipo de funciones. Además utilizo la función getRGB que devuelve la fila completa de píxeles. ¿Qué te parece esta solución? Abre una buena oportunidad para discutir cuál es la mejor manera de implementar dichas funciones de forma simple pero genérica en Java. ¿Alguna sugerencia?

Y tú, ¿cómo lo resolviste?

One thought on “Resolviendo el #TuentiContest: Problema 14 – Colors are beautiful

Leave a Reply