change-making problem in multiple languages

change.cpp

#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";
}

change.go

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[:]))
}

change.jl

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]))

change.js

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]))

change.py

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]))

change.rs

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]));
}

change.swift

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])!)

silly_similarity.jl

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

similarity.txt

   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

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

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.