Solving Perl Weekly Challeng 093 -- Max points on the same line, and the sum of binary tree paths.

作者：   發佈於：   #raku

Perl Weekly Challenge 093 -- It's been long months mostly staying at home. Luckly there are plenty of stuff to kill time. Besides the two tasks per week from Perl Weekly Challenge, there was the Advent of Code. It wouldn't be a nice chance of self-learning without doing these coding puzzles with a new programming language.

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

Solution #1 > Max Points

The input of this task is a collection of points on 2D plane, and the purpose is to find a line with maximum number of points on it. Time to review some basic geometry.

First is the condition for telling whether 3 points are on the sae line. Given arbitrary 3 points (pi, pj, pk), we could take line segment pi,pj and pj,pk with their slope. Since they share pj, the are the same line if and only if two slopes are the same.

From there, we could derive the following naive algorithm:

  1. Iterate through the collection all 3-point combinations of (pi,pj,pk)
    1. Take the segment pi,pj and save pi and pj as the points of that segment. Skip this step if segment pi,pj is already seen.
    2. If pi,pj,pk are one the same line, add pk to the saved record.
  2. Exaime the save records and find the lines with the most number of points in side.

Such algorithm, although pretty simple to describe, requires O(n³) in time, and O(n²) in space. Not a enery-saving one. Anyway, here's an implementation in Raku, with numerical labels matching its counterpart in the algorithm. 

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

For saving lines and their points, we use a plain Hash %lines, with keys constructed by just stringifiying the point and values being Array of points. Int array are by default, stringified with whitespcae-separated values. That is: 

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

With that, we could just use the expression "$pi - $pj" as the identifier of segment pi,pj. That makes strings such as "1 1 - 3 1".

The slope of two points with identical X-coordinate could be defined as Inf (infinitely large). In Raku, Inf == Inf is True, and Inf is not equal to any of numbers. Which means the case of vertical lines is transparently handled.

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)

Solution #2 > Sum Path

This seems to be the kind of assigments from Algorithm classes with a recursive solution. However one thing to note: each node is used not just once, but as many time as the number of paths that goes through them. The node 3 from example 2 is eused twice in calculating the sum, because it is on two paths.

There are no clear definition on the format of that input and how it should be convert to binary trees. Let me ignore that part.

Here's a basic definition of a binary tree that can hold Int payload. 

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

This problam can be solve with basic tree-traversal algorhm. The sum-and-paths subroutine defined below returns two values, one being the sum of paths, which is the answer, the other being the number of paths, which is required for the calcualtion. 

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);
}

At [1], we handle the terminal condition which is at the leave node. With sum being just the payload and the number of paths being exactly 1 -- there is exactly 1 way to traverse a single-node binary tree.

At [2], we handle the other cases by accumulating sum and paths from the left-tree and the right-tree.

At [3] the accumulated sum and paths are return. Note here that they won't be 0 because at least one of those two if statements are satisfied.

本文為《解 Perl Weekly Challenge 093 -- 最多共線點數與二元樹路徑和》之英文版。