iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 12
0

先前我們已經有講過 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 個數字)並且用上面的沙漏去操作,最後得到一個最大的值。那就讓我們開始吧!

Python 3

#!/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
  • 再來看到我們定義了一個 Function 叫做 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 
  • 而在 User input 的部份我們用了 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!
  • 我們可以發現要做矩陣的操作如果直接土炮的話會有點複雜,所以通常我們會利用 Python 一個強大的 Library Numpy 來幫助我們定義矩陣,計算矩陣囉!有興趣的可以參考這裡

Scala

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)
    }
}
  • 首先我們先來讓 User input 變成二維陣列 A。 arrayA就是我們的二維陣列 A,透過 ArrayFromUI(Array(), 6) 來得到。ArrayFromUI 是一個遞迴函式,我們來看看裡頭。 xStdIn.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 的 mapflatMap),最後得到 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 就得到我們想要的結果了!
  • Scala 部分關於陣列計算的 library 可以參考這裡囉!

Golang

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
}
  • 因為在上面我們已經把概念都解釋得差不多,所以 Golang 的部分讓我們偷懶一下,假裝我們已經知道整個結構,所以有些地方就先寫死,主要是要看怎麼用 Golang 來解題。
  • 首先看到 rowsmake([][]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 的位置的元素相加得到結果,就不像之前的語言是透過兩個二維陣列的相乘來得到結果囉!
  • 如果我們想要在 Golang 取 sub-array,可以運用我們先前說的 Golang 中的 Slice。如果想做到二維陣列的相乘,可以簡單地運用 nested for loop 囉!
  • 其實 Golang 也有 library 在幫忙做像 Matrix 相關的計算,可以參考這裡囉!

Rust

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);
}
  • 由於在 Rust 中 Vector 比 Array 靈活,而且 Vector 也是以 Array 實作。所以我們這邊用的是 Vector。 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 並且對其做 mapmap 中的 closure 做的事情就是把每個 SplitWhitespace iterate 出來的 sub-string 去 parse 出 i32 的整數。最後再 .collect() 來得到 Vector of i32 並且將其 .pushtable 來得到 Vector of vector of i32 ,也就是我們的二維陣列 A。
  • 再來的概念就跟 Golang 的做法一樣,因為我們已經知道每個 sub-array 是哪一些元素會拿來相加,所以這裡就是透過雙層的 for-loop 來把每個 sub-array 的結果算出來,並且不斷更新最大的值到 result 之中。也就是我們要的答案囉!
  • 在 Rust 也一樣有 library 可以幫助進行 matrix 的相關計算,可以參考這裡囉!

結語

今天的字數跟時間應該是目前花最多的,寫完都頭昏啦~不過就是希望大家能夠對於多維以上的陣列在處理上有一些感覺囉!明天見!


上一篇
[Day 10] 零壹零壹零零壹
下一篇
[Day 12] 如果我有富爸爸
系列文
30 天把自己榨好榨滿的四週四語言大挑戰!30

尚未有邦友留言

立即登入留言