Coin problem solutions - OCaml and Go

coin.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}]

coin.ml

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