RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved network analysis and change calculation. (Note that this ends today.)

Task 1: No Connection

You are given a list of routes, @routes.

Write a script to find the destination with no further outgoing connection.

I ignore the route aspect entirely here, and simply take the difference of sets of outging and incoming nodes. Raku:

sub noconnection(@a) {
    my %os = Set.new(@a.map({$_[0]}));
    my %is = Set.new(@a.map({$_[1]}));
    (%is (-) %os)[0]
}

Task 2: Making Change

Compute the number of ways to make change for given amount in cents. By using the coins e.g. Penny, Nickel, Dime, Quarter and Half-dollar, in how many distinct ways can the total value equal to the given amount? Order of coin selection does not matter.

A penny (P) is equal to 1 cent.
A nickel (N) is equal to 5 cents.
A dime (D) is equal to 10 cents.
A quarter (Q) is equal to 25 cents.
A half-dollar (HD) is equal to 50 cents.

Obviously the first step is to make it more generic (thus having a list of coins—which will need to be in ascending order).

I could have used a search loop, but I've written a lot of those recently, so instead I built this off cartesian products. It's less efficient because it iterates all possibilities rather than short-cutting (e.g. with coins 5, 1 and target value 11, it'll test two 5s and 2-11 1s rather than bailing out of that branks after testing a s ingle 1), but it was more amusing to write. (It does break the PostScript version, mind, with 160,000 stack entries in the third test case.)

I borrowed cartesian product functions from Rosetta Code and Stackoverflow for the languages that didn't have them available, or wrote my own when I felt like it. Perl:

sub cartesianproduct($lists) {
  my $sl = scalar @{$lists};
  my @c = (0) x $sl;
  my @cm = map {scalar @{$lists->[$_]} - 1} (0 .. $sl - 1);
  my @out;
  my $ex = 0;
  while (!$ex) {
    my @o;
    foreach my $i (0 .. $sl - 1) {
      push @o, $lists->[$i][$c[$i]];
    }
    push @out, \@o;
    my $ss = $sl - 1;
    while (1) {
      $c[$ss]++;
      if ($c[$ss] > $cm[$ss]) {
        if ($ss == 0) {
          $ex = 1;
          last;
        }
        $c[$ss] = 0;
        $ss--;
      } else {
        last;
      }
    }
  }
  return \@out;
}

sub makingchange($a) {
  my @coins = (1, 5, 10, 25, 50);
  my @mx = map {int($a / $_)} @coins;
  my @pat;
  foreach my $i (0 .. $#coins) {
    if ($mx[$i] > 0) {
        push @pat, [0 .. $mx[$i]];
    } else {
      last;
    }
  }
  my $ct;
  foreach my $combo (@{cartesianproduct(\@pat)}) {
    my $t = 0;
    while (my ($i, $c) = each @{$combo}) {
      $t += $c * $coins[$i];
      if ($t > $a) {
        last;
      }
    }
      if ($t == $a) {
        $ct++;
      }
  }
  return $ct;
}

Full code on github.