# the number of ways to change amount a using n kinds of coins:

# the number of ways to change amount a using all but the first
# kind of coin

# +

# the number of ways to change a - d using all n kinds of coins,
# where d is the denomination of the first kind of coin.

# c(a, [n = list of coins]) = c(a, n[:1]) + c(a-n[0], n)

# using the following base rules:

# if a = 0, result = 1
# if a < 0, result = 0
# if n = 0, result = 0

(defn first-denomination [kinds-of-coins]
  (cond
    (= kinds-of-coins 1) 1
    (= kinds-of-coins 2) 5
    (= kinds-of-coins 3) 10
    (= kinds-of-coins 4) 25
    (= kinds-of-coins 5) 50))

(defn cc [amount kind-of-coins]
  (cond
    (= amount 0) 1
    (or
      (< amount 0)
      (= kind-of-coins 0)) 0
    (+
     (cc amount (- kind-of-coins 1))
     (cc (- amount (first-denomination kind-of-coins)) kind-of-coins))))

(defn count-change [amount] 
  (cc amount 5))

# (cc 11.0 5)
# (cc 11.0 4) (cc -39.0 5)
# (cc 11.0 3) (cc -14.0 4)
# (cc 11.0 2) (cc 1.0 3)
# (cc 11.0 1) (cc 6.0 2) (cc 1.0 2) (cc -9.0 3)
# (cc 11.0 0) (cc 10.0 1) (cc 6.0 1) (cc 1.0 2) (cc 1.0 1) (cc -4.0 2)
# (cc 10.0 0) (cc 9.0 1) (cc 6.0 0) (cc 5.0 1) (cc 1.0 1) (cc -4.0 2) (cc 1.0 0) (cc 0.0 1)
# (cc 9.0 0) (cc 8.0 1) (cc 5.0 0) (cc 4.0 1) (cc 1.0 0) (cc 0.0 1) 1
# (cc 8.0 0) (cc 7.0 1) (cc 4.0 0) (cc 3.0 1) 1 1
# (cc 7.0 0) (cc 6.0 1) (cc 3.0 0) (cc 2.0 1) 1 1
# (cc 6.0 0) (cc 5.0 1) (cc 2.0 0) (cc 1.0 1) 1 1
# (cc 5.0 0) (cc 4.0 1) (cc 1.0 0) (cc 0.0 1) 1 1
# (cc 4.0 0) (cc 3.0 1) 1 1 1
# (cc 3.0 0) (cc 2.0 1) 1 1 1
# (cc 2.0 0) (cc 1.0 1) 1 1 1 
# (cc 1.0 0) 1 1 1 1
# 1 1 1 1 
# 4

(import ./dot :as dot)

(defn add-to [graph counter amount kind-of-coins parent]
  (def label (string/format "(cc %d %d)" amount kind-of-coins))
  (def node_name (string/format "node_%d" counter))
  (def clr
    (cond (<= kind-of-coins 0) "lightgray"
          (< amount 0) "lightgray"
          (= amount 0) "cyan"
          (= kind-of-coins 2) "pink"
          (= kind-of-coins 3) "mediumorchid"
          (= kind-of-coins 4) "mediumpurple1"
          (= kind-of-coins 5) "khaki1"
          "lightgreen"))
  (cond
    (= kind-of-coins 5) (dot/add-node (get (get graph :subgraphs) 4) node_name :label label :shape "box" :fillcolor clr :style "filled" :group "5")
    (= kind-of-coins 4) (dot/add-node (get (get graph :subgraphs) 3) node_name :label label :shape "box" :fillcolor clr :style "filled" :group "4")
    (= kind-of-coins 3) (dot/add-node (get (get graph :subgraphs) 2) node_name :label label :shape "box" :fillcolor clr :style "filled" :group "3")
    (= kind-of-coins 2) (dot/add-node (get (get graph :subgraphs) 1) node_name :label label :shape "box" :fillcolor clr :style "filled" :group "2")
    (= kind-of-coins 1) (dot/add-node (get (get graph :subgraphs) 0) node_name :label label :shape "box" :fillcolor clr :style "filled" :group "1")
    (do
      (dot/add-node graph node_name :label label :shape "box" :fillcolor clr :style "filled")))

  (dot/add-relation graph parent node_name)
  node_name)

