RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved breaking lists into groups and building a numerical sequence. (Note that this ends today.)

Task 1: Equal Pairs

You are given an array of integers with even number of elements.

Write a script to divide the given array into equal pairs such that: a) Each element belongs to exactly one pair. b) The elements present in a pair are equal.

The simple solution seems to me to take the input list, sort it, then consume it two at a time and make sure each pair of values fits. (If not, bail out with an empty list.) Most languages have some sort of "take two items off the list at a time" functionality, usually called something like "chunk", and the ones that don't have for loops with a step.

Kotlin:

fun shortestdistance(a0: List<Int>): List<List<Int>> {
    if (a0.size % 2 != 0) {
        return emptyList<List<Int>>()
    }
    var a = ArrayList(a0)
    a.sort()
    var out = ArrayList<List<Int>>()
    for (t in a.chunked(2)) {
        if (t[0] != t[1]) {
            return emptyList<List<Int>>()
        }
        out.add(listOf(t[0], t[0]))
    }
    return out.toList()
}

Python:

def equalpairs(a0):
  a = a0
  a.sort()
  out = []
  for i in range(0, len(a), 2):
    if a[i] != a[i+1]:
      return []
    out.append([a[i], a[i]])
  return out

Task 2: DI String Match

You are given a string s, consisting of only the characters "D" and "I".

Find a permutation of the integers [0 .. length(s)] such that for each character s[i] in the string: s[i] == 'I' ⇒ perm[i] < perm[i + 1] s[i] == 'D' ⇒ perm[i] > perm[i + 1]

In other words: arrange 0..len(s) such that each entry after the first is higher ("I") or lower ("D") than the previous one.

The most enjoyable part of this was working out an algorithm. I ended up using powers of two; say my first value is 16, then the next can be 16+8 or 16-8, then ±4, etc. Then I map the sorted order of those values to 0..len(s), and use that to create the output.

Perl:

sub distringmatch($a) {
  my $v = 1 << (length($a) - 1);
  my $wv = $v << 1;
  my @out = ($wv);

My first value is always in the mid-point of the potential range.

  foreach my $c (split '', $a) {

For each character, add or subtract the current delta value.

    if ($c eq 'I') {
      $wv += $v
    } else {
      $wv -= $v;
    }

Then halve the delta value and store the current working value.

    $v >>= 1;
    push @out, $wv;
  }

Build a separate list that's all those values in order.

  my @r = sort{$::a <=> $::b} @out;

Create a hash to map list values to index values.

  my %c = map {$r[$_] => $_} (0..$#r);

Return the index values in that order.

  return [map{$c{$_}} @out];
}

Full code on github.