Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#
# 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
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");
}
/*
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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment