1 #!/usr/bin/perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-209/#TASK1
 3 #
 4 # Task 1: Special Bit Characters
 5 # ==============================
 6 #
 7 # You are given an array of binary bits that ends with 0.
 8 #
 9 # Valid sequences in the bit string are:
10 #
11 ## [0] -decodes-to-> "a"
12 ## [1, 0] -> "b"
13 ## [1, 1] -> "c"
14 #
15 # Write a script to print 1 if the last character is an “a” otherwise print 0.
16 #
17 ## Example 1
18 ##
19 ## Input: @bits = (1, 0, 0)
20 ## Output: 1
21 ##
22 ## The given array bits can be decoded as 2-bits character (10) followed by
23 #1-bit character (0).
24 #
25 ## Example 2
26 ##
27 ## Input: @bits = (1, 1, 1, 0)
28 ## Output: 0
29 ##
30 ## Possible decode can be 2-bits character (11) followed by 2-bits character
31 #(10) i.e. the last character is not 1-bit character.
32 #
33 ############################################################
34 ##
35 ## discussion
36 ##
37 ############################################################
38 #
39 # We walk the array from start to end. If the current element is 1, we
40 # also take the next one, decode into the character and go on. If the
41 # last character we found was an "a", we return 1, otherwise 0.
42 
43 use strict;
44 use warnings;
45 
46 special_bit_characters(1, 0, 0);
47 special_bit_characters(1, 1, 1, 0);
48 
49 sub special_bit_characters {
50    my @bits = @_;
51    print "Input: (" . join(", ", @bits) . ")\n";
52    # the state we have consist of the last bit (either set to 1  or
53    # undef) and the current character (undef or one of a, b, c)
54    my $last_bit = undef;
55    my $char = undef;
56    foreach my $bit (@bits) {
57       # if the last bit was set, we either have a b or a c
58       if($last_bit) {
59          if($bit) {
60             $char = "c";
61          } else {
62             $char = "b";
63          }
64          # make sure we reset the state of the last bit so we're ready
65          # to read the next bit
66          $last_bit = undef;
67       } else {
68          # last bit was not set, so either we start a new 2-bits character
69          # or we have the 1-bit character "a"
70          if($bit) {
71             $last_bit = 1;
72             $char = undef;
73          } else {
74             $char = "a";
75          }
76       }
77    }
78    # Now we just need to check whether the last character was the 1-bit
79    # character "a" or not
80    if($char eq "a") {
81       print "Output: 1\n";
82       return 1;
83    } else {
84       print "Output: 0\n";
85       return 0;
86    }
87 }