16 August 2015

Problem 011

아래와 같은 20×20 격자가 있습니다.

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

위에서 대각선 방향으로 연속된 붉은 숫자 네 개의 곱은 26 × 63 × 78 × 14 = 1788696 입니다.

그러면 수평, 수직, 또는 대각선 방향으로 연속된 숫자 네 개의 곱 중 최대값은 얼마입니까?

Solution

작은 4 x 4 격자를 만들어서 모든 숫자 곱의 경우를 구하여 최대 값을 찾는다.

let gridStr:[String] = [
	 "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"]

let grid: [[Int]] = gridStr.map{ $0.componentsSeparatedByString(" ").map{ $0.toInt()! } }

let gridHorizonLength = grid[0].count
let gridVerticalLength = grid.count
let distance = 4
  • 수정 전
let result = [Int](0..<gridVerticalLength-distance).reduce(0) { (max1, y) in
	let maximum = [Int](0..<gridHorizonLength-distance).reduce(0) { (max2, x) in
		var maximum = 0
		let smallGrid = [Int](y..<y+distance).map { y1 in [Int](x..<x+distance).map { grid[y1][$0] } }
		maximum = max(maximum, [Int](0...3).reduce(1) { $0 * smallGrid[$1][$1] })
		maximum = max(maximum, [Int](0...3).reduce(1) { $0 * smallGrid[3-$1][$1] })
		maximum = max(maximum, [Int](0...3).reduce(0) { max3, y1 in
			let maximum = [Int](0...3).reduce(1) { $0 * smallGrid[y1][$1] }
			return maximum > max3 ? maximum : max3
		})
		maximum = max(maximum, [Int](0...3).reduce(0) { max3, x1 in
			let maximum = [Int](0...3).reduce(1){ $0 * smallGrid[$1][x1] }
			return maximum > max3 ? maximum : max3
		})
		return maximum > max2 ? maximum : max2
	}
	return maximum > max1 ? maximum : max1
}

println(result)	// 70600674
  • 수정 후
let result = reduce(0..<gridVerticalLength-distance, 0) { (maximum, y) in
	return max(maximum, reduce(0..<gridHorizonLength-distance, 0) { (max1, x) in
		let smallGrid = map(y..<y+distance){ y1 in map(x..<x+distance){ grid[y1][$0] } }
		var maxLists = [max1]
		maxLists += [reduce(0...3, 1){ $0 * smallGrid[$1][$1] }]
		maxLists += [reduce(0...3, 1){ $0 * smallGrid[3-$1][$1] }]
		maxLists += [reduce(0...3, 0){ max2, y1 in max(max2, reduce(0...3, 1){ $0 * smallGrid[y1][$1] })}]
		maxLists += [reduce(0...3, 0){ max2, x1 in max(max2, reduce(0...3, 1){ $0 * smallGrid[$1][x1] })}]
		return maxElement(maxLists)
		})
}

println(result)	// 70600674

문제 출처



blog comments powered by Disqus