Task — A 3-letter alphabet

You are given an array of binary bits that ends with 0. Valid sequences in the bit string are:

• [0] -decodes-to → 'a'
• [1, 0] → 'b'
• [1, 1] → 'c'

Write a script to print 1 if the last character is an 'a' otherwise print 0.

Analysis

This is an interesting challenge in that it is almost - but not quite - trivial.

The easy thing to note is that if the bit string ends in 00 then the final character must be 'a'.

But what if it ends with 10? Let's consider a generic bit string which looks like this:

some 1s, some 0s, some 1s, some 0s ... 10.

It is clear that there must always be a letter boundary after any 0, because 0 can only occur on its own as an 'a', or preceded by a 1 as 'b'. So considering our string ending 10, we only need to look at how many 1s precede the final 0. If it is an even number, then those must all form 'c' - so 11110 can only be 'cca', whereas 1110 can only be 'cb'.

So the answer to the challenge is that the string ends in 'a' if the bit sequence ends in 00 or in 0 immediately preceded by an even number of 1s.

Note that this depends on the assurances that the bit string ends with zero and that it can be parsed according to the stated rules.

Try it 

#!/usr/bin/perl

# Peter Campbell Smith - 2023-03-20

use v5.28;
use utf8;
use warnings;

# You are given an array of binary bits that ends with 0. Valid sequences in the bit string are:
# [0] -decodes-to-> "a"
# [1, 0] -> "b"
# [1, 1] -> "c"
# Write a script to print 1 if the last character is an "a" otherwise print 0.

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge/209/1

test_for_a([1, 0, 0]);
test_for_a([1, 1, 1, 0]);
test_for_a([1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0]);
test_for_a([1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0]);
test_for_a([0]);

sub test_for_a {
    
    my (@bits, $bit_string, $good);
    
    # get array and convert to string
    @bits = @{$_[0]};
    $bit_string = join('', @bits);
    
    # if it ends 00 or is just 0 then it ends in 'a'
    if ($bit_string =~ m|00$| or $bit_string eq '0') {
        $good = 1;
        
    # if it ends 10 then it ends in 'a' if the final 0 is preceded by an even no of 1s
    } else {
        $bit_string =~ m|(1*)0$|;
        $good = length($1) & 1 ? 0 : 1;
    }
    
    # say the answer
    say qq[\nInput:  \@bits = (] . join(', ', @bits) . qq[)\nOutput: $good];
}

Output

Input:  @bits = (1, 0, 0)
Output: 1

Input:  @bits = (1, 1, 1, 0)
Output: 0

Input:  @bits = (1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0)
Output: 0

Input:  @bits = (1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0)
Output: 1

Input:  @bits = (0)
Output: 1