Rosetta Code

Vogel's approximation method: Difference between revisions

Page Discussion

Vogel's approximation method (view source)

Revision as of 20:25, 28 August 2022

990 bytes added ,  1 year ago
m
syntax highlighting fixup automation
m (→‎{{header|Phix}}: syntax coloured)
m (syntax highlighting fixup automation)
Line 77:
{{trans|Python}}
 
<langsyntaxhighlight lang="11l">V costs = [‘W’ = [‘A’ = 16, ‘B’ = 16, ‘C’ = 13, ‘D’ = 22, ‘E’ = 17],
‘X’ = [‘A’ = 14, ‘B’ = 14, ‘C’ = 13, ‘D’ = 19, ‘E’ = 15],
‘Y’ = [‘A’ = 19, ‘B’ = 19, ‘C’ = 20, ‘D’ = 23, ‘E’ = 50],
Line 131:
print("\t", end' ‘ ’)
print()
print("\n\nTotal Cost = "cost)</langsyntaxhighlight>
 
{{out}}
Line 147:
=={{header|C}}==
{{trans|Kotlin}}
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <limits.h>
 
Line 254:
printf("\nTotal cost = %d\n", total_cost);
return 0;
}</langsyntaxhighlight>
 
{{output}}
Line 268:
 
If the program is changed to this (to accomodate the second Ruby example):
<langsyntaxhighlight lang="go">#include <stdio.h>
#include <limits.h>
Line 302:
printf("\nTotal cost = %d\n", total_cost);
return 0;
}</langsyntaxhighlight>
 
then the output, which agrees with the Phix output but not with the Ruby output itself is:
Line 318:
=={{header|C++}}==
{{trans|Java}}
<langsyntaxhighlight lang="cpp">#include <iostream>
#include <numeric>
#include <vector>
Line 448:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>[0, 0, 50, 0, 0]
Line 459:
Strongly typed version (but K is not divided in Task and Contractor types to keep code simpler).
{{trans|Python}}
<langsyntaxhighlight lang="d">void main() {
import std.stdio, std.string, std.algorithm, std.range;
 
Line 538:
}
writeln("\nTotal Cost = ", cost);
}</langsyntaxhighlight>
{{out}}
<pre>
Line 552:
=={{header|Go}}==
{{trans|Kotlin}}
<langsyntaxhighlight lang="go">package main
 
import (
Line 690:
}
fmt.Println("\nTotal cost =", totalCost)
}</langsyntaxhighlight>
 
{{out}}
Line 704:
 
If the program is changed as follows to accomodate the second Ruby example:
<langsyntaxhighlight lang="go">package main
 
import (
Line 749:
}
fmt.Println("\nTotal cost =", totalCost)
}</langsyntaxhighlight>
 
then the output, which agrees with the C and Phix output but not with the Ruby output itself, is:
Line 767:
Implementation:
 
<langsyntaxhighlight Jlang="j">vam=:1 :0
:
exceeding=. 0 <. -&(+/)
Line 794:
end.
_1 _1 }. R
)</langsyntaxhighlight>
 
Note that for our penalty we are using the difference between the two smallest relevant costs multiplied by 1 larger than the highest represented cost and we subtract from that multiple the smallest relevant cost. This gives us the tiebreaker mechanism currently specified for this task.
Line 800:
Task example:
 
<langsyntaxhighlight Jlang="j">demand=: 30 20 70 30 60
src=: 50 60 50 50
cost=: 16 16 13 22 17,14 14 13 19 15,19 19 20 23 50,:50 12 50 15 11
Line 808:
30 0 20 0 10
0 20 0 30 0
0 0 0 0 50</langsyntaxhighlight>
 
=={{header|Java}}==
{{works with|Java|8}}
<langsyntaxhighlight lang="java">import java.util.Arrays;
import static java.util.Arrays.stream;
import java.util.concurrent.*;
Line 908:
return isRow ? new int[]{pm, pc, mc, md} : new int[]{pc, pm, mc, md};
}
}</langsyntaxhighlight>
 
<pre>[0, 0, 50, 0, 0]
Line 926:
 
<code>Resource</code> stores the currently available quantity of a given supply or demand as well as its penalty, cost, and some meta-data. <code>isavailable</code> indicates whether any of the given resource remains. <code>isless</code> is designed to make the currently most usable resource appear as a maximum compared to other resources.
<syntaxhighlight lang="julia">
<lang Julia>
immutable TProblem{T<:Integer,U<:String}
sd::Array{Array{T,1},1}
Line 975:
isavailable(r::Resource) = 0 < r.quant
Base.isless(a::Resource, b::Resource) = a.p < b.p || (a.p == b.p && b.q < a.q)
</syntaxhighlight>
</lang>
 
