Monthly Archives: October 2016

8.14 Boolean Evaluation – CCI

# [8.14] Boolean Evaluation: Given a boolean expression 
# consisting of the symbols 0 (false), 1 (true), &
# (AND), | (OR), and ^ (XOR), and a desired boolean result
# value 'result', implement a function to count the number
# of ways of parenthesizing the expression such that it
# evaluates to 'result'. The expression should be
# fully parenthesize (e.g., (0)^(1)) but not extraneously
# (e.g., (((0))^(1))).

# EXAMPLE
# countEval("1^0|0|1", False) -> 2
# countEval("0&0&0&1^1|0", True) -> 10

import unittest

def bool_eval(expr, result):
    
    if expr == "1":
        if result:
            return 1
        return 0
    if expr == "0":
        if not result:
            return 1
        return 0

    subways = 0

    for i in xrange(1,len(expr),2):
        
        operator = expr[i]
        left = expr[0:i]
        right = expr[i+1:]

        left_true = bool_eval(left, True)
        left_false = bool_eval(left, False)
        right_true = bool_eval(right, True)
        right_false = bool_eval(right, False)
        total_ways = (left_true + left_false) * (right_true + right_false)
        true_ways = 0

        if operator == "&":
            true_ways += left_true*right_true
        elif operator == "|":
            true_ways += (
                (left_true*right_true) 
                + (left_true*right_false) 
                + (left_false*right_true)
            )
        elif operator == "^":
            true_ways += (left_true*right_false) + (left_false*right_true)

        if result:
            subways += true_ways
        else:
            subways += total_ways - true_ways

    return subways
    
class Test(unittest.TestCase):

    def test_bool_eval(self):
        self.assertEqual(bool_eval("0&0&0&1^1|0", True), 10)
        self.assertEqual(bool_eval("1^0|0|1", False), 2)
        
if __name__ == '__main__':
    unittest.main()

8.13 Stack of Boxes – CCI

# [8.13] Stack of Boxes: You have a stack of boxes, with width 
# w, heights h, and depths d. The boxes cannot be rotated
# and can only be stacked on top of one another if each box
# in the stack is strictly larger than the box above it
# in in width, height, and depth. Implement a method to compute
# the height of the tallest possible stack. The height of a 
# stack is the sum of the heights of each box.

import unittest

def max_stack_height_helper(boxes):
    if len(boxes) == 1:
        return boxes[0].height

    current_box = boxes[0]
    stackable_boxes = get_stackable_boxes(current_box, boxes[1:])

    if stackable_boxes:
        current_height = current_box.height + max_stack_height_helper(stackable_boxes)
    else:
        current_height = current_box.height

    return max(current_height, max_stack_height_helper(boxes[1:]))

def max_stack_height(boxes):
    boxes.sort(key=lambda x: x.height, reverse=True)
    return max_stack_height_helper(boxes)


def get_stackable_boxes(box, boxes):
    for i, top_box in enumerate(boxes):
        if box.can_stack(top_box):
            return boxes[i:]
    return None

class Box(object):
    def __init__(self, width, height, length):
        self.width = width
        self.height = height
        self.length = length

    def can_stack(self, top_box):
        return (
            self.width > top_box.width and
            self.height > top_box.height and
            self.length > top_box.length
        )

    def __repr__(self):
        return 'Box(%s, %s, %s)' % (self.width, self.height, self.length)


class Test(unittest.TestCase):
    def setUp(self):
        b1 = Box(1,1,1)
        b2 = Box(2,2,2)
        b3 = Box(3,3,3)
        self.boxes1 = [b1,b2,b3]

        b4 = Box(1,1,1)
        b5 = Box(3,2,2)
        b6 = Box(3,3,3)
        self.boxes2 = [b4,b5,b6]

        b7 = Box(6,4,4)
        b8 = Box(7,5,5)
        b9 = Box(7,8,2)
        self.boxes3 = [b7,b8,b9]

        b10 = Box(5,5,5)
        self.boxes4 = [b10]

    
    def test_max_stack_height(self):
        self.assertEqual(max_stack_height(self.boxes1), 6)
        self.assertEqual(max_stack_height(self.boxes2), 4)
        self.assertEqual(max_stack_height(self.boxes3), 9)
        self.assertEqual(max_stack_height(self.boxes4), 5)


if __name__ == '__main__':
    unittest.main()

8.12 Eight Queens – CCI

# [8.12] Eight Queens: Write an algorithm to print all ways of
# arranging eight queens on an 8x8 chess board so that none
# of them share the same row, column, or diagonal. In this case,
# "diagonal" means all diagonals, not just the two that bisect
# the board.

import unittest

