Torres

torres.c

/* Ejemplos de soluciones:
"2 1 2 3 2 3 2 1 2 2 1 4 3 2 3 1"
 ---------
| 3 4 2 1 |
| 2 1 4 3 |
| 4 3 1 2 |
| 1 2 3 4 |
 ---------

"4 3 2 1 1 2 2 2 4 3 2 1 1 2 2 2"
 ---------
| 1 2 3 4 |
| 2 3 4 1 |
| 3 4 1 2 |
| 4 1 2 3 |
 ---------

*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

int possibles[24][4] = {
    {1,2,3,4},
    {2,1,3,4},
    {3,1,2,4},
    {1,3,2,4},
    {2,3,1,4},
    {3,2,1,4},
    {3,2,4,1},
    {2,3,4,1},
    {4,3,2,1},
    {3,4,2,1},
    {2,4,3,1},
    {4,2,3,1},
    {4,1,3,2},
    {1,4,3,2},
    {3,4,1,2},
    {4,3,1,2},
    {1,3,4,2},
    {3,1,4,2},
    {2,1,4,3},
    {1,2,4,3},
    {4,2,1,3},
    {2,4,1,3},
    {1,4,2,3},
    {4,1,2,3},
};

// esta función sirve por si queremos trocear este programa
// en varios, entonces para guardar las permutaciones
// en otro programa c
int *get_possible(int i) {
    return possibles[i];
}

char calcular_pv(int a, int b, int c, int d) {
    // esta función recibe una lista de 4 numeros y devuelve el "punto de vista" (pv)
    int possible[] = { a, b, c, d };
    int pv = 0;

    int mas_alto = 0;
    int i = 0;

    while( i < 4 ) {
        int val = possible[i];

        if( val > mas_alto ) {
            pv++;
            mas_alto = val;
        }

        i++;
    }

    return '0' + pv;
}

char *tabla_a_secuencia(int *tabla[]) {
    char *secuencia = malloc(32); // el resultado tienen 16 chars, 15 espacios, 0 final = 32
    int i = 0;
    int j;

    // pv de arriba:
    j = 0;
    while( j < 4 ) {
        secuencia[i++] = calcular_pv( tabla[0][j], tabla[1][j], tabla[2][j], tabla[3][j] );
        secuencia[i++] = ' ';
        j++;
    }

    // pv de abajo:
    j = 0;
    while( j < 4 ) {
        secuencia[i++] = calcular_pv( tabla[3][j], tabla[2][j], tabla[1][j], tabla[0][j] );
        secuencia[i++] = ' ';
        j++;
    }

    // pv de izq:
    j = 0;
    while( j < 4 ) {
        secuencia[i++] = calcular_pv( tabla[j][0], tabla[j][1], tabla[j][2], tabla[j][3] );
        secuencia[i++] = ' ';
        j++;
    }

    // pv de dcha:
    j = 0;
    while( j < 4 ) {
        secuencia[i++] = calcular_pv( tabla[j][3], tabla[j][2], tabla[j][1], tabla[j][0] );
        secuencia[i++] = ' ';
        j++;
    }

    secuencia[i-1] = '\0';
    return secuencia;
}

void salir_programa_con_error(char *mensaje) {
    write( 1, mensaje, strlen(mensaje) );
    exit(1);
}

void validar_entrada( char *entrada ) {
    int i = 0;
    int len = strlen(entrada);

    if( len != 31 ) {
        salir_programa_con_error("Error: longitud de entrada inválida. Tiene que tener 31 caracteres!\n");
    }

    while( i < len ) {
        char num = entrada[i];

        // chequeamos que sean números de entre 1 y 4
        if( num < '1' || num > '4' ) {
            salir_programa_con_error("Error: hay caracters invalidos. Solo se permiten 1, 2, 3 y 4!\n");
        }

        // chequeamos que estén separados por espacios
        char separador = entrada[i+1];
        if( separador != ' ' && separador != '\0') {
            salir_programa_con_error("Error: los números deben estar separados por espacios!\n");
        }
        i+=2;
    }
}

int son_iguales( char *a, char *b ) {
    // aqui comparamos el string de entrada y la secuencia de la tabla en cuestión
    //  retornamos 0 (falso) si no son iguales, y 1 si lo son
    //   "4 1 2 3 1 2 2 3 4 3 2 1 2 2 3" es igual "4 1 2 3 1 2 2 3 4 3 2 1 2 2 3"

    int i = 0;
    while( i < 31 ) { // 16 chars, 15 espacios = 31
        if( a[i] != b[i] ) {
            // si hay tan solo 1 character distinto, no son iguales!
            return 0;
        }
        i++;
    }
    return 1;
}

char *to_string( int possible[] ) {
    // esta función convierte un array de 4 ints en un string de tipo "1 2 3 4"
    // se usa para visualizar la tabla en pantalla
    int i = 0;
    int j = 0;

    char *possible_str = malloc(9); // 4 chars, 4 espacios y 1 nulo al final

    while( i < 4 ) {
        possible_str[j] = possible[i] + '0';
        possible_str[j+1] = ' ';
        i++;
        j+=2;
    }

    possible_str[7] = '\0';  // nos comemos el espacio final

    return possible_str;
}

int tabla_es_legal(int *tabla[]) {
    int i = 0;
    int j = 0;
    while (i < 4) {
        if (tabla[i][0] == tabla[i][1] ||
                tabla[i][0] == tabla[i][2] ||
                tabla[i][0] == tabla[i][3] ||
                tabla[i][1] == tabla[i][2] ||
                tabla[i][1] == tabla[i][3] ||
                tabla[i][2] == tabla[i][3]) {
            return 0;
        }
        if (tabla[0][i] == tabla[1][i] ||
                tabla[0][i] == tabla[2][i] ||
                tabla[0][i] == tabla[3][i] ||
                tabla[1][i] == tabla[2][i] ||
                tabla[1][i] == tabla[3][i] ||
                tabla[2][i] == tabla[3][i]) {
            return 0;
        }
        i++;
    }
    return 1;
}

void imprime_tabla(int *tabla[]) {
    write( 1, to_string( tabla[0] ), 7 );
    write( 1, "\n", 1 );
    write( 1, to_string( tabla[1] ), 7 );
    write( 1, "\n", 1 );
    write( 1, to_string( tabla[2] ), 7 );
    write( 1, "\n", 1 );
    write( 1, to_string( tabla[3] ), 7 );
    write( 1, "\n", 1 );
}

int main(int argc, char **argv) {
    char *entrada = argv[1];  // coge el primer parámetro enviado en la llamada a.out en el shell

    validar_entrada(entrada);

    int rowpos1, rowpos2, rowpos3, rowpos4;

    rowpos1 = 0;

    // anidamos 3 bucles para generar las 255 mil permutaciones (tablas posibles)
    //  (el número de permutaciones se calcula con la formula del factorial ===> 24! / 20!)
    while( rowpos1 < 24 ) {
        rowpos2 = 0;
        while( rowpos2 < 24 ) {
            rowpos3 = 0;
            while( rowpos3 < 24 ) {
                rowpos4 = 0;
                while( rowpos4 < 24 ) {

                    int *tabla[] = {
                        get_possible(rowpos1),
                        get_possible(rowpos2),
                        get_possible(rowpos3),
                        get_possible(rowpos4)
                    };

                    // si la tabla tiene números duplicados en vertical y horizontal, es inválida, no la queremos
                    //   así que llamamos esta función que verifica si la tabla es legal
                    if( tabla_es_legal( tabla ) ) {
                        // printf( ">>>> %d %d %d %d <<<<\n", rowpos1, rowpos2, rowpos3, rowpos4 );

                        char *secuencia = tabla_a_secuencia( tabla );
                        // printf( "SECUENCIA: [%s] == [%s]\n", secuencia, entrada );

                        // si la secuencia correspondiente a esta tabla
                        //   es igual a la que nos han pasado como parámetro ("entrada")
                        //   hemos dado con ello
                        if( son_iguales(secuencia, entrada) ) {
                            // Coinciden!
                            // imprimimos row1, row2, row3 y row4
                            // salimos del programa con return
                            imprime_tabla( tabla );

                            return 0;
                        }

                        // después de cada malloc() hay que liberar memoria con free()
                        free(secuencia);
                    }

                    rowpos4++;
                }
                rowpos3++;
            }
            rowpos2++;
        }
        rowpos1++;
    }
}

Lógica:

• creamos todas las tablas posibles de las 24 permutaciones de 1 2 3 4... unas 250 mil tablas

Para cada tabla generada:

• verificamos si la tabla es válida utilizando la función tabla_es_legal(). La función chequea si hay números duplicados en las columnas y las filas
• generamos una secuencia de 16 números con sus espacios intermedios (31 caracteres) para cada tabla legal con la función tabla_a_secuencia()
• comparamos la secuencia de entrada con la secuencia para esta tabla con la función son_iguales(), comparando caracter a caracter
• si son iguales, imprimimos la tabla y salimos del programa
• si no son, vamos a la siguiente tabla...