DEV Community

Kang-min Liu
Kang-min Liu

Posted on

Solving Perl Weekly Challenge 086

Here comes the 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.
Enter fullscreen mode Exit fullscreen mode

A naive, brute-force solution is take the pairwise differece of all numbers and check whethery any one of them is equal to $A.

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

Which is an algorithm with time complexity of O(n²). If we store the position of each number in a HashMap, we could improve it to be O(n) in both time and space.

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

The adverb syntax of :exists in Raku looks special to me. It makes sense though, if we design it to be %H{$x}.exists() or exists(%H{$x}), then it would look as if we are asking if the value of %H{$x} exists, rather than asking the container %H.

TASK #2 › Sudoku Puzzle

I just happened to have a spare sudoku solver in my 'bin/' directory: sudoku-solutions.raku.


本文為《解 Perl Weekly Challenge 086》之英文版。

Top comments (0)