8
\$\begingroup\$

Fixed trade route with goods and prices and fixed cargo capacity.

How can I optimize profit?

No cost to trade or transport - just fixed capacity, route, and prices. All products use the same capacity, which is kind of artificial, but this is just a single pass starting with an empty vessel. It does a semi brute force on all possible trades

The example would be 3 port and 3 products, like apples, pears, and oranges trading at various prices.

Test:

Int32[,] portsProducts = new Int32[,] { { 1, 1, 1 }, { 2, 1, 1 }, { 4, 2, 3 } };
Int32[,]  answer = PortsProducts(portsProducts);

Code:

public static Int32[,] PortsProducts(Int32[,] portsProducts)
{           
    int rowCount = portsProducts.GetLength(0);
    int colCount = portsProducts.GetLength(1);
    Int32[,] buySell  = new Int32[rowCount, colCount];
    Int32[,] buySellMax = new Int32[rowCount, colCount];
    Int32[] highPrice = new Int32[colCount];
    Int32[] lowPrice  = new Int32[colCount];

    List<int> rowDisplay = new List<int>();
    Debug.WriteLine("portsProducts");
    for (int i = 0; i < rowCount; i++)
    {
        //Debug.WriteLine("i = " + i.ToString());
        rowDisplay.Clear();
        for (int j = 0; j < colCount; j++)
        {
            rowDisplay.Add(portsProducts[i, j]);
        }
        Debug.WriteLine(string.Join(", ", rowDisplay));    
    }
    Debug.WriteLine("");

    // get high and low prices 
    // would never but at hight price 
    // and would never sell at low pric 
    for (int i = 0; i < rowCount; i++)
    {
        for (int j = 0; j < colCount; j++)
        {
            buySell[i, j] = 0;
            if (i == 0)
            {
                highPrice[j] = portsProducts[i, j];
                lowPrice[j]  = portsProducts[i, j];
            }
            else
            {
                if (highPrice[j] < portsProducts[i, j])
                    highPrice[j] = portsProducts[i, j];
                if (lowPrice[j]  > portsProducts[i, j])
                    lowPrice[j]  = portsProducts[i, j];
            }
        }
    }

    // build up a matrix of all possible buy sell hold for next rowCount - 1 
    // 0 hold, 1 is sell, 2 buy
    List<Int32[,]> allBuySellOptions = new List <Int32[,]>();
    Int32[,] buySellOptions = new Int32[rowCount, colCount];
    //Int32[,] buySellOptionsOld = new Int32[rowCount - 1, colCount];
    for (int i = 0; i < rowCount; i++)
    {               
        for (int j = 0; j < colCount; j++)
        {
            buySellOptions[i, j] = 0;
        }
    }
    //allBuySellOptions.Add(buySellOptions);  // all hold will never be used
    int row = rowCount - 1;
    int col = colCount - 1;
    int rowMin = row;
    int colMin = col;

    bool restart = false;
    while (true)
    {
        buySellOptions = BuySellOptionsClone(buySellOptions);
        if (buySellBump2(buySellOptions, ref row, ref col, ref restart, portsProducts, highPrice, lowPrice))
        {
            allBuySellOptions.Add(buySellOptions);
            //Debug.WriteLine("");
            //Debug.WriteLine("buySellBump2 buySellOptions");
            for (int i = 0; i < rowCount; i++)
            {
                //Debug.WriteLine("i = " + i.ToString());
                rowDisplay.Clear();
                for (int j = 0; j < colCount; j++)
                {
                    rowDisplay.Add(buySellOptions[i, j]);
                }
                //Debug.WriteLine(string.Join(", ", rowDisplay));    
            }
        }
        else
        {
            break;
        }
        if (restart)
        {   // the next was just bumped so need to start at the beginning
            restart = false;
            row = rowCount - 1;
            col = colCount - 1;
            buySellOptions = BuySellOptionsClone(buySellOptions);
            if (buySellBump2(buySellOptions, ref row, ref col, ref restart, portsProducts, highPrice, lowPrice))
            {
                allBuySellOptions.Add(buySellOptions);
                //Debug.WriteLine("");
                //Debug.WriteLine("buySellBump2 restart buySellOptions");
                for (int i = 0; i < rowCount; i++)
                {
                    //Debug.WriteLine("i = " + i.ToString());
                    rowDisplay.Clear();
                    for (int j = 0; j < colCount; j++)
                    {
                        rowDisplay.Add(buySellOptions[i, j]);
                    }
                    //Debug.WriteLine(string.Join(", ", rowDisplay));
                }
            }
            else
            {
                break;
            }
        }
    }
    // so now need to see what is most profitable 
    // not sure how to deal with don't have anything to sell on first stop  
    int capacity = 2*3*5*7*11*13;  // put in as many primes as can be stops
    int[] curProduct = new int[colCount]; 
    int curCapacity = capacity;
    int buyEach;
    int profit = 0;
    int profitMax = 0;
    int buyCount = 0;
    foreach (int[,] buySellOpt in allBuySellOptions)
    {
        //Debug.WriteLine("");
        for (int i = 0; i < rowCount; i++)
        {                  
            rowDisplay.Clear();
            for (int j = 0; j < colCount; j++)
            {
                rowDisplay.Add(buySellOpt[i, j]);
            }
            //Debug.WriteLine(string.Join(", ", rowDisplay));
        }
    }
    for (int i = 0; i < rowCount; i++)
    {
        for (int j = 0; j < colCount; j++)
        {
            if (buySell[i, j] != 0)
            {
                Debug.WriteLine("buySell[i, j] != 0");
            }
        }
    }
    Debug.WriteLine("Capacity {0}", capacity);
    int count = 0;
    foreach (int[,] buySellOpt in allBuySellOptions)
    {
        //1, 0, 0
        //2, 0, 1
        //0, 0, 2
        //if (buySellOpt[0, 0] == 1 &&
        //    buySellOpt[1, 0] == 2 &&
        //    buySellOpt[1, 2] == 1 &&
        //    buySellOpt[2, 2] == 2)
        //{
        //    Debug.WriteLine("this should be max");
        //}
        curCapacity = capacity;
        profit = 0;
        for (int i = 0; i < colCount; i++)
            curProduct[i] = 0;
        for (int i = 0; i < rowCount; i++)
        {
            for (int j = 0; j < colCount; j++)
            {
                buySell[i, j] = 0;
            }
        }
        count++;
        if (count == 18)
        {
            //Debug.WriteLine("Problem count == 18");
        }
        for (int i = 0; i < rowCount; i++)
        { 
            buyCount = 0;
            for (int j = 0; j < colCount; j++)
            {

                //Debug.WriteLine("");
                //Debug.WriteLine("buySellOpt[{0}, {1}] =  {2}", i, j, buySellOpt[i, j]);
                //Debug.WriteLine("buySell[{0}, {1}] =  {2}", i, j, buySell[i, j]);
                //Debug.WriteLine("curProduct[{0}] =  {1}", j, curProduct[j]);
                if (buySellOpt[i, j] == 2 && curProduct[j] > 0)
                {   // sell
                    // sell first to clear capacity 
                    profit += curProduct[j] * portsProducts[i, j];
                    curCapacity += curProduct[j];
                    buySell[i, j] = -curProduct[j];
                    curProduct[j] = 0;                     
                }
                else if(buySellOpt[i, j] == 1)
                {
                    buyCount++;
                }
            }                    
            if (buyCount > 0 && curCapacity > 0)
            {   // buy
                buyEach = curCapacity / buyCount;
                for (int j = 0; j < colCount; j++)
                {                          
                    if (buySellOpt[i, j] == 1)
                    {
                        profit -= buyEach * portsProducts[i, j];
                        curCapacity -= buyEach;
                        buySell[i, j] = buyEach;
                        curProduct[j] += buyEach;
                    }
                }
            }
        }
        if (profit > 0)
        {
            Debug.WriteLine("");
            if (profit > profitMax)
            {
                profitMax = profit;
                for (int i = 0; i < rowCount; i++)
                {
                    for (int j = 0; j < colCount; j++)
                    {
                        buySellMax [i, j] = buySell[i, j];
                    }
                }                     
                Debug.WriteLine("new max");
            }
            Debug.WriteLine("");
            Debug.WriteLine("profit " + profit.ToString("N0") + " count " + count);
            for (int i = 0; i < rowCount; i++)
            {
                buyCount = 0;
                for (int j = 0; j < colCount; j++)
                {
                    Debug.WriteLine("buySell[{0}, {1}] =  {2}", i, j, buySell[i, j].ToString("N0"));
                }
            }                 
        }
    }
    return buySellMax;
}
public static Int32[,] BuySellOptionsClone (Int32[,] buySellOptions)
{
    int rowCount = buySellOptions.GetLength(0);
    int colCount = buySellOptions.GetLength(1);
    Int32[,] buySellOptionsClone = new Int32[rowCount, colCount];
    for (int i = 0; i < rowCount; i++)
    {
        for (int j = 0; j < colCount; j++)
        {
            buySellOptionsClone[i, j] = buySellOptions[i, j];
        }
    }
    return buySellOptionsClone;
}
public static bool buySellBump2(Int32[,] buySellOptions, ref int i, ref int j, ref bool restart, Int32[,] portsProducts, Int32[] highPrice, Int32[] lowPrice)
{
    //Debug.WriteLine("buySellBump buySellOptions[" + i + ", " + j + "] =  " + buySellOptions[i, j]);
    if (buySellOptions[i, j] == 0 && (portsProducts[i, j] != highPrice[j] || portsProducts[i, j] != lowPrice[j]))
    {
        if (portsProducts[i, j] != highPrice[j])
        {
            buySellOptions[i, j] = 1;  // buy
        }
        else if (portsProducts[i, j] != lowPrice[j])
        {
            buySellOptions[i, j] = 2;   // sell 
        }
        return true;
    }
    else if (buySellOptions[i, j] == 1 && portsProducts[i, j] != lowPrice[j])
    {
        buySellOptions[i, j] = 2;  // sell
        return true;
    }
    else
    {
        // bumping the next value
        int rowCount = buySellOptions.GetLength(0);
        int colCount = buySellOptions.GetLength(1);
        for (int jj = j; jj < colCount; jj++)
        {
            buySellOptions[i, jj] = 0;
        }
        for (int ii = i + 1; ii < rowCount; ii++)
        {
            for (int jjj = 0; jjj < colCount; jjj++)
            {
                buySellOptions[ii, jjj] = 0;
            }
        }               
        if (j == 0)
        {
            if (i == 0)
                return false;
            i--;
            j = colCount - 1;
        }
        else
            j--;
        restart = true;
        return buySellBump2(buySellOptions, ref i, ref j, ref restart, portsProducts, highPrice, lowPrice);
    }
}
\$\endgroup\$
  • \$\begingroup\$ I personally prefer the C#'s alias int instead of Int32, short instead of Int16 but it's up to a personal preference I guess. \$\endgroup\$ – Denis Dec 26 '16 at 15:44
  • \$\begingroup\$ Found a bug where with split buys would get and uneven divide. But the fix there is to only one buy per stop. If there is a tie then buying all of 1 is the same profit. And just letting is loop twice got the answer for looping. On the first loop you simple cannot sell what you have not bought yet. And on the last loop simply don't buy what you cannot sell. \$\endgroup\$ – paparazzo Dec 26 '16 at 23:40
  • \$\begingroup\$ If anyone can: A: work out exactly what algorithm OP is using and whether it's any faster than pure brute force, which is \$\mathcal{O}(m^n)\$, (where n is the number of ports, and m is the number of products) and B: state a better approach, or at least provide a link to some source relevant to this kind of problem. Then they'll deserve that bounty. I've tried it twice today and been scuppered each time. \$\endgroup\$ – Ryan Mills Jan 4 '17 at 11:41
  • \$\begingroup\$ @RyanMills Actually my approach is failed. You can just optimize from port to port once and get the correct answer. But this is code review and it had an answer so I did not take it down. \$\endgroup\$ – paparazzo Jan 4 '17 at 11:47
  • \$\begingroup\$ It's OK if you found the bugs etc after you posted your code. This is an interesting question. It's identical to one traders often ask: Given a list of stocks and a range of historical prices, what would have been the most profitable set of trades? In fact, I've got a feeling it can be done much faster, say \$\mathcal{O}(n^3)\$, which would allow for hundreds of ports and products. And with compact code, too. \$\endgroup\$ – Ryan Mills Jan 4 '17 at 12:00
