Transportation problem: Difference between revisions
m
→{{header|Wren}}: Minor tidy
SqrtNegInf (talk | contribs) (Added Perl) |
m (→{{header|Wren}}: Minor tidy) |
||
(3 intermediate revisions by 3 users not shown) | |||
Line 58:
=={{header|1C}}==
<syntaxhighlight lang="text">// based on the program of <romix>
перем m,n; // Table size
Line 445:
Процедура КомандаРассчитать(Команда)
РешениеТранспортнойЗадачи();
КонецПроцедуры</
=={{header|C sharp|C#}}==
{{trans|Java}}
<
using System.Collections.Generic;
using System.IO;
Line 695:
}
}
}</
{{out}}
<pre>Optimal solution input1.txt
Line 724:
=={{header|C++}}==
{{trans|Kotlin}}
<
#include <iomanip>
#include <iostream>
Line 731:
#include <string>
#include <vector>
#include <cfloat>
using namespace std;
Line 1,029 ⟶ 1,030:
return 0;
}</
{{out}}
<pre>input1.txt
Line 1,085 ⟶ 1,086:
=={{header|D}}==
{{trans|Java}}
<
final class Shipment {
Line 1,327 ⟶ 1,328:
printResult(fileName, demand, supply, costs, matrix);
}
}</
{{out}}
<pre>Optimal solution transportation_problem1.txt
Line 1,352 ⟶ 1,353:
=={{header|Glagol}}==
<syntaxhighlight lang="text">ОТДЕЛ Транспорт+;
ИСПОЛЬЗУЕТ
Вывод ИЗ "...\Отделы\Обмен\",
Line 1,801 ⟶ 1,802:
ВывестиПлан
КОН Транспорт.</
=== Input ===
Line 1,825 ⟶ 1,826:
=={{header|Go}}==
{{trans|Java}}
<
import (
Line 2,106 ⟶ 2,107:
t.printResult()
}
}</
{{out}}
Line 2,179 ⟶ 2,180:
In other words:
<
ndxasgn=: conjunction define
:
Line 2,199 ⟶ 2,200:
r=. n (<ndxs)} r
end.
)</
Task data:
<
supply=: 25 35
cost=:3 5 7,:3 2 5</
Task example:
<
20 0 5
0 30 5</
=={{header|Java}}==
{{works with|Java|8}}
<
import java.util.*;
import static java.util.Arrays.stream;
Line 2,438 ⟶ 2,439:
}
}
}</
<pre>input1.txt
Line 2,496 ⟶ 2,497:
=={{header|Julia}}==
Code taken from [https://github.com/dylanomics/transportation_problem here] using [https://jump.dev/JuMP.jl/stable/ JuMP].
<
# cost vector
Line 2,528 ⟶ 2,529:
λ = [JuMP.dual(C1[1]),JuMP.dual(C1[2])]
μ = [JuMP.dual(C2[1]),JuMP.dual(C2[2]),JuMP.dual(C2[3])]
</syntaxhighlight>
{{out}}
Line 2,536 ⟶ 2,537:
=={{header|Kotlin}}==
{{trans|Java}}
<
import java.io.File
Line 2,740 ⟶ 2,741:
}
}
}</
{{out}}
Line 2,749 ⟶ 2,750:
=={{header|Nim}}==
{{trans|Go}}
<
type
Line 2,943 ⟶ 2,944:
tr.northWestCornerRule()
tr.steppingStone()
tr.printResult()</
{{out}}
Line 2,999 ⟶ 3,000:
=={{header|Pascal}}==
<
{ based on the program of <Svetlana Belashova> }
Line 3,481 ⟶ 3,482:
GotoXY(40,1);
l1: d:=ReadKey;
END.</
=={{header|Perl}}==
Just re-using the code from [[Vogel's_approximation_method#Perl|Vogel's approximation method]], tweaked to handle specific input:
<
use warnings;
use feature 'say';
Line 3,521 ⟶ 3,522:
}
say my $result = "cost $cost\n\n" . $table =~ s/[A-Z]{2}/--/gr;</
{{out}}
<pre>cost 170
Line 3,532 ⟶ 3,533:
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.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<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>
<span style="color: #000080;font-style:italic;">-- the costs parameter should be length(avail/*aka suppliers*/) rows
--
<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>
<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>
<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>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<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>
<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>
<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>
<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>
<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>
<span style="color: #000000;">best</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">csc</span>
<span style="color: #000000;">supplier</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span>
<span style="color: #000000;">customer</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">c</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;">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>
<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>
<span style="color: #000080;font-style:italic;">-- obviously amt can be 0, in which case this just
-- removes cost entry from further consideration.</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: #0000FF;">-=</span> <span style="color: #000000;">amt</span>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<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>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 3,572 ⟶ 3,575:
Obviously I did not really quite understand the problem when I rattled out the above... this does much better.
{{trans|Go}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Transportation_problem.exw</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<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>
<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>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</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: #000000;">0</span> <span style="color: #008080;">then</span>
<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>
<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;">return</span> <span style="color: #000000;">l</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<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>
<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>
<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>
<span style="color: #000080;font-style:italic;">-- remove (and keep removing) elements that do not have a
-- vertical AND horizontal neighbor</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">removals</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<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>
<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>
<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>
<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>
<span style="color: #000000;">removals</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000080;font-style:italic;">-- place the remaining elements in the correct plus-minus order</span>
<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>
<span style="color: #000000;">prev</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">shipment</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;">stones</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<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>
<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>
<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>
<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>
<span style="color: #000080;font-style:italic;">-- check for and fix any imbalance</span>
<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>
<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>
<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>
<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>
<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>
<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>
<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>
<span style="color: #000080;font-style:italic;">--DEV...
-- costs[i]
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<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>
<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>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</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;">"generating initial feasible solution using northwest corner method...\n"</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: #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>
<span style="color: #004080;">integer</span> <span style="color: #000000;">northwest</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</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;">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>
<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>
<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;">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>
<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>
<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>
<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>
<span style="color: #000000;">northwest</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">c</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;">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>
<span style="color: #000080;font-style:italic;">--for i=1 to length(tests) do</span>
<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>
<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>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #008000;">"done"</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span>
<!--</syntaxhighlight>-->
{{out}}
(Obviously the other eight tests all work fine and produce similar output.)
Line 3,856 ⟶ 3,869:
Using <code>lpSolve::lp.transport</code>.
<
# cost matrix
Line 3,875 ⟶ 3,888:
rownames(sol) <- c("Supplier 1", "Supplier 2")
colnames(sol) <- c("Customer 1", "Customer 2", "Customer 3")
sol </
{{out}}
<pre>Success: the objective function is 180
Line 3,889 ⟶ 3,902:
Using <code>typed/racket</code>, to keep track of Vectors of Vectors of data.
<
;; {{trans|Java}}
(define-type (V2 A) (Vectorof (Vectorof A)))
Line 4,115 ⟶ 4,128:
30 40 35 45
$
1000))</
{{out}}
Output of: <code>raco test Transportation-problem.rkt</code>:
Line 4,145 ⟶ 4,158:
{{works with|Rakudo|2019.03.1}}
Using [[Vogel's_approximation_method#Raku|Vogel's approximation method]]:
<syntaxhighlight lang="raku"
my %demand = :20C1, :30C2, :10C3;
my %supply = :25S1, :35S2;
Line 4,200 ⟶ 4,213:
print "\n";
}
say "\nTotal cost: $total";</
{{out}}
<pre> C1 C2 C3
Line 4,208 ⟶ 4,221:
=={{header|REXX}}==
{{trans|Java}}
<
* Solve the Transportation Problem using the Northwest Corner Method
Default Input
Line 4,586 ⟶ 4,599:
Nop
End
Exit 12</
{{out}}
<pre>F:\>rexx tpx2 input1.txt
Line 4,653 ⟶ 4,666:
Use network solver in SAS/OR:
<
data cost_data;
input from $ to $ cost;
Line 4,693 ⟶ 4,706:
print _OROPTMODEL_NUM_['OBJECTIVE'];
print flow;
quit;</
Output:
Line 4,707 ⟶ 4,720:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Class Shipment
Line 4,963 ⟶ 4,976:
End Sub
End Module</
{{out}}
<pre>Optimal solution input1.txt
Line 4,997 ⟶ 5,010:
{{libheader|Wren-seq}}
{{libheader|Wren-fmt}}
<
import "./ioutil" for FileUtil, File
import "./math" for Nums
import "./seq" for Lst
import "./fmt" for Fmt
var Shipment = Struct.create("Shipment", ["quantity", "costPerUnit", "r", "c"])
Line 5,194 ⟶ 5,207:
t.steppingStone()
t.printResult()
}</
{{out}}
|