Skip to content

Instantly share code, notes, and snippets.

@nlw0 nlw0/change.cpp
Last active Dec 5, 2019

Embed
What would you like to do?
change-making problem in multiple languages
#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";
}
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[:]))
}
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]))
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]))
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]))
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]));
}
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])!)
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
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
@develooper1994

This comment has been minimized.

Copy link

develooper1994 commented Dec 5, 2019

Have you ever tried pypy for Python. Also you should try nim.

@nlw0

This comment has been minimized.

Copy link
Owner Author

nlw0 commented Dec 5, 2019

Have you ever tried pypy for Python. Also you should try nim.

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.