Last active
December 5, 2019 16:16
-
-
Save nlw0/04ec031eaa839d5e358d7ad0d194c497 to your computer and use it in GitHub Desktop.
change-making problem in multiple languages
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <unordered_set> | |
#include <vector> | |
#include <optional> | |
#include <iostream> | |
#include <chrono> | |
#include <ctime> | |
template<typename T> std::optional<int> minimum_coins(T target, std::vector<T> denominations) { | |
auto values = new std::unordered_set<T>(); values->insert(target); | |
auto k = 0; | |
while (values->size() > 0) { | |
k += 1; | |
auto newvalues = new std::unordered_set<T>(); | |
for (auto v : *values) { | |
for (auto d : denominations) { | |
if (v == d) | |
return k; | |
else if (v > d) | |
newvalues->insert(v - d); | |
else | |
continue; | |
} | |
} | |
delete values; | |
values = newvalues; | |
} | |
return {}; | |
} | |
int main() { | |
std::cout << *minimum_coins<int>(97, std::vector<int>({11, 10, 1})) << "\n"; | |
std::cout << *minimum_coins<int>(13, std::vector<int>({9, 5, 3, 1})) << "\n"; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
import "fmt" | |
import "time" | |
func minimum_coins(target int, denominations []int) int { | |
values := &map[int]bool{target:true} | |
k := 0 | |
for (len(*values) > 0) { | |
k += 1 | |
newvalues := &map[int]bool{} | |
for v := range *values { | |
for _, d := range denominations { | |
if (v == d) { | |
return k | |
} else if (v > d) { | |
(*newvalues)[v - d] = true | |
} else { | |
continue | |
} | |
} | |
} | |
values = newvalues | |
} | |
return -1; | |
} | |
func main() { | |
d1 := []int{11, 10, 1} | |
d2 := []int{9, 5, 3, 1} | |
fmt.Println(minimum_coins(97, d1[:])) | |
fmt.Println(minimum_coins(13, d2[:])) | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function minimum_coins(target, denominations) | |
values = Set([target]) | |
k = 0 | |
while length(values) > 0 | |
k += 1 | |
newvalues = Set{eltype(values)}([]) | |
for (v, d) in Iterators.product(values, denominations) | |
if v == d | |
return k | |
elseif v > d | |
push!(newvalues, v-d) | |
else | |
continue | |
end | |
end | |
values = newvalues | |
end | |
return nothing | |
end | |
println(minimum_coins(97, [11, 10, 1])) | |
println(minimum_coins(13, [9, 5, 3, 1])) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function minimum_coins(target, denominations) { | |
let values = new Set([target]) | |
let k = 0 | |
while (values.size > 0) { | |
k += 1 | |
let newvalues = new Set([]) | |
for (let v of values) { | |
for (let d of denominations) { | |
if (v == d) { | |
return k | |
} else if (v > d) { | |
newvalues.add(v-d) | |
} else { | |
continue | |
} | |
} | |
} | |
values = newvalues | |
} | |
return null | |
} | |
print(minimum_coins(97, [11, 10, 1])) | |
print(minimum_coins(13, [9, 5, 3, 1])) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import itertools | |
def minimum_coins(target, denominations): | |
values = set([target]) | |
k = 0 | |
while len(values) > 0: | |
k += 1 | |
newvalues = set([]) | |
for v, d in itertools.product(values, denominations): | |
if v == d: | |
return k | |
elif v > d: | |
newvalues.add(v-d) | |
else: | |
continue | |
values = newvalues | |
return None | |
print(minimum_coins(97, [11, 10, 1])) | |
print(minimum_coins(13, [9, 5, 3, 1])) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
use itertools::iproduct; | |
use num::Integer; | |
use std::collections::HashSet; | |
use std::hash::Hash; | |
fn minimum_coins<T>(target: T, denominations: &[T]) -> Option<T> | |
where | |
T: Integer + Hash + Copy, | |
{ | |
let mut values = HashSet::new(); values.insert(target); | |
let mut k = T::zero(); | |
while !values.is_empty() { | |
k = k + T::one(); | |
let mut newvalues: HashSet<T> = HashSet::new(); | |
for (v, d) in iproduct!(values, denominations) { | |
if v == *d { | |
return Some(k); | |
} else if v > *d { | |
newvalues.insert(v - *d); | |
} else { | |
continue; | |
} | |
} | |
values = newvalues | |
} | |
None | |
} | |
fn main() { | |
println!("{:?}", minimum_coins(97, &vec![11, 10, 1])); | |
println!("{:?}", minimum_coins(13, &vec![9, 5, 3, 1])); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import Foundation | |
func minimum_coins(_ target: Int, _ denominations: [Int]) -> Int? { | |
var values: Set = [target] | |
var k = 0 | |
while (values.count > 0) { | |
k += 1 | |
var newvalues: Set<Int> = [] | |
for v in values { | |
for d in denominations { | |
if (v == d) { | |
return k | |
} else if (v > d) { | |
newvalues.insert(v - d) | |
} else { | |
continue | |
} | |
} | |
} | |
values = newvalues | |
} | |
return nil | |
} | |
print(minimum_coins(97, [11, 10, 1])!) | |
print(minimum_coins(13, [9, 5, 3, 1])!) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using Printf | |
exts = ["py", "jl", "js", "swift", "go", "rs", "cpp"] | |
function finddiff(filea, fileb) | |
common = map(split(read(ignorestatus(`wdiff -s $filea $fileb`), String), "\n")[end-2:end-1]) do row | |
parse(Int, match(r"(\d+)\% common", row)[1]) | |
end | |
sqrt(prod(common ./ 100.0)) | |
end | |
for (a, b) in [(a,b) for a in 1:6 for b in a+1:7] | |
ea = exts[a] | |
eb = exts[b] | |
similar = finddiff("change." * ea, "change."*eb) | |
@printf("%5s %5s %5.2f\n", ea, eb, similar) | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
py jl 0.61 | |
py js 0.55 | |
py swift 0.46 | |
py go 0.33 | |
py rs 0.30 | |
py cpp 0.30 | |
jl js 0.54 | |
jl swift 0.40 | |
jl go 0.31 | |
jl rs 0.33 | |
jl cpp 0.32 | |
js swift 0.65 | |
js go 0.55 | |
js rs 0.43 | |
js cpp 0.51 | |
swift go 0.53 | |
swift rs 0.41 | |
swift cpp 0.42 | |
go rs 0.33 | |
go cpp 0.41 | |
rs cpp 0.33 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Thanks for your comment. I'm familiar with both, and I don't really like either of them. It's sure interesting to wonder how they compare.