RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved calculating change and finding loops. (Note that this ends today.)

Task 1: Exact Change

You are asked to sell juice; each costs $5. You are given an array of bills. You can only sell ONE juice to each customer but make sure you return exact change back. You only have $5, $10 and $20 notes. You do not have any change in hand at first.

Write a script to find out if it is possible to sell to each customers with correct change.

I got enthusiastic so I generalised this problem. I was in a rate OO mood, so I built a "Reserve" class with a list of valid notes, and counts of each – which can cope with a items at different prices, and indeed with multiple tendered notes (such as paying for a ¤25 item with three ¤10 notes).

(I have an unreasonable fondness for the ¤ CURRENCY SIGN symbol. It was originally included in non-US ASCII in 1972 for "your own local national currency symbol for you weirdoes who don't use dollars"; I like to use it as "whatever currency it is that we are currently talking about", for example when writing about board games or RPGs which may have entirely imaginary currencies.)

Most of the work is done in the makechange method:

• accept a price and a series of notes;
• increment the counter for each note tendered;
• subtract the price from the total tendered value to get the amount of change to be given;
• pay out that change, largest notes first if possible;
• if after having checked all notes change is still owed, report failure.

Ruby:

When the class is instantiated, build the three data structures: values which is a list of the note values in descending order, counts which is a list of the number of each that we currently hold, and vm which is a lookup hash of value to index in those two lists.

class Reserve
  def initialize(vv)
    @values = vv.sort.reverse
    @counts = Array.new([0] * vv.length)
    @vm = Hash.new
    @values.each_with_index do |v, n|
      @vm[v] = n
    end
  end

The main workhorse.

  def makechange(price, tendered)
    val = 0

Check that each note exists; if so, add it to the stock and increment value-tendered.

    tendered.each do |note|
      if !@vm.has_key?(note) then
        return false
      end
      @counts[@vm[note]] += 1
      val += note
    end

Make sure we were given enough.

    if val < price then
      return false
    end

Subtract the price, and remaining value is change to be given.

    val -= price

For each sort of note, largest to smallest,

    0.upto(@values.length - 1) do |bid|

While we should pay at least this note's value, and we have at least one of this note, hand one over. (This could be optimised by dividing val by @values[bid] but the iteration seems to me to do no harm.)

      while val >= @values[bid] && @counts[bid] > 0 do
        val -= @values[bid]
        @counts[bid] -= 1
      end
    end

If the change to be given has reached zero, this was a success.

    return (val == 0)
  end
end

That's the object. The exactchange shim function works to localise it for the specific examples, with fixed price and note set.

def exactchange(a)

Set up a new Reserve.

  reserve = Reserve.new([5, 10, 20])

Present each single note, in order, for a separate purchase.

  a.each do |tendered|
    if !reserve.makechange(5, [tendered]) then
      return false
    end
  end
  return true
end

Of the languages I'm using, only PostScript doesn't have an object syntax. One day I shall write one (such that class variables and methods both go into an internal data structure, probably a pair of dicts).

One fiddly point was the idea of a compulsory parameter to the constructor, which various languages do in different ways. Thanks to PNDC and Elizabeth Mattijsen for leading me to realise that the right answer in Raku wasn't to subvert new (which, if not overridden, does necessary things) but to use the post-constructor hook:

method TWEAK(:@notes) {
    my @vq = @notes.sort({$^b <=> $^a});
    for (0..@vq.end) -> $i {
        %!vm{@vq[$i]} = $i;
    }
    @!values = @vq;
    @!counts = 0 xx @vq.elems;
}

Task 2: Array Loops

You are given an array of unique integers.

Write a script to determine how many loops are in the given array.

To determine a loop: Start at an index and take the number at array[index] and then proceed to that index and continue this until you end up at the starting index.

Given the problem statement, any given number can ultimately lead either to a loop (possibly a loop consisting only of itself), or outside the scope of the list. (This latter possibility isn't covered by the tests.)

A loop is potentially more of a rayed circle: there can be multiple entry points that lead into a loop (perhaps via different loop members) but not into each other. In the test cases, though, there are no tails and every item is a main loop member.

My search starts at each entry in turn, checks whether it's part of a known loop, and if not builds up its own trail list until it encounters either a previously-known loop member or an entry already in its list. All entries on the list are then marked with the loop ID to which they belong (a new one if it's a new loop, 0 if it led out of the list).

Then it's just a matter of returning the highest loop ID.

Perl:

sub arrayloops($a) {

Initialise loop counter and map of list members to loop IDs.

  my $loop_id = 0;
  my %loops;

Test each list index.

  foreach my $origin (0..$#{$a}) {

If we already know where that leads, move on.

    unless (exists $loops{$origin}) {

li will hold the loop ID when we discover it. thisloop (a set, where available) will hold the trail leading to the detected loop. x is the current position.

      my $li = 0;
      my %thisloop;
      my $x = $origin;
      while (1) {

If this leads outside the list, bail out with the loop ID we have (which will be the default zero).

        if ($x < 0 || $x > $#{$a}) {
          last;
        }

Store this position in the current trail.

        $thisloop{$x} = 1;

Jump to the next position.

        $x = $a->[$x];

Is this new position it in an existing loop? Then drop out with that loop ID.

        if (exists $loops{$x}) {
          $li = $loops{$x};
          last;
        }

Is it anywhere in our own trail? Then drop out with a new loop ID.

        if (exists $thisloop{$x}) {
          $loop_id++;
          $li = $loop_id;
          last;
        }

(And keep going until at least one of those things is true.)

      }

Whatever loop ID we've now got, set the loop value of everywhere on the trail to that. (Even if it's an existing loop, some of the values might be a new tail leading into there.)

      foreach my $i (keys %thisloop) {
        $loops{$i} = $li;
      }
    }
  }

And return the number of loops.

  return $loop_id;
}

Full code on github.