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

8.4 Power Set – CCI

  • When adding an element to a set, we can find all new subsets by taking all the old subsets, duplicating them, and adding the new element to each
  • By making recursive calls to smaller sets, we can use this calculation to get all subsets
# [8.4] Power Set: Write a method to return all subsets of
# a set.

import unittest

def get_subsets(a_set):
    if len(a_set) == 1:
        return [set(), a_set]

    current_item = a_set.pop()
    smaller_set = get_subsets(a_set)
    copy_smaller_set = [item.copy() for item in smaller_set]
    
    for item in copy_smaller_set:
        item.add(current_item)

    return copy_smaller_set + smaller_set



class Test(unittest.TestCase):
    
    def setUp(self):
        self.results = get_subsets(set([1,2,3]))
        self.answer = [
            set([]), 
            set([1]),
            set([2]), 
            set([3]),
            set([1, 2]), 
            set([1, 3]), 
            set([2, 3]), 
            set([1, 2, 3])
        ]


    def test_get_subsets(self):
        self.assertEqual(len(self.results), 8)
        self.assertTrue(self.check_lists_equal(self.results, self.answer))


    def check_lists_equal(self, list1, list2):
        if len(list1) != len(list2):
            return False

        for a_set in list1:
            if not a_set in list2:
                return False

        return True


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

8.3 Magic Index – CCI

# [8.3] Magic Index: A magic index in an array A[0...n-1] is
# defined to be an index such that A[i] = i. Given a sorted
# array of distinct integers, write a method to find a magic
# index, if one exists, in array A.

# FOLLOW UP: What if the values are not distinct?

import unittest

def find_magic_index(arr):
    return find_magic_index_helper(arr, 0, len(arr))

def find_magic_index_helper(arr, start, end):

    if end < start:
        return False
    
    mid = (start + end) / 2

    if arr[mid] == mid:
        return mid
    elif arr[mid] < mid:
        return find_magic_index_helper(arr, mid+1, end)
    else:
        return find_magic_index_helper(arr, start, mid-1)

def find_magic_index_not_distinct(arr):
    return find_magic_index_not_distinct_helper(arr, 0, len(arr))

def find_magic_index_not_distinct_helper(arr, start, end):
    if end < start or start == len(arr):
        return False
    
    mid = (start + end) / 2
    
    if arr[mid] == mid:
        return mid
    else:
        return (
            find_magic_index_not_distinct_helper(arr, mid+1, end) 
            or 
            find_magic_index_not_distinct_helper(arr, start, mid-1)
        )


class Test(unittest.TestCase):
    
    def test_find_magic_index(self):
        self.assertEqual(find_magic_index([0,2,3,4]), 0)
        self.assertEqual(find_magic_index([-1,0,1,3]), 3)
        self.assertEqual(find_magic_index([-2,1,4,5,6,7]), 1)
        self.assertEqual(find_magic_index([-2,2,4,5,6,7]), False)

    def test_find_magic_index(self):
        self.assertEqual(find_magic_index_not_distinct([0,0,0,0]), 0)
        self.assertEqual(find_magic_index_not_distinct([0,0,3,3]), 3)
        

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

8.2 Robot in a Grid – CCI

# [8.2] Robot in a Grid: Imagine a robot sitting on the upper
# left corner of grid with r rows and c columns. The robot can
# only move in two directions, right and down, but certain
# cells are "off limits" such that the robot cannot step on
# them. Design an algorithm to find a path for the robot from
# the top left to the bottom right.


import unittest

def find_exit(maze):
    failed = {}
    return find_exit_helper(maze, failed, len(maze)-1, len(maze[0])-1)

def find_exit_helper(maze, failed, r, c):
    # coordinates have already been evaluated to not work
    if (r,c) in failed:
        return failed[(r,c)]

    # coordinates fail if they are out of bounds of the maze
    if r < 0 or c < 0:
        failed[(r,c)] = False
        return False

    # coordinates fail if there is a blocking pattern
    if maze[r] == 1:
        failed[(r,c)] = False
        return False

    # if the robot reaches coordinate 0,0 return that coordinate
    if r == 0 and c == 0:
        return [(r,c)]

    # recursively call on space above and to the left
    result = find_exit_helper(maze, failed, r-1, c) or find_exit_helper(maze, failed, r, c-1)
    
    # if robot eventually gets to coord 0,0 the path will be returned
    # otherwise will evaluate to False
    if result:
        return result + [(r,c)]
    else:
        return result

class Test(unittest.TestCase):
    
    def setUp(self):
        self.maze = [
            [0,0,0,0,0,0],
            [1,0,0,0,1,1],
            [1,1,0,0,1,1],
            [1,1,1,0,0,0],
            [1,1,0,1,1,0]
        ]

        self.maze2 = [
            [0,0,0,0,0,0],
            [1,0,0,0,1,1],
            [1,1,0,0,1,1],
            [1,1,1,1,0,0],
            [1,1,0,1,1,0]
        ]

    def test_find_exit(self):
        self.assertTrue(isinstance(find_exit(self.maze),list))
        self.assertFalse(isinstance(find_exit(self.maze2),list))
        

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

8.1 Triple Step – CCI

# [8.1] Triple Step: A child is running up a staircase with n
# steps and can hop either 1 step, 2 steps, or 3 steps at a 
# time. Implement a method to count how many possible ways
# the child can run up the stairs.

import unittest

def fib(n):
    if n < 1:
        raise ValueError('Must be positive Integer')
    elif n < 3:
        return 1
    elif n < 4:
        return 2
    else:
        a = 1
        b = 1
        c = 2
        d = 4

        for i in xrange(n-4):
            a = b
            b = c
            c = d
            d = a + b + c

        return d

def fib_r(n):
    memo = {}
    return fib_r_helper(n, memo)

def fib_r_helper(n, memo):
    if n in memo:
        return memo[n]

    if n < 1:
        raise ValueError('Must be positive Integer')
    elif n < 3:
        return 1
    elif n < 4:
        return 2
    else:
        result = fib_r(n-1) + fib_r(n-2) + fib_r(n-3)
        memo[n] = result
        return result



class Test(unittest.TestCase):
    
    def test_fib(self):
        self.assertEqual(fib(1), 1)
        self.assertEqual(fib(2), 1)
        self.assertEqual(fib(3), 2)
        self.assertEqual(fib(4), 4)
        self.assertEqual(fib(5), 7)
        self.assertEqual(fib(6), 13)
        self.assertRaises(ValueError, fib, -1)

    def test_fib_r(self):
        self.assertEqual(fib_r(1), 1)
        self.assertEqual(fib_r(2), 1)
        self.assertEqual(fib_r(3), 2)
        self.assertEqual(fib_r(4), 4)
        self.assertEqual(fib_r(5), 7)
        self.assertEqual(fib_r(6), 13)
        self.assertRaises(ValueError, fib_r, -1)



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