Rendezvous on a Tetrahedron - 解法詳解，Swift 實作（中文）

日本語版は後ほどアップさせていただきます。

題目： <https://onlinejudge.u-aizu.ac.jp/problems/1384>

## 問題簡意

有兩隻毛毛蟲在正四面體上爬行，都從頂點 A 以夾角 d 的方向出發，爬行到鄰接面的時候爬行方向和鄰接邊夾角不會改變，求兩隻毛毛蟲爬了一段距離 l 後停下來所在的面是不是在同一個。是則回傳字串 YES 否則回傳字串 NO 。

## 解題大方向步驟

1. 把四面體展開成一個大三角型，以 A 為 (0,0) 在直角坐標中無限鋪開，會形成無數個正的正大三角形和反的正大三角形。在這裡把正的和反的組合起來成為一個平行四邊形。
2. 由於最後想要把爬行位置正規化到第一象限的第一個平行四邊形，因此把爬行位置都往第三和第四象限延伸，這樣可以讓後續的計算比較好處理。
3. 將兩隻毛毛蟲在第三或第四象限中的終點算出來。
4. 第一步的正規化：把點移動到第一象限和第二象限裡面第一行的平行四邊形中。移動方式是移動到自己右上的那一組平行四邊形。
5. 算出平行四邊形投影到正方形的線性變換矩陣，接著套到 (4.) 移動後的座標。
6. 把各自的 x 座標橫向移動到第一象限第一組的平行四邊形
7. 根據 (6) 取得的座標，就可以算出會落在哪個三角形
8. 根據 (7) 取得的結果，回傳兩者是否相同

## 各步驟詳解

輸入值以以下的值為例

``` text
CD 30 1
DB 30 1 
```

### ① 展開正四面體

這一段是來定下解題和思考方式的基礎。

在紙面上試著畫畫看就會發現直接對四面體運算無法解決。接著透過題目給的條件，就可以知道可以把三角形展開來思考。為了處理方便，我們把出發點的 A 放在座標軸 (0,0) 的位置上

<img width="203" alt="image.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/41979/5b51e4b3-3a27-a691-d92d-428a443f346d.png"> → <img width="245" alt="image.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/41979/88ca8e94-b9a3-3037-0ccc-62561f300f6f.png">

由於進到另外一個面之後行進方向不會改變，就會發現毛毛蟲的路徑在攤開的平面上會是直線，如下圖所示。這時候也會發現結束的點不只可能會在正的大正三角形上，也有可能會落在反的大正三角形裡面。

![image](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/41979/7ece14f7-e1c0-dbc2-32ff-e2894dcd77c5.png)

以正反大三角形為一組成為一個平行四邊形，對無限攤開的座標上色之後，會如下圖。
我們最後會期望把點正規化到在第一象限、接著原點的藍色平行四邊形裡面。

![image](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/41979/3cf1fbe3-1312-3e68-fd16-9e1996a7f87b.png)


### ② 決定前進方向

![image](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/41979/80bdb1eb-93a7-f8f5-3102-0c8d45f8170d.png)

基於我們的平行四邊形移動方式是不斷往右上移動，因此我們會想讓初始的位置都落在第三和第四象限。

由於套用 cos, sin 時需要用 **正向角** ，因此各自的方向向量從 0 開始計算，而移動的方向角如下：

vector AD = 360˚
vector AB = 300˚
vector AC = 240˚

於是實際的移動方向會是 「vector - θ」

這邊的 θ 就是題目中提到的 d ，為了好理解這邊用 θ 表示。

### ③ 計算原始的移動終點

- angle = vector - θ

l 是題目給的移動長度

根據式子和題目給的條件，算出的終點位置是 (l * cos(angle), l * sin(angle))

*註： cos 可求鄰邊，也就是 x 軸上的位置；而 sin 則可求對邊，也就是 y 軸上的位置*

根據這個式子，兩隻毛毛蟲的最後位置會如下：

＜毛毛蟲①＞

CD 30 1 -> (AC) 240˚ - 30˚ = 210˚ -> (l * cos(angle), l * sin(angle)) = **(-sqrt(3)/2, -1/2)**

＜毛毛蟲②＞

DB 30 1 -> (AD) 360˚ - 30˚ = 330˚ -> (l * cos(angle), l * sin(angle)) = **(sqrt(3)/2,- 1/2)**

### ④ 正規化到第一、二象限中的第一行平行四邊形群

第一和第二象限的第一行平行四邊形群為止移動 (也就是 y 會 >= 0)
以單位邊長為 1 ，三角形的高便會是 sqrt(3)/2 ，移動到上面緊鄰的四邊形中同樣位置的 y 軸距離的算法是 sqrt(3)/2 * 2 = sqrt(3))

因此各自的移動距離如下，示意則如圖

