RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved a list search and combinations. (Note that this ends today.)

Task 1: Count Smaller

You are given an array of integers.

Write a script to calculate the number of integers smaller than the integer at each index.

Well, you could just search the array repeatedly. But that seemed dull. In Rust:

fn countsmaller(nums: Vec<u32>) -> Vec<u32> {

b is a sorted copy of the input list.

    let mut b = nums.clone();
    b.sort();
    let mut sm: HashMap<u32, u32> = HashMap::new();

l is the latest number we've seen.

    let mut l = 0;
    for (i, e) in b.iter().enumerate() {

If we're looking at the first value, or the value here isn't the same as the last value we saw…

        if i == 0 || *e != l {

The number of values less than it equals its index in the sorted list.

            sm.insert(*e, i as u32);

And update the last value seen.

            l = *e;
        }
    }

Then map out the original list to the values hash.

    nums.into_iter().map(|n| *sm.get(&n).unwrap()).collect::<Vec<u32>>()
}

Task 2: Group Hero

You are given an array of integers representing the strength.

Write a script to return the sum of the powers of all possible combinations; power is defined as the square of the largest number in a sequence, multiplied by the smallest.

So clearly we're going to have to calculate all possible combinations, for which in Perl I'll use Algorithm::Combinatorics as usual.

sub grouphero($nums0) {

Finding an algorithm that preserves the order makes this easy: just do one big sort at the start.

  my @nums = sort {$a <=> $b} @{$nums0};
  my $sum = 0;

For each possible combination length, then for each possible combination of that length…

  foreach my $l (1 .. scalar @nums) {
    foreach my $c (combinations(\@nums, $l)) {

Add (highest squared) * (lowest).

      $sum += $c->[-1] * $c->[-1] * $c->[0];
    }
  }
  return $sum;
}

Full code on github.