{{ message }}

Instantly share code, notes, and snippets.

# EpiphanyMachine/Balanced Parentheses Prompt

Last active Dec 26, 2015
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 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 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 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.