Problem 11 auf projecteuler.net

Die Lösung zu Problem 11 habe ich ebenfalls in PHP umgesetzt.

Meiner Meinung nach war das Schwierigste an der Aufgabe sich in verschiedene Richtungen im Array zu bewegen. Wenn das klappt, berechnet sich die Lösung allerdings sehr schnell:

Result: 70600674

real 0m0.012s user 0m0.008s sys 0m0.004s

<?php

$p = 0;

$grid = "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 ";


$grid = preg_replace('/0(\d)/', " $1", $grid);
$grid = explode("\n", $grid);

for ($i = 0; $i < count($grid); $i++)
  $grid[$i] = preg_split('/[ ]+/', trim($grid[$i]));

for($n = 0; $n <= 19; $n++) {
    for($k = 0; $k <= 16; $k++) {
        $p = max($p, $grid[$n][$k+0] * $grid[$n][$k+1] * $grid[$n][$k+2] * $grid[$n][$k+3]);
        $p = max($p, $grid[$k+0][$n] * $grid[$k+1][$n] * $grid[$k+2][$n] * $grid[$k+3][$n]);
    }
}

for($n = 0; $n <= 16; $n++) {
    for($k = 0; $k <= 16; $k++) {
        $p = max($p, $grid[$n+0][$k+0] * $grid[$n+1][$k+1] * $grid[$n+2][$k+2] * $grid[$n+3][$k+3]);
        $p = max($p, $grid[$n+0][$k+3] * $grid[$n+1][$k+2] * $grid[$n+2][$k+1] * $grid[$n+3][$k+0]);
    }
}

echo "Result: ".$p."\n";

?>

<?php

$p = 0;

$grid = "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 ";

$grid = preg_replace('/0(\d)/', " $1", $grid);

$grid = explode("\n", $grid);

for ($i = 0; $i < count($grid); $i++)

$grid[$i] = preg_split('/[ ]+/', trim($grid[$i]));

for($n = 0; $n <= 19; $n++) {

for($k = 0; $k <= 16; $k++) {

$p = max($p, $grid[$n][$k+0] * $grid[$n][$k+1] * $grid[$n][$k+2] * $grid[$n][$k+3]);

$p = max($p, $grid[$k+0][$n] * $grid[$k+1][$n] * $grid[$k+2][$n] * $grid[$k+3][$n]);

}

for($n = 0; $n <= 16; $n++) {

for($k = 0; $k <= 16; $k++) {

$p = max($p, $grid[$n+0][$k+0] * $grid[$n+1][$k+1] * $grid[$n+2][$k+2] * $grid[$n+3][$k+3]);

$p = max($p, $grid[$n+0][$k+3] * $grid[$n+1][$k+2] * $grid[$n+2][$k+1] * $grid[$n+3][$k+0]);

}

echo "Result: ".$p."\n";

mborm.net

Ein Computerprogramm tut was Du schreibst, nicht was Du willst.

Problem 11 auf projecteuler.net

Schreibe einen Kommentar Antworten abbrechen