Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Algorithms Meetup 21 Oct 13
#
# write a function that takes a string of text and returns true if
# the parentheses, brackets, and braces are balanced and false otherwise.
#
# Example:
# balanceParens('[](){}'); // true
# balanceParens('[({})]'); // true
# balanceParens('[(]{)}'); // false
#
# Step 3:
# ignore non-parenthesis characters, and add support for quotes (single and double)
# balanceParens(' var wow = { "yo": thisIsAwesome() }'); // true
# balanceParens(' var hubble = function() { telescopes.awesome();'); // false
#
# our solution uses a stack for all opening items and when it finds a closing
# item tests the top of the stack to see if it matches
Solution 1:
https://gist.github.com/morenoh149/7145832
/*
In England the currency is made up of pound, £, and pence, p,
and there are eight coins in general circulation:
1p piece
2p piece
5p piece
10p piece
20p piece
50p piece
1 pound (100p)
2 pound (200p)
How many different ways can £2 be made using any number of coins?
example usage of `makeChange`:
// aka, there's only one way to make 1p. that's with a single 1p piece
makeChange(1) === 1
// aka, there's only two ways to make 2p. that's with two, 1p pieces or
with a single 2p piece
makeChange(2) === 2
[1, 2, 5, 10, 20, 50, 100, 200]
*/
var makeChange = function(total){
var combinations = 0;
function checkcombinations(denominations, tot) {
var currentDenomination = denominations.pop();
if (denominations.length === 0) {
while( tot > 0 ) { tot -= currentDenomination }
if( tot === 0 ){
combinations++;
}
} else {
while (tot >= 0) {
checkcombinations(denominations.slice(), tot);
tot -= currentDenomination;
}
}
}
checkcombinations([1, 2, 5, 10, 20, 50], total);
return combinations;
};
console.log('200:', makeChange(200));
// £2 can be made up in 73,682 different ways
#!/bin/env python
#
# Thanks to Tyler Prete for the following solutions
# https://github.com/tylerprete
#
# Returns number of solutions using coins for value
def solution_count(coins, value):
coins.sort(reverse=True)
return solution_count_inner(coins, value)
def solution_count_inner(coins, value):
if not coins or value <= 0:
return 0
total = 0
biggest_coin = coins[0]
if biggest_coin == value:
total += 1
elif value > biggest_coin:
total += solution_count_inner(coins[:], value - biggest_coin)
total += solution_count_inner(coins[1:], value)
return total
if __name__ == "__main__":
coins = [1, 5, 10, 25, 100, 200]
value = 10000
print solution_count(coins, value)
#!/bin/env python
#
# Memoization for the solution above
# Thanks to Tyler Prete again
# https://github.com/tylerprete
#
# Returns number of solutions using coins for value
def solution_count(coins, value):
coins.sort(reverse=True)
return solution_count_inner(coins, value)
cache = {}
def get_cache(coins, value):
coins_tup = tuple(coins)
cache_tup = (coins_tup, value)
return cache.get(cache_tup)
def set_cache(coins, value, total):
coins_tup = tuple(coins)
cache_tup = (coins_tup, value)
cache[cache_tup] = total
def solution_count_inner(coins, value):
# Check cache for memoized value
cache_val = get_cache(coins, value)
if cache_val:
return cache_val
if not coins or value <= 0:
return 0
total = 0
biggest_coin = coins[0]
if biggest_coin == value:
total += 1
elif value > biggest_coin:
total += solution_count_inner(coins, value - biggest_coin)
total += solution_count_inner(coins[1:], value)
set_cache(coins, value, total)
return total
if __name__ == "__main__":
coins = [1, 5, 10, 25, 100, 200]
value = 100000
print solution_count(coins, value)
#
# Tests for the solution above
# Thanks to Tyler Prete again
# https://github.com/tylerprete
#
from coins import solution_count
import unittest
from random import shuffle
class CoinTest(unittest.TestCase):
def test_solution_count_for_30(self):
coins = [25, 10, 5, 1]
value = 30
self.assertEqual(18, solution_count(coins, value))
shuffle(coins)
self.assertEqual(18, solution_count(coins, value))
def test_given(self):
coins = [1,2,5,10]
solutions = {1:1, 2:2, 3:2, 4:3, 5:4, 15:22, 30:98, 57:476, 185:12160}
for value, solution in solutions.items():
self.assertEqual(solution, solution_count(coins, value))
@EpiphanyMachine

This comment has been minimized.

Copy link
Owner Author

@EpiphanyMachine EpiphanyMachine commented Oct 22, 2013

If you would like to expand more on any of these you could try to optimize the number of ways to make change. One method may be to memoize some of recursive calls.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment