https://projecteuler.net/problem=11
Se ahorra muchísimo tiempo al utilizar lenguajes de "alto nivel", que nos abstraigan el manejo de cadenas, que vigilen por nosotros si nos "salimos" de un array... Programar en C nos ayuda a recordar los intríngulis de la memoria y de cómo se hacen las cosas "por dentro".
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 #define MAX_MATRIX 20
6 #define MAX_TEST 4
7
8
9 /** Returns an array of strings, it doesn't care about limits */
10 void calculate_list(char *test_list[MAX_TEST], char *input[MAX_MATRIX][MAX_MATRIX], char *orientation, int x, int y) {
11 int i_inc = 0, j_inc = 0;
12 if (strcmp(orientation, "e") == 0) { // East
13 i_inc = 0 ; j_inc = 1;
14 } else if (strcmp(orientation, "ne") == 0) { // North - East
15 i_inc = -1 ; j_inc = 1;
16 } else if (strcmp(orientation, "n") == 0) {
17 i_inc = -1 ; j_inc = 0;
18 } else if (strcmp(orientation, "nw") == 0) {
19 i_inc = -1 ; j_inc = -1;
20 } else if (strcmp(orientation, "w") == 0) {
21 i_inc = 0 ; j_inc = -1;
22 } else if (strcmp(orientation, "sw") == 0) {
23 i_inc = 1 ; j_inc = -1;
24 } else if (strcmp(orientation, "s") == 0) {
25 i_inc = 1 ; j_inc = 0;
26 } else if (strcmp(orientation, "se") == 0) {
27 i_inc = 1 ; j_inc = 1;
28 } else {
29 return;
30 }
31 printf("Start: (%d,%d) //Orientation '%s': ", x, y, orientation);
32 for (int i = x, j = y, a = 0; a < MAX_TEST; i = i + i_inc, j = j + j_inc, a++) {
33 test_list[a] = input[i][j];
34 printf("%s ", test_list[a]);
35 }
36 printf("\n");
37
38 }
39
40 long calculate_product(char *test_list[MAX_TEST]) {
41 long result = 1;
42 for (int x = 0; x < MAX_TEST; x++)
43 result *= atoi(test_list[x]);
44 return result;
45 }
46
47 long check_list(char *test_list[MAX_TEST], long max_product) {
48 long tmp = calculate_product(test_list);
49 if (tmp > max_product) max_product = tmp;
50 printf("List: %s %s %s %s // Current product: %ld // Max. product: %ld\n", test_list[0], test_list[1], test_list[2], test_list[3], tmp, max_product);
51 return max_product;
52 }
53
54 int main() {
55 long max_product = 1;
56 char *test_list[MAX_TEST] = {"00", "00", "00", "00"};
57 char *input[MAX_MATRIX][MAX_MATRIX] = {
58 {"08", "02", "22", "97", "38", "15", "00", "40", "00", "75", "04", "05", "07", "78", "52", "12", "50", "77", "91", "08"},
59 {"49", "49", "99", "40", "17", "81", "18", "57", "60", "87", "17", "40", "98", "43", "69", "48", "04", "56", "62", "00"},
60 {"52", "70", "95", "23", "04", "60", "11", "42", "69", "24", "68", "56", "01", "32", "56", "71", "37", "02", "36", "91"},
61 {"22", "31", "16", "71", "51", "67", "63", "89", "41", "92", "36", "54", "22", "40", "40", "28", "66", "33", "13", "80"},
62 {"81", "49", "31", "73", "55", "79", "14", "29", "93", "71", "40", "67", "53", "88", "30", "03", "49", "13", "36", "65"},
63 {"24", "47", "32", "60", "99", "03", "45", "02", "44", "75", "33", "53", "78", "36", "84", "20", "35", "17", "12", "50"},
64 {"32", "98", "81", "28", "64", "23", "67", "10", "26", "38", "40", "67", "59", "54", "70", "66", "18", "38", "64", "70"},
65 {"67", "26", "20", "68", "02", "62", "12", "20", "95", "63", "94", "39", "63", "08", "40", "91", "66", "49", "94", "21"},
66 {"24", "55", "58", "05", "66", "73", "99", "26", "97", "17", "78", "78", "96", "83", "14", "88", "34", "89", "63", "72"},
67 {"21", "36", "23", "09", "75", "00", "76", "44", "20", "45", "35", "14", "00", "61", "33", "97", "34", "31", "33", "95"},
68 {"16", "39", "05", "42", "96", "35", "31", "47", "55", "58", "88", "24", "00", "17", "54", "24", "36", "29", "85", "57"},
69 {"78", "17", "53", "28", "22", "75", "31", "67", "15", "94", "03", "80", "04", "62", "16", "14", "09", "53", "56", "92"},
70 {"86", "56", "00", "48", "35", "71", "89", "07", "05", "44", "44", "37", "44", "60", "21", "58", "51", "54", "17", "58"},
71 {"19", "80", "81", "68", "05", "94", "47", "69", "28", "73", "92", "13", "86", "52", "17", "77", "04", "89", "55", "40"},
72 {"04", "52", "08", "83", "97", "35", "99", "16", "07", "97", "57", "32", "16", "26", "26", "79", "33", "27", "98", "66"},
73 {"88", "36", "68", "87", "57", "62", "20", "72", "03", "46", "33", "67", "46", "55", "12", "32", "63", "93", "53", "69"},
74 {"04", "42", "16", "73", "38", "25", "39", "11", "24", "94", "72", "18", "08", "46", "29", "32", "40", "62", "76", "36"},
75 {"20", "69", "36", "41", "72", "30", "23", "88", "34", "62", "99", "69", "82", "67", "59", "85", "74", "04", "36", "16"},
76 {"01", "70", "54", "71", "83", "51", "54", "69", "16", "92", "33", "48", "61", "43", "52", "01", "89", "19", "67", "48"},
77 {"20", "73", "35", "29", "78", "31", "90", "01", "74", "31", "49", "71", "48", "86", "81", "16", "23", "57", "05", "54"}
78 };
79 for (int x = 0; x < MAX_MATRIX; x++) {
80 for (int y = 0; y < MAX_MATRIX; y++) {
81 if (x < MAX_TEST - 1) {
82 if (y < MAX_MATRIX - MAX_TEST) {
83 calculate_list(test_list, input, "e", x, y);
84 max_product = check_list(test_list, max_product);
85 calculate_list(test_list, input, "se", x, y);
86 max_product = check_list(test_list, max_product);
87 }
88 calculate_list(test_list, input, "s", x, y);
89 max_product = check_list(test_list, max_product);
90 if (y > MAX_TEST - 1) { // Last columns, east => no
91 calculate_list(test_list, input, "sw", x, y);
92 max_product = check_list(test_list, max_product);
93 calculate_list(test_list, input, "w", x, y);
94 max_product = check_list(test_list, max_product);
95 }
96 } else if (x > MAX_MATRIX - MAX_TEST) { // Last rows, south not available
97 if (y < MAX_MATRIX - MAX_TEST) {
98 calculate_list(test_list, input, "e", x, y);
99 max_product = check_list(test_list, max_product);
100 calculate_list(test_list, input, "ne", x, y);
101 max_product = check_list(test_list, max_product);
102 }
103 calculate_list(test_list, input, "n", x, y);
104 max_product = check_list(test_list, max_product);
105 if (y > MAX_TEST - 1) {
106 calculate_list(test_list, input, "nw", x, y);
107 max_product = check_list(test_list, max_product);
108 calculate_list(test_list, input, "w", x, y);
109 max_product = check_list(test_list, max_product);
110 }
111 } else {
112 if (y < MAX_MATRIX - MAX_TEST) { //
113 calculate_list(test_list, input, "se", x, y);
114 max_product = check_list(test_list, max_product);
115 calculate_list(test_list, input, "e", x, y);
116 max_product = check_list(test_list, max_product);
117 calculate_list(test_list, input, "ne", x, y);
118 max_product = check_list(test_list, max_product);
119 }
120 calculate_list(test_list, input, "n", x, y);
121 max_product = check_list(test_list, max_product);
122 if (y > MAX_TEST - 1) {
123 calculate_list(test_list, input, "nw", x, y);
124 max_product = check_list(test_list, max_product);
125 calculate_list(test_list, input, "w", x, y);
126 max_product = check_list(test_list, max_product);
127 calculate_list(test_list, input, "sw", x, y);
128 max_product = check_list(test_list, max_product);
129 }
130 calculate_list(test_list, input, "s", x, y);
131 max_product = check_list(test_list, max_product);
132 }
133 }
134 }
135 }
136
La principal dificultad que he encontrado ha sido el propio lenguaje C, el código es un ejemplo de cómo no programar (pasando por referencia las variables tipo array, con muy pocas comprobaciones de límites, etc). Dándole una vuelta más, seguro que puede hacerse más conciso y no ir tanto caso por caso.
De todas formas, no ha estado mal el ejercicio. Viene bien para poner en valor nuestros Python, PHP, JavaScript y demás lenguajes de alto nivel.
No hay comentarios:
Publicar un comentario