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

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

## TASK #1 › Max Points

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

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

``````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)]``````

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

## TASK #2 › Sum Path

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

``````class IntBinaryTree {
has \$.left-child;
has \$.right-child;
}``````

``````sub sum-and-paths (\$tree) {
# [1]
unless \$tree.left-child or \$tree.right-child {
}

# [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);
}``````