RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved a binary expansion and string analysis. (Note that this closes today.)

Task 1: Binary String

You are given an integer, $n > 0.

Write a script to find all possible binary numbers of size $n.

So that's everything from zero to one less than 1 << n. Easy enough.

Perl:

sub binarystring($n) {
  my @o;
  foreach my $a (0..(1 << $n)-1) {
    push @o,sprintf('%0'.$n.'b', $a);
  }
  return \@o;
}

…I mean, I could have used a recursive incremental approach to build up the string character by character, but this just seemed cleaner. Lots of variation in how you get a binary number string, of course.

Task 2: Odd String

You are given a list of strings of same length, @s.

Write a script to find the odd string in the given list. Use positional value of alphabet starting with 0, i.e. a = 0, b = 1, ... z = 25.

Find the difference array for each string as shown in the example. Then pick the odd one out.

In other words, "abc" and "fgh" would both become [1, 1], but "fec" would be [-1, -2]

I end up doing this just one character at a time and bailing out when we reach a singleton.

Kotlin:

fun oddstring(ss: List<String>): String {

We know each string is the same length, so the outer iteration is by character index.

    for (i in 0..ss[0].length-2) {

Set up the table of differences.

        var tab = mutableMapOf<Int, ArrayList<String>>()

For each string,

        for (s in ss) {

work out the difference in code between character i and the next,

            val v = s[i+1].code - s[i].code

and store the string in the hash indexed by the difference.

            var ll = tab.getOrDefault(v, ArrayList<String>())
            ll.add(s)
            tab.put(v, ll)
        }

Then for each hash value (list of strings),

        for (j in tab.values) {

if there's only one string in that list (for this difference value),

            if (j.size == 1) {

it's the answer, so return it.

                return j[0]
            }
        }
    }

Otherwise go on to the next character. If we never got a match, return an empty string.

    return ""
}

Full code on github.