'''Functions'''
Line 982:
 
<code>vogel</code> implements Vogel's approximation method on a <code>TProblem</code>. It is somewhat straightforward, given the types and <code>penalize!</code>.
<syntaxhighlight lang="julia">
<lang Julia>
function penalize!{T<:Integer,U<:String}(sd::Array{Array{Resource{T},1},1},
tp::TProblem{T,U})
Line 1,030:
return sol
end
</syntaxhighlight>
</lang>
 
'''Main'''
<langsyntaxhighlight Julialang="julia">using Printf
 
sup = [50, 60, 50, 50]
Line 1,062:
end
println("The total cost is: ", cost)
</syntaxhighlight>
</lang>
 
{{out}}
Line 1,077:
=={{header|Kotlin}}==
{{trans|Java}}
<langsyntaxhighlight lang="scala">// version 1.1.3
 
val supply = intArrayOf(50, 60, 50, 50)
Line 1,166:
}
println("\nTotal Cost = $totalCost")
}</langsyntaxhighlight>
 
{{out}}
Line 1,181:
=={{header|Lua}}==
{{trans|Kotlin}}
<langsyntaxhighlight lang="lua">function initArray(n,v)
local tbl = {}
for i=1,n do
Line 1,328:
end
 
main()</langsyntaxhighlight>
{{out}}
<pre> A B C D E
Line 1,339:
=={{header|Nim}}==
{{trans|Kotlin}}
<langsyntaxhighlight Nimlang="nim">import math, sequtils, strutils
 
var
Line 1,423:
stdout.write " ", ($item).align(2)
echo()
echo "\nTotal cost = ", totalCost</langsyntaxhighlight>
 
{{out}}
Line 1,435:
 
=={{header|Perl}}==
<langsyntaxhighlight lang="perl">#!/usr/bin/perl
 
use strict; # https://rosettacode.org/wiki/Vogel%27s_approximation_method
Line 1,474:
$data =~ s/\b$_=\K\d+/ $& - $allocate || '' /e for $t, $c;
}
print "cost $cost\n\n", $table =~ s/[A-Z]{2}/--/gr;</langsyntaxhighlight>
{{out}}
<pre>
Line 1,490:
{{trans|YaBasic}}
{{trans|Go}}
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">supply</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>
Line 1,560:
<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 cost = %d\n"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">total_cost</span><span style="color: #0000FF;">)</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 1,572:
</pre>
Using the sample from Ruby:
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #004080;">sequence</span> <span style="color: #000000;">supply</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">461</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">277</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">356</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">488</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">393</span><span style="color: #0000FF;">},</span>
<span style="color: #000000;">demand</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">278</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">60</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">461</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">116</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1060</span><span style="color: #0000FF;">},</span>
Line 1,580:
<span style="color: #0000FF;">{</span><span style="color: #000000;">61</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">81</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">44</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">88</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">85</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">60</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">14</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">25</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">79</span><span style="color: #0000FF;">}}</span>
<!--</langsyntaxhighlight>-->
{{Out}}
Note this agrees with C and Go but not Ruby
Line 1,596:
=={{header|Python}}==
{{trans|Ruby}}
<langsyntaxhighlight lang="python">from collections import defaultdict
 
