解 Perl Weekly Challenge 093 -- 最多共線點數與二元樹路徑和

作者：gugod 發佈於：2021/01/02 #raku

Perl Weekly Challenge 093 -- 最近幾週在家時間很長，還好有不少事情可以用來打發時間。除了一週兩題的 Perl Weekly Challenge，尚有 12 月的 Advent Of Code 。用新學的程式語言來解這些題目，也算是能自我充實一下。

TASK #1 › Max Points

Submitted by: Mohammad S Anwar

You are given set of co-ordinates @N.

Write a script to count maximum points on a straight line when given co-ordinates plotted on 2-d plane.

Example 1:

|
|     x
|   x
| x
+ _ _ _ _

Input: (1,1), (2,2), (3,3)
Output: 3

Example 2:

|
|
| x       x
|   x
| x   x
+ _ _ _ _ _

Input: (1,1), (2,2), (3,1), (1,3), (5,3)
Output: 3

解 #1 > Max Points

這題的輸入是很多二維平面上的點，要找出的是同在一條直線上的點數。可以順便複習一下基礎平面幾何。

首先是判斷三點是否共線。任取三點 (pi, pj, pk)，可得 pi,pj 與 pj,pk 兩組線段，再取兩線段之斜率。兩線段具一共點 pj, 若兩斜率也相同，則此三點必定共在同一直線上。

以這判別方式為起點，尋思可得如下演算法：

逐一列舉出所有三個點的組合 (pi,pj,pk)
1. 將 pi,pj 作為一線段，pi,pj 為此線段中的兩個點，紀錄下來，倘若已經有此紀錄，則不再重複記錄。
2. 若 pi,pj,pk 共線，則將 pk 計入 pi,pj 線段中
逐一檢查紀錄，找出點數最多者。

此演算法時間複雜度為 O(n³)，空間複雜度為 O(n²)，除了思路簡潔，算不上是什麼省能源之流。總之，其 Raku 語實作如下，每處數字標對應到演算法中的步驟。

sub max-points( @points ) {
    my %lines;

    # [1]
    for @points.combinations(3) -> ($pi, $pj, $pk) {
        # [1.1]
        %lines{"$pi - $pj"} //= [$pi, $pj];

        my $slope_ij = slope($pi, $pj);
        my $slope_jk = slope($pj, $pk);

        # [1.2] (Inf == Inf) == True
        if $slope_ij == $slope_jk {
            %lines{"$pi - $pj"}.push($pk);
        }
    }

    # [2]
    my $maxline = %lines.pairs.max({ .value.elems });

    return $maxline.value.elems;
}

sub slope ($p1, $p2) {
    my $dx = $p2[0] - $p1[0];
    my $dy = $p2[1] - $p1[1];
    return $dx == 0 ?? Inf !! ($dy / $dx);
}

say max-points ((1,1), (2,2), (3,1), (1,3), (5,3));
#=> 3
#  [(2 2) (3 1) (1 3)]

紀錄線段的資料結構，在此直接用普通雜湊 %lines。其索引為每個點之子串形式，對應到的內容則是陣列。在 Raku 中整數數列能自動被轉換成字串。其預設格式是用空格隔開。也就是說：

my $S = (1, 2, 3);
say "$S" eq @S.join(" "); 
#=> True

所以在紀錄線段時，可以直接用 "$pi - $pj" 當作線段的識別字，實際上內容會像是 "1 1 - 3 1" 這樣。

當有兩點之 x 座標相同時，此兩點所構成線段之斜率可定義為 Inf (無限大)。在 Raku 語中 Inf == Inf 為真，且 Inf 不等於任何其他數字。所以垂直線這個特例無需另外特別處理。

TASK #2 › Sum Path

Submitted by: Mohammad S Anwar

You are given binary tree containing numbers 0-9 only.

Write a script to sum all possible paths from root to leaf.

Example 1:

Input:
     1
    /
   2
  / \
 3   4

Output: 13
as sum two paths (1->2->3) and (1->2->4)

Example 2:

Input:
     1
    / \
   2   3
  /   / \
 4   5   6

Output: 26
as sum three paths (1->2->4), (1->3->5) and (1->3->6)

解 #2 > Sum Path

這題似乎是修演算法課時會寫到的作業。看來可以用遞迴演算法來解，但有個要注意的地方：每個節點的值被使用的次數不會只有一次，而是等於其路徑數。如題目範例二中的 3 這個節點，由於有兩條路徑經過，所以就會在總和計算過程當中被使用兩次。

題目似乎並沒有仔細定義這輸入是如何轉換成為二元樹的，那就讓我忽略這部分，直接處理手動建好的二元樹吧。

先定義二元樹本身：

class IntBinaryTree {
    has Int $.payload;
    has $.left-child;
    has $.right-child;
}

然後配合基本的二元樹走訪演算法，就可以解決此題。以下 sum-and-paths 函式傳回值有兩項。第一項是路徑和，也就是本題所要求的解答。第二項是路徑數目，是在計算過程中需要的數字。

sub sum-and-paths ($tree) {
    # [1]
    unless $tree.left-child or $tree.right-child {
        return ($tree.payload, 1);
    }

    # [2]
    my $paths = 0;
    my $sum = 0;
    if $tree.left-child {
        my ($left-sum, $left-paths) = sum-and-paths($tree.left-child);
        $sum += $left-paths * $tree.payload + $left-sum;
        $paths += $left-paths;
    }
    if $tree.right-child {
        my ($right-sum, $right-paths) = sum-and-paths($tree.right-child);
        $sum += $right-paths * $tree.payload + $right-sum;
        $paths += $right-paths;
    }

    # [3]
    return ($sum, $paths);
}

在 [1] 處是設定終端條件。在葉節點時，路徑和就是該節點本身的值，而路徑數則為 1。

在 [2] 之後則是分別處理有左右子節點的狀況。將左右兩邊的路徑和與路徑數分別累加至 $sum 與 $paths 中。

在 [3] 處就是把累加完畢的數字回傳。另外注意此處實際上不會有兩者皆為 0 的狀況，因為在 [1] 處已經事先判別並處理了葉節點，所以在 [2] 處的兩個 if 條件至少會有一個成立。