RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved sorted lists and iterative reductions. (Note that this closes today.)

Task 1: Matching Members

You are given a list of positive integers, @ints.

Write a script to find the total matching members after sorting the list increasing order.

Pretty straightforward, sort and then compare. Some languages have a zip to merge two iterables, others don't.

If they do, as in Python:

def matchingmembers(a):
  b = a.copy()
  b.sort()
  o = 0
  for i in zip(a, b):
    if i[0] == i[1]:
      o += 1
  return o

If not, as in JavaScript:

function matchingmembers(a) {
    let b = [...a];
    b.sort(function(a,b) {
        return a-b;
    });
    let o = 0;
    for (let i = 0; i < a.length; i++) {
        if (a[i] == b[i]) {
            o++;
        }
    }
    return o;
}

Task 2: Last Member

You are given an array of positive integers, @ints.

Write a script to find the last member if found otherwise return 0. Each turn pick 2 biggest members (x, y) then decide based on the following conditions, continue this until you are left with 1 member or none.

a) if x == y then remove both members

b) if x != y then remove both members and add new member (y-x)

My rule of thumb is that if I want the single largest entry from a list I'll use max, which is obviously cheaper than a full sort, but if I want two or more it's usually less faff just to sort it rather than messing around with a custom max routine. So on each pass I do that, pop the two largest entries off the end of the list, and push on a difference if it's needed. (This is always the non-negative difference, so I take advantage of the sorted list.)

This looks basically the same in all languages. Perl:

sub lastmember($a0) {
  my @a = @{$a0};
  while (scalar @a > 1) {
    @a = sort {$a <=> $b} @a;
    my $x = pop @a;
    my $y = pop @a;
    if ($x != $y) {
      push @a, $x - $y;
    }
  }
  if (scalar @a == 0) {
    return 0;
  } else {
    return $a[0];
  }
}

Full code on github.