RogerBW's Blog

The Weekly Challenge 236: Change for the Machines 01 October 2023

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.

Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action advent of code aeronautics aikakirja anecdote animation anime army astronomy audio audio tech base commerce battletech beer boardgaming book of the week bookmonth chain of command children chris chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 crime crystal cthulhu eternal cycling dead of winter doctor who documentary drama driving drone ecchi economics en garde espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 essen 2022 essen 2023 essen 2024 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo genesys geocaching geodata gin gkp gurps gurps 101 gus harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo 2021 hugo 2022 hugo 2023 hugo 2024 hugo-nebula reread in brief avoid instrumented life javascript julian simpson julie enfield kickstarter kotlin learn to play leaving earth linux liquor lovecraftiana lua mecha men with beards mpd museum music mystery naval noir non-fiction one for the brow opera parody paul temple perl perl weekly challenge photography podcast politics postscript powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs ruby rust scala science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance the weekly challenge thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult
Special All book reviews, All film reviews
Produced by aikakirja v0.1