RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved set intersections and a complex sort. (Note that this ends today.)

Task 1: Arrays Intersection

You are given a list of array of integers.

Write a script to return the common elements in all the arrays.

Sets seem like the obvious tool for this job.

Scala:

  def arraysintersection(a: List[List[Int]]): List[Int] = {

Set up the set of members in the first list.

    var s = a(0).toSet

For each later list,

    for (b <- a.drop(1)) {

intersect that set with the new list.

      s = s & b.toSet
    }

Then produce a list of the remaining members.

    s.toList.sortWith(_ < _)
  }

(Strictly speaking I don't need to skip the first list in the iteration, since a set intersected with itself is itself, but it's inefficient and irks my aesthetic sense.)

Task 2:

You are given an array of integers.

Write a script to sort odd index elements in decreasing order and even index elements in increasing order in the given array.

sub sortoddeven(@a) {

Set up the sublists.

    my @odds;
    my @evens;

Iterate through the input, breaking out the sublist entries.

    for @a.kv -> $i, $x {
        if ($i % 2 == 0) {
            @evens.push($x);
        } else {
            @odds.push($x);
        }
    }

Sort the sublists.

    @evens = @evens.sort({$^a <=> $^b});
    @odds = @odds.sort({$^b <=> $^a});

Set up the output.

    my @out;

Iterate up to the higher list length.

    for 0 .. max(@evens.end, @odds.end) -> $i {

For each sublist in turn, if we haven't exceeded its length, add its next entry.

        if ($i <= @evens.end) {
            @out.push(@evens[$i]);
        }
        if ($i <= @odds.end) {
            @out.push(@odds[$i]);
        }
    }
    @out;
}

In some languages I'd natively use double-ended queues, or interleaving primitives, but this seemed clear and easily portable.

Full code on github.