Transportation problem: Difference between revisions

← Older edit

Transportation problem (view source)

Revision as of 15:22, 14 February 2024

135,856 bytes added , 4 months ago

m

→‎{{header|Wren}}: Minor tidy

PureFox

9,488

edits

Revision as of 05:46, 5 November 2018 (view source) Petelomax (talk \| contribs) (→‎{{header\|Phix}}) ← Older edit		Latest revision as of 15:22, 14 February 2024 (view source) PureFox (talk \| contribs) m (→‎{{header\|Wren}}: Minor tidy)
(60 intermediate revisions by 10 users not shown)
Line 5: <br><br> :::::: {\| border="1" style="border-collapse: collapse; border: 1px solid black; text-align: center;" \|- !style="width:100pt"\| Line 29: <br><br> ::::::{\| border="1" style="border-collapse: collapse; border: 1px solid black; text-align: center;" \|- !style="width:100pt"\| Line 58: =={{header\|1C}}== <syntaxhighlight lang="text">// based on the program of <romix> перем m,n; // Table size Line 445: Процедура КомандаРассчитать(Команда) РешениеТранспортнойЗадачи(); КонецПроцедуры</~~lang~~syntaxhighlight> =={{header\|C sharp\|C#}}== {{trans\|Java}} <syntaxhighlight lang="csharp">using System; using System.Collections.Generic; using System.IO; using System.Linq; namespace TransportationProblem { class Shipment { public Shipment(double q, double cpu, int r, int c) { Quantity = q; CostPerUnit = cpu; R = r; C = c; } public double CostPerUnit { get; } public double Quantity { get; set; } public int R { get; } public int C { get; } } class Program { private static int[] demand; private static int[] supply; private static double[,] costs; private static Shipment[,] matrix; static void Init(string filename) { string line; using (StreamReader file = new StreamReader(filename)) { line = file.ReadLine(); var numArr = line.Split(); int numSources = int.Parse(numArr[0]); int numDestinations = int.Parse(numArr[1]); List<int> src = new List<int>(); List<int> dst = new List<int>(); line = file.ReadLine(); numArr = line.Split(); for (int i = 0; i < numSources; i++) { src.Add(int.Parse(numArr[i])); } line = file.ReadLine(); numArr = line.Split(); for (int i = 0; i < numDestinations; i++) { dst.Add(int.Parse(numArr[i])); } // fix imbalance int totalSrc = src.Sum(); int totalDst = dst.Sum(); if (totalSrc > totalDst) { dst.Add(totalSrc - totalDst); } else if (totalDst > totalSrc) { src.Add(totalDst - totalSrc); } supply = src.ToArray(); demand = dst.ToArray(); costs = new double[supply.Length, demand.Length]; matrix = new Shipment[supply.Length, demand.Length]; for (int i = 0; i < numSources; i++) { line = file.ReadLine(); numArr = line.Split(); for (int j = 0; j < numDestinations; j++) { costs[i, j] = int.Parse(numArr[j]); } } } } static void NorthWestCornerRule() { for (int r = 0, northwest = 0; r < supply.Length; r++) { for (int c = northwest; c < demand.Length; c++) { int quantity = Math.Min(supply[r], demand[c]); if (quantity > 0) { matrix[r, c] = new Shipment(quantity, costs[r, c], r, c); supply[r] -= quantity; demand[c] -= quantity; if (supply[r] == 0) { northwest = c; break; } } } } } static void SteppingStone() { double maxReduction = 0; Shipment[] move = null; Shipment leaving = null; FixDegenerateCase(); for (int r = 0; r < supply.Length; r++) { for (int c = 0; c < demand.Length; c++) { if (matrix[r, c] != null) { continue; } Shipment trial = new Shipment(0, costs[r, c], r, c); Shipment[] path = GetClosedPath(trial); double reduction = 0; double lowestQuantity = int.MaxValue; Shipment leavingCandidate = null; bool plus = true; foreach (var s in path) { if (plus) { reduction += s.CostPerUnit; } else { reduction -= s.CostPerUnit; if (s.Quantity < lowestQuantity) { leavingCandidate = s; lowestQuantity = s.Quantity; } } plus = !plus; } if (reduction < maxReduction) { move = path; leaving = leavingCandidate; maxReduction = reduction; } } } if (move != null) { double q = leaving.Quantity; bool plus = true; foreach (var s in move) { s.Quantity += plus ? q : -q; matrix[s.R, s.C] = s.Quantity == 0 ? null : s; plus = !plus; } SteppingStone(); } } static List<Shipment> MatrixToList() { List<Shipment> newList = new List<Shipment>(); foreach (var item in matrix) { if (null != item) { newList.Add(item); } } return newList; } static Shipment[] GetClosedPath(Shipment s) { List<Shipment> path = MatrixToList(); path.Add(s); // remove (and keep removing) elements that do not have a // vertical AND horizontal neighbor int before; do { before = path.Count; path.RemoveAll(ship => { var nbrs = GetNeighbors(ship, path); return nbrs[0] == null \|\| nbrs[1] == null; }); } while (before != path.Count); // place the remaining elements in the correct plus-minus order Shipment[] stones = path.ToArray(); Shipment prev = s; for (int i = 0; i < stones.Length; i++) { stones[i] = prev; prev = GetNeighbors(prev, path)[i % 2]; } return stones; } static Shipment[] GetNeighbors(Shipment s, List<Shipment> lst) { Shipment[] nbrs = new Shipment[2]; foreach (var o in lst) { if (o != s) { if (o.R == s.R && nbrs[0] == null) { nbrs[0] = o; } else if (o.C == s.C && nbrs[1] == null) { nbrs[1] = o; } if (nbrs[0] != null && nbrs[1] != null) { break; } } } return nbrs; } static void FixDegenerateCase() { const double eps = double.Epsilon; if (supply.Length + demand.Length - 1 != MatrixToList().Count) { for (int r = 0; r < supply.Length; r++) { for (int c = 0; c < demand.Length; c++) { if (matrix[r, c] == null) { Shipment dummy = new Shipment(eps, costs[r, c], r, c); if (GetClosedPath(dummy).Length == 0) { matrix[r, c] = dummy; return; } } } } } } static void PrintResult(string filename) { Console.WriteLine("Optimal solution {0}\n", filename); double totalCosts = 0; for (int r = 0; r < supply.Length; r++) { for (int c = 0; c < demand.Length; c++) { Shipment s = matrix[r, c]; if (s != null && s.R == r && s.C == c) { Console.Write(" {0,3} ", s.Quantity); totalCosts += (s.Quantity * s.CostPerUnit); } else { Console.Write(" - "); } } Console.WriteLine(); } Console.WriteLine("\nTotal costs: {0}\n", totalCosts); } static void Main() { foreach (var filename in new string[] { "input1.txt", "input2.txt", "input3.txt" }) { Init(filename); NorthWestCornerRule(); SteppingStone(); PrintResult(filename); } } } }</syntaxhighlight> {{out}} <pre>Optimal solution input1.txt 20 - 5 - 30 5 Total costs: 180 Optimal solution input2.txt - - - 12 20 - 10 10 - 30 - 3 Total costs: 130 Optimal solution input3.txt - - - 14 - 9 - 1 10 - 5 - - 5 7 - - 1 - - Total costs: 1000</pre> =={{header\|C++}}== {{trans\|Kotlin}} <syntaxhighlight lang="cpp">#include <algorithm> #include <iomanip> #include <iostream> #include <fstream> #include <numeric> #include <string> #include <vector> #include <cfloat> using namespace std; class Shipment { public: double costPerUnit; int r, c; double quantity; Shipment() : quantity(0), costPerUnit(0), r(-1), c(-1) { // empty } Shipment(double q, double cpu, int r, int c) : quantity(q), costPerUnit(cpu), r(r), c(c) { // empty } friend bool operator==(const Shipment &lhs, const Shipment &rhs) { return lhs.costPerUnit == rhs.costPerUnit && lhs.quantity == rhs.quantity && lhs.r == rhs.r && lhs.c == rhs.c; } friend bool operator!=(const Shipment &lhs, const Shipment &rhs) { return !(lhs == rhs); } static Shipment ZERO; }; Shipment Shipment::ZERO = {}; vector<int> demand, supply; vector<vector<double>> costs; vector<vector<Shipment>> matrix; void init(string filename) { ifstream ifs; ifs.open(filename); if (!ifs) { cerr << "File not found: " << filename << '\n'; return; } size_t numSources, numDestinations; ifs >> numSources >> numDestinations; vector<int> src, dst; int t; for (size_t i = 0; i < numSources; i++) { ifs >> t; src.push_back(t); } for (size_t i = 0; i < numDestinations; i++) { ifs >> t; dst.push_back(t); } // fix imbalance int totalSrc = accumulate(src.cbegin(), src.cend(), 0); int totalDst = accumulate(dst.cbegin(), dst.cend(), 0); if (totalSrc > totalDst) { dst.push_back(totalSrc - totalDst); } else if (totalDst > totalSrc) { src.push_back(totalDst - totalSrc); } supply = src; demand = dst; costs.clear(); matrix.clear(); double d; for (size_t i = 0; i < numSources; i++) { size_t cap = max(numDestinations, demand.size()); vector<double> dt(cap); vector<Shipment> st(cap); for (size_t j = 0; j < numDestinations; j++) { ifs >> d; dt[j] = d; } costs.push_back(dt); matrix.push_back(st); } for (size_t i = numSources; i < supply.size(); i++) { size_t cap = max(numDestinations, demand.size()); vector<Shipment> st(cap); matrix.push_back(st); vector<double> dt(cap); costs.push_back(dt); } } void northWestCornerRule() { int northwest = 0; for (size_t r = 0; r < supply.size(); r++) { for (size_t c = northwest; c < demand.size(); c++) { int quantity = min(supply[r], demand[c]); if (quantity > 0) { matrix[r][c] = Shipment(quantity, costs[r][c], r, c); supply[r] -= quantity; demand[c] -= quantity; if (supply[r] == 0) { northwest = c; break; } } } } } vector<Shipment> matrixToVector() { vector<Shipment> result; for (auto &row : matrix) { for (auto &s : row) { if (s != Shipment::ZERO) { result.push_back(s); } } } return result; } vector<Shipment> getNeighbors(const Shipment &s, const vector<Shipment> &lst) { vector<Shipment> nbrs(2); for (auto &o : lst) { if (o != s) { if (o.r == s.r && nbrs[0] == Shipment::ZERO) { nbrs[0] = o; } else if (o.c == s.c && nbrs[1] == Shipment::ZERO) { nbrs[1] = o; } if (nbrs[0] != Shipment::ZERO && nbrs[1] != Shipment::ZERO) { break; } } } return nbrs; } vector<Shipment> getClosedPath(const Shipment &s) { auto path = matrixToVector(); path.insert(path.begin(), s); // remove (and keep removing) elements that do not have a // vertical AND horizontal neighbor size_t before; do { before = path.size(); path.erase( remove_if( path.begin(), path.end(), [&path](Shipment &ship) { auto nbrs = getNeighbors(ship, path); return nbrs[0] == Shipment::ZERO \|\| nbrs[1] == Shipment::ZERO; }), path.end()); } while (before != path.size()); // place the remaining elements in the correct plus-minus order vector<Shipment> stones(path.size()); fill(stones.begin(), stones.end(), Shipment::ZERO); auto prev = s; for (size_t i = 0; i < stones.size(); i++) { stones[i] = prev; prev = getNeighbors(prev, path)[i % 2]; } return stones; } void fixDegenerateCase() { double eps = DBL_MIN; if (supply.size() + demand.size() - 1 != matrixToVector().size()) { for (size_t r = 0; r < supply.size(); r++) { for (size_t c = 0; c < demand.size(); c++) { if (matrix[r][c] == Shipment::ZERO) { Shipment dummy(eps, costs[r][c], r, c); if (getClosedPath(dummy).empty()) { matrix[r][c] = dummy; return; } } } } } } void steppingStone() { double maxReduction = 0; vector<Shipment> move; Shipment leaving; bool isNull = true; fixDegenerateCase(); for (size_t r = 0; r < supply.size(); r++) { for (size_t c = 0; c < demand.size(); c++) { if (matrix[r][c] != Shipment::ZERO) { continue; } Shipment trial(0, costs[r][c], r, c); vector<Shipment> path = getClosedPath(trial); double reduction = 0; double lowestQuantity = INT32_MAX; Shipment leavingCandidate; bool plus = true; for (auto &s : path) { if (plus) { reduction += s.costPerUnit; } else { reduction -= s.costPerUnit; if (s.quantity < lowestQuantity) { leavingCandidate = s; lowestQuantity = s.quantity; } } plus = !plus; } if (reduction < maxReduction) { isNull = false; move = path; leaving = leavingCandidate; maxReduction = reduction; } } } if (!isNull) { double q = leaving.quantity; bool plus = true; for (auto &s : move) { s.quantity += plus ? q : -q; matrix[s.r][s.c] = s.quantity == 0 ? Shipment::ZERO : s; plus = !plus; } steppingStone(); } } void printResult(string filename) { ifstream ifs; string buffer; ifs.open(filename); if (!ifs) { cerr << "File not found: " << filename << '\n'; return; } cout << filename << "\n\n"; while (!ifs.eof()) { getline(ifs, buffer); cout << buffer << '\n'; } cout << '\n'; cout << "Optimal solution " << filename << "\n\n"; double totalCosts = 0.0; for (size_t r = 0; r < supply.size(); r++) { for (size_t c = 0; c < demand.size(); c++) { auto s = matrix[r][c]; if (s != Shipment::ZERO && s.r == r && s.c == c) { cout << ' ' << setw(3) << s.quantity << ' '; totalCosts += s.quantity * s.costPerUnit; } else { cout << " - "; } } cout << '\n'; } cout << "\nTotal costs: " << totalCosts << "\n\n"; } void process(string filename) { init(filename); northWestCornerRule(); steppingStone(); printResult(filename); } int main() { process("input1.txt"); process("input2.txt"); process("input3.txt"); return 0; }</syntaxhighlight> {{out}} <pre>input1.txt 2 3 25 35 20 30 10 3 5 7 3 2 5 Optimal solution input1.txt 20 - 5 - 30 5 Total costs: 180 input2.txt 3 3 12 40 33 20 30 10 3 5 7 2 4 6 9 1 8 Optimal solution input2.txt - - - 12 20 - 10 10 - 30 - 3 Total costs: 130 input3.txt 4 4 14 10 15 12 10 15 12 15 10 30 25 15 20 15 20 10 10 30 20 20 30 40 35 45 Optimal solution input3.txt - - - 14 - 9 - 1 10 - 5 - - 5 7 - - 1 - - Total costs: 1000</pre> =={{header\|D}}== {{trans\|Java}} <~~lang~~syntaxhighlight lang="d">import std.stdio, std.range, std.algorithm, std.conv, std.math, std.traits; final class Shipment { Line 691 ⟶ 1,328: printResult(fileName, demand, supply, costs, matrix); } }</~~lang~~syntaxhighlight> {{out}} <pre>Optimal solution transportation_problem1.txt Line 716 ⟶ 1,353: =={{header\|Glagol}}== <syntaxhighlight lang="text">ОТДЕЛ Транспорт+; ИСПОЛЬЗУЕТ Вывод ИЗ "...\Отделы\Обмен\", Line 1,165 ⟶ 1,802: ВывестиПлан КОН Транспорт.</~~lang~~syntaxhighlight> === Input === Line 1,189 ⟶ 1,826: =={{header\|Go}}== {{trans\|Java}} <~~lang~~syntaxhighlight lang="go">package main import ( Line 1,470 ⟶ 2,107: t.printResult() } }</~~lang~~syntaxhighlight> {{out}} Line 1,543 ⟶ 2,180: In other words: <~~lang~~syntaxhighlight Jlang="j">NB. C's y[m] v= x implemented as x m ndxasgn v y ndxasgn=: conjunction define : Line 1,563 ⟶ 2,200: r=. n (<ndxs)} r end. )</~~lang~~syntaxhighlight> Task data: <~~lang~~syntaxhighlight Jlang="j">need=: 20 30 10 supply=: 25 35 cost=:3 5 7,:3 2 5</~~lang~~syntaxhighlight> Task example: <~~lang~~syntaxhighlight Jlang="j"> need cost trans supply 20 0 5 0 30 5</~~lang~~syntaxhighlight> =={{header\|Java}}== {{works with\|Java\|8}} <~~lang~~syntaxhighlight lang="java">import java.io.File; import java.util.; import static java.util.Arrays.stream; Line 1,802 ⟶ 2,439: } } }</~~lang~~syntaxhighlight> <pre>input1.txt Line 1,859 ⟶ 2,496: =={{header\|Julia}}== ~~Using~~Code taken from [https://github.com/~~JuliaOpt~~dylanomics/~~MathProgBase.jl~~transportation_problem ~~MathProgBase~~here] using [https://jump.dev/JuMP.jl/stable/ JuMP]. <~~lang~~syntaxhighlight lang="julia">using ~~MathProgBase~~JuMP, ~~Clp~~GLPK # cost vector ~~c = [3, 5, 7, 3, 2, 5]~~ c = [3, 5, 7, 3, 2, 5]; N = size(c,1); # constraints Ax (<,>,=) b A = [1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1]; b = [ 25, 35, 20, 30, 10]; s = ['<', '<', '=', '=', '=']; # construct model ~~b = [ 25, 35, 20, 30, 10]~~ model = Model(GLPK.Optimizer) ~~s = ['<', '<', '=', '=', '=']~~ @variable(model, x[i=1:N] >= 0, base_name="traded quantities") cost_fn = @expression(model, c'x) # cost function @constraint(model, C1, A[1:2,:]x .<= b[1:2]) # inequality constraints @constraint(model, C2, A[3:5,:]x .== b[3:5]) # equality constraints @objective(model, Min, cost_fn) # objective function # solve model ~~sol = linprog(c, A, b, s, ClpSolver())~~ status = JuMP.optimize!(model); ~~@show sol.status~~ xstar = value.(x); ~~@show sol.sol~~ println("solution vector of quantities = ", xstar) ~~@show sol.objval</lang>~~ println("minimum total cost = ", JuMP.objective_value(model)) # recover Lagrange multipliers for post-optimality λ = [JuMP.dual(C1[1]),JuMP.dual(C1[2])] μ = [JuMP.dual(C2[1]),JuMP.dual(C2[2]),JuMP.dual(C2[3])] </syntaxhighlight> {{out}} <pre>solution vector of quantities = [20.0, 0.0, 5.0, 0.0, 30.0, 5.0] ~~<pre>sol.status = :Optimal~~ minimum total cost = 180.0</pre> ~~sol.sol = [20.0, 0.0, 5.0, 0.0, 30.0, 5.0]~~ ~~sol.objval = 180.0</pre>~~ =={{header\|Kotlin}}== {{trans\|Java}} <~~lang~~syntaxhighlight lang="scala">// version 1.1.51 import java.io.File Line 2,089 ⟶ 2,741: } } }</~~lang~~syntaxhighlight> {{out}} Line 2,095 ⟶ 2,747: Same as Java entry </pre> =={{header\|Nim}}== {{trans\|Go}} <syntaxhighlight lang="nim">import fenv, lists, math, sequtils, strformat, strutils type Shipment = object quantity: float costPerUnit: float r, c: int Transport = object filename: string supply: seq[int] demand: seq[int] costs: seq[seq[float]] matrix: seq[seq[Shipment]] ShipmentList = DoublyLinkedList[Shipment] const ShipZero = Shipment() template emitError(msg: string) = raise newException(ValueError, msg) proc initTransport(filename: string): Transport = let infile = filename.open() let fields = infile.readLine().splitWhitespace().map(parseInt) let numSources = fields[0] let numDests = fields[1] if numSources < 1 or numDests < 1: emitError "wrong number of sources or destinations." var src = infile.readLine().splitWhitespace().map(parseInt) if src.len != numSources: emitError "wrong number of sources; got $1, expected $2.".format(src.len, numSources) var dst = infile.readLine().splitWhitespace().map(parseInt) if dst.len != numDests: emitError "wrong number of destinations; got $1, expected $2.".format(dst.len, numDests) # Fix imbalance. let totalSrc = sum(src) let totalDst = sum(dst) let diff = totalSrc - totalDst if diff > 0: dst.add diff elif diff < 0: src.add -diff var costs = newSeqWith(src.len, newSeq[float](dst.len)) var matrix = newSeqWith(src.len, newSeq[Shipment](dst.len)) for i in 0..<numSources: let fields = infile.readLine().splitWhitespace().map(parseFloat) if fields.len > dst.len: emitError "wrong number of costs; got $1, expected $2.".format(fields.len, numDests) for j in 0..<numDests: costs[i][j] = fields[j] result = Transport(filename: filename, supply: move(src), demand: move(dst), costs: move(costs), matrix: move(matrix)) func northWestCornerRule(tr: var Transport) = var northWest = 0 for r in 0..tr.supply.high: for c in northWest..tr.demand.high: let quantity = min(tr.supply[r], tr.demand[c]) if quantity > 0: tr.matrix[r][c] = Shipment(quantity: quantity.toFloat, costPerUnit: tr.costs[r][c], r: r, c: c) dec tr.supply[r], quantity dec tr.demand[c], quantity if tr.supply[r] == 0: northWest = c break func getNeighbors(tr: Transport; s: Shipment; list: ShipmentList): array[2, Shipment] = for o in list: if o != s: if o.r == s.r and result[0] == ShipZero: result[0] = o elif o.c == s.c and result[1] == ShipZero: result[1] = o if result[0] != ShipZero and result[1] != ShipZero: break func matrixToList(tr: Transport): ShipmentList = for m in tr.matrix: for s in m: if s != ShipZero: result.append(s) func getClosedPath(tr: Transport; s: Shipment): seq[Shipment] = var path = tr.matrixToList path.prepend(s) # Remove (and keep removing) elements that do not have a # vertical and horizontal neighbor. while true: var removals = 0 for e in path.nodes: let nbrs = tr.getNeighbors(e.value, path) if nbrs[0] == ShipZero or nbrs[1] == ShipZero: path.remove(e) inc removals if removals == 0: break # Place the remaining elements in the correct plus-minus order. var prev = s var i = 0 for _ in path: result.add prev prev = tr.getNeighbors(prev, path)[i] i = 1 - i func fixDegenerateCase(tr: var Transport) = const Eps = minimumPositiveValue(float) if tr.supply.len + tr.demand.len - 1 != tr.matrix.len * tr.matrix[0].len: for r in 0..tr.supply.high: for c in 0..tr.demand.high: if tr.matrix[r][c] == ShipZero: let dummy = Shipment(quantity: Eps, costPerUnit: tr.costs[r][c], r: r, c: c) if tr.getClosedPath(dummy).len == 0: tr.matrix[r][c] = dummy return func steppingStone(tr: var Transport) = var maxReduction = 0.0 var move: seq[Shipment] var leaving = ShipZero tr.fixDegenerateCase() for r in 0..tr.supply.high: for c in 0..tr.demand.high: if tr.matrix[r][c] != ShipZero: continue let trial = Shipment(quantity: 0, costPerUnit: tr.costs[r][c], r: r, c: c) var path = tr.getClosedPath(trial) var reduction = 0.0 var lowestQuantity = float(int32.high) var leavingCandidate = ShipZero var plus = true for s in path: if plus: reduction += s.costPerUnit else: reduction -= s.costPerUnit if s.quantity < lowestQuantity: leavingCandidate = s lowestQuantity = s.quantity plus = not plus if reduction < maxReduction: move = move(path) leaving = leavingCandidate maxReduction = reduction if move.len != 0: let q = leaving.quantity var plus = true for s in move.mitems: if plus: s.quantity += q else: s.quantity -= q tr.matrix[s.r][s.c] = if s.quantity == 0: ShipZero else: s plus = not plus tr.steppingStone() proc printResult(tr: Transport) = echo tr.filename, '\n' stdout.write tr.filename.readFile() echo "\nOptimal solution for ", tr.filename, '\n' var totalCosts = 0.0 for r in 0..tr.supply.high: for c in 0..tr.demand.high: let s = tr.matrix[r][c] if s != ShipZero and s.r == r and s.c == c: stdout.write &" {int(s.quantity):3} " totalCosts += s.quantity * s.costPerUnit else: stdout.write " - " echo() echo &"\nTotal costs: {totalCosts:g}\n" when isMainModule: const Filenames = ["input1.txt", "input2.txt", "input3.txt"] for filename in Filenames: var tr = initTransport(filename) tr.northWestCornerRule() tr.steppingStone() tr.printResult()</syntaxhighlight> {{out}} <pre>input1.txt 2 3 25 35 20 30 10 3 5 7 3 2 5 Optimal solution for input1.txt 20 - 5 - 30 5 Total costs: 180 input2.txt 3 3 12 40 33 20 30 10 3 5 7 2 4 6 9 1 8 Optimal solution for input2.txt - - - 12 20 - 10 10 - 30 - 3 Total costs: 130 input3.txt 4 4 14 10 15 12 10 15 12 15 10 30 25 15 20 15 20 10 10 30 20 20 30 40 35 45 Optimal solution for input3.txt - - - 14 - 9 - 1 10 - 5 - - 5 7 - - 1 - - Total costs: 1000</pre> =={{header\|Pascal}}== <~~lang~~syntaxhighlight lang="pascal">Program transport; { based on the program of <Svetlana Belashova> } Line 2,579 ⟶ 3,482: GotoXY(40,1); l1: d:=ReadKey; END.</~~lang~~syntaxhighlight> =={{header\|Perl 6}}== Just re-using the code from [[Vogel's_approximation_method#Perl\|Vogel's approximation method]], tweaked to handle specific input: ~~{{works with\|Rakudo\|2018.09}}~~ <syntaxhighlight lang="perl">use strict; ~~Using [[Vogel's_approximation_method#Perl6\|Vogel's approximation method]]:~~ use warnings; ~~<lang perl6>my %costs = :S1{:3C1, :5C2, :7C3}, :S2{:3C1, :2C2, :5C3};~~ use feature 'say'; ~~my %demand = :20C1, :30C2, :10C3;~~ use List::AllUtils qw( max_by nsort_by min ); ~~my %supply = :25S1, :35S2;~~ my ~~@cols~~$data = ~~%demand.keys.sort~~<<END; A=20 B=30 C=10 S=25 T=35 AS=3 BS=5 CS=7 CT=3 BT=2 CT=5 END my $table = sprintf +('%4s' x 4 . "\n") x 3, ~~my %res;~~ map {my $t = $_; map "$_$t", '', 'A' .. 'C' } '' , 'S' .. 'T'; ~~my %g = (\|%supply.keys.map: -> $x { $x => [%costs{$x}.sort(.value)».key]}),~~ ~~(\|%demand.keys.map: -> $x { $x => [%costs.keys.sort({%costs{$_}{$x}})]});~~ my ($cost, %assign) = (0); ~~while (+%g) {~~ while( $data =~ /\b\w=\d/ ) { ~~my @d = %demand.keys.map: -> $x~~ my @penalty; ~~{[$x, my $z = %costs{%g{$x}[0]}{$x},%g{$x}[1] ?? %costs{%g{$x}[1]}{$x} - $z !! $z]}~~ for ( $data =~ /\b(\w)=\d/g ) { my @all = map /(\d+)/, nsort_by { /\d+/ && $& } grep { my ($t, $c) = /(.)(.)=/; $data =~ /\b$c=\d/ and $data =~ /\b$t=\d/ } $data =~ /$_\w=\d+\|\w$_=\d+/g; push @penalty, [ $_, ($all[1] // 0) - $all[0] ]; } my $rc = (max_by { $_->[1] } nsort_by { my $x = $_->[0]; $data =~ /(?:$x\w\|\w$x)=(\d+)/ && $1 } @penalty)->[0]; my @lowest = nsort_by { /\d+/ && $& } grep { my ($t, $c) = /(.)(.)=/; $data =~ /\b$c=\d/ and $data =~ /\b$t=\d/ } $data =~ /$rc\w=\d+\|\w$rc=\d+/g; my ($t, $c) = $lowest[0] =~ /(.)(.)/; my $allocate = min $data =~ /\b[$t$c]=(\d+)/g; $table =~ s/$t$c/ sprintf "%2d", $allocate/e; $cost += $data =~ /$t$c=(\d+)/ && $1 $allocate; $data =~ s/\b$_=\K\d+/ $& - $allocate \|\| '' /e for $t, $c; } say my $result = "cost $cost\n\n" . $table =~ s/[A-Z]{2}/--/gr;</syntaxhighlight> ~~my @s = %supply.keys.map: -> $x~~ {{out}} ~~{[$x, my $z = %costs{$x}{%g{$x}[0]},%g{$x}[1] ?? %costs{$x}{%g{$x}[1]} - $z !! $z]}~~ <pre>cost 170 A B C ~~@d = \|@d.grep({ (.[2] == [max] @d».[2]) }).&min: :by(.[1]);~~ S 20 -- 5 ~~@s = \|@s.grep({ (.[2] == [max] @s».[2]) }).&min: :by(.[1]);~~ T -- 30 5</pre> =={{header\|Phix}}== ~~my ($t, $f) = @d[2] == @s[2] ?? (@s[1],@d[1]) !! (@d[2],@s[2]);~~ The simplest solution I could think of.<br> ~~my ($d, $s) = $t > $f ?? (@d[0],%g{@d[0]}[0]) !! (%g{@s[0]}[0], @s[0]);~~ 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 -- of length(needs/aka customers/) cols</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> <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> {{20,0,5}, {0,30,5}} </pre> ===stepping stones=== 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;">if</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] &= 0</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> <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.) <pre> test 3: src: {14,10,15,12}, dst: {10,15,12,15}, costs: {{10,30,25,15}, {20,15,20,10}, {10,30,20,20}, {30,40,35,45}} adding dummy supplier... ~~my $v = %supply{$s} min %demand{$d};~~ generating initial feasible solution using northwest corner method... 10 4 - - - 10 - - - 1 12 2 - - - 12 - - - 1 Total costs: 1220 ~~%res{$s}{$d} += $v;~~ ~~%demand{$d} -= $v;~~ fixing degenerate case... ~~if (%demand{$d} == 0) {~~ Optimal solution ~~%supply.grep( .value != 0 )».key.map: -> $v~~ ~~{ %g{$v}.splice((%g{$v}.first: * eq $d, :k),1) };~~ ~~%g{$d}:delete;~~ ~~%demand{$d}:delete;~~ } - ~~%supply{$s}~~ -= ~~$v;~~ - 14 - 9 - 1 10 - 5 - - 5 7 - - 1 - - Total costs: 1000 (expected 1000) ~~if (%supply{$s} == 0) {~~ </pre> ~~%demand.grep( .value != 0 )».key.map: -> $v~~ Note that [[Vogel%27s_approximation_method#Phix]] gets a few of the others wrong and loops on #2, then again that is unbalanced (needs a dummy customer), and I'm not sure whether throwing such at VAM is fair or not. ~~{ %g{$v}.splice((%g{$v}.first: eq $s, :k),1) };~~ ~~%g{$s}:delete;~~ ~~%supply{$s}:delete;~~ } } =={{header\|R}}== ~~say join "\t", flat '', @cols;~~ Using <code>lpSolve::lp.transport</code>. ~~my $total;~~ ~~for %costs.keys.sort -> $g {~~ ~~print "$g\t";~~ ~~for @cols -> $col {~~ ~~print %res{$g}{$col} // '-', "\t";~~ ~~$total += (%res{$g}{$col} // 0) * %costs{$g}{$col};~~ } ~~print "\n";~~ } ~~say "\nTotal cost: $total";</lang>~~ ~~{{out}}~~ ~~<pre> C1 C2 C3~~ ~~S1 20 - 5~~ ~~S2 - 30 5 </pre>~~ <syntaxhighlight lang="r">library(lpSolve) ~~=={{header\|Phix}}==~~ ~~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, costs)~~ ~~sequence res = repeat(repeat(0,length(needs)),length(avail))~~ ~~while true do~~ ~~integer best = 0, supplier, customer~~ ~~for s=1 to length(costs) do~~ ~~for c=1 to length(costs[s]) do~~ ~~integer csc = costs[s][c]~~ ~~if csc!=0 and (best=0 or csc<best) then~~ ~~best = csc~~ ~~supplier = s~~ ~~customer = c~~ ~~end if~~ ~~end for~~ ~~end for~~ ~~if best=0 then exit end if -- all costs examined~~ ~~integer amt = min(avail[supplier],needs[customer])~~ ~~-- obviously amt can be 0, in which case this just~~ ~~-- removes cost entry from further consideration.~~ ~~avail[supplier] -= amt~~ ~~needs[customer] -= amt~~ ~~res[supplier,customer] = amt~~ ~~costs[supplier,customer] = 0~~ ~~end while~~ ~~pp(res,{pp_Nest,1})~~ ~~end procedure~~ # cost matrix ~~constant needs = {20,30,10}, -- (customers)~~ costs <- matrix(c(3, 5, 7, ~~avail = {25,35}, -- (suppliers)~~ ~~costs~~ = ~~{{3,5,7},~~ -- ~~(length~~3, ~~suppliers~~2, ~~rows~~5), nrow = 2, byrow = ofTRUE) ~~{3,2,5}} -- length customers columns)~~ # constraints for suppliers ~~solve(needs,avail,costs)</lang>~~ row.signs <- rep("<=", 2) row.rhs <- c(25, 35) # constraints for customers col.signs <- rep("=", 3) col.rhs <- c(20, 30, 10) # minimum cost (objective value) lp.transport(costs, "min", row.signs, row.rhs, col.signs, col.rhs) # solution matrix sol = lp.transport(costs, "min", row.signs, row.rhs, col.signs, col.rhs)$solution rownames(sol) <- c("Supplier 1", "Supplier 2") colnames(sol) <- c("Customer 1", "Customer 2", "Customer 3") sol </syntaxhighlight> {{out}} <pre>Success: the objective function is 180 ~~<pre>~~ ~~{{20,0,5},~~ Customer 1 Customer 2 Customer 3 ~~{0,30,5}}~~ Supplier 1 20 0 5 Supplier 2 0 30 5 </pre> Line 2,691 ⟶ 3,902: Using <code>typed/racket</code>, to keep track of Vectors of Vectors of data. <~~lang~~syntaxhighlight lang="racket">#lang typed/racket ;; {{trans\|Java}} (define-type (V2 A) (Vectorof (Vectorof A))) Line 2,917 ⟶ 4,128: 30 40 35 45 $ 1000))</~~lang~~syntaxhighlight> {{out}} Output of: <code>raco test Transportation-problem.rkt</code>: Line 2,942 ⟶ 4,153: 3 tests passed </pre> =={{header\|Raku}}== (formerly Perl 6) {{works with\|Rakudo\|2019.03.1}} Using [[Vogel's_approximation_method#Raku\|Vogel's approximation method]]: <syntaxhighlight lang="raku" line>my %costs = :S1{:3C1, :5C2, :7C3}, :S2{:3C1, :2C2, :5C3}; my %demand = :20C1, :30C2, :10C3; my %supply = :25S1, :35S2; my @cols = %demand.keys.sort; my %res; my %g = (\|%supply.keys.map: -> $x { $x => [%costs{$x}.sort(.value)».key]}), (\|%demand.keys.map: -> $x { $x => [%costs.keys.sort({%costs{$_}{$x}})]}); while (+%g) { my @d = %demand.keys.map: -> $x {[$x, my $z = %costs{%g{$x}[0]}{$x},%g{$x}[1] ?? %costs{%g{$x}[1]}{$x} - $z !! $z]} my @s = %supply.keys.map: -> $x {[$x, my $z = %costs{$x}{%g{$x}[0]},%g{$x}[1] ?? %costs{$x}{%g{$x}[1]} - $z !! $z]} @d = \|@d.grep({ (.[2] == max @d».[2]) }).&min: :by(.[1]); @s = \|@s.grep({ (.[2] == max @s».[2]) }).&min: :by(.[1]); my ($t, $f) = @d[2] == @s[2] ?? (@s[1],@d[1]) !! (@d[2],@s[2]); my ($d, $s) = $t > $f ?? (@d[0],%g{@d[0]}[0]) !! (%g{@s[0]}[0], @s[0]); my $v = %supply{$s} min %demand{$d}; %res{$s}{$d} += $v; %demand{$d} -= $v; if (%demand{$d} == 0) { %supply.grep( .value != 0 )».key.map: -> $v { %g{$v}.splice((%g{$v}.first: * eq $d, :k),1) }; %g{$d}:delete; %demand{$d}:delete; } %supply{$s} -= $v; if (%supply{$s} == 0) { %demand.grep( .value != 0 )».key.map: -> $v { %g{$v}.splice((%g{$v}.first: eq $s, :k),1) }; %g{$s}:delete; %supply{$s}:delete; } } say join "\t", flat '', @cols; my $total; for %costs.keys.sort -> $g { print "$g\t"; for @cols -> $col { print %res{$g}{$col} // '-', "\t"; $total += (%res{$g}{$col} // 0) * %costs{$g}{$col}; } print "\n"; } say "\nTotal cost: $total";</syntaxhighlight> {{out}} <pre> C1 C2 C3 S1 20 - 5 S2 - 30 5 </pre> =={{header\|REXX}}== {{trans\|Java}} <syntaxhighlight lang="rexx">/* REXX *************************************************************** * Solve the Transportation Problem using the Northwest Corner Method Default Input 2 3 # of sources / # of demands 25 35 sources 20 30 10 demands 3 5 7 cost matrix 3 2 5 * 20201210 support no input file -courtesy GS * Note: correctnes of input is not checked * 20201226 add optimization * 20210103 remove debug code ********************************************************************/ Signal On Halt Signal On Novalue Signal On Syntax Parse Arg fid If fid='' Then fid='input1.txt' Call init matrix.=0 ms=0 Do r=1 To rr Do c=1 To cc matrix.r.c=r c cost.r.c 0 End End r=1 c=1 Do While r<=rr & c<=cc q=min(source.r,demand.c) matrix.r.c=r c cost.r.c q source.r=source.r-q demand.c=demand.c-q If source.r=0 Then r=r+1 If demand.c=0 Then c=c+1 End Call show_alloc 'after NWC application' Call steppingstone Exit /******************************************************************** * Subroutines for NWC Algorithm *********************************************************************/ init: If lines(fid)=0 Then Do Say 'Input file not specified or not found. Using default input instead.' fid='Default input' in.1=sourceline(4) Parse Var in.1 numSources . Do i=2 To numSources+3 in.i=sourceline(i+3) End End Else Do Do i=1 By 1 while lines(fid)>0 in.i=linein(fid) End End Parse Var in.1 numSources numDestinations . 1 rr cc . source_sum=0 Do i=1 To numSources Parse Var in.2 source.i in.2 ss.i=source.i source_in.i=source.i source_sum=source_sum+source.i End l=linein(fid) demand_sum=0 Do i=1 To numDestinations Parse Var in.3 demand.i in.3 dd.i=demand.i demand_in.i=demand.i demand_sum=demand_sum+demand.i End Do i=1 To numSources j=i+3 l=in.j Do j=1 To numDestinations Parse Var l cost.i.j l End End Do i=1 To numSources ol=format(source.i,3) Do j=1 To numDestinations ol=ol format(cost.i.j,4) End End ol=' ' Do j=1 To numDestinations ol=ol format(demand.j,4) End Select When source_sum=demand_sum Then Nop / balanced / When source_sum>demand_sum Then Do / unbalanced - add dummy demand / Say 'This is an unbalanced case (sources exceed demands). We add a dummy consumer.' cc=cc+1 demand.cc=source_sum-demand_sum demand_in.cc=demand.cc dd.cc=demand.cc Do r=1 To rr cost.r.cc=0 End End Otherwise / demand_sum>source_sum / Do / unbalanced - add dummy source / Say 'This is an unbalanced case (demands exceed sources). We add a dummy source.' rr=rr+1 source.rr=demand_sum-source_sum source_in.rr=source.rr ss.rr=source.rr Do c=1 To cc cost.rr.c=0 End End End Say 'Sources / Demands / Cost' ol=' ' Do c=1 To cc ol=ol format(demand.c,3) End Say ol Do r=1 To rr ol=format(source.r,4) Do c=1 To cc ol=ol format(cost.r.c,3) End Say ol End Return show_alloc: Procedure Expose matrix. rr cc demand_in. source_in. Parse Arg header If header='' Then Return Say '' Say header total=0 ol=' ' Do c=1 to cc ol=ol format(demand_in.c,3) End Do r=1 to rr ol=format(source_in.r,4) a=word(matrix.r.1,4) If a>0 Then ol=format(a,4) Else ol=' - ' total=total+word(matrix.r.1,4)word(matrix.r.1,3) Do c=2 To cc a=word(matrix.r.c,4) If a>0 Then ol=ol format(a,4) Else ol=ol ' - ' total=total+word(matrix.r.c,4)word(matrix.r.c,3) End Say ol End Say 'Total costs:' format(total,4,1) Return /********************************************************************* * Subroutines for Optimization *********************************************************************/ steppingstone: Procedure Expose matrix. cost. rr cc demand_in., source_in. fid maxReduction=0 move='' Call fixDegenerateCase Do r=1 To rr Do c=1 To cc Parse Var matrix.r.c r c cost qrc If qrc=0 Then Do path=getclosedpath(r,c) reduction = 0 lowestQuantity = 1e10 leavingCandidate = '' plus=1 pathx=path Do While pathx<>'' Parse Var pathx s '\|' pathx If plus Then reduction=reduction+word(s,3) Else Do reduction=reduction-word(s,3) If word(s,4)<lowestQuantity Then Do leavingCandidate = s lowestQuantity = word(s,4) End End plus=\plus End If reduction < maxreduction Then Do move=path leaving=leavingCandidate maxReduction = reduction End End End End if move <> '' Then Do quant=word(leaving,4) plus=1 Do While move<>'' Parse Var move m '\|' move Parse Var m r c cpu qrc Parse Var matrix.r.c vr vc vcost vquant If plus Then nquant=vquant+quant Else nquant=vquant-quant matrix.r.c = vr vc vcost nquant plus=\plus End move='' Call steppingStone End Else Do Call show_alloc 'Optimal Solution' fid End Return getclosedpath: Procedure Expose matrix. cost. rr cc Parse Arg rd,cd path=rd cd cost.rd.cd word(matrix.rd.cd,4) do r=1 To rr Do c=1 To cc If word(matrix.r.c,4)>0 Then Do path=path'\|'r c cost.r.c word(matrix.r.c,4) End End End path=magic(path) Return stones(path) magic: Procedure Parse Arg list Do Forever list_1=remove_1(list) If list_1=list Then Leave list=list_1 End Return list_1 remove_1: Procedure Parse Arg list cntr.=0 cntc.=0 Do i=1 By 1 While list<>'' parse Var list e.i '\|' list Parse Var e.i r c . cntr.r=cntr.r+1 cntc.c=cntc.c+1 End n=i-1 keep.=1 Do i=1 To n Parse Var e.i r c . If cntr.r<2 \|, cntc.c<2 Then Do keep.i=0 End End list=e.1 Do i=2 To n If keep.i Then list=list'\|'e.i End Return list stones: Procedure Parse Arg lst tstc=lst Do i=1 By 1 While tstc<>'' Parse Var tstc o.i '\|' tstc end stones=lst o.0=i-1 prev=o.1 Do i=1 To o.0 st.i=prev k=i//2 nbrs=getNeighbors(prev, lst) Parse Var nbrs n.1 '\|' n.2 If k=0 Then prev=n.2 Else prev=n.1 End stones=st.1 Do i=2 To o.0 stones=stones'\|'st.i End Return stones getNeighbors: Procedure parse Arg s, lst Do i=1 By 1 While lst<>'' Parse Var lst o.i '\|' lst End o.0=i-1 nbrs.='' sr=word(s,1) sc=word(s,2) Do i=1 To o.0 If o.i<>s Then Do or=word(o.i,1) oc=word(o.i,2) If or=sr & nbrs.0='' Then nbrs.0 = o.i else if oc=sc & nbrs.1='' Then nbrs.1 = o.i If nbrs.0<>'' & nbrs.1<>'' Then Leave End End return nbrs.0'\|'nbrs.1 pelems: Procedure Parse Arg p Do i=1 By 1 While p<>'' Parse Var p x '\|' p End Return i fixDegenerateCase: Procedure Expose matrix. rr cc ms Call matrixtolist If (rr+cc-1)<>ms Then Do Do r=1 To rr Do c=1 To cc If word(matrix.r.c,4)=0 Then Do matrix.r.c=subword(matrix.r.c,1,3) 1.e-10 Return End End End End Return matrixtolist: Procedure Expose matrix. rr cc ms ms=0 list='' Do r=1 To rr Do c=1 To cc If word(matrix.r.c,4)>0 Then Do list=list'\|'matrix.r.c ms=ms+1 End End End Return strip(list,,'\|') Novalue: Say 'Novalue raised in line' sigl Say sourceline(sigl) Say 'Variable' condition('D') Signal lookaround Syntax: Say 'Syntax raised in line' sigl Say sourceline(sigl) Say 'rc='rc '('errortext(rc)')' halt: lookaround: If fore() Then Do Say 'You can look around now.' Trace ?R Nop End Exit 12</syntaxhighlight> {{out}} <pre>F:\>rexx tpx2 input1.txt Sources / Demands / Cost 20 30 10 25 3 5 7 35 3 2 5 after NWC application 20 5 - - 25 10 Total costs: 185.0 Optimal Solution input1.txt 20 - 5 - 30 5 Total costs: 180.0 F:\>rexx tpx2 input2.txt This is an unbalanced case (sources exceed demands). We add a dummy consumer. Sources / Demands / Cost 20 30 10 25 12 3 5 7 0 40 2 4 6 0 33 9 1 8 0 after NWC application 12 - - - 8 30 2 - - - 8 25 Total costs: 248.0 Optimal Solution input2.txt - - - 12 20 - 10 10 - 30 - 3 Total costs: 130.0 F:\>rexx tpx2 input3.txt This is an unbalanced case (demands exceed sources). We add a dummy source. Sources / Demands / Cost 10 15 12 15 14 10 30 25 15 10 20 15 20 10 15 10 30 20 20 12 30 40 35 45 1 0 0 0 0 after NWC application 10 4 - - - 10 - - - 1 12 2 - - - 12 - - - 1 Total costs: 1220.0 Optimal Solution input3.txt - - - 14 - 9 - 1 10 - 5 - - 5 7 - - 1 - - Total costs: 1000.0</pre> =={{header\|SAS}}== Use network solver in SAS/OR: <~~lang~~syntaxhighlight lang="sas">/ create SAS data sets / data cost_data; input from $ to $ cost; Line 2,986 ⟶ 4,706: print _OROPTMODEL_NUM_['OBJECTIVE']; print flow; quit;</~~lang~~syntaxhighlight> Output: Line 2,996 ⟶ 4,716: s1 20 0 5 s2 0 30 5 </pre> =={{header\|Visual Basic .NET}}== {{trans\|C#}} <syntaxhighlight lang="vbnet">Module Module1 Class Shipment Public Sub New(q As Double, cpu As Double, rv As Integer, cv As Integer) Quantity = q CostPerUnit = cpu R = rv C = cv End Sub Public ReadOnly Property CostPerUnit() As Double Public Property Quantity() As Double Public ReadOnly Property R As Integer Public ReadOnly Property C As Integer Public Shared Operator =(s1 As Shipment, s2 As Shipment) As Boolean Return s1.CostPerUnit = s2.CostPerUnit _ AndAlso s1.Quantity = s2.Quantity _ AndAlso s1.R = s2.R _ AndAlso s1.C = s2.C End Operator Public Shared Operator <>(s1 As Shipment, s2 As Shipment) As Boolean Return s1.CostPerUnit <> s2.CostPerUnit _ OrElse s1.Quantity <> s2.Quantity _ OrElse s1.R <> s2.R _ OrElse s1.C <> s2.C End Operator End Class Class Program Private demand() As Integer Private supply() As Integer Private costs(,) As Double Private matrix(,) As Shipment Sub Init(filename As String) Dim file = My.Computer.FileSystem.OpenTextFileReader(filename) Dim line = file.ReadLine Dim numArr = line.Split Dim numSources = Integer.Parse(numArr(0)) Dim numDestinations = Integer.Parse(numArr(1)) Dim src As New List(Of Integer) Dim dst As New List(Of Integer) line = file.ReadLine numArr = line.Split For i = 1 To numSources src.Add(Integer.Parse(numArr(i - 1))) Next line = file.ReadLine numArr = line.Split For i = 1 To numDestinations dst.Add(Integer.Parse(numArr(i - 1))) Next REM fix imbalance Dim totalSrc = src.Sum Dim totalDst = dst.Sum If totalSrc > totalDst Then dst.Add(totalSrc - totalDst) ElseIf totalDst > totalSrc Then src.Add(totalDst - totalSrc) End If supply = src.ToArray demand = dst.ToArray ReDim costs(supply.Length - 1, demand.Length - 1) ReDim matrix(supply.Length - 1, demand.Length - 1) For i = 1 To numSources line = file.ReadLine numArr = line.Split For j = 1 To numDestinations costs(i - 1, j - 1) = Integer.Parse(numArr(j - 1)) Next Next End Sub Sub NorthWestCornerRule() Dim northwest = 1 For r = 1 To supply.Length For c = northwest To demand.Length Dim quantity = Math.Min(supply(r - 1), demand(c - 1)) If quantity > 0 Then matrix(r - 1, c - 1) = New Shipment(quantity, costs(r - 1, c - 1), r - 1, c - 1) supply(r - 1) -= quantity demand(c - 1) -= quantity If supply(r - 1) = 0 Then northwest = c Exit For End If End If Next Next End Sub Sub SteppingStone() Dim maxReduction = 0.0 Dim move() As Shipment = Nothing Dim leaving As Shipment = Nothing FixDegenerateCase() For r = 1 To supply.Length For c = 1 To demand.Length If Not IsNothing(matrix(r - 1, c - 1)) Then Continue For End If Dim trial As New Shipment(0, costs(r - 1, c - 1), r - 1, c - 1) Dim path = GetClosedPath(trial) Dim reduction = 0.0 Dim lowestQuanity = Integer.MaxValue Dim leavingCandidate As Shipment = Nothing Dim plus = True For Each s In path If plus Then reduction += s.CostPerUnit Else reduction -= s.CostPerUnit If s.Quantity < lowestQuanity Then leavingCandidate = s lowestQuanity = s.Quantity End If End If plus = Not plus Next If reduction < maxReduction Then move = path leaving = leavingCandidate maxReduction = reduction End If Next Next If Not IsNothing(move) Then Dim q = leaving.Quantity Dim plus = True For Each s In move s.Quantity += If(plus, q, -q) matrix(s.R, s.C) = If(s.Quantity = 0, Nothing, s) plus = Not plus Next SteppingStone() End If End Sub Sub FixDegenerateCase() Const eps = Double.Epsilon If supply.Length + demand.Length - 1 <> MatrixToList().Count Then For r = 1 To supply.Length For c = 1 To demand.Length If IsNothing(matrix(r - 1, c - 1)) Then Dim dummy As New Shipment(eps, costs(r - 1, c - 1), r - 1, c - 1) If GetClosedPath(dummy).Length = 0 Then matrix(r - 1, c - 1) = dummy Return End If End If Next Next End If End Sub Function MatrixToList() As List(Of Shipment) Dim newList As New List(Of Shipment) For Each item In matrix If Not IsNothing(item) Then newList.Add(item) End If Next Return newList End Function Function GetClosedPath(s As Shipment) As Shipment() Dim path = MatrixToList() path.Add(s) REM remove (and keep removing) elements that do not have a veritcal AND horizontal neighbor Dim before As Integer Do before = path.Count path.RemoveAll(Function(ship) Dim nbrs = GetNeighbors(ship, path) Return IsNothing(nbrs(0)) OrElse IsNothing(nbrs(1)) End Function) Loop While before <> path.Count REM place the remaining elements in the correct plus-minus order Dim stones = path.ToArray Dim prev = s For i = 1 To stones.Length stones(i - 1) = prev prev = GetNeighbors(prev, path)((i - 1) Mod 2) Next Return stones End Function Function GetNeighbors(s As Shipment, lst As List(Of Shipment)) As Shipment() Dim nbrs() As Shipment = {Nothing, Nothing} For Each o In lst If o <> s Then If o.R = s.R AndAlso IsNothing(nbrs(0)) Then nbrs(0) = o ElseIf o.C = s.C AndAlso IsNothing(nbrs(1)) Then nbrs(1) = o End If If Not IsNothing(nbrs(0)) AndAlso Not IsNothing(nbrs(1)) Then Exit For End If End If Next Return nbrs End Function Sub PrintResult(filename As String) Console.WriteLine("Optimal solution {0}" + vbNewLine, filename) Dim totalCosts = 0.0 For r = 1 To supply.Length For c = 1 To demand.Length Dim s = matrix(r - 1, c - 1) If Not IsNothing(s) AndAlso s.R = r - 1 AndAlso s.C = c - 1 Then Console.Write(" {0,3} ", s.Quantity) totalCosts += (s.Quantity s.CostPerUnit) Else Console.Write(" - ") End If Next Console.WriteLine() Next Console.WriteLine(vbNewLine + "Total costs: {0}" + vbNewLine, totalCosts) End Sub End Class Sub Main() For Each filename In {"input1.txt", "input2.txt", "input3.txt"} Dim p As New Program p.Init(filename) p.NorthWestCornerRule() p.SteppingStone() p.PrintResult(filename) Next End Sub End Module</syntaxhighlight> {{out}} <pre>Optimal solution input1.txt 20 - 5 - 30 5 Total costs: 180 Optimal solution input2.txt - - - 12 20 - 10 10 - 30 - 3 Total costs: 130 Optimal solution input3.txt - - - 14 - 9 - 1 10 - 5 - - 5 7 - - 1 - - Total costs: 1000</pre> =={{header\|Wren}}== {{trans\|Java}} {{libheader\|Wren-dynamic}} {{libheader\|Wren-ioutil}} {{libheader\|Wren-math}} {{libheader\|Wren-seq}} {{libheader\|Wren-fmt}} <syntaxhighlight lang="wren">import "./dynamic" for Struct 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"]) class Transport { construct new(filename) { var lines = FileUtil.readLines(filename) var split = lines[0].split(" ") var numSources = Num.fromString(split[0]) var numDests = Num.fromString(split[1]) var src = List.filled(numSources, 0) var dst = List.filled(numDests, 0) split = lines[1].split(" ") for (i in 0...numSources) src[i] = Num.fromString(split[i]) split = lines[2].split(" ") for (i in 0...numDests) dst[i] = Num.fromString(split[i]) // fix imbalance var totalSrc = Nums.sum(src) var totalDst = Nums.sum(dst) if (totalSrc > totalDst) { dst.add(totalSrc - totalDst) } else if (totalDst > totalSrc) { src.add(totalDst - totalSrc) } _supply = src _demand = dst _costs = List.filled(_supply.count, null) _matrix = List.filled(_supply.count, null) for (i in 0..._supply.count) { _costs[i] = List.filled(_demand.count, 0) _matrix[i] = List.filled(_demand.count, null) } for (i in 0...numSources) { split = lines[i + 3].split(" ") for (j in 0...numDests) _costs[i][j] = Num.fromString(split[j]) } _filename = filename } northWestCornerRule() { var northwest = 0 for (r in 0..._supply.count) { var c = northwest while (c < _demand.count) { var quantity = _supply[r].min(_demand[c]) if (quantity > 0) { _matrix[r][c] = Shipment.new(quantity, _costs[r][c], r, c) _supply[r] = _supply[r] - quantity.floor _demand[c] = _demand[c] - quantity.floor if (_supply[r] == 0) { northwest = c break } } c = c + 1 } } } steppingStone() { var maxReduction = 0 var move = null var leaving = null fixDegenerateCase_() for (r in 0..._supply.count) { for (c in 0..._demand.count) { if (_matrix[r][c] != null) continue var trial = Shipment.new(0, _costs[r][c], r, c) var path = getClosedPath_(trial) var reduction = 0 var lowestQuantity = Num.maxSafeInteger var leavingCandidate = null var plus = true for (s in path) { if (plus) { reduction = reduction + s.costPerUnit } else { reduction = reduction - s.costPerUnit if (s.quantity < lowestQuantity) { leavingCandidate = s lowestQuantity = s.quantity } } plus = !plus } if (reduction < maxReduction) { move = path leaving = leavingCandidate maxReduction = reduction } } } if (move) { var q = leaving.quantity var plus = true for (s in move) { s.quantity = s.quantity + ((plus) ? q : -q) _matrix[s.r][s.c] = (s.quantity == 0) ? null : s plus = !plus } steppingStone() } } matrixToList_() { Lst.flatten(_matrix).where { \|s\| s != null }.toList } getClosedPath_(s) { var path = matrixToList_() path.insert(0, s) // remove (and keep removing) elements that do not have a // vertical AND horizontal neighbor while (true) { var removals = 0 for (e in path) { var nbrs = getNeighbors_(e, path) if (nbrs[0] == null \|\| nbrs[1] == null) { path.remove(e) removals = removals + 1 } } if (removals == 0) break } // place the remaining elements in the correct plus-minus order var stones = List.filled(path.count, null) var prev = s for (i in 0...stones.count) { stones[i] = prev prev = getNeighbors_(prev, path)[i % 2] } return stones } getNeighbors_(s, lst) { var nbrs = List.filled(2, null) for (o in lst) { if (o != s) { if (o.r == s.r && nbrs[0] == null) { nbrs[0] = o } else if (o.c == s.c && nbrs[1] == null) { nbrs[1] = o } if (nbrs[0] != null && nbrs[1] != null) break } } return nbrs } fixDegenerateCase_() { var eps = Num.smallest if (_supply.count + _demand.count - 1 != matrixToList_().count) { for (r in 0..._supply.count) { for (c in 0..._demand.count) { if (_matrix[r][c] == null) { var dummy = Shipment.new(eps, _costs[r][c], r, c) if (getClosedPath_(dummy).count == 0) { _matrix[r][c] = dummy return } } } } } } printResult() { var text = File.read(_filename) System.print("%(_filename)\n\n%(text)") System.print("Optimal solution %(_filename)\n") var totalCosts = 0 for (r in 0..._supply.count) { for (c in 0..._demand.count) { var s = _matrix[r][c] if (s != null && s.r == r && s.c == c) { Fmt.write(" $3d ", s.quantity.floor) totalCosts = totalCosts + s.quantity * s.costPerUnit } else System.write(" - ") } System.print() } System.print("\nTotal costs: %(totalCosts)\n") } } var filenames = ["input1.txt", "input2.txt", "input3.txt"] for (filename in filenames) { var t = Transport.new(filename) t.northWestCornerRule() t.steppingStone() t.printResult() }</syntaxhighlight> {{out}} <pre> input1.txt 2 3 25 35 20 30 10 3 5 7 3 2 5 Optimal solution input1.txt 20 - 5 - 30 5 Total costs: 180 input2.txt 3 3 12 40 33 20 30 10 3 5 7 2 4 6 9 1 8 Optimal solution input2.txt - - - 12 20 - 10 10 - 30 - 3 Total costs: 130 input3.txt 4 4 14 10 15 12 10 15 12 15 10 30 25 15 20 15 20 10 10 30 20 20 30 40 35 45 Optimal solution input3.txt - - - 14 - 9 - 1 10 - 5 - - 5 7 - - 1 - - Total costs: 1000 </pre>