Perlウィークリーチャレンジ093を解決してください--同じ線の上の最大点と二進木経路の合計.

Perl Weekly Challenge 093 -- それは、長い間、主にほとんど家にとどまっていました.幸いにも時間を殺すためにたくさんのものがあります.Perl Weekly Challengeから週につき2つの仕事の他に、コードの出現がありました.それは、新しいプログラミング言語でこれらのコーディングパズルをすることなく、自己学習の良いチャンスではないでしょう.

タスク・ワン・ポイント
提出されます:モハメッドsアンワール
あなたはコーデックのセットを与えられます＠N.
スクリプトを2次元平面上でプロットを与えられたときに直線上の最大点をカウントするために書き込みます.
例1 :

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

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

例2 :

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

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

1つのマックスポイント
このタスクの入力は、2 D平面上の点のコレクションです、そして、目的はそれの上で点の最大数で線を見つけることです.いくつかの基本的なジオメトリを確認する時間.
まず、SAEラインに3点があるかどうかを示す条件です.任意の3点(pi,pj,pk)を与えられた場合,ラインセグメントpi,pjとpj,pkを傾斜で取ることができた.彼らがPJを共有するので、2つの斜面が同じであるならば、同じ線は同じです.
そこから、以下のナイーブアルゴリズムを導き出した.

コレクション内のすべての3点の組み合わせを繰り返します.

セグメントpi、pjを取って、そのセグメントのポイントとしてpiとpjを保存してください.セグメントPI、PJが既に見られるならば、このステップを飛ばしてください.

pi、pj、pkが1つの同じ行であるならば、保存された記録にPKを加えてください.

Exameはレコードを保存し、側のポイントの最も多くの行を見つける.

そのようなアルゴリズムは、記述するのが非常に簡単であるが、時間内にO(n≠)、及び空間内でO(n←)を必要とする.ないenery保存1.とにかく、ここで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 , 点と配列の点である値をstrimpfiyingすることによって造られるキーで.Int arrayはデフォルトで、空白文字で区切られた文字列です.つまり、

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

それによって、私たちはその表現を使うことができました"$pi - $pj" セグメントpi、pjの識別子として.それは文字列を作る"1 1 - 3 1" .
同一のx座標を持つ2つの点の傾きをInf (無限大)楽でInf == Inf is True , and Inf は数値のどれにも等しくない.つまり、垂直線の場合は透過的に扱われる.

タスク△2周和パス
提出されます:モハメッドsアンワール
あなたは2 - 9のみ番号を含むバイナリツリーを与えられます.
ルートからリーフまでのすべての経路を合計するためにスクリプトを書きます.
例1 :

Input:
     1
    /
   2
  / \
 3   4

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

例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 >和経路
これは再帰的な解を持つアルゴリズムクラスからの帰属の一種である.しかし、注意する1つのもの:各ノードは、一度だけではなく、それらを通過するパスの数として多くの時間として使用されます.実施例2からのノード3は、2パスであるので、合計を計算する際に2回使用される.
その入力の形式と、バイナリツリーに変換する方法について明確な定義はありません.私にその部分を無視させてください.
ここでは保持できるバイナリツリーの基本的な定義ですInt ペイロード

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

この問題は、基本的なツリー横断アルゴリズムで解決できます.The sum-and-paths 以下で定義されたサブルーチンは2つの値を返します.そして、1が答えである経路の合計であり、もう一つは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);
}

[ 1 ]で、我々は出発点にある終点条件を扱います.サムがちょうどペイロードと正確に1である経路の数であるので、1つのノードバイナリ木を横断する正確に1つの方法があります.
[ 2 ]では、左の木と右の木から合計とパスを蓄積することによって、我々は他のケースを取り扱います.
で累算された合計とパスは戻ります.これらの2つのうちの少なくとも1つのため、彼らは0ではないことに注意してくださいif ステートメントを満たします.
本文為印解 Perl Weekly Challenge 093 -- 最多共線點數與二元樹路徑和 》之英文版.