costs = {'W': {'A': 16, 'B': 16, 'C': 13, 'D': 22, 'E': 17},
Line 1,652:
print "\t",
print
print "\n\nTotal Cost = ", cost</langsyntaxhighlight>
{{out}}
<pre> A B C D E
Line 1,670:
somehow at the same total cost!
 
<langsyntaxhighlight lang="racket">#lang racket
(define-values (1st 2nd 3rd) (values first second third))
 
Line 1,772:
(DEMAND (hash 'A 30 'B 20 'C 70 'D 30 'E 60))
(SUPPLY (hash 'W 50 'X 60 'Y 50 'Z 50)))
(displayln (describe-VAM-solution COSTS DEMAND (VAM COSTS SUPPLY DEMAND))))</langsyntaxhighlight>
 
{{out}}
Line 1,789:
{{trans|Sidef}}
 
<syntaxhighlight lang="raku" perl6line>my %costs =
:W{:16A, :16B, :13C, :22D, :17E},
:X{:14A, :14B, :13C, :19D, :15E},
Line 1,849:
print "\n";
}
say "\nTotal cost: $total";</langsyntaxhighlight>
{{out}}
<pre> A B C D E
Line 1,862:
{{trans|java}}
===Vogel's Approximation===
<langsyntaxhighlight lang="rexx">/* REXX ***************************************************************
* Solve the Transportation Problem using Vogel's Approximation
Default Input
Line 2,365:
Nop
End
Exit 12</langsyntaxhighlight>
{{out}}
<pre>F:\>regina tpv vv.txt
Line 2,392:
 
===Low Cost Algorithm===
<langsyntaxhighlight lang="rexx">/* REXX ***************************************************************
* Solve the Transportation Problem using the Least Cost Method
Default Input
Line 2,795:
End
Exit 12
</syntaxhighlight>
</lang>
{{out}}
<pre>F:\>rexx tpl vv.txt
Line 2,824:
Breaks ties using lowest cost cell.
===Task Example===
<langsyntaxhighlight lang="ruby"># VAM
#
# Nigel_Galloway
Line 2,877:
puts
end
print "\n\nTotal Cost = ", cost</langsyntaxhighlight>
{{out}}
<pre>
Line 2,892:
===Reference Example===
Replacing the data in the Task Example with:
<langsyntaxhighlight lang="ruby">COSTS = {S1: {D1: 46, D2: 74, D3: 9, D4: 28, D5: 99},
S2: {D1: 12, D2: 75, D3: 6, D4: 36, D5: 48},
S3: {D1: 35, D2: 199, D3: 4, D4: 5, D5: 71},
Line 2,898:
S5: {D1: 85, D2: 60, D3: 14, D4: 25, D5: 79}}
demand = {D1: 278, D2: 60, D3: 461, D4: 116, D5: 1060}
supply = {S1: 461, S2: 277, S3: 356, S4: 488, S5: 393}</langsyntaxhighlight>
Produces:
<pre>
Line 2,914:
=={{header|Sidef}}==
{{trans|Ruby}}
<langsyntaxhighlight lang="ruby">var costs = :(
W => :(A => 16, B => 16, C => 13, D => 22, E => 17),
X => :(A => 14, B => 14, C => 13, D => 19, E => 15),
Line 2,980:
}
 
say "\n\nTotal Cost = #{cost}"</langsyntaxhighlight>
{{out}}
<pre>
Line 2,995:
=={{header|Tcl}}==
{{works with|Tcl|8.6}}
<langsyntaxhighlight lang="tcl">package require Tcl 8.6
 
# A sort that works by sorting by an auxiliary key computed by a lambda term
Line 3,098:
}
return $res
}</langsyntaxhighlight>
Demonstration:
<langsyntaxhighlight lang="tcl">set COSTS {
W {A 16 B 16 C 13 D 22 E 17}
X {A 14 B 14 C 13 D 19 E 15}
Line 3,120:
}] \t]
}
puts "\nTotal Cost = $cost"</langsyntaxhighlight>
{{out}}
<pre>
Line 3,136:
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<langsyntaxhighlight lang="ecmascript">import "/math" for Int, Nums
import "/fmt" for Fmt
 
Line 3,226:
i = i + 1
}
System.print("\nTotal Cost = %(totalCost)")</langsyntaxhighlight>
 
{{out}}
Line 3,241:
=={{header|Yabasic}}==
{{trans|C}}
<syntaxhighlight lang="yabasic">
<lang Yabasic>
N_ROWS = 4 : N_COLS = 5
Line 3,389:
print
next i
print "\nTotal cost = ", total_cost</langsyntaxhighlight>
 
=={{header|zkl}}==
{{trans|Python}}{{trans|Ruby}}
<langsyntaxhighlight lang="zkl">costs:=Dictionary(
"W",Dictionary("A",16, "B",16, "C",13, "D",22, "E",17),
"X",Dictionary("A",14, "B",14, "C",13, "D",19, "E",15),
Line 3,399:
"Z",Dictionary("A",50, "B",12, "C",50, "D",15, "E",11)).makeReadOnly();
demand:=Dictionary("A",30, "B",20, "C",70, "D",30, "E",60); // gonna be modified
supply:=Dictionary("W",50, "X",60, "Y",50, "Z",50); // gonna be modified</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">cols:=demand.keys.sort();
res :=vogel(costs,supply,demand);
cost:=0;
Line 3,413:
println();
}
println("\nTotal Cost = ",cost);</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">fcn vogel(costs,supply,demand){
// a Dictionary can be created via a list of (k,v) pairs
res:= Dictionary(costs.pump(List,fcn([(k,_)]){ return(k,D()) }));
Line 3,443:
}//while
res
}</langsyntaxhighlight>
{{out}}
<pre>
Thundergnat
10,333

edits

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