- x += 1
- y += sqrt(3) 

![image](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/41979/431e1e89-119f-cb29-4642-f13fe30fc316.png)

接下來就來移動我們的毛毛蟲吧！

＜毛毛蟲①＞

(-sqrt(3)/2, -1/2) -> **(-sqrt(3)/2+1, -1/2+sqrt(3))**

＜毛毛蟲②＞

(sqrt(3)/2,-1/2) -> **(sqrt(3)/2+1,-1/2+sqrt(3))**

而運算過程我傾向先不要把他們簡化，這比較算是個人的選擇 XDDD

### ⑤ 找出線性變換矩陣，並套到 ④ 中正規化之後的點

![image](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/41979/0f34a3a8-d327-b676-fed6-6790fc2f8b2e.png)

由於要判斷在哪個正三角形中，直接用正三角形找的話計算過程會變得異常複雜。於是這裡我們就要做如上圖的變換，把我們要面對的問題簡化。

而得出來的線性變換矩陣去對 ④ 算出來的座標運算之後，就會變換到正方形中相對的位置。這樣就比較好判斷到底是落在哪一個三角形中。

於是根據線性變換公式，把以 [(0,0),(1,2),(3,2),(2,0)] 圍起來的四邊形往 [(0,0),(0,2),(2,2),(2,0)] 圍成的正方形投影的線性變化矩陣如下。

*註：需要取兩個點變化前後的座標才可以解出變換公式中的 a, b, c, d 等係數*

這邊就不贅述該怎麼算線性變換矩陣（高中數學中通常叫他 A），可以自行去搜尋。或是參考這個 YouTube 影片，這位老師其實說明的還滿清楚的： <https://www.youtube.com/watch?v=V4POGsNaAd8>

得出線性變換矩陣如下（請原諒我不知道怎麼打矩陣出來）：

``` text
1  -1/sqrt(3)  →  a  b
0   2/sqrt(3)  →  c  d
```

接著就來更新我們毛毛蟲的位置吧，怎麼運算也可以參考上面貼的 YouTube 影片。

公式：

- newX = ax + by
- newY = cx + dy

＜毛毛蟲①＞ (-sqrt(3)/2+1, -1/2+sqrt(3))

- newX = 1 * (-sqrt(3)/2 + 1) + -1/sqrt(3) * (-1/2+sqrt(3)) = -sqrt(3)/3 ~= -0.577
- newY = 0 * (-sqrt(3)/2 + 1) + 2/sqrt(3) * (-1/2+sqrt(3)) = (6-sqrt(3))/3 ~= 1.423

＜毛毛蟲②＞ (sqrt(3)/2+1, -1/2+sqrt(3)) 

- newX = 1 * (sqrt(3)/2 + 1) + -1/sqrt(3) * (-1/2+sqrt(3)) = 2 * sqrt(3) / 3 ~= 1.547
- newY = 0 * (sqrt(3)/2 + 1) + 2/sqrt(3) * (-1/2+sqrt(3)) = (6-sqrt(3))/3 ~= 1.423

### ⑥ 移動到第一象限上的第一個大正方形

由於需要判斷落在哪一個面上， 還必須要把 x 移動到 0 < x < 2  之間（這時候 y 已經是在 0 到 2 之間了），由於移動到隔壁的正方形中同樣的位置的 x 軸差是 2 ，因此如果 x 大於 2 則不斷 -2 直到落到範圍之間，反之 x 小於 0 的話，則不斷 +2 直到進入範圍。當已經在範圍內的話，就不需要再做加減運算。

＜毛毛蟲①＞ (-sqrt(3)/3, (6-sqrt(3))/3) ~= (-0.577, 1.423)

(-sqrt(3)/3, (6-sqrt(3))/3) -> (-sqrt(3)/3 + 2, (6-sqrt(3))/3) ~= (1.423, 1.423)

＜毛毛蟲②＞ (2 * sqrt(3) / 3, (6-sqrt(3))/3) ~= (1.547, 1.423)

毛毛蟲② 的 x 軸已經在 0 到 2 之間了，因此不需要計算。

為了下個步驟方便，這邊就把各自大約的值算出來了。


### ⑦ 把會落在哪個點算出來

![image](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/41979/cd2c0878-bc02-c7d3-d785-6042f5d52aed.png)


上圖對應的面和條件如下表

| 面 | 條件 | |
|---|---|---|
| **① △ACD** | x < 1, y < 1, x + y < 1 | x > 1, y > 1, (x-1) + (y -1) > 1
| **② △BCD** | x < 1, y < 1, x + y > 1 | x > 1, y > 1, (x-1) + (y -1) < 1
| **③ △ABD** | x < 1, y > 1, x + (y-1) > 1 | x > 1, y < 1, (x-1) + y < 1
| **④ △ABC** | x < 1, y > 1, x + (y-1) < 1 | x > 1, y < 1, (x-1) + y > 1

