RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved decoding a sequence and merging lists. (Note that this closes for public solutions today.)

Task 1: Special Bit Characters

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.

One might take this backwards until one reached an unambiguous start character, but it seemed easier to start from the beginning. Python:

def specialbitcharacters(a):

Set up a latch showing where we are in the decoding process.

  s = 0
  for v in a:

If the last start bit was a 1, we don't care what this bit is, but it's part of that character.

    if s == 1:
      s = 2

Otherwise this is a start bit, so set the latch to its value.

    else:
      s = v

At the end, the latch is zero if and only if the last bit was both zero and a start bit.

  return s == 0

Task 2: Merge Account

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.

This suddenly lacked fun for me, so I only did it in Perl, Raku and PostScript. Each entry in the list consists of a list of which the first entry is an account name (not necessarily unique) and the rest are addresses. Perl:

sub mergeaccount($a) {
  my @aname;
  my $id = 0;
  my %r;

Looking through the list, build up a mapping of account ID (row number) to name, and each email address to a list of account IDs.

  foreach my $acc (@{$a}) {
    push @aname, $acc->[0];
    foreach my $i (1..$#{$acc}) {
      push @{$r{$acc->[$i]}}, $id;
    }
    $id++;
  }

Now a mapping of accounts to other accounts. If an address occurs in account IDs x and y, map y to x.

  my %m;
  foreach my $idlist (values %r) {
    if (scalar @{$idlist} > 1) {
      my $root = $idlist->[0];
      while (exists $m{$root}) {
        $root = $m{$root};
      }
      foreach my $i (1..$#{$idlist}) {
        $m{$idlist->[$i]} = $root;
      }
    }
  }

Actually merge the accounts. For each ID, find out which final account its addresses should go into, and put them there. Also save the first account name as a prefix.

  my %staging;
  my %prefix;
  foreach my $id (0..$#{$a}) {
    my $ii = $id;
    while (exists $m{$ii}) {
      $ii = $m{$ii};
    }
    my $acc = $a->[$id];
    if (!exists $prefix{$ii}) {
      $prefix{$ii} = $acc->[0];
    }
    foreach my $addr (map {$acc->[$_]} 1..$#{$acc}) {
      $staging{$ii}{$addr} = 1;
    }
  }

Finally assemble the results (hash keys to array entries)

  my @out;
  foreach my $k (keys %staging) {
    push @out,[$prefix{$k}, sort keys %{$staging{$k}}];
  }

and sort them (order unspecified, but account name and then first address seems to match the examples).

  @out = sort {$::a->[0] cmp $::b->[0] ||
                 $::a->[1] cmp $::b->[1]} @out;
  return \@out;
}

Full code on github.