# Maximize profit on a trade route

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 } };


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++)
{
}
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++)
{
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++)
{
}
}
int row = rowCount - 1;
int col = colCount - 1;
int rowMin = row;
int colMin = col;

bool restart = false;
while (true)
{
{
//Debug.WriteLine("");
for (int i = 0; i < rowCount; i++)
{
//Debug.WriteLine("i = " + i.ToString());
rowDisplay.Clear();
for (int j = 0; j < colCount; 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;
{
//Debug.WriteLine("");
for (int i = 0; i < rowCount; i++)
{
//Debug.WriteLine("i = " + i.ToString());
rowDisplay.Clear();
for (int j = 0; j < colCount; 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 profit = 0;
int profitMax = 0;
{
//Debug.WriteLine("");
for (int i = 0; i < rowCount; i++)
{
rowDisplay.Clear();
for (int j = 0; j < colCount; j++)
{
}
//Debug.WriteLine(string.Join(", ", rowDisplay));
}
}
for (int i = 0; i < rowCount; i++)
{
for (int j = 0; j < colCount; j++)
{
{
}
}
}
Debug.WriteLine("Capacity {0}", capacity);
int count = 0;
{
//1, 0, 0
//2, 0, 1
//0, 0, 2
//if (buySellOpt[0, 0] == 1 &&
//    buySellOpt[1, 0] == 2 &&
//    buySellOpt[1, 2] == 1 &&
//{
//    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++)
{
}
}
count++;
if (count == 18)
{
//Debug.WriteLine("Problem count == 18");
}
for (int i = 0; i < rowCount; i++)
{
for (int j = 0; j < colCount; j++)
{

//Debug.WriteLine("");
//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];
curProduct[j] = 0;
}
{
}
}
if (buyCount > 0 && curCapacity > 0)
for (int j = 0; j < colCount; j++)
{
{
profit -= buyEach * portsProducts[i, j];
}
}
}
}
if (profit > 0)
{
Debug.WriteLine("");
if (profit > profitMax)
{
profitMax = profit;
for (int i = 0; i < rowCount; i++)
{
for (int j = 0; j < colCount; j++)
{
}
}
Debug.WriteLine("new max");
}
Debug.WriteLine("");
Debug.WriteLine("profit " + profit.ToString("N0") + " count " + count);
for (int i = 0; i < rowCount; i++)
{
for (int j = 0; j < colCount; j++)
{
}
}
}
}
}
{
Int32[,] buySellOptionsClone = new Int32[rowCount, colCount];
for (int i = 0; i < rowCount; i++)
{
for (int j = 0; j < colCount; j++)
{
}
}
}
public static bool buySellBump2(Int32[,] buySellOptions, ref int i, ref int j, ref bool restart, Int32[,] portsProducts, Int32[] highPrice, Int32[] lowPrice)
{
if (buySellOptions[i, j] == 0 && (portsProducts[i, j] != highPrice[j] || portsProducts[i, j] != lowPrice[j]))
{
if (portsProducts[i, j] != highPrice[j])
{
}
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
for (int jj = j; jj < colCount; jj++)
{
}
for (int ii = i + 1; ii < rowCount; ii++)
{
for (int jjj = 0; jjj < colCount; jjj++)
{
}
}
if (j == 0)
{
if (i == 0)
return false;
i--;
j = colCount - 1;
}
else
j--;
restart = true;
}
}

• 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. Dec 26, 2016 at 15:44
• 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. Dec 26, 2016 at 23:40
• 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. Jan 4, 2017 at 11:41
• @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. Jan 4, 2017 at 11:47
• 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. Jan 4, 2017 at 12:00

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;
}

• 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. Jan 5, 2017 at 4:12
• 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. Jan 5, 2017 at 5:25
• 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. Jan 5, 2017 at 6:27
• @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. Jan 5, 2017 at 6:41
• @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.
– JS1
Jan 5, 2017 at 7:39

### 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.

• An extra iteration on j might be more expensive than i == 0 Dec 26, 2016 at 11:12
• What is the maximum dimension of the portsProducts you would like to support? Dec 26, 2016 at 11:55
• 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. Dec 26, 2016 at 13:01
• Fair enough, I dropped that point Dec 26, 2016 at 13:12
//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.

• Donating a bounty and answering yourself? Reputation points laundering? :-P Jan 4, 2017 at 10:37
• @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. Jan 4, 2017 at 10:39

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 } };
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("");
}
for (int i = 0; i < trades.GetLongLength(0); i++)
{
Debug.Write("port " + i + "  products");
for (int j = 0; j < trades.GetLongLength(1); 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++)
{
}
// 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
}
private static void PortToPort(int[,] buySell, int[,] portsProducts, int portFrom, int portTo)
{
//should not get any exceptions
if (portsProducts == null)
throw new ArgumentNullException("portsProducts");
if (productCount != portsProducts.GetLength(1))
throw new ArgumentNullException("product count does not match");
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;
for (int j = 0; j < productCount; j++)
{
profitThis = portsProducts[portTo, j] - portsProducts[portFrom, j];
if (profitThis > profitMax)
{
profitMax = profitThis;