mpenkov/coins.py

## coins.py
import copy

def coinChangePossibleSolutions(amount, denominations):
    """Return the total number of ways of obtaining the specified amount using an unlimited number of coins of the specified denominations."""
    #
    # The cache keeps a mapping of amounts to a set of arrangements of coins.
    # We use set to keeps solutions unique.
    # Each arrangement is represented as a tuple, since the mutable lists aren't hashable and cannot be kept in the above set.
    #
    cache = {}
    cache[0] = set([tuple()])

    def solve(amt):
        #
        # Return the set of all possible solutions for amt.
        #
        if amt in cache:
            return cache[amt]
        cache[amt] = set()

        for denom in denominations:
            if denom <= amt:
                for soln in solve(amt-denom):
                    new_soln = list(copy.copy(soln))
                    new_soln.append(denom)
                    assert sum(new_soln) == amt
                    cache[amt].add(tuple(sorted(new_soln)))
        return cache[amt]

    solutions = solve(amount)
    #for i, soln in enumerate(sorted(solutions, key=lambda x: len(x), reverse=True)):
    #    print i, soln
    return len(solutions)

def main():
    import sys
    amount = int(sys.argv[1])
    denominations = [int(a) for a in sys.argv[2:]]
    print coinChangePossibleSolutions(amount, denominations)

if __name__ == "__main__":
    main()

## fiddle.css
table { border-collapse:collapse; }
table, th, td { border: 1px solid black; }
th, td { padding: 5px; }
td.currentlySelected { background-color: green; }
td.currentlySelectedLeft { background-color: blue; }
td.currentlySelectedAbove { background-color: red; }

## fiddle.html
<html>
  <head>
    <link rel="stylesheet" type="text/css" href="fiddle.css">
  </head>
  <body>
    <h1>Coins</h1>

    <p>Total amount: <input id="txtAmount" type="text" value="4"> (enter an integer)</p>
    <p>Coins: <input id="txtCoins" type="text" value="1 2 3"> (enter a space-separated list)</p>
    <p><button id="btnGo">Go</button>
    <hr>

    <h2>Solutions</h2>

    <p id="pTotalSolutions"></p>

    <h2>Dynamic Programming Matrix</h2>

    <p>Each matrix cell corresponds to a subproblem.
    Click on a matrix cell to see which sub-problems it was calculated from.</p>

    <table>
      <thead id="tblHead">
      </thead>
      <tbody id="tblBody">
      </tbody>
    </table>

    <script src="jquery-1.11.0.min.js"></script>
    <script src="fiddle.js"></script>
  </body>
</html>

