先前我們已經有講過 Array 以及各語言與 Array 類似的資料結構，現在讓我們進一步來看當我們的 Array 從 Single dimension 變成 Multiple dimensions 的時候，該怎麼來使用呢？
今天挑戰的題目如下說明。假使我們有如下的二維矩陣 A：
1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 2 4 4 0
0 0 0 2 0 0
0 0 1 2 4 0
另外用如下圖的形狀來表示一個 hourglass (沙漏)。
a b c
d
e f g
當我用這個沙漏從左到右，從上到下 (step = 1)去掃原來的二維矩陣，每次就是把疊在一起的部分抓出來，並且把數字相加。我們的目標就是找出數字加起來最大的值是多少。舉例，如果我們用上面的沙漏跟二維矩陣 A 去操作的話，會掃出下面這麼多個組合：
1 1 1 1 1 0 1 0 0 0 0 0
1 0 0 0
1 1 1 1 1 0 1 0 0 0 0 0
0 1 0 1 0 0 0 0 0 0 0 0
1 1 0 0
0 0 2 0 2 4 2 4 4 4 4 0
1 1 1 1 1 0 1 0 0 0 0 0
0 2 4 4
0 0 0 0 0 2 0 2 0 2 0 0
0 0 2 0 2 4 2 4 4 4 4 0
0 0 2 0
0 0 1 0 1 2 1 2 4 2 4 0
最後可以發現最大的值是 19，由下面所掃出來的組合得到。
2 4 4
2
1 2 4
我們每次的 User input 就是去定義二維矩陣 A (每次輸入一行，並以空格隔開 每一行的 6 個數字)並且用上面的沙漏去操作，最後得到一個最大的值。那就讓我們開始吧！
#!/bin/python3
HOUR_GLASS = [[1, 1, 1], [0, 1, 0], [1, 1, 1]]
def multiply(a, b):
result = 0
for i in range(len(a)):
for j in range(len(a[0])):
result += a[i][j] * b[i][j]
return result
A = []
for _ in range(6):
row = [int(element) for element in input().strip().split(' ')]
A.append(row)
results = []
steps = len(A[0]) - len(HOUR_GLASS[0]) + 1
for i in range(steps):
for j in range(steps):
sub = [row[j:j+3] for row in A[i:i+3]]
results.append(multiply(sub, HOUR_GLASS))
print(max(results))
HOUR_GLASS ，是一個 List of list (相當於 2D Array)，其中 1 的部分表示待會和二維矩陣 A 作用時重疊的部分，相當於：1 1 1
0 1 0
1 1 1
mutiply ，會把 input 的兩個 2D array (實際上是兩個 List of list)，做 Element-wised 相乘，也就是分別把 兩個 2D array 中 index 相同的元素進行相乘後，把所有結果進行相加。所以當例如下面兩個 array 進到 multiply 後會得到 9，也就是得到我們題目中沙漏的效果。實際上的作法就是利用兩個 for 迴圈來把直的和橫的部份都掃過一遍。1 1 1 0 2 4
0 1 0 * 0 0 2
1 1 1 0 1 2
for _ in range(6) 來讓我們可以輸入 6 個 row 來產生 A。每個 row 是透過 [int(element)for element in input().strip().split(' ')] 得到。這裡邏輯是先 input() 得到 User 輸入的字串，再透過 strip() 把前後的空白去掉。透過 split(' ') 得到 row 中的元素 (以 List)，而最後透過整個 [int(element)for element in input().strip().split(' ')] 來得到新的 List 是把元素從剛才的 List 中取出並且轉換成 int。results 是一個用來存放每次掃描的結果。 steps 是計算出沙漏在這個二維矩陣 A，在上下以及左右的方向各有幾步需要走，才能把整個 A 給掃瞄完畢。最後是另一個雙層的 for-loop 。 sub 是取出 A 二維矩陣的 sub-array，也就是要跟沙漏進行作用的部分，每一個 sub-array 就是跟沙漏進到 multiply 這個 Function 做運算，並把結果放到 results 。當全部都掃瞄完畢並且把結果放到 results 後，我們就透過 max(results) 來找到最大的值啦！The end！import scala.io.StdIn
object Solution {
def main(args: Array[String]): Unit = {
def getArrayFromUI(current: Array[Array[Int]], remainTime: Int): Array[Array[Int]] = {
if (remainTime == 0) current
else {
val x = StdIn.readLine().split(" ").map(_.toInt)
getArrayFromUI(current :+ x, remainTime-1)
}
}
def multiply(arrayA: Array[Array[Int]], arrayB: Array[Array[Int]]) =
(for {
zipped <- arrayA.zip(arrayB)
(t1, t2) <- zipped._1.zip(zipped._2)
} yield {
t1 * t2
}).sum
val arrayA = getArrayFromUI(Array(), 6)
val hourGlass = Array(Array(1, 1, 1), Array(0, 1, 0), Array(1, 1, 1))
val steps = arrayA.length - hourGlass.length + 1
val results = for {
i <- (0 until steps).toArray
j <- (0 until steps).toArray
} yield {
val a = arrayA.slice(i, i + 3).map(_.slice(j, j + 3))
multiply(a, hourGlass)
}
println(results.max)
}
}
arrayA就是我們的二維陣列 A，透過 ArrayFromUI(Array(), 6) 來得到。ArrayFromUI 是一個遞迴函式，我們來看看裡頭。 x 從 StdIn.readLine() 得到 User input 的 string，並且用 .split(" ") ，也就是以空白格當作 Separator 來得到 Array of string，也就是一個 row (Array)的元素們 (string)，最後 .map(_.toInt) ，來把裡頭的元素轉換成 Int。得到 x 後把它加掉現在目前得到的 Array current 之中 (用 :+)，然後遞迴下去，直到 remainTime 等於 0 時，就回傳最終的 Array，也就是二維陣列 A。附帶提一下 Array[Array[Int]] 就是說 Array of Array of Int (因為 Array of Int 是一維的，而 Array of Array of Int 就是二維囉)hourGlass 這時候就是用 Scala 初始化一個 Array instance 的方式。 steps 的概念跟 Python 的部分是一樣的。results ，也就是把每次 “掃描 sub-array 和沙漏做 element-wised 相乘後並相加所有元素” 的結果，通通存放在一個 Array。我們最後要的答案就是把這個 Array results 取 Max 得到答案 ( results.max)。而 results 是怎麼來的呢？首先我們看到 Scala 中的 for … yield 語法 (可參考這裡)，其實跟迴圈有點像，我們直接看個例子。就像 For loop 一樣， i 是 iterate Array(1, 2) ， j 是 iterate Array(3, 4) ，而 (i, j) 是我們希望每次 iterate 的組合所產生 (yield) 的結果，而這些結果最後會存到最一開始的資料結構之中，也就是 Array(1, 2) 的 Array 這個結構中 (進階：這裡跟 flatMap 有關係，有興趣可以查查 Scala 的 map 和 flatMap)，最後得到 Array((1, 3), (1, 4), (2, 3), (2, 4)) 。val result = for {
i <- Array(1, 2)
j <- Array(3, 4)
} yield (i , j)
result.foreach(println)
// result:
// (1,3)
// (1,4)
// (2,3)
// (2,4)
results ，這裡的 (0 until steps).toArray 會得到 Array(0,1, ... steps — 1) ，其實只是為了讓 i 可以 iterate 0~(steps-1)， j 也是相同的道理。而 yield 裡頭要產生的，就是像 Python 一樣，得到 sub-array 以及 hourglass 的相乘相加結果。取 sub-array a 的方式概念跟 Python 一樣 arrayA.slice(i, i+3).map(_.slice(j, j+3)) 就是先取出需要的 row (Array)，再對 row 去取出需要的元素 (map(_.slice(j, j+3))。得到 sub-array a 之後，和 hourGlass 一起丟到 multiply 這個 Function 來得到相乘相加結果。multiply 。這裡也是一個 for yield，首先我們先 iterate arrayA.zip(arrayB) ， zip 會把兩個 Array 中對應 index 的元素 “zip” 再一起，變成一個 tuple，例如 Array(1, 2).zip(Array(3, 4)) 會變成 Array((1, 3), (2, 4)) ，所以 arrayA.zip(arrayB) 的 type 會是 Array[(Array[Int], Array[Int])] ，而 zipped 是 iterate 的結果所以是 (Array[Int], Array[Int]) 。 zipped 會是下一個 iterate 的其中一個參數 (想成雙層 for-loop)，zipped._1.zip(zipped._2) 就是把 zipped 這個 tuple 中的兩個 Array 再 zip 一次得到 Array([Int, Int]) ，概念上就是 sub-array 和 hourglass 相同 index 的元素所組成的 tuple 的 Array。在 yield 中我們把這個 tuple 內的元素相乘，也就是 element-wised 的相乘，這樣整個 for-yield 就得到 Array of (element-wised 相乘) 了，最後對這個 Array .sum 得到相加後的結果囉！results 最後就是一個 Array，裡頭的元素就是每一組相乘相加的結果，對 results.max 就得到我們想要的結果了！package main
import (
"fmt"
"bufio"
"os"
"strings"
"strconv"
)
func main() {
reader := bufio.NewReader(os.Stdin)
rows := make([][]int, 6)
for i := 0; i < 6; i++ {
rowstr, _ := reader.ReadString('\n')
srow := strings.Split(strings.TrimSpace(rowstr), " ")
row := make([]int, 6)
for i, s := range srow {
n, _ := strconv.Atoi(s)
row[i] = n
}
rows[i] = row
}
var maxA int
for i := 0; i < 4; i++ {
for j := 0; j < 4; j++ {
a := computeA(rows, i, j)
if a > maxA {
maxA = a
}
}
}
fmt.Println(maxA)
}
func computeA(rows [][]int, row, col int) int {
var total int
total += rows[row][col]
total += rows[row][col+1]
total += rows[row][col+2]
total += rows[row+1][col+1]
total += rows[row+2][col]
total += rows[row+2][col+1]
total += rows[row+2][col+2]
return total
}
rows 是 make([][]int, 6) ，這裡是定義一個二維陣列，也就是 Array of array of int， 6 代表有 6 個 array of int。接著是個 for loop 來把 User input 逐行讀進來，rowstr, _ := reader.ReadString('\n') ， rowstr 是讀進來的一行字串，透過 strings.Split(strings.TrimSpace(rowstr), " ") ，先把前後的空白 ( strings.TrimSpace(rowstr)) 去掉，再以空白當 Separator (strings.Split(..., " ")) 來得到 Array of string (Array of 表示元素數字的字串)。接下來就是把這個 Array of string 變成 Array of integer (透過 strconv.Atoi(s) 把字串轉成整數)，存到 row 之中 (以 make([]int, 6) 初始化的 Array of integer)。最後把所有的 row 放到 rows 來得到 User 所輸入的二維陣列 A。maxA ，而過程之中就是不斷地去看 sub-array 和 hourglass 的相乘相加結果是否有出現更大的值。這裡的關鍵是 computeA(rows, i, j) 。computeA(rows, i, j) 內的做法是，因為我們已經知道 hourglass 的長相，所以知道其實我們要取的是每個 sub-array 的哪些值進行相加，咦？那相乘呢？因為我們知道 hourglass 內的元素不是 0 就是 1，如果是 1 的話，其實就是元素本身 (因為乘以 1 還是本身)，所以我們直接將 sub-array 中對應到 hourglass 的位置的元素相加得到結果，就不像之前的語言是透過兩個二維陣列的相乘來得到結果囉！fn main() {
let mut table: Vec<Vec<i32>> = vec![];
for _ in 0..6 {
let mut input = String::new();
std::io::stdin().read_line(&mut input).expect("Failed to read");
let buf = input.split_whitespace().map(|q| q.parse::<i32>().unwrap()).collect();
table.push(buf);
}
let mut result = 0;
for i in 0..4 {
for j in 0..4 {
let sum = table[i][j]
+ table[i][j+1]
+ table[i][j+2]
+ table[i+1][j+1]
+ table[i+2][j]
+ table[i+2][j+1]
+ table[i+2][j+2];
if sum > result { result = sum };
}
}
println!("{}", result);
}
table (mutable) 是 Vector of vector of i32 ，以 vec![] 來產生一個 instance。for _ in 0..6 { ... } 就是在把 User input 逐行讀取進來。和之前都一樣，把 User 每一行的輸入存到 input 之中 (std::io::stdin().read_line(&mut input).expect(“Failed to read”);)，接著我們 call split_whitespace() 來得到 SplitWhitespace 這個 struct，也是一個 Iterator 並且對其做 map ， map 中的 closure 做的事情就是把每個 SplitWhitespace iterate 出來的 sub-string 去 parse 出 i32 的整數。最後再 .collect() 來得到 Vector of i32 並且將其 .push 進 table 來得到 Vector of vector of i32 ，也就是我們的二維陣列 A。result 之中。也就是我們要的答案囉！今天的字數跟時間應該是目前花最多的，寫完都頭昏啦～不過就是希望大家能夠對於多維以上的陣列在處理上有一些感覺囉！明天見！
iThome鐵人賽
看影片追技術