Essays/PropagatingMinimum

Given: an economy in which there are several countries, one commodity, and limited opportunities for trade. Each country wants to acquire the commodity at the minimum cost. Each country i can produce an unlimited amount of the commodity at a cost per unit of i{C, or (because of free-trade agreements) it can import from its right-hand neighbor at that neighbor's cost, plus transportation cost i{P. No other direct trade is possible, but note that when country i imports from country i+1, it gets country i+1's best price, whether that comes from import or local production.

What will each country's cost be?

The question can be answered by straightforward means using suffix to propagate the minimum cost right-to-left. At each country, we add the transportation cost to the import price, and use the smaller of that total and the local cost as the cost for that country.

The code to do this is

   C =: 3 5 2 8 3 5 3 1
   P =: 1 2 1 2 3 1 1 0
   {."1 (2 {. <./@(+ |.))/\. C,.P
3 4 2 5 3 3 2 1

Countries 1, 3, 5, and 6 import. Country 5's imports originate in country 7.

This code works but is inefficient, because it executes each verb on small arguments containing only 1 or 2 atoms. For large arguments, this will be slow.

The fast method is to roll up the costs first, applying the cumulative cost in one operation rather than spread across many:

   <./\. &. (-&(+/\.P)) C
3 4 2 5 3 3 2 1

Each verb is executed once, because <./\. is handled by special code.

Trade barriers can be represented as a high (but not infinite) transportation cost. If country 5 is not allowed to import from country 6, a solution would be

   C =: 3 5 2 8 3 5 3 1
   P =: 1 2 1 2 3 1000 1 0
   <./\. &. (-&(+/\.P)) C
3 4 2 5 3 5 2 1

Alternatively, J's partitioned scan functions can be used to prevent trade across the border:

   C =: 3 5 2 8 3 5 3 1
   P =: 1 2 1 2 3 1 1 0
   B =: 0 0 0 0 0 1 0 1
   B&(;@:(<@(<./\.);.2)) &. (-&(+/\.P)) C
3 4 2 5 3 5 2 1

this almost as fast as the single scan.

---

Contributed by Henry Rich.