## fiddle.js
window.onload = function() {
    function calculateDynamicProgrammingArray(amount, coins) {
        var dparray = [];
        for (var i = 0; i <= amount; ++i) {
            dparray[i] = [0];
        }

        for (var j = 0; j <= coins.length; ++j) {
            dparray[0][j] = 1;
        }

        for (var i = 1; i <= amount; ++i) {
            for (var j = 1; j <= coins.length; ++j) {
                dparray[i][j] = dparray[i][j-1];

                var coinValue = coins[j-1];
                if (coinValue <= i) {
                    dparray[i][j] += dparray[i-coinValue][j];
                }
            }
        }

        return dparray;
    }

    function updateTable(coins, dparray) {
        var getCell = function(i, j) {
            return $("#cell_" + i + "_" + j);
        };

        var clearHighlighting = function() {
            for (var i = 0; i < dparray.length; ++i) {
                for (var j = 0; j < dparray[i].length; ++j) {
                    getCell(i,j).removeClass("currentlySelected");
                    getCell(i,j).removeClass("currentlySelectedLeft");
                    getCell(i,j).removeClass("currentlySelectedAbove");
                }
            }
        };

        var oldHead = document.getElementById("tblHead");
        var newHead = document.createElement("thead");
        newHead.id = "tblHead";
        tr = document.createElement("tr")
        tr.appendChild(document.createElement("th"));
        for (var i = 0; i <= coins.length; ++i) {
            var th = document.createElement("th");
            th.innerHTML = i == 0 ? "&nbsp;" : coins[i-1];
            tr.appendChild(th);
        }
        newHead.appendChild(tr);

        tr = document.createElement("tr")
        tr.appendChild(document.createElement("th"));
        for (var i = 0; i <= coins.length; ++i) {
            var th = document.createElement("th");
            th.innerHTML = i;
            tr.appendChild(th);
        }
        newHead.appendChild(tr);

        oldHead.parentNode.replaceChild(newHead, oldHead);

        var oldBody = document.getElementById("tblBody");
        var newBody = document.createElement("tbody");
        newBody.id = "tblBody";
        for (var i = 0; i < dparray.length; ++i) {
            var tr = document.createElement("tr");
            var th = document.createElement("th");
            th.innerHTML = i;
            tr.appendChild(th);
            for (var j = 0; j < dparray[i].length; ++j) {
                var td = document.createElement("td");
                td.innerHTML = dparray[i][j];
                td.id = "cell_" + i + "_" + j;
                td.onclick = function(ii, jj) {
                    return function() {
                        clearHighlighting();
                        getCell(ii,jj).addClass("currentlySelected");
                        getCell(ii,jj-1).addClass("currentlySelectedLeft");
                        var coinVal = coins[jj-1];
                        if (coinVal <= ii) {
                            getCell(ii-coinVal,jj).addClass("currentlySelectedAbove");
                        }
                    };
                }(i, j);
                tr.appendChild(td);
            }
            newBody.appendChild(tr);
        }
        oldBody.parentNode.replaceChild(newBody, oldBody);
    }

    function updateSolution() {
        var amount = parseInt($("#txtAmount").val(), 10);
        if (isNaN(amount)) {
            alert("the amount must be an integer");
            return;
        }

        var coins = $("#txtCoins").val().split(" ");
        for (var i = 0; i < coins.length; ++i) {
            coins[i] = parseInt(coins[i], 10);
            if (isNaN(coins[i])) {
                alert("coins must be a space-separated list of integers");
                return;
            }
        }

        var dparray = calculateDynamicProgrammingArray(amount, coins);
        updateTable(coins, dparray);

        $("#pTotalSolutions").text("Total number of solutions: " + dparray[amount][coins.length]);
    }

    $("#btnGo").click(updateSolution);
    updateSolution();

};

## fiddle.manifest
name: Coins
description: Some description, please keep it in one line
authors:
  - Michael Penkov
