RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved list partitioning and a progressive score calculator. (Note that this ends today.)

Task 1: Equal Group

You are given an array of integers.

Write a script to return true if the given array can be divided into one or more groups: each group must be of the same size as the others, with at least two members, and with all members having the same value.

What I want to work with here is the count of each number; the values of the numbers themselves don't matter. In Perl:

sub equalgroup($a) {

Use a hash to build up the counts.

  my %s;
  map {$s{$_}++} @{$a};

Then take the counts themselves, remove any duplicates, and sort them. (I don't actually need to sort them, only to find the minimum, but in some languages it's easier to do that and the deduplication with a sort first.)

  my @v = sort {$::a <=> $::b} uniq values %s;

A naïve reading of the question would suggest that all these values should have to be the same, but I can have multiple groups with the same numbers in them; in other words, a group of 4 can be regarded as two groups of 2 (as in example 1). So I'm looking for a group size which is at least 2, and by which all my counts can be evenly divided.

The smallest group must be at least 2, or it won't work at all.

  my $l = $v[0];
  if ($l < 2) {
    return 0;
  }

Otherwise I'll check each possible group size, from 2 up to the size of the smallest group.

  foreach my $t (2 .. $l) {

If all the groups can be evenly divided by it, we have a solution.

    if (all {$_ % $t == 0} @v) {
      return 1;
    }
  }

If we tried all the possibilities and none of them worked, we don't.

  0;
}

Task 2: Final Score

You are given an array of scores by a team.

Write a script to find the total score of the given team. The score can be any integer, +, C or D. The + adds the sum of previous two scores. The score C invalidates the previous score. The score D will double the previous score.

This is a stack-based problem, so I will indulge myself and show the PostScript solution.

/finalscore {

Push a start-array marker below the input list.

    [ exch

Iterate over the input list.

      {

We don't have a switch-case type statement in PostScript, and I want a default, so it's nested ifs.

          /n exch def

It's a C: pop the last score. (deepeq is a library function I wrote because strings in PostScript are in many ways arrays of characters, and so two strings can have different pointer values (which eq would compare) but identical content.)

          n (C) deepeq {
              pop
          } {

It's a "D": copy the last score and double it.

              n (D) deepeq {
                  dup 2 mul
              } {

It's a "+": copy the last two scores and add them together.

                  n (+) deepeq {
                      2 copy add
                  } {

Otherwise, it's a number; convert it to an integer.

                      n cvi
                  } ifelse
              } ifelse
          } ifelse
      } forall

There's no explicit stack pushing for any of this, because if I leave a number sitting there it gets pushed automatically. Finally, close off the array, and adds its values. (reduce is another of my library functions.)

    ] { add } reduce
} bind def

Full code on github.