The Jarfish
19May/11Off

Issuing vending machine change: Using C# to recursively build and search a tree

As a business application programmer I am often challenged more by understanding the business that I program in than the actual programming. For instance if I am working on a fleet management system, there is a need to understand the business and the rules around it. The programming is often more a tool to facilitate the flow and manipulation of data -- than hardcore programming.

Recently I have been working with cash handling machines and devices -- a welcome break from CRUD type applications. One of the recent challenges I faced took me back to my early university days...

We were introducing money handling and the associated change dispensing into our application. The logic to handle the change dispensing was required.

Dispensing change

Say for instance the user required 0.50c in change -- the machine would be required to output the optimal amount of change from its current float. So if the float contained 1x50c coin, that would be dispensed. If the float had 5x10c and 1x20c, it would issue 3x10c and 1x20c.

There may not always be the right coin denominations to issue out the correct amount of change. For instance, 0.50c may be required but there are 3x20c. The solution presented will not deliver an answer, it will merely state that there is no solution found. Handling the affects of this case falls under the business specifications, and therefore is not covered in this post.

Some graph theory

The easiest way to solve the problem was to use graph theory. I decided to model the problem into a tree -- each node on the tree would represent an assigned coin denomination and the affect of that on the float (float is the inventory of money in the tree at that point).

The basic algorithm is at each node, at the current depth, investigate the float to see what denominations are available. For each one of those add a child leaf onto the parent. At each child leaf subtract one from the inventory for that coin denomination. Check all the current children, if a solution is found -- give it. Otherwise add child leafs onto all the constructed children, as documented above. This is known as a breadth first search.

Pretty pictures

To illustrate the above -- there is a float containing 5x5c, 1x10c and 1x20c and the application is required to dispense 35c change.

At the first step, I chose to construct a parent node with value of 0 and it contains the full float.

The value is checked, and it is 0. The next iteration will expand the parent adding a child node for every denomination in the float that has at least 1 coin present. In this case it is all the denominations. The tree is expanded as such:

Notice that each child node has a 'localized' float -- basically one less of it's denomination. This represents what has occurred at that node. The parent can have a 5c, 10c, and 20c child.

There is no solution found at this iteration. The next iteration will expand each of the childless nodes. The expansion will look at each node's float -- a coin for each denomination which is present in the inventory will be added. So for the 10c it has only 2 children: 5c and 20c. Similarly for 20c: 5c and 10c. The 5c has 3 children: 5c, 10c and 20c.

The children nodes are added as illustrated above(for clarity of the picture, I have left out the localized float). The tree is traversed to see the total. So starting at the bottom left node (5c) the total is 10c, the total at the sibling node is 15c, then 25c. For the pink node children the totals are 15c and 30c etc etc.

This occurs for each node until:

  • A solution is found
  • The float is exhausted -- there are no more coins to create child nodes from

Data structures: Building a tree in C#

A data structure that would represent the number of coins in the  float. To do this I created a dictionary with the key being the value of the denomination and the value being the number of coins/notes of that denomination -- in C# terms:

Dictionary<decimal, int>

Next was to create a tree-like structure which could be easily traversed. A custom class  was modeled with a few tweaks.  A tree contains the parent nodes and its associated children. At each iteration the children become parents. Each node has an assigned denomination representing the coin associated to it. Also each node has a running total which represents the sum of all its parent's denominations -- this is not really necessary.

  public class Tree
    {
        public decimal Denomination;
        public decimal RunningTotal;
        public Tree ParentNode;
        public Dictionary<decimal, int> CashFloat;

        public List<Tree> Children = new List<Tree>();

        public Tree(decimal denomination, Tree parentNode, Dictionary<decimal, int> cashFloat)
        {
            ParentNode = parentNode;
            Denomination = denomination;
            RunningTotal = ((parentNode != null) ? parentNode.RunningTotal : 0) + ((int)denomination);

            //Create a new register
            CashFloat = new Dictionary<decimal, int>();
            foreach (var floatItem in cashFloat)
            {
                CashFloat.Add(floatItem.Key, floatItem.Value);
            }
            //Check not really needed
            if (denomination != 0)
                CashFloat[denomination]--;
        }
    }

Build the tree and find the solution

Recursion is a great tool to use when one knows that at each iteration the problem domain will be getting smaller and smaller. It involves calling the function that the program is in, from within the very same function (if that makes sense). The recursion is used to find a solution (perform the breadth first part) and build the next nodes if a solution is not found.

So given a node, it checks to see that the tree contains any children.

  • If there are children, then recurse the children. This is done by checking if there are any more coins in float at that node. If there are, continue. If not, prune the node (do nothing).
  • If there are no children, it adds children to that node. The children are added provided that the float at the parent contains coins of that denomination. For each of the children added, check to see if a child has the solution. If so, return it -- if not return nothing/null.
  /// <summary>
        /// Recurses the tree to work out the change.
        /// </summary>
        /// <param name="dataTree"></param>
        /// <param name="desiredTotal"></param>
        /// <returns></returns>
        private Tree Recurse(Tree dataTree, decimal desiredTotal)
        {
            Tree foundLeaf = null;
            if (dataTree.Children.Count != 0)
                foreach (var item in dataTree.Children)
                {
                    if (item.CashFloat.Where(a => a.Value > 0).Any())
                    {
                        Tree temp = Recurse(item, desiredTotal);
                        if (temp != null)
                        {
                            foundLeaf = temp;
                            break;
                        }
                    }
                }
            else
            {
                for (int i = 0; i < dataTree.CashFloat.Count; i++)
                {
                    var item = dataTree.CashFloat.ElementAt(i);
                    if (item.Value > 0)
                    {
                        var newTreeLeaf = new Tree(item.Key, dataTree, dataTree.CashFloat);

                        dataTree.Children.Add(newTreeLeaf);
                        if (newTreeLeaf.RunningTotal == desiredTotal)
                            return newTreeLeaf;
                    }
                }

            }
            return foundLeaf;
        }

Where to start: Building the tree

The root node is set to 0. In the below code a limit has been set to the number of iterations -- this is not necessary. The recursion only returns a successful search match, we therefore loop until it returns a value.

   Tree dataStructure = new Tree(0m, null, GetFloat());

            int iterations = 20;

            Tree solution = null;
            while (solution == null)
            {
                //check to see if there is answer.
                solution = Recurse(dataStructure, desiredDenomination);

                //manual stopping point, can be removed.
                iterations++;
                if (iterations == 20)
                    break;
            }

Criticism

The solution outlined is by no means perfect -- and it is always important to reflect on any solution. There are many optimizations that can be made.

  • Too many unnecessary variables are stored at each tree node -- thus making the solution memory heavy.
  • The tree gets traversed at each iteration to find the child nodes, before expanding them.

Final thoughts

During the writing of this blog post...I have thought about an number of optimizations that can be done to the solution. I have listed these under the heading: Further investigation. This post is not meant to be seen as a text book solution to the problem, but a solution.

Further investigation:

  • There is no need to keep parent nodes, a future blog post is going to look into removing some of the unnecessary clutter in the structure -- which will result in a cleaner solution.
  • If the running total at a node exceeds the target -- that node does not require any more children added to it.
  • I would like to look into pruning symmetrical nodes -- this will avoid unnecessary calculations. Although in most instances I don't believe it would necessarily result in significant computational gains.
Comments (0) Trackbacks (0)

Sorry, the comment form is closed at this time.

Trackbacks are disabled.