normalize_css: no
	import copy

	def coinChangePossibleSolutions(amount, denominations):
	"""Return the total number of ways of obtaining the specified amount using an unlimited number of coins of the specified denominations."""
	#
	# The cache keeps a mapping of amounts to a set of arrangements of coins.
	# We use set to keeps solutions unique.
	# Each arrangement is represented as a tuple, since the mutable lists aren't hashable and cannot be kept in the above set.
	#
	cache = {}
	cache[0] = set([tuple()])

	def solve(amt):
	#
	# Return the set of all possible solutions for amt.
	#
	if amt in cache:
	return cache[amt]
	cache[amt] = set()

	for denom in denominations:
	if denom <= amt:
	for soln in solve(amt-denom):
	new_soln = list(copy.copy(soln))
	new_soln.append(denom)
	assert sum(new_soln) == amt
	cache[amt].add(tuple(sorted(new_soln)))
	return cache[amt]

	solutions = solve(amount)
	#for i, soln in enumerate(sorted(solutions, key=lambda x: len(x), reverse=True)):
	# print i, soln
	return len(solutions)

	def main():
	import sys
	amount = int(sys.argv[1])
	denominations = [int(a) for a in sys.argv[2:]]
	print coinChangePossibleSolutions(amount, denominations)

	if __name__ == "__main__":
	main()
	table { border-collapse:collapse; }
	table, th, td { border: 1px solid black; }
	th, td { padding: 5px; }
	td.currentlySelected { background-color: green; }
	td.currentlySelectedLeft { background-color: blue; }
	td.currentlySelectedAbove { background-color: red; }
	<html>
	<head>
	<link rel="stylesheet" type="text/css" href="fiddle.css">
	</head>
	<body>
	<h1>Coins</h1>

	<p>Total amount: <input id="txtAmount" type="text" value="4"> (enter an integer)</p>
	<p>Coins: <input id="txtCoins" type="text" value="1 2 3"> (enter a space-separated list)</p>
	<p><button id="btnGo">Go</button>
	<hr>

	<h2>Solutions</h2>

	<p id="pTotalSolutions"></p>

	<h2>Dynamic Programming Matrix</h2>

	<p>Each matrix cell corresponds to a subproblem.
	Click on a matrix cell to see which sub-problems it was calculated from.</p>

	<table>
	<thead id="tblHead">
	</thead>
	<tbody id="tblBody">
	</tbody>
	</table>

	<script src="jquery-1.11.0.min.js"></script>
	<script src="fiddle.js"></script>
	</body>
	</html>
	window.onload = function() {
	function calculateDynamicProgrammingArray(amount, coins) {
	var dparray = [];
	for (var i = 0; i <= amount; ++i) {
	dparray[i] = [0];
	}

	for (var j = 0; j <= coins.length; ++j) {
	dparray[0][j] = 1;
	}

	for (var i = 1; i <= amount; ++i) {
	for (var j = 1; j <= coins.length; ++j) {
	dparray[i][j] = dparray[i][j-1];

	var coinValue = coins[j-1];
	if (coinValue <= i) {
	dparray[i][j] += dparray[i-coinValue][j];
	}
	}
	}

	return dparray;
	}

	function updateTable(coins, dparray) {
	var getCell = function(i, j) {
	return $("#cell_" + i + "_" + j);
	};

	var clearHighlighting = function() {
	for (var i = 0; i < dparray.length; ++i) {
	for (var j = 0; j < dparray[i].length; ++j) {
	getCell(i,j).removeClass("currentlySelected");
	getCell(i,j).removeClass("currentlySelectedLeft");
	getCell(i,j).removeClass("currentlySelectedAbove");
	}
	}
	};

	var oldHead = document.getElementById("tblHead");
	var newHead = document.createElement("thead");
	newHead.id = "tblHead";
	tr = document.createElement("tr")
	tr.appendChild(document.createElement("th"));
	for (var i = 0; i <= coins.length; ++i) {
	var th = document.createElement("th");
	th.innerHTML = i == 0 ? " " : coins[i-1];
	tr.appendChild(th);
	}
	newHead.appendChild(tr);

	tr = document.createElement("tr")
	tr.appendChild(document.createElement("th"));
	for (var i = 0; i <= coins.length; ++i) {
	var th = document.createElement("th");
	th.innerHTML = i;
	tr.appendChild(th);
	}
	newHead.appendChild(tr);

	oldHead.parentNode.replaceChild(newHead, oldHead);

	var oldBody = document.getElementById("tblBody");
	var newBody = document.createElement("tbody");
	newBody.id = "tblBody";
	for (var i = 0; i < dparray.length; ++i) {
	var tr = document.createElement("tr");
	var th = document.createElement("th");
	th.innerHTML = i;
	tr.appendChild(th);
	for (var j = 0; j < dparray[i].length; ++j) {
	var td = document.createElement("td");
	td.innerHTML = dparray[i][j];
	td.id = "cell_" + i + "_" + j;
	td.onclick = function(ii, jj) {
	return function() {
	clearHighlighting();
	getCell(ii,jj).addClass("currentlySelected");
	getCell(ii,jj-1).addClass("currentlySelectedLeft");
	var coinVal = coins[jj-1];
	if (coinVal <= ii) {
	getCell(ii-coinVal,jj).addClass("currentlySelectedAbove");
	}
	};
	}(i, j);
	tr.appendChild(td);
	}
	newBody.appendChild(tr);
	}
	oldBody.parentNode.replaceChild(newBody, oldBody);
	}

	function updateSolution() {
	var amount = parseInt($("#txtAmount").val(), 10);
	if (isNaN(amount)) {
	alert("the amount must be an integer");
	return;
	}

	var coins = $("#txtCoins").val().split(" ");
	for (var i = 0; i < coins.length; ++i) {
	coins[i] = parseInt(coins[i], 10);
	if (isNaN(coins[i])) {
	alert("coins must be a space-separated list of integers");
	return;
	}
	}

	var dparray = calculateDynamicProgrammingArray(amount, coins);
	updateTable(coins, dparray);

	$("#pTotalSolutions").text("Total number of solutions: " + dparray[amount][coins.length]);
	}

	$("#btnGo").click(updateSolution);
	updateSolution();

	};
	name: Coins
	description: Some description, please keep it in one line
	authors:
	- Michael Penkov
	normalize_css: no