Rosetta Code

Transportation problem: Difference between revisions

Page Discussion

Transportation problem (view source)

Revision as of 16:54, 16 April 2022

72,547 bytes added ,  2 years ago
m
→‎{{header|Phix}}: syntax coloured, made p2js compatible
(Added Perl)
m (→‎{{header|Phix}}: syntax coloured, made p2js compatible)
Line 3,532:
The simplest solution I could think of.<br>
Assumes 0 cost is not allowed, but using say -1 as the "done" cost instead should be fine.
<!--<lang Phix>procedure solve(sequence needs, avail, costsphixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
sequence res = repeat(repeat(0,length(needs)),length(avail))
<span style="color: #008080;">procedure</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">needs</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">avail</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">)</span>
while true do
<span style="color: #000080;font-style:italic;">-- the costs parameter should be length(avail/*aka suppliers*/) rows
integer best = 0, supplier, customer
-- for s=1 to of length(costsneeds/*aka customers*/) docols</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">)==</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">avail</span><span style="color: #0000FF;">))</span>
for c=1 to length(costs[s]) do
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">)==</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">needs</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">avail</span><span style="color: #0000FF;">)))</span>
integer csc = costs[s][c]
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">needs</span><span style="color: #0000FF;">)),</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">avail</span><span style="color: #0000FF;">))</span>
if csc!=0 and (best=0 or csc<best) then
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
best = csc
<span style="color: #004080;">integer</span> <span style="color: #000000;">best</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">supplier</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">customer</span>
supplier = s
<span style="color: #008080;">for</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
customer = c
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
end if
<span style="color: #004080;">integer</span> <span style="color: #000000;">csc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span>
end for
<span style="color: #008080;">if</span> <span style="color: #000000;">csc</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">best</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">csc</span><span style="color: #0000FF;"><</span><span style="color: #000000;">best</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
end for
<span style="color: #000000;">best</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">csc</span>
if best=0 then exit end if -- all costs examined
<span style="color: #000000;">supplier</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span>
integer amt = min(avail[supplier],needs[customer])
<span style="color: #000000;">customer</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">c</span>
-- obviously amt can be 0, in which case this just
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
-- removes cost entry from further consideration.
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
avail[supplier] -= amt
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
needs[customer] -= amt
<span style="color: #008080;">if</span> <span style="color: #000000;">best</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- all costs examined</span>
res[supplier,customer] = amt
<span style="color: #004080;">integer</span> <span style="color: #000000;">amt</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">avail</span><span style="color: #0000FF;">[</span><span style="color: #000000;">supplier</span><span style="color: #0000FF;">],</span><span style="color: #000000;">needs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">customer</span><span style="color: #0000FF;">])</span>
costs[supplier,customer] = 0
<span style="color: #000080;font-style:italic;">-- obviously amt can be 0, in which case this just
end while
-- removes cost entry from further consideration.</span>
pp(res,{pp_Nest,1})
<span style="color: #000000;">avail</span><span style="color: #0000FF;">[</span><span style="color: #000000;">supplier</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">amt</span>
end procedure
<span style="color: #000000;">needs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">customer</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">amt</span>
 
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">supplier</span><span style="color: #0000FF;">,</span><span style="color: #000000;">customer</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">amt</span>
constant needs = {20,30,10}, -- (customers)
<span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">supplier</span><span style="color: #0000FF;">,</span><span style="color: #000000;">customer</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
avail = {25,35}, -- (suppliers)
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
costs = {{3,5,7}, -- (length suppliers rows of
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,{</span><span style="color: #004600;">pp_Nest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>
{3,2,5}} -- length customers columns)
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
 
solve(needs,avail,costs)</lang>
<span style="color: #000000;">solve</span><span style="color: #0000FF;">({</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">35</span><span style="color: #0000FF;">},{{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">}})</span>
<!--</lang>-->
{{out}}
<pre>
Line 3,572 ⟶ 3,574:
Obviously I did not really quite understand the problem when I rattled out the above... this does much better.
{{trans|Go}}
<!--<lang Phix>(phixonline)-->
<lang Phix>-- demo\rosetta\Transportation_problem.exw
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Transportation_problem.exw</span>
enum QTY, COST, R, C -- (a shipment)
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
constant eps = 1e-12
<span style="color: #008080;">enum</span> <span style="color: #000000;">QTY</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">COST</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">R</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">C</span> <span style="color: #000080;font-style:italic;">-- (a shipment)</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">eps</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1e-12</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">print_matrix</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">total_costs</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0.0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">st</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">" - "</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">R</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">r</span> <span style="color: #008080;">and</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">C</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">c</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">qty</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">round</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">QTY</span><span style="color: #0000FF;">])</span> <span style="color: #000080;font-style:italic;">-- (remove +/-eps)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">qty</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">st</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">" %3d "</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">qty</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">total_costs</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">qty</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">COST</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">st</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">total_costs</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">print_result</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">transport</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">expected</span><span style="color: #0000FF;">)</span>
function print_matrix(sequence matrix)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">matrix</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">transport</span><span style="color: #0000FF;">[</span><span style="color: #000000;">4</span><span style="color: #0000FF;">]</span>
atom total_costs = 0.0
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Optimal solution\n\n"</span><span style="color: #0000FF;">)</span>
for r=1 to length(matrix) do
<span style="color: #004080;">atom</span> <span style="color: #000000;">total_costs</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">print_matrix</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">)</span>
for c=1 to length(matrix[r]) do
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nTotal costs: %g (expected %g)\n\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">total_costs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">expected</span><span style="color: #0000FF;">})</span>
object s = matrix[r][c]
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
string st = " - "
if s!=0 and s[R]==r and s[C]==c then
atom qty = round(s[QTY]) -- (remove +/-eps)
if qty!=0 then
st = sprintf(" %3d ", qty)
total_costs += qty * s[COST]
end if
end if
puts(1,st)
end for
printf(1,"\n")
end for
return total_costs
end function
 
procedure print_result(sequence transport, atom expected)
sequence matrix = transport[4]
printf(1,"Optimal solution\n\n")
atom total_costs = print_matrix(matrix)
printf(1,"\nTotal costs: %g (expected %g)\n\n", {total_costs,expected})
end procedure
 
function get_neighbors(sequence shipment, lst)
sequence nbrs = {0,0}
for e=1 to length(lst) do
sequence o = lst[e]
if o!=shipment then
if o[R]==shipment[R] and nbrs[1]==0 then
nbrs[1] = o
elsif o[C]==shipment[C] and nbrs[2]==0 then
nbrs[2] = o
end if
if nbrs[1]!=0 and nbrs[2]!=0 then
exit
end if
end if
end for
return nbrs
end function
 
function matrix_to_list(sequence matrix)
sequence l = {}
for r=1 to length(matrix) do
for c=1 to length(matrix[r]) do
if matrix[r,c]!=0 then
l = append(l,matrix[r,c])
end if
end for
end for
return l
end function
 
function get_closed_path(sequence matrix, shipment)
sequence path = matrix_to_list(matrix)
path = prepend(path,shipment)
 
-- remove (and keep removing) elements that do not have a
-- vertical AND horizontal neighbor
while true do
integer removals = 0
for e=length(path) to 1 by -1 do
sequence nbrs = get_neighbors(path[e], path)
if nbrs[1]==0 or nbrs[2]==0 then
path[e..e] = {}
removals += 1
end if
end for
if removals==0 then exit end if
end while
<span style="color: #008080;">function</span> <span style="color: #000000;">get_neighbors</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">shipment</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">lst</span><span style="color: #0000FF;">)</span>
-- place the remaining elements in the correct plus-minus order
<span style="color: #004080;">sequence</span> <span style="color: #000000;">nbrs</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span>
sequence stones = repeat(0,length(path)),
<span style="color: #008080;">for</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lst</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
prev = shipment
<span style="color: #004080;">sequence</span> <span style="color: #000000;">o</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lst</span><span style="color: #0000FF;">[</span><span style="color: #000000;">e</span><span style="color: #0000FF;">]</span>
for i=1 to length(stones) do
<span style="color: #008080;">if</span> <span style="color: #000000;">o</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">shipment</span> <span style="color: #008080;">then</span>
stones[i] = prev
<span style="color: #008080;">if</span> <span style="color: #000000;">o</span><span style="color: #0000FF;">[</span><span style="color: #000000;">R</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">shipment</span><span style="color: #0000FF;">[</span><span style="color: #000000;">R</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">and</span> <span style="color: #000000;">nbrs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
prev = get_neighbors(prev, path)[mod(i,2)+1]
<span style="color: #000000;">nbrs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">o</span>
end for
<span style="color: #008080;">elsif</span> <span style="color: #000000;">o</span><span style="color: #0000FF;">[</span><span style="color: #000000;">C</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">shipment</span><span style="color: #0000FF;">[</span><span style="color: #000000;">C</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">and</span> <span style="color: #000000;">nbrs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
return stones
<span style="color: #000000;">nbrs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">o</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nbrs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">nbrs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">nbrs</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">matrix_to_list</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">)</span>
function fix_degenerate_case(sequence matrix, costs)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
if length(matrix)+length(matrix[1])-1 != length(matrix_to_list(matrix)) then
<span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
printf(1,"fixing degenerate case...\n")
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
for r=1 to length(matrix) do
<span style="color: #008080;">if</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
for c=1 to length(matrix[r]) do
<span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">])</span>
if matrix[r][c] == 0 then
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
sequence dummy = {eps, costs[r][c], r, c}
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
if length(get_closed_path(matrix,dummy)) == 0 then
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
matrix[r][c] = dummy
<span style="color: #008080;">return</span> <span style="color: #000000;">l</span>
return matrix
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
end if
end if
end for
end for
?9/0 -- ??
end if
return matrix
end function
 
function initialise(sequence tests, integer t)
sequence {src,dst,costs} = tests[t]
string cs = ppf(costs,{pp_Nest,1,pp_StrFmt,3,pp_IntCh,false,pp_Indent,7})
printf(1,"test %d:\nsrc: %v,\ndst: %v,\ncosts: %s\n",{t,src,dst,cs})
<span style="color: #008080;">function</span> <span style="color: #000000;">get_closed_path</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">shipment</span><span style="color: #0000FF;">)</span>
-- check for and fix any imbalance
<span style="color: #004080;">sequence</span> <span style="color: #000000;">path</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">matrix_to_list</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">)</span>
atom totalSrc = sum(src),
<span style="color: #000000;">path</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">prepend</span><span style="color: #0000FF;">(</span><span style="color: #000000;">path</span><span style="color: #0000FF;">,</span><span style="color: #000000;">shipment</span><span style="color: #0000FF;">)</span>
totalDst = sum(dst),
diff = totalSrc-totalDst
if diff>0 then
puts(1,"adding dummy consumer...\n")
dst = append(dst, diff)
for i=1 to length(costs) do
costs[i] &= 0
end for
elsif diff<0 then
puts(1,"adding dummy supplier...\n")
src = append(src, -diff)
costs = append(costs,repeat(0,length(dst)))
end if
<span style="color: #000080;font-style:italic;">-- remove (and keep removing) elements that do not have a
printf(1,"generating initial feasible solution using northwest corner method...\n")
-- vertical AND horizontal neighbor</span>
sequence matrix = repeat(repeat(0,length(dst)),length(src))
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
integer northwest = 1
<span style="color: #004080;">integer</span> <span style="color: #000000;">removals</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
for r=1 to length(src) do
<span style="color: #008080;">for</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">path</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
for c=northwest to length(dst) do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">nbrs</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_neighbors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">path</span><span style="color: #0000FF;">[</span><span style="color: #000000;">e</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">path</span><span style="color: #0000FF;">)</span>
atom qty = min(src[r],dst[c])
<span style="color: #008080;">if</span> <span style="color: #000000;">nbrs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">nbrs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
if qty>0 then
<span style="color: #000000;">path</span><span style="color: #0000FF;">[</span><span style="color: #000000;">e</span><span style="color: #0000FF;">..</span><span style="color: #000000;">e</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
matrix[r][c] = {qty,costs[r,c],r,c}
<span style="color: #000000;">removals</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
src[r] -= qty
<span style="color: #008080;">end</span> dst[c]<span -style="color: qty#008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
if src[r]=0 then
<span style="color: #008080;">if</span> <span style="color: #000000;">removals</span><span style="color: #0000FF;">==</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
northwest = c
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
exit
end if
<span style="color: #000080;font-style:italic;">-- place the remaining elements in the correct plus-minus order</span>
end if
<span style="color: #004080;">sequence</span> <span style="color: #000000;">stones</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">path</span><span style="color: #0000FF;">)),</span>
end for
<span style="color: #000000;">prev</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">shipment</span>
end for
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stones</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
printf(1,"\nTotal costs: %g\n\n", print_matrix(matrix))
<span style="color: #000000;">stones</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">prev</span>
<span style="color: #000000;">prev</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_neighbors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">prev</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">path</span><span style="color: #0000FF;">)[</span><span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
return {src,dst,costs,matrix}
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">stones</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">fix_degenerate_case</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">)+</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])-</span><span style="color: #000000;">1</span> <span style="color: #0000FF;">!=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix_to_list</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"fixing degenerate case...\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">dummy</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">eps</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">get_closed_path</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dummy</span><span style="color: #0000FF;">))</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dummy</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">matrix</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">-- ??</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">matrix</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">initialise</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
function stepping_stone(sequence transport)
<span style="color: #004080;">sequence</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">src</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dst</span><span style="color: #0000FF;">,</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">])</span>
sequence {src, dst, costs, matrix} = transport
<span style="color: #004080;">string</span> <span style="color: #000000;">cs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">ppf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">,{</span><span style="color: #004600;">pp_Nest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #004600;">pp_StrFmt</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #004600;">pp_IntCh</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #004600;">pp_Indent</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">})</span>
atom maxReduction = 0
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"test %d:\nsrc: %v,\ndst: %v,\ncosts: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">src</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dst</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cs</span><span style="color: #0000FF;">})</span>
object move = NULL, leaving
matrix = fix_degenerate_case(matrix, costs)
<span style="color: #000080;font-style:italic;">-- check for and fix any imbalance</span>
for r=1 to length(src) do
<span style="color: #004080;">atom</span> <span style="color: #000000;">totalSrc</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">),</span>
for c=1 to length(dst) do
<span style="color: #000000;">totalDst</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dst</span><span style="color: #0000FF;">),</span>
if matrix[r][c] = 0 then
<span style="color: #000000;">diff</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">totalSrc</span><span style="color: #0000FF;">-</span><span style="color: #000000;">totalDst</span>
sequence trial_shipment = {0, costs[r][c], r, c},
<span style="color: #008080;">if</span> <span style="color: #000000;">diff</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
path = get_closed_path(matrix,trial_shipment)
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"adding dummy consumer...\n"</span><span style="color: #0000FF;">)</span>
atom reduction = 0.0,
<span style="color: #000000;">dst</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dst</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">diff</span><span style="color: #0000FF;">)</span>
lowestQuantity = 1e308
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
object leavingCandidate = 0
<span style="color: #000080;font-style:italic;">--DEV...
bool plus = true
-- costs[i] for i&=1 to length(path) do0</span>
<span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">0</span>
sequence s = path[i]
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
if plus then
<span style="color: #008080;">elsif</span> <span style="color: #000000;">diff</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
reduction += s[COST]
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"adding dummy supplier...\n"</span><span style="color: #0000FF;">)</span>
else
<span style="color: #000000;">src</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">diff</span><span style="color: #0000FF;">)</span>
reduction -= s[COST]
<span style="color: #000000;">costs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dst</span><span style="color: #0000FF;">)))</span>
if s[QTY] < lowestQuantity then
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
leavingCandidate = s
lowestQuantity = s[QTY]
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"generating initial feasible solution using northwest corner method...\n"</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #004080;">sequence</span> <span style="color: #000000;">matrix</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dst</span><span style="color: #0000FF;">)),</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">))</span>
end if
<span style="color: #004080;">integer</span> <span style="color: #000000;">northwest</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
plus = not plus
<span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
end for
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">northwest</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dst</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
if reduction < maxReduction then
<span style="color: #004080;">atom</span> <span style="color: #000000;">qty</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">],</span><span style="color: #000000;">dst</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">])</span>
move = path
<span style="color: #008080;">if</span> <span style="color: #000000;">qty</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
leaving = leavingCandidate
<span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">qty</span><span style="color: #0000FF;">,</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">],</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">}</span>
maxReduction = reduction
<span style="color: #000000;">src</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">qty</span>
end if
<span style="color: #000000;">dst</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">qty</span>
end if
<span style="color: #008080;">if</span> <span style="color: #000000;">src</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
end for
<span style="color: #000000;">northwest</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">c</span>
end for
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nTotal costs: %g\n\n"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">print_matrix</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">src</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dst</span><span style="color: #0000FF;">,</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">stepping_stone</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">transport</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">src</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dst</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">transport</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">maxReduction</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">move</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">NULL</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">leaving</span>
<span style="color: #000000;">matrix</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">fix_degenerate_case</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dst</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">trial_shipment</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">c</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">},</span>
<span style="color: #000000;">path</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_closed_path</span><span style="color: #0000FF;">(</span><span style="color: #000000;">matrix</span><span style="color: #0000FF;">,</span><span style="color: #000000;">trial_shipment</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">reduction</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0.0</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">lowestQuantity</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1e308</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">leavingCandidate</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">plus</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">path</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">path</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">plus</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">reduction</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">COST</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">reduction</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">COST</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">QTY</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">lowestQuantity</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">leavingCandidate</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span>
<span style="color: #000000;">lowestQuantity</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">QTY</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">plus</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">not</span> <span style="color: #000000;">plus</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">reduction</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">maxReduction</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">move</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">path</span>
<span style="color: #000000;">leaving</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">leavingCandidate</span>
<span style="color: #000000;">maxReduction</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">reduction</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">move</span><span style="color: #0000FF;">!=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">q</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">leaving</span><span style="color: #0000FF;">[</span><span style="color: #000000;">QTY</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">plus</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">move</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">move</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">plus</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">QTY</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">q</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">QTY</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">q</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">QTY</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">R</span><span style="color: #0000FF;">]][</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">C</span><span style="color: #0000FF;">]]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">matrix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">R</span><span style="color: #0000FF;">]][</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">C</span><span style="color: #0000FF;">]]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">plus</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">not</span> <span style="color: #000000;">plus</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">src</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dst</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">stepping_stone</span><span style="color: #0000FF;">({</span><span style="color: #000000;">src</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dst</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">src</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dst</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">matrix</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #000080;font-style:italic;">-- -- source dest costs expected total</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{{</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">35</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">}},</span> <span style="color: #000000;">180</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">40</span><span style="color: #0000FF;">,</span><span style="color: #000000;">33</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">}},</span> <span style="color: #000000;">130</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">14</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">25</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">40</span><span style="color: #0000FF;">,</span><span style="color: #000000;">35</span><span style="color: #0000FF;">,</span><span style="color: #000000;">45</span><span style="color: #0000FF;">}},</span> <span style="color: #000000;">1000</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">100</span><span style="color: #0000FF;">,</span><span style="color: #000000;">300</span><span style="color: #0000FF;">,</span><span style="color: #000000;">300</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">300</span><span style="color: #0000FF;">,</span><span style="color: #000000;">200</span><span style="color: #0000FF;">,</span><span style="color: #000000;">200</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">40</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">80</span><span style="color: #0000FF;">,</span><span style="color: #000000;">40</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">90</span><span style="color: #0000FF;">,</span><span style="color: #000000;">70</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">}},</span> <span style="color: #000000;">39000</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">40</span><span style="color: #0000FF;">,</span><span style="color: #000000;">60</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">}},</span> <span style="color: #000000;">920</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{{</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">}},</span> <span style="color: #000000;">68</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">18</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">14</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">19</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">70</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">40</span><span style="color: #0000FF;">,</span><span style="color: #000000;">60</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">40</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">70</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">}},</span> <span style="color: #000000;">743</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">14</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{{</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">14</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">16</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">18</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">17</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">16</span><span style="color: #0000FF;">}},</span> <span style="color: #000000;">259</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">60</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">70</span><span style="color: #0000FF;">,</span><span style="color: #000000;">30</span><span style="color: #0000FF;">,</span><span style="color: #000000;">60</span><span style="color: #0000FF;">},{{</span><span style="color: #000000;">16</span><span style="color: #0000FF;">,</span><span style="color: #000000;">16</span><span style="color: #0000FF;">,</span><span style="color: #000000;">13</span><span style="color: #0000FF;">,</span><span style="color: #000000;">22</span><span style="color: #0000FF;">,</span><span style="color: #000000;">17</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">14</span><span style="color: #0000FF;">,</span><span style="color: #000000;">14</span><span style="color: #0000FF;">,</span><span style="color: #000000;">13</span><span style="color: #0000FF;">,</span><span style="color: #000000;">19</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">19</span><span style="color: #0000FF;">,</span><span style="color: #000000;">19</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">23</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">}},</span> <span style="color: #000000;">3100</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">75</span><span style="color: #0000FF;">,</span><span style="color: #000000;">25</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">50</span><span style="color: #0000FF;">,</span><span style="color: #000000;">60</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}},</span> <span style="color: #000000;">610</span><span style="color: #0000FF;">}}</span>
if move!=NULL then
atom q = leaving[QTY]
bool plus = true
for i=1 to length(move) do
sequence s = move[i]
if plus then
s[QTY] += q
else
s[QTY] -= q
end if
if s[QTY] == 0 then
matrix[s[R]][s[C]] = 0
else
matrix[s[R]][s[C]] = s
end if
plus = not plus
end for
{src, dst, costs, matrix} = stepping_stone({src, dst, costs, matrix})
end if
return {src, dst, costs, matrix}
end function
<span style="color: #000080;font-style:italic;">--for i=1 to length(tests) do</span>
-- -- source dest costs expected total
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span> <span style="color: #008080;">to</span> <span style="color: #000000;">3</span> <span style="color: #008080;">do</span>
constant tests = {{{25,35}, {20,30,10}, {{3,5,7},
<span style="color: #000000;">print_result</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stepping_stone</span><span style="color: #0000FF;">(</span><span style="color: #000000;">initialise</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)),</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">4</span><span style="color: #0000FF;">])</span>
{3,2,5}}, 180},
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
{{12,40,33}, {20,30,10}, {{3,5,7},
{2,4,6},
<span style="color: #0000FF;">?</span><span style="color: #008000;">"done"</span>
{9,1,8}}, 130},
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span>
{{14,10,15,12}, {10,15,12,15}, {{10,30,25,15},
<!--</lang>-->
{20,15,20,10},
{10,30,20,20},
{30,40,35,45}}, 1000},
{{100,300,300}, {300,200,200}, {{50,40,30},
{80,40,30},
{90,70,50}}, 39000},
{{40,60,50}, {20,30,50,50}, {{4,6,8,8},
{6,8,6,7},
{5,7,6,8}}, 920},
{{12,1,5}, {10,8}, {{ 2, 4},
{ 8,12},
{12, 6}}, 68},
{{7,9,18}, {5,8,7,14}, {{19,30,50,10},
{70,30,40,60},
{40, 8,70,20}}, 743},
{{12,11,14,8}, {10,11,15,5,4}, {{ 7,12, 1, 5, 6},
{15, 3,12, 6,14},
{ 8,16,10,12, 7},
{18, 8,17,11,16}}, 259},
{{50,60,50,50}, {30,20,70,30,60},{{16,16,13,22,17},
{14,14,13,19,15},
{19,19,20,23,50},
{50,12,50,15,11}}, 3100},
{{50,75,25}, {20,20,50,60}, {{3,5,7,6},
{2,5,8,2},
{3,6,9,2}}, 610}}
 
--for i=1 to length(tests) do
for i=3 to 3 do
print_result(stepping_stone(initialise(tests,i)),tests[i][4])
end for</lang>
{{out}}
(Obviously the other eight tests all work fine and produce similar output.)
Petelomax
7,794

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/232252"