Last active
December 26, 2015 06:09
-
-
Save EpiphanyMachine/7105567 to your computer and use it in GitHub Desktop.
Algorithms Meetup 21 Oct 13
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # | |
| # 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #!/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) | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #!/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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # | |
| # 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)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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.