The weekly challenge 305 - Task 1: Binary Prefix

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-305/#TASK1
 3 #
 4 # Task 1: Binary Prefix
 5 # =====================
 6 #
 7 # You are given a binary array.
 8 #
 9 # Write a script to return an array of booleans where the partial binary number
10 # up to that point is prime.
11 #
12 ## Example 1
13 ##
14 ## Input: @binary = (1, 0, 1)
15 ## Output: (false, true, true)
16 ##
17 ## Sub-arrays (base-10):
18 ## (1): 1 - not prime
19 ## (1, 0): 2 - prime
20 ## (1, 0, 1): 5 - prime
21 #
22 ## Example 2
23 ##
24 ## Input: @binary = (1, 1, 0)
25 ## Output: (false, true, false)
26 ##
27 ## Sub-arrays (base-10):
28 ## (1): 1 - not prime
29 ## (1, 1): 3 - prime
30 ## (1, 1, 0): 6 - not prime
31 #
32 ## Example 3
33 ##
34 ## Input: @binary = (1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1)
35 ## Output: (false, true, true, false, false, true, false, false, false, false,
36 ## false, false, false, false, false, false, false, false, false, true)
37 #
38 ############################################################
39 ##
40 ## discussion
41 ##
42 ############################################################
43 #
44 # We can initialize $num as 0. Appending another binary digit is the same
45 # as multiplying $num by two, then adding the next digit. So we can go
46 # digit by digit, calculating the new number in each step and checking whether
47 # or not it is prime. Then we just need to print the result.
48 # Note: I used the is_prime() function from my solution to challenge 233.
49 
50 use strict;
51 use warnings;
52 
53 binary_prefix(1, 0, 1);
54 binary_prefix(1, 1, 0);
55 binary_prefix(1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1);
56 
57 sub binary_prefix {
58    my @binary = @_;
59    print "Input: (" . join(", ", @binary) . ")\n";
60    my @result = ();
61    my $num = 0;
62    foreach my $digit (@binary) {
63       $num *= 2;
64       $num += $digit;
65       push @result, is_prime($num) ? "true" : "false";
66    }
67    print "Output: (" . join(", ", @result) . ")\n";
68 }
69 
70 
71 {
72    my $cache;
73    sub is_prime {
74       my $num = shift;
75       return 0 if $num == 1;
76       return $cache->{$num} if defined $cache->{$num};
77       my $divider = 2;
78       while($divider <= sqrt($num)) {
79          if(int($num/$divider) == $num/$divider) {
80             $cache->{$num} = 0;
81             return 0;
82          }
83          $divider++;
84       }
85       $cache->{$num} = 1;
86       return 1;
87    }
88 }
89