Making change (or select pipe lengths) at #RTCEUR

Building on yesterday’s post about pipe splitting, you may want a semi-intelligent way to choose quantities of pre-cut lengths to use when you break apart a long element into fabricated pieces.

Fortunately, this is the same challenge as how to make change for a given amount of money. You have a total amount (of money, length of pipe, etc) and a defined set of options (quarter, nickels, dimes, 6 and 10 foot pieces of pipe, etc) to use to get to the total. Many computer science students have probably tackled this problem and there are various solutions on the web.

The approach below uses recursion which is always exciting and adds a wrinkle that change-making doesn’t include. I added the idea of a “flexible length” and a minimum flexible length. It is possible to cut pipe into non-uniform lengths, but there is a minimum length that should not be allowed.

Some sample output for different lengths:

static List<double> amounts = new List<double>();
static List<List<double>> results = new List<List<double>>();
static double minFlexibleDistance = 0;
static double goal = 0;
public void makeChange()
{
     amounts.Clear();
     
     // lengths that can be combined to reach the goal length
    amounts.Add(4);
    amounts.Add(6);
    amounts.Add(10);
    
    // this is the shortest possible length of a piece
    minFlexibleDistance = 1.0;
    
    // length of the pipe or other element to divide into pieces
    goal = 26.5;
    
    Change(new List<double>(), 0, 0, goal);
    
    // more than one way to "make change" may have been found
    // prefer using no varialbe length pieces and as few pieces as possible
    List<double> bestResult = new List<double>();
    
    if (results.Count == 0)
    {
        TaskDialog td = new TaskDialog("Error");
        td.MainInstruction = "Could not make pieces with total length = " + goal;
        td.MainContent = "Minimum flexible length = " + minFlexibleDistance;
        td.Show();
        return;
    }
    
    List<double> resultWithShortestFlex = results.OrderBy(q => q.Last()).FirstOrDefault();
    double shortestFlexPiece = resultWithShortestFlex.Last();
    
    double numberOfPieces = Double.PositiveInfinity;
    foreach (List<double> thisResult in results.Where(q => q.Last() == shortestFlexPiece))
    {
        if (thisResult.Count < numberOfPieces)
        {
            numberOfPieces = thisResult.Count;
            bestResult = thisResult;
        }            
    }
    
    Display(bestResult);
    
}

private static void Change(List<double> coins, double highest, double sum, double goal)
{
    if (sum == goal) // OK - perfect match with no flexible lengths
    {
        coins.Add(0); // 0 is the flexible length
        results.Add(coins);
        return;
    }

    if (sum > goal)
    {
        double floorValue = sum - highest;
        double remainder = goal - floorValue;
        if (remainder >= minFlexibleDistance) // OK - can make up difference with flexible piece
        {
            coins.RemoveAt(coins.Count - 1);
            coins.Add(remainder);
            results.Add(coins);
            return;
        }
        else // BAD - min flexible distance would be too small - do not use this set of values
        {
            return;
        }
    }

    foreach (double value in amounts)
    {
        if (value >= highest) // Only add higher or equal amounts.
        {
            List<double> copy = new List<double>(coins);
            copy.Add(value);
            Change(copy, value, sum + value, goal);
        }
    }
    return;
}

private static void Display(List<double> coins)
{
    string data = "";
    foreach (double amount in amounts)
    {
        double count = coins.Count(value => value == amount);
        string pieces = "pieces";
        if (count == 1)
            pieces = "piece";
        
        data += count + " " + pieces + " each " + amount + " feet long" + Environment.NewLine;
    }
    foreach (double coin in coins)
    {
        if (!amounts.Contains(coin))
        {
            data += "One variable length piece = " + coin + " feet long" + Environment.NewLine;
        }
    }
    TaskDialog td = new TaskDialog("Output");
    td.MainInstruction = "Best way to make " + goal.ToString() + " feet from pieces";
    td.MainContent = data;
    td.Show();
}