Project Euler -> Problema 11

Se parece en algo al Problema 8 pero es peor x_X

En la grilla de 20×20, 4 número en diagonal están marcados.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

El producto de 26 × 63 × 78 × 14 = 1788696.

Cual es el mayor producto de 4 número en cualquier dirección (arriba, abajo, izquierda, derecha o diagonal) en la grilla de 20×20?

asd asd asd😯

Vamos por parte.

El primer problema fue llenar la grilla xD


public class Problema11 {
    int[][] grilla =
        {{8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8},
        {49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 04, 56, 62, 0},
        {81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 03, 49, 13, 36, 65},
        {52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 36, 91},
        {22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80},
        {24, 47, 32, 60, 99, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50},
        {32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70},
        {67, 26, 20, 68, 2, 62, 12, 20, 95, 63, 94, 39, 63,  8, 40, 91, 66, 49, 94, 21},
        {24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72},
        {21, 36, 23,  9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95},
        {78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92},
        {16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57},
        {86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58},
        {19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40},
        {4, 52,  8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66},
        {88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69},
        {4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18,  8, 46, 29, 32, 40, 62, 76, 36},
        {20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16},
        {20, 73, 35, 29, 78, 31, 90, 01, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54},
        {1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48}};
    public long mayor = 0;
    
    public Problema11(){
        //Revisamos recorriendo de izquierda a derecha
        System.out.println(mayor);
        izader();
        System.out.println(mayor);
        arrabj();
        System.out.println(mayor);
        diagarrder();
        System.out.println(mayor);
        diagabader();
        System.out.println(mayor);
    }
    
    private void izader(){
        //Lo hacemos 20 veces (filas)
        for (int i = 0; i < grilla.length; i++) {
            //Fijamos el límite derecho. Llegamos hasta 16 (de der a izq)
            for (int j = 0; j <= grilla[0].length - 4; j++) {
                long multi = 1;
                //Desde la columna 0 hasta el límite derecho +4. Para llegar al 20
                //Paramos cuando estamos en la columna +4 avanzando sobre mi mismo
                for (int k = j; k < j + 4; k++) {
                    multi *= grilla[i][k];
                }
                if (multi > mayor)
                    mayor = multi;
            }
        }
    }
    private void arrabj(){
        //Los mesmo de arriba, simplemente invertimos las columnas por las filas al multiplicar
        for (int i = 0; i < grilla.length; i++) {
            for (int j = 0; j <= grilla[0].length - 4; j++) {
                long multi = 1;
                for (int k = j; k < j + 4; k++) {
                    multi *= grilla[k][i];
                }
                if (multi > mayor)
                    mayor = multi;
            }
        }
    }
    private void diagarrder(){
        for (int i = 0; i <= grilla.length - 4; i++) {
            for (int j = 0; j <= grilla[0].length - 4; j++) {
                long multi = 1;
                //Agregamos el auxiliar para avanzar a la derecha
                for (int k = j, aux = 0; k < j + 4; k++, aux++) {
                    multi *= grilla[i + aux][k];
                }
                if (multi > mayor)
                    mayor = multi;
            }
        }
    }
    private void diagabader(){
        for (int i = 0; i <= grilla.length - 4; i++) {
            //Ojo con el - 1 y el j-- Que aquí vamos pa tras
            for (int j = grilla[0].length - 4 - 1; j > 0; j--) {
                long multi = 1;
                for (int k = j + 4, x = 0; k > j; k--, x++) {
                    multi *= grilla[i + x][k];
                }
                if (multi > mayor)
                    mayor = multi;
            }
        }
    }
}

A todo esto, me hice un repositorio en BitBucket para alojar mejor los resultados😉

Acerca de MaritoCares

Ingeniero Informático. Con tendencias a la programación en [C#, VB].NET, Java(Web principalmente...), PHP, JavaScript, algo mínimo de [ruby, python], y el clásico C.
Esta entrada fue publicada en Java, Problemas Project Euler. Guarda el enlace permanente.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s