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

5.8 Draw Line – CCI

# [5.8] Draw Line: a monochrome screen is stored as a single
# array of bytes allowing eight consecutive pixels to be stored
# in one byte. The screen has width w, where w is divisible by
# 8 (that is, no byte will be split across rows). The height
# of the screen, of course, can be derived from the length of the
# array and the width. Implement a function that draws a 
# horizontal line from (x1, y) to (x2, y).

# The method signature should look something like:
# drawLine(byte[] screen, int width, int x1, int x2, int y)

import unittest

def draw_line(screen, width, x1, x2, y):
    index_start = y*width + x1
    line_width = x2 - x1 + 1
    for i in xrange(line_width):
        screen[index_start + i] = 255

class Test(unittest.TestCase):

    def setUp(self):
        self.screen = []
        self.blank_byte = 0
        self.filled_byte = 255
        self.width = 3
        self.height = 4

        for i in xrange(self.width * self.height):
            self.screen.append(self.blank_byte)
    
    def test_draw_line(self):
        draw_line(
            screen = self.screen,
            width = self.width,
            x1 = 1,
            x2 = 2,
            y = 1
        )
        result = [self.blank_byte]*4 + [self.filled_byte]*2 + [self.blank_byte]*6
        self.assertEqual(self.screen,result)

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

5.7 Pairwise Swap – CCI

# [5.7] Pairwise Swap: Write a program to swap odd and even bits
# in an integer with as few instructions as possible (e.g., bit
# 0 and bit 1 are swapped, bit 2 and bit 3 and swapped, and so on)

import unittest

def pairwise_swap(num):
    
    even_mask = create_even_mask(num)
    odd_mask = create_odd_mask(num)
    even_cleared = num & even_mask
    odd_cleared = num & odd_mask
    combined = (odd_cleared >> 1) | (even_cleared << 1)
    return (odd_cleared >> 1) | (even_cleared << 1)

def create_odd_mask(num):
    bin_representation = bin(num)[2:]
    bit_length = len(bin_representation)
    bit_sign = '0'
    mask = []

    for i in range(bit_length):
        mask.insert(0, bit_sign)
        bit_sign = '1' if bit_sign =='0' else '0'

    return int(''.join(mask),2)

def create_even_mask(num):
    bin_representation = bin(num)[2:]
    bit_length = len(bin_representation)
    bit_sign = '1'
    mask = []

    for i in range(bit_length):
        mask.insert(0, bit_sign)
        bit_sign = '1' if bit_sign =='0' else '0'

    return int(''.join(mask),2)


class Test(unittest.TestCase):
    
    def test_create_even_mask(self):
        self.assertEqual(create_even_mask(int('111000', 2)), int('010101',2))
        self.assertEqual(create_even_mask(int('1110000', 2)), int('1010101',2))

    def test_create_odd_mask(self):
        self.assertEqual(create_odd_mask(int('111000', 2)), int('101010',2))
        self.assertEqual(create_odd_mask(int('11100110', 2)), int('10101010',2))

    def test_pairwise_swap(self):
        self.assertEqual(pairwise_swap(int('111000',2)), int('110100',2))
        self.assertEqual(pairwise_swap(int('11100111',2)), int('11011011',2))

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

5.6 Conversion – CCI

# [5.6] Conversion: Write a function to determine the number of
# bits you would need to flip to convert integer A to integer B.

# EXAMPLE
# Input: 29 (or: 11101), 15 (or: 01111)
# Output: 2

import unittest

def test_flip_to_make_equal(n1, n2):
    different_bits = n1 ^ n2
    count = 0
    while different_bits:
        different_bits = different_bits & (different_bits - 1)
        count += 1
    return count

class Test(unittest.TestCase):
    
    def test_flip_to_make_equal(self):
        self.assertEqual(test_flip_to_make_equal(29, 15), 2)


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

5.5 Debugger – CCI

# [5.5] Debugger: Explain what the following code does:
# ((n & (n-1)) == 0)

# n & (n-1) removes the most least significant 1
# if the result is zero, means there was only one
# one-bit. This means the number was a power of two

import unittest

def check_power_of_two(n):
    return ((n & (n-1)) == 0)

class Test(unittest.TestCase):
    
    def test_check_power_of_two(self):
        self.assertTrue(check_power_of_two(2))
        self.assertTrue(check_power_of_two(4))
        self.assertTrue(check_power_of_two(8))
        self.assertTrue(check_power_of_two(16))

        self.assertFalse(check_power_of_two(3))
        self.assertFalse(check_power_of_two(5))
        self.assertFalse(check_power_of_two(9))
        self.assertFalse(check_power_of_two(17))


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

5.4 Next Number – CCI

# [5.4] Next Number: Given a positive integer, print the next
# smallest and the next largest number that have the same number
# of 1 bits in their binary representation.

import unittest

def get_next_bin_same_ones(num):
    higher_bin = higher_bin_same_ones(num)
    lower_bin = lower_bin_same_ones(num)
    return (lower_bin, higher_bin)

def higher_bin_same_ones(num):
    count_zeros = 0
    count_ones = 0
    current_bit = num & 1

    while count_ones == 0 or current_bit == 1:
        if current_bit == 1:
            count_ones += 1
        else:
            count_zeros += 1

        current_bit = (num >> count_ones + count_zeros) & 1
        
    pos = count_ones + count_zeros
    flipped_num = (1 << pos ^ num)
    cleared_num = flipped_num & (~0 << pos)
    ones_mask = (1 << (count_ones - 1) ) - 1
    return cleared_num | ones_mask

def lower_bin_same_ones(num):
    count_zeros = 0
    count_ones = 0
    current_bit = num & 1

    while count_zeros == 0 or current_bit == 0:
        if current_bit == 1:
            count_ones += 1
        else:
            count_zeros += 1

        current_bit = (num >> count_ones + count_zeros) & 1
        
    pos = count_ones + count_zeros
    flipped_num = (1 << pos) ^ num
    cleared_num = flipped_num & (~0 << pos)
    ones_mask = (1 << (count_ones + 1) ) - 1
    ones_mask_shifted = (ones_mask << (pos - (count_ones + 1)))
    return cleared_num  | ones_mask_shifted

class Test(unittest.TestCase):
    
    def test_higher_bin_same_ones(self):
        self.assertEqual(higher_bin_same_ones(39), 43)
        self.assertEqual(higher_bin_same_ones(10), 12)
        self.assertEqual(higher_bin_same_ones(60), 71)

    def test_lower_bin_same_ones(self):
        self.assertEqual(lower_bin_same_ones(39), 30)
        self.assertEqual(lower_bin_same_ones(60), 58)

    def test_get_next_bin_same_ones(self):
        self.assertEqual(get_next_bin_same_ones(39), (30, 43))
        self.assertEqual(get_next_bin_same_ones(60), (58, 71))


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