來求各自的面：

＜毛毛蟲①＞ (-sqrt(3)/3 + 2, (6-sqrt(3))/3) ~= (1.423, 1.423) → **② △BCD**

＜毛毛蟲②＞ (2 * sqrt(3) / 3, (6-sqrt(3))/3) ~= (1.547, 1.423) → **② △BCD**

### ⑧ 把比較後的結果回傳

＜毛毛蟲①＞ ② △BCD
＜毛毛蟲②＞ ② △BCD

因為兩隻毛毛蟲都落在  ***② △BCD*** ，所以根據題目要求回傳 ***YES*** 。

## 程式語言的三角函數運算

程式語言的三角函數運算接受的參數都 **必須** 要是「弧角」 (radian) 而不是角度，因此在運算之前，需要多一步把角度轉換成弧角。

- radian = angle * (pi/180.0)

## 程式碼

``` swift
import Foundation

// MARK: - Implementation

enum Face: Int {
    case unkown = -1
    case acd = 1
    case bcd = 2
    case abd = 3
    case abc = 4
}

/// 算出單一毛毛蟲最終位置的面的方法
func findFace(edge: String, degree: Double, length: Double) -> Face {
    let pi = Double.pi
    let sqrt3 = sqrt(3)
    
    let startVertex = String(edge[edge.startIndex])
    var radian: Double!
    
    // ② 決定前進方向
    switch startVertex {
    case "D": // "D", 360˚
        radian = (360 - degree) * (pi/180.0)
    case "B": // "B", 300
        radian = (300 - degree) * (pi/180.0)
    default:  // "C", 240˚
        radian = (240 - degree) * (pi/180.0)
    }
    
    // ③ 計算原始的移動終點
    var x = length * cos(radian)
    var y = length * sin(radian)
    
    // ④ 正規化到第一、二象限中的第一行平行四邊形群
    while y < 0 {
        x += 1
        y += sqrt3
    }
    
    // ⑤ 找出線性變換矩陣，並套到 ④ 中正規化之後的點
    var newX = x * 1 + y * (-1/sqrt3)
    let newY = x * 0 + y * (2/sqrt3)
    
    // ⑥ 移動到第一象限上的第一個大正方形
    while newX <= 0 { newX += 2 }
    while newX >= 2 { newX -= 2 }
    
    // ⑦ 把會落在哪個點算出來
    if newX < 1 && newY < 1             { return (newX     + newY     < 1) ? .acd : .bcd }
    if newX < 1 && 1 < newY && newY < 2 { return (newX     + newY - 1 < 1) ? .abc : .abd }
    if 1 < newX && newX < 2 && newY < 1 { return (newX - 1 + newY     < 1) ? .abd : .abc }
    if 1 < newX && 1 < newY && newY < 2 { return (newX - 1 + newY - 1 < 1) ? .bcd : .acd }
    
    return .unkown
}


// MARK: - Main Method

func isAtDifferenceFaces(lines: [String]) -> String {
    // 先簡單的處理輸入值，接著執行找面的方法
    let results = lines
        .map { $0.components(separatedBy: " ") }
        .map { (edge: $0[0], degree: Double($0[1])!, length: Double($0[2])!) }
        .map { findFace(edge: $0.edge, degree: $0.degree, length: $0.length) }

    // ⑧ 把比較後的結果回傳
    return results[0] == results[1] ? "YES" : "NO"
}
```

### 執行和驗證

佈置 test cases

``` swift
/// Test cases from the problem
let sources = [
    ["CD 30 1", "DB 30 1"],
    ["BC 1 1", "DB 59 1"],
    ["BC 29 20", "BC 32 20"]
]
```

執行並驗證結果

``` swift
let results = sources.map(isAtDifferenceFaces(lines:))

if results == ["YES", "YES", "NO"] {
    print("Passed")
} else {
    print("Failed")
}
```

## 複雜度分析

- 令一毛毛蟲為 P, 爬行長度 lp 後的原始座標 Y 軸是 Yp, Y 軸正規化後的 X 軸是 Xp
- 令另一毛毛蟲為 Q, 爬行長度 lq 後的原始座標 Y 軸是 Yq, Y 軸正規化後的 X 軸是 Xq

則

- 時間複雜度： O(max(Yp/sqrt(3), Yq/sqrt(3), Xp/2, Xq/2) 簡化後為 O(max(Yp, Yq, Xp, Xq))
  - 算法就是單純取出有跑 loop 的地方，因為所有迴圈都沒有互相隸屬，所以直接從中取最大值即可。
- 空間複雜度：O(1)
  - 沒有字串長度或是陣列長度這一類的處理，因此把它歸為常數。

以上。