Special Accounts

Weekly Challenge 209

Challenge, My solutions

Task 1: Special Bit Characters

Task

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.

My solution

The first observation to make is that a list of bits can only be converted into a single sequence. So I can save a recursive function for a rainy day :)

I create a variable called last_a to determine if the last character we found is an a. I then go through the supplied list, and remove the first item. If it is a 0, I set last_a to True. If it is a 1, I set last_a to False, and remove the next first item since that will make it a b or c.

After the list is exhausted, I print 1 if last_a is True, or 0 if it is not.

Examples

$ ./ch-1.py 1 0 0
1

$ ./ch-1.py 1 1 1 0
0

Task 2: Merge Account

Task

You are given an array of accounts i.e. name with list of email addresses.

Write a script to merge the accounts where possible. The accounts can only be merged if they have at least one email address in common.

My solution

This proved trickier than I thought it would be. Or maybe I just didn't think of the best solution. For the input, I take a JSON string, and turn it into a list (arrayref in Perl).

The next step is to create a dict (hash in Perl) called groups where the key is the account and the value is a list of sets (array of arrayrefs in Perl) with the addresses in it.

I then create a list called results that are going to have the final rows in it. I iterate over the groups dict (sorted by the key), and call the groups_list function providing the key (account) and values (the lists of e-mail address sets). It returns the rows to add to the results list. So far so good, pretty straight forward.

The groups_list function works like a stack. I loop until the stack is empty. For each loop, I take the first set of e-mail addresses from the top of the stack. I then compare the remaining items in the stack (if any) to see if they have a common address. If they do, I remove that set from the stack, and add a new value at the top of the stack with the combined set of e-mail addresses. If there is no match, I create an row in the rows list, and continue to the next item in the stack.

I chose to use sets rather than a list, because set1 & set2 is true if there are common items. Additionally set1 | set2 will produce a new set of all items with no duplicates. For the Perl peeps, a set is like a hash with no values. For the Perl solution, I use Array::Utils intersect and unique functions to provide equivalent features.

Finally, I print the items in the result list as a pretty JSON array.

Examples

$ ./ch-2.py '[ ["A", "[e-mail]", "[e-mail]"], ["B", "[e-mail]"], ["A", "[e-mail]", "[e-mail]"] ]'
[
    [
        "A",
        "[e-mail]",
        "[e-mail]",
        "[e-mail]"
    ],
    [
        "B",
        "[e-mail]"
    ]
]

$ ./ch-2.py '[ ["A", "[e-mail]", "[e-mail]"],  ["B", "[e-mail]"], ["A", "[e-mail]"], ["B", "[e-mail]", "[e-mail]"] ]'
[
    [
        "A",
        "[e-mail]",
        "[e-mail]"
    ],
    [
        "A",
        "[e-mail]"
    ],
    [
        "B",
        "[e-mail]",
        "[e-mail]"
    ]
]