def queens(num_queens):
    results = []
    grid_size = num_queens
    columns = [None]*num_queens
    n_ways(columns, 0, results, grid_size)
    return results


def n_ways(columns, row, results, grid_size):
    
    if row == grid_size:
        results.append(columns)
        return

    for col in range(0, grid_size):
        if is_valid(columns, row, col, grid_size):
            cols_copy = columns[:]
            cols_copy[row] = col
            n_ways(cols_copy, row+1, results, grid_size)


def is_valid(columns, row1, col1, grid_size):
    
    if col1 in columns:
        return False

    for row2, col2 in enumerate(columns):
        if col2 is not None:
            if abs(col1 - col2) == abs(row1 - row2):
                return False

    return True


class Test(unittest.TestCase):
    
    def test_queens(self):
        self.assertEqual(len(queens(8)), 92)

if __name__ == '__main__':
    unittest.main()

8.11 Coins – CCI

# [8.11] Coins: Given an infinite number of quarters, dimes, 
# nickels, and pennies, write code to calculate the number of 
# ways of representing n cents.

import unittest

def change(amount):
    coins = [25,10,5,1]
    return change_helper(amount, 0, coins)

def change_helper(amount, denom, coins):
    if denom == 3:
        return 1
    elif amount < 0:
        return 0

    denom_amount = coins[denom]
    subtract_denom = change_helper(amount-denom_amount, denom, coins)
    move_to_next_denom = change_helper(amount, denom+1, coins)
    return subtract_denom + move_to_next_denom

class Test(unittest.TestCase):
    
    def test_change(self):
        self.assertEqual(change(10), 4)
        self.assertEqual(change(15), 6)


if __name__ == '__main__':
    unittest.main()

8.10 Paint Fill – CCI

# [8.10] Paint Fill: Implement the "paint fill" function that 
# one might see on many image editing programs. That is, given
# a screen (represented by a two-dimensional array of colors),
# a point, and a new color, fill in the surrounding area until 
# the color changes from the original color.

import unittest

def paint_fill(grid, row, col, color):
    target_color = grid[row][col]
    paint_fill_helper(grid, row, col, target_color, color)
    
def paint_fill_helper(grid, row, col, color_from, color_to):
    if not coords_in_bounds(grid, row, col):
        return

    if grid[row][col] == color_from:
        grid[row][col] = color_to
        paint_fill_helper(grid, row-1, col, color_from, color_to)
        paint_fill_helper(grid, row+1, col, color_from, color_to)
        paint_fill_helper(grid, row, col-1, color_from, color_to)
        paint_fill_helper(grid, row, col+1, color_from, color_to)


def coords_in_bounds(grid, row, col):
    row_in_bounds = row < len(grid) and row >= 0
    col_in_bounds = col < len(grid[0]) and col >= 0
    return row_in_bounds and col_in_bounds

class Test(unittest.TestCase):
    def setUp(self):
        self.grid = [
            ['white', 'white','red','red'],
            ['white', 'white','white','white'],
            ['white', 'white','white','white'],
            ['blue', 'blue','white','white'],
            ['blue', 'blue','white','white'],
        ]
        self.result = [
            ['blue', 'blue','red','red'],
            ['blue', 'blue','blue','blue'],
            ['blue', 'blue','blue','blue'],
            ['blue', 'blue','blue','blue'],
            ['blue', 'blue','blue','blue'],
        ]

    
    def test_paint_fill(self):
        paint_fill(self.grid, 0, 0, 'blue')
        self.assertEqual(self.grid, self.result)


if __name__ == '__main__':
    unittest.main()

8.9 Parens – CCI

# [8.9] Parens: Implement an algorithm to print all valid (e.g
# properly opened and closed) combinations of n pairs of
# parentheses

# EXAMPLE: 
# Input: 3
# Output: ((())), (()()), (())(), ()(()), ()()()

import unittest

def parens(n):
    result = []
    parens_helper('', 0, 0, n, result)
    return result

def parens_helper(s, left, right, n, result):
    if left == n and right == n:
        result.append(s)

    if left < n:
        parens_helper(s + '(', left+1, right, n, result)

    if right < left:
        parens_helper(s + ')', left, right+1, n, result)


class Test(unittest.TestCase):
    def setUp(self):
        self.result = ['((()))', '(())()', '()()()', '()(())', '()()()', '(()())']
    
    def test_parents(self):
        self.assertEqual(set(parens(3)), set(self.result))


if __name__ == '__main__':
    unittest.main()

8.8 Permutation with Dups – CCI

# [8.8] Permutation with Dups: Write a method to computer all
# permutations of a string whose characters are not necessarily
# unique. The list of permutations should not have duplicates.

import unittest

def perms_with_dups(s):
    char_count = get_char_count(s)
    result = []
    perms_with_dups_helper('', char_count, len(s), result)
    return result