4
+50
\$\begingroup\$

Never hold your cargo

This problem simplifies a great deal, because it turns out that it is never correct to hold cargo past one port. Here is the proof (note I am not mathematician so I'll do my best):

Theorem: If it optimal strategy is to carry cargo x from port A to port C, then:
1. Between A and B, it is the optimal strategy to buy x at A and sell x at B.
2. Between B and C, it is the optimal strategy to buy x at B and sell x at C.

Proof:

The given statement means that the optimal profit from A to C is this:

optimal profit = cost[C,x] - cost[A,x]

This cost can be rewritten as:

optimal profit = (cost[B,x] - cost[A,x]) + (cost[C,x] - cost[B,x])

Assume that between A and B, there is some better strategy than buying x at A and selling x at B. Call this better strategy S and the profit of S is profit(S). Since this strategy is better than trading in x, we have this inequality:

profit(S) > (cost[B,x] - cost[A,x])

But this means that we should use strategy S between ports A and B, and then we should buy x at B and sell x at C, making our total profit:

total profit using S = profit(S) + (cost[C,x] - cost[B,x])

Notice this total profit is greater than the supposedly optimal profit, which was:

 optimal profit = (cost[B,x] - cost[A,x]) + (cost[C,x] - cost[B,x])

because profit(S) was greater than (cost[B,x] - cost[A,x]) from the inequality above. Thus, with proof by contradiction, there can be no such strategy S better than trading in x.

Repeat the same proof by contradiction for strategies between ports B and C.

Conclusion

Because you should always sell your cargo at each port, the best strategy is to maximize the profit between each pair of neighboring ports. So you just find the cargo with the greatest price differential between each pair of neighboring ports and trade in it. Of course, if between some pair of ports every cargo has a negative price differential, then you just don't carry anything between those ports. This makes the function trivial to write. Here is an example:

public static Int32[,] PortsProducts(Int32[,] portsProducts)
{
    // put in as many primes as can be stops
    int capacity = 2*3*5*7*11*13;
    int numPorts = portsProducts.GetLength(0);
    int numItems = portsProducts.GetLength(1);
    Int32[,] ret = new Int32[numPorts, numItems];

    for (int i = 0; i < numPorts - 1; i++) {
        int maxDiff    = -1;
        int maxProduct = -1;
        for (int j = 0; j < numItems; j++) {
            int diff = portsProducts[i+1, j] - portsProducts[i, j];
            if (diff > maxDiff) {
                maxDiff    = diff;
                maxProduct = j;
            }
        }
        if (maxDiff > 0) {
            ret[i,   maxProduct] += capacity;
            ret[i+1, maxProduct] -= capacity;
        }
    }
    return ret;
}
\$\endgroup\$
  • \$\begingroup\$ Actually I thought this at first too. But, then, a counter-example: { { 1 1 1 }, { 2 3 6 }, { 1 2 6 }, { 4 1 1 } } The optimal path: buy product 3 -> sell at port 2 -> buy product 1 at port 2 -> hold cargo past port 3 -> sell at port 4. Your statement holds only if all prices increase monotonically (ie. never decrease) with distance from the origin, as in OP's example. \$\endgroup\$ – Ryan Mills Jan 5 '17 at 4:12
  • \$\begingroup\$ I mean, once it becomes profitable to skip ports, then the decision becomes which ports to skip. As in, your code skips port 3 in my example as the optimal path (because maxDiff is negative), when in fact it's most profitable to skip port 2. \$\endgroup\$ – Ryan Mills Jan 5 '17 at 5:25
  • \$\begingroup\$ As stated in a comment I came the same conclusion. Since there is no cost to load and unload you can look at it port by port. You can get into a situation of actually buy back the product you just sold and it does not matter. Your answer misses circle pack to port 0. And you can just use as capacity of 1. Since this is code review and there was and still is an answer with up votes I did not want to change the question. \$\endgroup\$ – paparazzo Jan 5 '17 at 6:27
  • \$\begingroup\$ @Paparazzi "Your answer misses circle pack to port 0." It's probably best to let the user decide about that. If desired, they would add a final entry to PortsProducts identical to the starting port. That way, JS1's code can be used for both return and one-way journeys. Although, of course, you know your spec better than I do. \$\endgroup\$ – Ryan Mills Jan 5 '17 at 6:41
  • \$\begingroup\$ @RyanMills In your example, the best strategy is to skip buying at port 2, which is what my code does (don't know why you think it skips port 3?). Paparazzi, I didn't see in the problem statement that the ports were in a cycle. I imagined that after reaching the end of the line, you would need to turn back and go through the ports in reverse order. \$\endgroup\$ – JS1 Jan 5 '17 at 7:39
5
\$\begingroup\$

Code organization

PortsProducts is one gigantic method. I suggest to decompose it to many small methods that each have a single clear responsibility, with a descriptive method name.

Mutually exclusive conditions

portsProducts[i, j] will never be higher than the highest prices and lower than the lowest at the same time, so the 2nd if statement here should be an else if:

if (highPrice[j] < portsProducts[i, j])
    highPrice[j] = portsProducts[i, j];
if (lowPrice[j]  > portsProducts[i, j])
    lowPrice[j]  = portsProducts[i, j];

Use more helper variables

In the buySellBump2 method there are many references to buySellOptions[i, j] and portsProducts[i, j]. It would be easier to write and to read if you put those in local helper variables.

\$\endgroup\$
  • \$\begingroup\$ An extra iteration on j might be more expensive than i == 0 \$\endgroup\$ – paparazzo Dec 26 '16 at 11:12
  • \$\begingroup\$ What is the maximum dimension of the portsProducts you would like to support? \$\endgroup\$ – janos Dec 26 '16 at 11:55
  • \$\begingroup\$ That is the cheap part. allBuySellOptions is what gets big and expensive. Right now 13 int capacity = 2*3*5*7*11*13; Could not do a brute with a high number of stops/ports. \$\endgroup\$ – paparazzo Dec 26 '16 at 13:01
  • \$\begingroup\$ Fair enough, I dropped that point \$\endgroup\$ – janos Dec 26 '16 at 13:12
2
\$\begingroup\$
//Debug.WriteLine("i = " + i.ToString());

Commented out code is dead code so it should be removed. If you need to know something you tried for testing etc. you should use a code versioning system like svn or git.

// get high and low prices 
// would never but at hight price 
// and would never sell at low pric  

Comments should be used to explain why something is done. Let the code itself tell the reader what is done by using well and meaningful named methods, variables and classes. In addition comments should be seen like code which means spelling errors should be corrected and comments which aren't adding any value should be deleted.


Stick to one choosen style. Switching styles makes it much harder to read and understand the code. This is important for you as well as for Sam the maintainer if one of you is looking at this code in a month to find a bug or to add some functionality.

  • Sometimes you use braces {} for for loops and sometimes you don't.
  • Sometimes you use braces for single instruction if's and sometimes you don't.

I would like to encourage you to always use them to avoid hidden bugs which are very hard to find. Using braces will make your code less error prone.


Based on the NET naming guidelines methods should be named using PascalCase casing. Hence buySellBump2 should be BuySellBump2.

While we are at buySellBump2... If you have a if..else if..else construct out of which you return the method like so

if (condition)
{
    return someValue;
}
else if (anotherCondition)
{
   return anotherValue;
}
else
{
   return aValue;
}  

at least the else is superflous and can be removed like so

if (condition)
{
    return someValue;
}
else if (anotherCondition)
{
   return anotherValue;
}

return aValue;

The most annoying part of your code is already mentioned by @janos: Having such a god method like PortsProducts is a nightmare to maintain and shouldn't be anywhere near a production code base.

\$\endgroup\$
  • \$\begingroup\$ Donating a bounty and answering yourself? Reputation points laundering? :-P \$\endgroup\$ – t3chb0t Jan 4 '17 at 10:37
  • \$\begingroup\$ @t3chb0t no winterbash ;-). thats why I awarded a bounty to a question with an answer so I can award the bounty to that (not mine) answer. \$\endgroup\$ – Heslacher Jan 4 '17 at 10:39
0
\$\begingroup\$

Once I got into it realized you only need to look forward one port. If that same product sells for even more at the next port you essentially just sell and then buy it back.

This circles back to the first port.

//test
int[,] portsProducts = new int[,] { { 1, 2, 1 }, { 2, 1, 1 }, { 4, 2, 1 }, { 1, 1, 2 } };
Int32[,] trades = PortsProducts2(portsProducts);
Debug.WriteLine("portsProducts");
for (int i = 0; i < portsProducts.GetLongLength(0); i++)
{
    Debug.Write("port " + i + "  products");
    for (int j = 0; j < portsProducts.GetLongLength(1); j++)
    {
        Debug.Write(" " + portsProducts[i, j]);
    }
    Debug.WriteLine("");
}
Debug.WriteLine("trades");
for (int i = 0; i < trades.GetLongLength(0); i++)
{
    Debug.Write("port " + i + "  products");
    for (int j = 0; j < trades.GetLongLength(1); j++)
    {
        Debug.Write(" " + trades[i, j]);
    }
    Debug.WriteLine("");
}
Debug.WriteLine("");


public static int[,] PortsProducts2(int[,] portsProducts)
{
    int rowCount = portsProducts.GetLength(0);
    int colCount = portsProducts.GetLength(1);
    int[,] buySell = new int[rowCount, colCount];
    for (int i = 0; i < rowCount - 1; i++)
    {
        PortToPort(buySell, portsProducts, i, i+1);
    }
    // now circle back to first port 
    // on the first pass you cannot sell what you have not purcchased yet  
    // on the last pass don't buy at the last port
    PortToPort(buySell, portsProducts, rowCount-1, 0);
    return buySell;
}
private static void PortToPort(int[,] buySell, int[,] portsProducts, int portFrom, int portTo)
{
    //should not get any exceptions
    if (buySell == null)
        throw new ArgumentNullException("buySell");
    if (portsProducts == null)
        throw new ArgumentNullException("portsProducts");
    int productCount = buySell.GetLength(1);
    if (productCount != portsProducts.GetLength(1))
        throw new ArgumentNullException("product count does not match");
    int portCount = buySell.GetLength(0);
    if (portCount != portsProducts.GetLength(0))
        throw new ArgumentNullException("port count does not match");
    if (productCount == 0)
        throw new ArgumentNullException("productCount == 0");
    if (portFrom < 0)
        throw new ArgumentNullException("portFrom < 0");
    if (portTo < 0)
        throw new ArgumentNullException("portTo < 0");
    if (portFrom > portCount - 1)
        throw new ArgumentNullException("portFrom > portCount - 1");
    if (portTo > portCount - 1)
        throw new ArgumentNullException("portTo > portCount - 1");

    //OK can get down to business
    int capacity = 100;
    int profitMax = 0;
    int profitThis = 0;
    int jTrade = -1;
    for (int j = 0; j < productCount; j++)
    {
        profitThis = portsProducts[portTo, j] - portsProducts[portFrom, j];
        if (profitThis > profitMax)
        {
            profitMax = profitThis;
            jTrade = j;
        }
    }
    if (profitMax > 0)
    {
        buySell[portFrom,jTrade] += capacity; // positive is buy
        buySell[portTo, jTrade]  -= capacity; // negative is sell
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.