Project Euler - 011 - Golang - Chinaunix - Powered by Discuz! Archiver

icymirror 发表于 2015-09-29 11:16

Project Euler - 011

本帖最后由 icymirror 于 2015-09-29 11:18 编辑

Problem 011:
In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

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

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.
What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

问题11：
在下面的20*20的表格里，有四个对角线方向的标识成红色的数字。
（表格同上，略）
这四个数字的积是：26 * 63 * 78 * 14 = 1788686
试找出在这个20*20的表格中，在同一方向上(横、竖、斜)相邻的四个数字的乘积的最大值是多少。

代码：
package main

import (
"fmt"
)

func Problem011(data [][]int, count int) int {
var height int = len(data)
if height < 1 {
return 0
}

var width int = len(data)
if (height < count || width < count) {
return 0
}

maxProduct := 0

// Check on horizental direction
for index := 0; index < height; index++ {
for subIndex := 0; subIndex < width - count; subIndex++ {
currentProduct := 1
for offset := 0; offset < count; offset++{
currentProduct *= data
}
if currentProduct > maxProduct {
maxProduct = currentProduct
}
}
}

// Check on vertical direction
for index := 0; index < width; index++ {
for subIndex := 0; subIndex < height - count; subIndex++ {
currentProduct := 1
for offset := 0; offset < count; offset++ {
currentProduct *= data
}
if currentProduct > maxProduct {
maxProduct = currentProduct
}
}
}

// Check on back slash direction
for index := 0; index < width - count; index++ {
for subIndex := 0; subIndex < height - count; subIndex++ {
currentProduct := 1
for offset := 0; offset < count; offset++ {
currentProduct *= data
}
if currentProduct > maxProduct {
maxProduct = currentProduct
}
}
}

// Check on slash direction
for index := count; index < width; index++ {
for subIndex := 0; subIndex < height - count; subIndex++ {
currentProduct := 1
for offset := 0; offset < count; offset++ {
currentProduct *= data
}
if currentProduct > maxProduct {
maxProduct = currentProduct
}
}
}

return maxProduct
}

func main() {
data := [][] int {{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,4,56,62,0},
   {81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,3,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,1,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}}
fmt.Println("Problem 011 result: ", Problem011(data, 4))
}

ba_du_co 发表于 2015-10-07 14:59

本帖最后由 ba_du_co 于 2015-10-09 14:06 编辑

拿来练练手。

70600674#!perl6
# g002edea

my @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>;

sub max-value {
my @direction =
   0..19, 0..16,0, -1, 0,1,
   0..16, 0..19, -1,0, 1,0,
   0..16, 0..16, -1, -1, 1,1,
   0..16, 3..19, -1,1, 1, -1;

@direction.map: -> $a, $b, $m, $n, $i, $j {
   $a.map: -> $x {
         |$b.map: -> $y {
            my $X = $x + $m;
            my $Y = $y + $n;
            [*] (0 .. 3).map: { @grid[ $X += $i ][ $Y += $j ] }
         }
   }
}
}

say max-value; # 70600674

zsszss0000 发表于 2016-08-17 17:10

Project 是否有什么比较快的算法啊？回复 1# icymirror

dorodaloo 发表于 2017-03-31 09:14

问题，看似很简单，可还真写不好哦
这个司机不简单，今天算是见识了。
是否有更好的思路。:mrgreen:

页: [1]

Chinaunix's Archiver

Project Euler - 011