Skip to content

Instantly share code, notes, and snippets.

@jamessouth
Last active January 28, 2022 02:17
Show Gist options
  • Save jamessouth/3baa1fdd63f494ec0250350d24e71c0b to your computer and use it in GitHub Desktop.
Save jamessouth/3baa1fdd63f494ec0250350d24e71c0b to your computer and use it in GitHub Desktop.
Coin problem solutions - OCaml and Go
// Problem: Find all integer values of X (1 <= X <= 100) that satisfy the
// following statement: It is impossible to make $1 using exactly X U.S. coins.
// Consider only coins with these denominations: 1¢, 5¢, 10¢, 25¢, 50¢, and $1.
package main
import "fmt"
type results struct {
coins int
ok bool
}
func coin(k int) bool {
diff := 100 - k
for d := 0; d <= 10; d++ {
for n := 0; n <= 20; n++ {
if (n*4)+(d*9) == diff {
return true
}
}
}
return false
}
func main() {
res := []results{}
for i := 1; i <= 100; i++ {
if tf := coin(i); !tf {
res = append(res, results{
coins: i,
ok: tf,
})
}
}
fmt.Println(res)
}
// [{77 false} {81 false} {85 false} {86 false} {89 false} {90 false}
// {93 false} {94 false} {95 false} {97 false} {98 false} {99 false}]
(* Problem: Find all integer values of X (1 <= X <= 100) that satisfy the
following statement: It is impossible to make $1 using exactly X U.S. coins.
Consider only coins with these denominations: 1¢, 5¢, 10¢, 25¢, 50¢, and $1. *)
module Coin : sig
type 'a tree
type coins
val cents : coins -> int
val oneToOneHundred : (int * int * coins tree) list
val memo_rec : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b
val dfs_memo : int * int * coins tree -> bool
val run : ('a * 'b * 'c -> 'd) -> ('a * 'b * 'c) list -> ('a * 'd) list
end = struct
type 'a tree = | Node of 'a
type coins = Dollar | Half | Quarter | Dime | Nickel | Penny | Zero
let cents = function
| Dollar -> 100
| Half -> 50
| Quarter -> 25
| Dime -> 10
| Nickel -> 5
| Penny -> 1
| Zero -> 0
let oneToOneHundred = List.init 100 (fun y -> (y + 1, 0, Node(Zero)))
let memo_rec f =
let h = Hashtbl.create 50000 in
let rec g x =
try Hashtbl.find h x
with Not_found ->
let y = f g x in
Hashtbl.add h x y;
y
in
g
let dfs_memo =
let dfs self arg = let (n, acc, tree) = arg in match tree with
| Node(v) -> let sum = acc + cents(v) in match sum < 101 with
| true -> if sum = 100 && n = 0 then true else if (sum = 100 && n > 0) || n < 1 then false else
self ((n-1), sum, (Node(Dollar)))
|| self ((n-1), sum, (Node(Half)))
|| self ((n-1), sum, (Node(Quarter)))
|| self ((n-1), sum, (Node(Dime)))
|| self ((n-1), sum, (Node(Nickel)))
|| self ((n-1), sum, (Node(Penny)))
|| false
| false -> false in memo_rec dfs
let rec run f = function
| [] -> []
| h::t -> match h with
| (n,_,_) -> (n, f h)::run f t
end
(* List.filter (fun (_,y) -> not y) Coin.(run dfs_memo oneToOneHundred);;
- : (int * bool) list =
[(77, false); (81, false); (85, false); (86, false); (89, false); (90, false);
(93, false); (94, false); (95, false); (97, false); (98, false); (99, false)] *)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment