Algorithms Meetup 21 Oct 13

Balanced Parentheses Prompt

#
# 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

Number of Ways to Make Change - JS

/*

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

Number of Ways to Make Change - Python

#!/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)

Number of Ways to Make Change - Python Memoized

#!/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)

Number of Ways to Make Change - Python Tests

#
# 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))

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.