Problema - Square Math

Este problema aparecio en la ronda 1 del Codejam 2009. El link del problema: http://code.google.com/codejam/contest/dashboard?c=186264#s=p2. En el problema se define lo que es el Square Math (SM) y se te pide encontrar la secuencia menor que genere este cuya suma sea igual a un valor determinado. Un SM tiene esta forma:

2+3
+4-
1+0

Una secuencia del Square Math que sume 20 es "5+5+5+5" y 2 es "2". Tambien te dicen que una secuencia es menor si es mas corta o si, siendo de igual longitud, es menor lexicograficamente. A simple vista, un enfoque de brute-force puede servir pero siendo los limites de las entradas son demasiado grandes incluso para la entrada pequeña.

El truco es el darse cuenta de que el problema se puede representar por medio de un grafo, donde cada nodo es una posible solucion para el query de q = suma. Y donde cada arista marca la posibilidad de ir de una solucion a otra en el SM. Luego se puede usar BFS (Breadth First Search) y una cola de prioridad para encontrar la solucion mas corta.

class Nodo{  

  int i; //la coordenada i de la posicion actual (vertical).

  int j; //la coordenada j de la posicion actual (horizontal). 

  int suma; //la suma acumulada hasta la posicion actual

  String exp; //auxiliar: la expresion hasta la pos. actual "2+2+3"  

}

Por ejemplo, el (0,0,2,"2") se conecta a (0,2,5,"2+3"), es decir sumamos 3 al nodo inicial yendo de (0,0) a (0,2) y pasando por (0,1) que es '+'. El nodo (0,0,2,"2") tambien se conecta al nodo (1,1,6,"2+4"). De igual manera todos los nodos que tengan que tengan la forma (0,0,X,"...") se conectan al nodo (1,1,X+4,"...+4"). Se comienza con un grafo como la imagen donde los nodos en amarillo son los nodos iniciales a considerar.

Este enfoque es correcto pero en realidad no es necesario generar un grafo real para calcular el bfs. En la funcion de BFS se puede ir generando cada nodo dinamicamente, encontrar sus nodos "hijos" y añadirlos en caso no existan.

Los nodos conforme se vayan generando se almacenaran en un arreglo de Nodos. Se usara una cola de prioridad (una cola normal pero que siempre se mantiene ordenada de acuerdo a una funcion de comparacion) para obtener el nodo siguiente a procesar en el BFS.

Nodo[][][] nodos = new Nodo[w][w][3000];
//almacenamos los nodos conforme los generamos
Queue<Nodo> cola = new PriorityQueue<Nodo>(500,
 new ComparadorNodo()); ;
// la cola de prioridad. Procesaremos primero los nodos
// con una expresion menor 

El tamaño "3000" del campo suma de nodos se da suponiendo que la suma maxima de un nodo esta dentro de -1500 y +1500. Esto si se cumple considerando que los querys se encuentran entre -250 y +250. El codigo del bfs seria algo asi:

private static Nodo bfs(String[] SM, int query) {
    int i,j;
    Nodo v;

    //si es el primer caso, generar los nodos iniciales
    if (cola.isEmpty()) {
        for(i=0;i<SM.length;i++){
            for(j=0;j<SM.length;j++){
                if(Character.isDigit(SM[i].charAt(j)))
                    cola.add(new Nodo(i,j,SM[i].charAt(j)-'0',""+
                            SM[i].charAt(j)));
            }
        }
    }

    //en caso ya se tenga la solucion, se busca la que tenga
    //menor expresion
    Nodo sol = null;
    ComparadorNodo cmp = new ComparadorNodo();
    for(i=0;i<SM.length;i++){
        for(j=0;j<SM.length;j++){
            Nodo n =nodos[i][j][query+1500];
            if(n!=null && (sol == null || cmp.compare(sol, n)>0))
                sol=n;
        }
    }
    if(sol!=null)
        return sol;

    while (!cola.isEmpty()) {
        v = cola.peek();
        if (v.suma == query) 
            return v;              
        v = cola.poll();

        List<Nodo> hijos = BuscarHijos(v,SM); //serian 16 hijos
        Collections.sort(hijos,cmp); //ordenarlos de acuerdo a exp.
        for (i = 0; i < hijos.size(); i++) {
            Nodo hijo = hijos.get(i);
            if (nodos[hijo.i][hijo.j][hijo.suma+1500]==null) {
                nodos[hijo.i][hijo.j][hijo.suma+1500] = hijo;
                cola.add(hijo);
            }
        }
    }
    return null;
}