(defn count-change2 [amount denom]
  (def graph (dot/create "change" :graph_type :digraph))
  (dot/add-subgraph graph (dot/create-subgraph "rank_1"))
  (dot/add-subgraph graph (dot/create-subgraph "rank_2" :rank "same"))
  (dot/add-subgraph graph (dot/create-subgraph "rank_3" :rank "same"))
  (dot/add-subgraph graph (dot/create-subgraph "rank_4" :rank "same"))
  (dot/add-subgraph graph (dot/create-subgraph "rank_5" :rank "same"))
  (var counter 0)
  (defn cc [amount kind-of-coins parent]
    (def name (add-to graph counter amount kind-of-coins parent))
    (set counter (+ counter 1))
    (cond
      (= amount 0) 1
      (or
          (< amount 0)
          (= kind-of-coins 0)) 0
      (+
        (cc amount (- kind-of-coins 1) name)
        (cc (- amount (first-denomination kind-of-coins)) kind-of-coins name))))

  (def result (cc amount denom "start"))
  (dot/write graph "exercise_1_14.gv")
  result)

(print (count-change2 51 5))

# Using the graph we can find the following relation for (cc n 1)
# f(0,1) = 1
# f(1,1) = 3 = f(0,1) + 2
# f(2,1) = 5 = f(1,1) + 2
# f(3,1) = 7 = f(2,1) + 2
# f(n,1) = f(n-1, 1) + 2
# f(n,1) = 2*n + 1

# graphing (cc n 2)
# we can see that every iteration of (cc n 2) splits into two trees:
# (cc n 1) and (cc (n-5) 2).
# Starting with f(1,2) = f(-4, 2) + f(1, 1).
# we know that f(1,1) = 3 steps, f(-4, 2) = 1 step, and accounting
# for the original f(1,2), we get a total of 5 steps.
# f(6, 2) = f(1,2) + f(6,1) = 5 + 6 + 1 = 11
# in general we can say:
# f(n, 2) = f(n, 1) + f(n-x_2, 2) + 1
# given x_2 = 5
# example f(1, 2) = f(1, 1) + f(-4, 2) + 1 = 3 + 1 + 1 = 5
# example f(6, 2) = f(6, 1) + f(1, 2) + 1 = 13 + 5 + 1 = 19
# the closed form of this is:
# f(n, 2) = ceil(n/5) + sum_i=0^floor(n/5){ f(n-x_2*i, 1) } + (ceil(n/5) - floor(n/5))
# f(6, 2) = 2 + [f(6, 1) + f(1, 1)] + (2-1) = 2 + 13 + 3 + 1 = 19
# f(11, 2) = 3 + [f(11, 1) + f(6, 1) + f(1,1)] + (3-2) = 3 + 23 + 13 + 3 + 1 = 43
# f(n, 2) = 2*ceil(n/5) - floor(n/5) + (ceil(n/5) * (f(n, 1) + f(n%x_2, 1)) / 2)
# f(n, 2) = ceil(n/x_2) * [(f(n,1) + f(n%x_2, 1)) / 2 + 2] - floor(n%x_2)
# f(n, 2) = ceil(n/x_2) * [(2*n + 1 + 2*(n%x_2) + 1) / 2 + 2] - floor(n%x_2)
# f(n, 2) = ceil(n/x_2) * [n + (n<F2><F3><F4>-x_2*floor(n/x_2)) + 3] - floor(n/x_2)
# f(11, 2) = 2*3 - 2 + 3 * (23 + 3) / 2 = 6 - 2 + 39 = 43
# f(11, 2) = 3 * [(23 + 3) / 2 + 2] - 2 = 3 * 45 - 2 = 43
# f(11, 2) = 3 * [11 + 1 + 3] - 2 = 3 * [15] - 2 = 43

# graphing (cc n 3)
# we can see that every iteration of (cc n 3) splits into two trees:
# (cc n 2) + (cc (n-x_3),3)
# an recursive form of this definition would be:
# f(n, 3) = f(n, 2) + f(n-x_2, 3) + 1
# test:
# f(1, 3) = f(1, 2) + f(-9, 3) + 1 = 5 + 1 + 1 = 7
# f(11, 3) = f(11, 2) + f(1, 3) + 1 = 43 + 1 + 7 = 51