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

BalancedParens.js

var _ = require("underscore");
var stack = [];

//var program = "((){{{}}()}[''\"\"])";
//var program = ' var wow  = { "yo": thisIsAwesome() }';
var program = ' var hubble = function() { telescopes.awesome();';

var re = /[\(\)\{\}\[\]'"]/;

//filter out all non-formatting characters
program = _.filter(program, function(c){ return c.match(re); });

function match(temp, item) {
  if (temp === "(" && item === ")") {
    return true;
  }
  else if (temp === "[" && item === "]") {
    return true;
  }
  else if (temp === "{" && item === "}") {
    return true;
  }
  else {
    return false;
  }
}

var insideQuotes = false;
for (var i=0; i < program.length; i++) {
  var item = program[i];

  if (item === "\"" || item === "'") {
    var top = stack.pop();
    if (top === item) {
      insideQuotes = false;
    }
    else {
      if (top != undefined) { stack.push(top); }
      stack.push(item);
      insideQuotes = true;
    }
  }
  if (!insideQuotes) {
    if (item === "(" ||
        item === "[" ||
        item === "{" ) {
      stack.push(item);
    }
    else if (item === "\"" || item === "'") {
      //don't put it on the stack if we're not inside quotes
    }
    else if (stack.length == 0) {
      stack.push(item);
      break;
    }
    else {
      var temp = stack.pop();
      if (match(temp, item)) {
      //nothing
      }
      else {
        stack.push(temp);
        stack.push(item);
      }
    }
  }
  else {
    //ignore chars between quotes
  }
}

if (stack.length != 0) {
  console.log("false");
}
else {
  console.log("true");
}

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