The Weekly Challenge 305

Binary Prefix and Alien Dictionary

Solutions on GitHub

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