def perms_with_dups_helper(s, char_count, n, result):
    if len(s) == n:
        result.append(s)

    for char in char_count:

        if char_count[char] == 1:
            del char_count[char]
        else:
            char_count[char] -= 1

        perms_with_dups_helper(s + char, char_count, n, result)

        if not char in char_count:
            char_count[char] = 1
        else:
            char_count[char] += 1


def get_char_count(s):
    char_count = {}
    for char in s:
        if char not in char_count:
            char_count[char] = 1
        else:
            char_count[char] += 1

    return char_count

class Test(unittest.TestCase):
    
    def setUp(self):
        self.result = ['aaac', 'aaca', 'acaa', 'caaa']

    def test_perms_with_dups(self):
        self.assertEqual(set(perms_with_dups('aaac')), set(self.result))


if __name__ == '__main__':
    unittest.main()

8.7 Permutations without Duplicates – CCI

  • we can find all permutations starting with a certain char by prepending it to all the permutations of the remaining characters
  • by recursively calling on subsequently smaller groups of chars, we can return the result
# [8.7] Permutations without Dups: Write a method to compute
# all permutations of a string of unique characters.

import unittest

def perms_with_dups(s):
    if len(s) == 1:
        return [s]

    result = []
    for char_index in range(len(s)):
        active_char = s[char_index]
        remaining = s[:char_index] + s[char_index+1:]
        remaining_perms = perms_with_dups(remaining)
        perms = [active_char + perm for perm in remaining_perms]
        result.extend(perms) 

    return result

class Test(unittest.TestCase):
    
    def setUp(self):
        self.result = ['abc','acb','bac','bca','cab','cba']

    def test_perms_with_dups(self):
        self.assertEqual(set(perms_with_dups('abc')), set(self.result))


if __name__ == '__main__':
    unittest.main()

8.6 Towers of Hanoi – CCI

# [8.6] Towers of Hanoi: In the classic problem of the Towers
# of Hanoi, you have 3 towers and N disks of different sizes
# which can slide onto any tower. The puzzle starts with disks
# sorted in ascending order of size from top to bottom (i.e.
# each disk sits on top of an even larger one). You have the 
# following constraints:

# (1) Only one disk can be moved at a time
# (2) A disk is slid off the top of one tower onto another
# (3) A disk cannot be placed on top of a smaller disk

# Write a program to move the disks from the first tower to the
# last using stacks.

import unittest

def hanoi(towers, n, start, temp, end):
    if n > 0:
        hanoi(towers, n-1, start, end, temp)
        if towers[start]:
            disk = towers[start].pop()
            towers[end].append(disk)
        hanoi(towers, n-1, temp, start, end)
    

class Test(unittest.TestCase):
    def setUp(self):
        self.towers = [[5,4,3,2,1], [], []]
        self.result = [[], [], [5,4,3,2,1]]
    
    def test(self):
        hanoi(self.towers, len(self.towers[0]), 0, 1, 2)
        self.assertEqual(self.towers, self.result)

if __name__ == '__main__':
    unittest.main()

8.5 Recursive Multiply – CCI

# [8.5] Recursive Multiply: Write a recursive function to
# multiply two positive integers without using the * 
# operator. You can use addition, subtraction, and bit 
# shifting, but you should minimize the number of those
# operations.

#Time and Space Complexity 1: O(k)
#Time and Space Complexity 2: O(log(k))
# k is the smaller integer

import unittest

def r_multiply1(a,b):
    if a == 1:
        return b

    if a < b:
        small = a
        large = b
    else:
        large = a
        small = b

    return r_multiply1(a - 1, b) + b

def r_multiply2(a,b):
    if a < b:
        small = a
        large = b
    else:
        large = a
        small = b

    if small == 1:
        return large

    s = small >> 1
    half_prod = r_multiply2(s, large)

    if small % 2 == 1:
        return half_prod + half_prod + large

    return half_prod + half_prod

class Test(unittest.TestCase):
    
    def test_r_multiply1(self):
        self.assertEqual(r_multiply1(4,2),8)
        self.assertEqual(r_multiply1(4,3),12)
        self.assertEqual(r_multiply1(3,4),12)
        self.assertEqual(r_multiply1(4,1),4)
        self.assertEqual(r_multiply1(1,6),6)

    def test_r_multiply2(self):
        self.assertEqual(r_multiply2(4,2),8)
        self.assertEqual(r_multiply2(4,3),12)
        self.assertEqual(r_multiply2(3,4),12)
        self.assertEqual(r_multiply2(1,6),6)
        self.assertEqual(r_multiply2(4,1),4)
        
if __name__ == "__main__":
    unittest.main()