解 Perl Weekly Challenge 086

Perl Weekly Challenge 086 來了。

TASK #1 › Pair Difference

You are given an array of integers @N and an integer $A.

Write a script to find find if there exists a pair of elements in the
array whose difference is $A.

Print 1 if exists otherwise 0.

這題的暴力解法就是先取得兩兩數字之間的差，再逐一檢查是否等於 $A。

@N.combinations(2).first(-> @combo { $A == abs([-] @combo) });

上述解法的時間複雜度為 O(n²)，但如果用個 HashMap 把每個出現的數字的位置記著，就可以做出個時間複雜度為 O(n)、空間複雜度為 O(n) 的解法：

my %pos;
@N.kv.map(-> $k, $v { %pos{$v}.push($k) });
@N.first(
    -> $n {
        %pos{$n + $A}:exists or %pos{$n - $A}:exists
    });

Raku 裡這個 :exists 語法還真是特別，看來是種「副詞」。但似乎有其道理。如果語法設計成 %H{$x}.exists() 或 exists(%H{$x}) ，那就變成是去問 %H{$x} 對應到的值是否存在，而不是去問 %H 這個容器裡面是否存在有對應到 $x 之值。

TASK #2 › Sudoku Puzzle

第二題就是解數獨... 正巧以前我以遞迴解過一次：sudoku-solutions.raku。