Task 1: Binary Prefix
You are given a binary array.
Write a script to return an array of booleans where the partial binary number up to that point is prime.
Example 1
Input: @binary = (1, 0, 1)
Output: (false, true, true)
(1): 1 - not prime
(1,0): 2 - prime
(1,0,1): 5 - prime
Example 2
Input: @binary = (1, 1, 0)
Output: (false, true, false)
(1): 1 - not prime
(1,1): 3 - prime
(1,1,0): 6 - not prime
Logic
Build the binary number incrementally: for each new bit, shift left (multiply by 2) and add the bit. Check primality at each step using trial division up to sqrt(n).
Perl Solution
ch-1.pl
use strict;
use warnings;
use Test::More;
sub is_prime {
my ($n) = @_;
return 0 if $n <= 1;
return 1 if $n == 2;
return 0 if $n % 2 == 0;
for (my $i = 3; $i <= sqrt($n); $i += 2) {
return 0 if $n % $i == 0;
}
return 1;
}
sub binary_prefix {
my @binary = @_;
my @result;
my $current_num = 0;
foreach my $bit (@binary) {
$current_num = $current_num * 2 + $bit;
push @result, is_prime($current_num) ? 1 : 0;
}
return @result;
}
is_deeply([binary_prefix(1,0,1)], [0,1,1], 'Example 1');
is_deeply([binary_prefix(1,1,0)], [0,1,0], 'Example 2');
Python Solution
ch-1.py
def is_prime(n: int) -> bool:
if n <= 1: return False
if n == 2: return True
if n % 2 == 0: return False
for i in range(3, int(n**0.5) + 1, 2):
if n % i == 0: return False
return True
def binary_prefix(binary: list[int]) -> list[bool]:
current_num = 0
result = []
for bit in binary:
current_num = current_num * 2 + bit
result.append(is_prime(current_num))
return result
Task 2: Alien Dictionary
You are given a list of words and an alien dictionary character order.
Write a script to sort lexicographically the given list of words based on the alien dictionary order.
Example 1
Input: @words = ("perl", "python", "raku")
@alien = qw/h l a b y d e f g i r k m n o p q j s t u v w x c z/
Output: ("raku", "python", "perl")
Example 2
Input: @words = ("the", "weekly", "challenge")
@alien = qw/c o r l d a b t e f g h i j k m n p q s w u v x y z/
Output: ("challenge", "the", "weekly")
Logic
Create a priority hash from the alien order. Define a custom comparator that compares two words character by character using the priority hash. If all compared characters match, the shorter word comes first. In Perl, use a sort block with the custom comparison. In Python, use functools.cmp_to_key.
Perl Solution
ch-2.pl
use strict;
use warnings;
use Test::More;
sub alien_sort {
my ($words, $alien) = @_;
my %order;
@order{@$alien} = 0 .. $#$alien;
return [ sort {
for my $i (0 .. length($a)-1) {
last if $i >= length($b);
my $ca = substr($a, $i, 1);
my $cb = substr($b, $i, 1);
return $order{$ca} <=> $order{$cb} if $ca ne $cb;
}
length($a) <=> length($b);
} @$words ];
}
use Test::More;
is_deeply(alien_sort(["perl","python","raku"],
[qw/h l a b y d e f g i r k m n o p q j s t u v w x c z/]),
["raku","python","perl"], 'Example 1');
is_deeply(alien_sort(["the","weekly","challenge"],
[qw/c o r l d a b t e f g h i j k m n p q s w u v x y z/]),
["challenge","the","weekly"], 'Example 2');
Python Solution
ch-2.py
from functools import cmp_to_key
def alien_sort(words: list[str], alien_order: list[str]) -> list[str]:
order = {char: idx for idx, char in enumerate(alien_order)}
def compare(a, b):
for ca, cb in zip(a, b):
if ca != cb:
return -1 if order[ca] < order[cb] else 1
return len(a) - len(b)
return sorted(words, key=cmp_to_key(compare))