Skip to content

Instantly share code, notes, and snippets.

@mohanrajendran
Last active August 29, 2015 14:04
Show Gist options
  • Save mohanrajendran/a3a8ea66bd5f66cbfbc5 to your computer and use it in GitHub Desktop.
Save mohanrajendran/a3a8ea66bd5f66cbfbc5 to your computer and use it in GitHub Desktop.
SICP Exercise 1.14 Plotting
import pygraphviz as pgv
import networkx as nx
nodeCount = 1
G = nx.DiGraph()
Ranks = {}
def countChange(amount):
global G
global Ranks
l = '(count-change ' + str(amount) +')'
G.add_node(0, label = l)
Ranks[0] = [0]
return cc(amount,5, 0, 1)
coins = [0,1,5,10,25,50]
def cc(amount, kinds, parent, depth):
global nodeCount
global G
global Ranks
curNode = nodeCount
nodeCount += 1
l = '(cc ' + str(amount) + ' ' + str(kinds) + ')'
G.add_node(curNode, label = l)
if depth in Ranks:
Ranks[depth].append(curNode)
else:
Ranks[depth] = [curNode]
G.add_edge(parent, curNode)
if amount == 0:
return 1
if amount < 0 or kinds == 0:
return 0
return cc(amount, kinds-1, curNode, depth+1) + cc(amount-coins[kinds], kinds, curNode, depth+1)
print countChange(11)
print Ranks
A = nx.to_agraph(G)
for r in Ranks:
A.add_subgraph(r, rank='same')
print A.string()
A.draw('graph.png', prog='dot')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment