Skip to content

Instantly share code, notes, and snippets.

@mpenkov

mpenkov/coins.py

Last active August 29, 2015 13:56
Show Gist options
  • Save mpenkov/8971200 to your computer and use it in GitHub Desktop.
Save mpenkov/8971200 to your computer and use it in GitHub Desktop.
Download ZIP
Coding for Interviews: Dynamic Programming
Raw
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()
Raw
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; }
Raw
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>
Raw
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();
};
Raw
fiddle.manifest
name: Coins
description: Some description, please keep it in one line
authors:
- Michael Penkov
normalize_css: no
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment