Showing posts with label coding challenges. Show all posts
Showing posts with label coding challenges. Show all posts

Friday, July 28, 2023

Pythonic Coding Exercises: Recursion

Target audience: Intermediate
Estimated reading time: 4'
The most effective way to truly grasp a programming language is by diving in and tackling unique algorithm challenges. In this article, we'll explore common uses of recursion, taking full advantage of Python's dynamic capabilities.

Let's look at some coding gems and have the fun begin!!

Table of contents

       Find a line with max number of points

Follow me on LinkedIn

What you will learn: How to apply recursion in Python to solve search, optimization and computational problems.

Note: The implementation uses Python 3.11

Introduction

Recursion involves solving a problem by breaking it down into simpler instances of the same problem. Essentially, it's a method where a procedure references itself during its execution.

Tail recursion, a specific kind of recursion, occurs when the function's last action is a recursive call. It's optimized to prevent unnecessary stacking, allowing the recursive calls to delve deeper without overwhelming the call stack.

Implicit recursion is another variant where a function indirectly calls itself, without an overt recursive statement

Coding exercises

Find a line with max number of points

ProblemGiven n points on a 2-dimension plane, find the maximum number of points that lie on the same line.

Solution From the mathematics standpoint, N points with coordinates (x, y) are aligned if slope dy/dx between each of these N points are the same (i.e. (1, 1), (3, 3) and (6, 6) belongs to line y = 3.x). This implementation uses recursion. We define a data class Point with basic == and slope computation methods. Time complexity O(n).

Implementation:

from dataclasses import dataclass
from typing import TypeVar, List, Set, Dict
Point = TypeVar("Point")


@dataclass
class Point(object):
    """ 
      Convenient class wrapper to implement the == operator and computation of the derivative 
    """
    x: int
    y: int

    # Override == operator for this class
def __eq__(self, other: Point) -> bool: return self.x == other.x and self.y == other.y  
    # Compute the derivative/sloped between any two points
    def slope(self, other: Point) -> float:
        if self == other:          # To safe guard against self
            return -1.0
        elif self.x == other.x:  # To avoid divide by zero
            return 1e+8
        else:                          # Otherwise compute the derivative
            return float(self.y - other.y)/(self.x - other.x)




def max_num_points(points: List[Point]) -> List[Point]:
  """ 
   Compute the number of points which belongs to the same line (same slope) using recursion
  """
    
   # Execute recursion along the list of points using  list index
   def align(index: int, visited: Dict[float, List[Point]]) -> Dict[float, List[Point]]:
      if index >= len(points) - 1:
         return visited
      else:
        for pt in points:
                
           # Make sure we exclude a data point already visited
           if not points[index] == pt:
              this_slope = points[index].slope(pt)
              # Update or create
              new_visited: List[Point] = visited[this_slope] if this_slope in visited else []

             # Avoid duplicate list of points associated with
              if pt not in new_visited:
                  new_visited.append(pt)

                 # Update the dictionary { slope: list of points with same slope }
                 visited[this_slope] = new_visited

            return align(index+1, visited)
 

 if len(points) == 0:
    return [] 
 else:
   all_slopes_dict = align(0, {})

   # Finally extract the list of points associated with
   # a slope with maximum number of points.
   max_num_pts = -1
   output_points = None
   for slope, points in all_slopes_dict.items():
      if max_num_pts < len(points):
         max_num_pts = len(points)
         output_points = points

   return output_points


Test:
input_points = [
  Point(1, 1), Point(2, 4), Point(3, 3), Point(4, 1), Point(5, 11), Point(6, 6), Point(8, 13)
]

print(str(max_num_points(input_points))) 
    # [Point(x=3, y=3), Point(x=6, y=6), Point(x=1, y=1)]



Optimize coins distribution

ProblemFind the minimum set of coins for a set of coin_types (1 cent, 5 cents  ... 10 cents) required to foot a given bill (meet a target_amount). For example  168 = 100 cents * 1 + 50 cents * 1 + 10  cents * 2 + 5 cent * 1 + 1 cent * 3.

Solution Use recursion, minimizing the number of coins needs to reach the needed amount at each step. The recursion exits when either all the various type of coins have been used or the target amount has been finally reached. The time complexity is O(n)

Implementation:

class CoinsDistribution(object):
    """
        Find the optimal distribution of set of coins (1 cent, 5 cent, 10 cent,..)
        to foot a given bill (i.e. 127 cents = 100 cents*1 + 25 cents*1 + 1 cent* 2
        Recursion on the remaining amount to close once a coin if found
    """
    def __init__(self, coins: []):
        # We do not assume the coins are actually sorted
        self.coin_types = sorted(coins, reverse=True)

    
    def find(self,  target_amount: int) -> List[int]:

        def _find(left_over_amount: int, index: int, coin_distribution: List[int]) -> List[int]:
            # Recursion exit condition (amount reached or no more coin left)
            if left_over_amount == 0 or index >= len(self.coin_types):
                return coin_distribution
            
           else:
                remaining_amount = left_over_amount

                # Attempt to assign as many coins for this category of coins
                while remaining_amount >= self.coin_types[index]:
                    remaining_amount -= self.coin_types[index]
                    coin_distribution[index] += 1
                # Move to the next type of coin
                return _find(remaining_amount, index+1, coin_distribution)

        return _find(target_amount, 0, [0] * len(self.coin_types))


Test:
coin_types = [1, 5, 10, 25, 50, 100]
target_amount = 376
coins_distribution = CoinsDistribution(coin_types)
distribution = coins_distribution.find(target_amount)

acc = [f'{distribution}*{coins_distribution.coin_types[index]}'
           for index, distribution in enumerate(distribution) if distribution > 0]
print(' + '.join(acc))  # 3*100 + 1*50 + 1*25 + 1*1



Test if a list has a cycle

Problem: Find if a list, input_values has a cycle. The problem is equivalent to finding the first duplicate in a list.

Solution: Use two iterators: the second iterator advancing twice as fast the first one. Time complexity O(n).

Implementation:
def has_cycle(input_values: List[int]) -> bool:
  """ Test if a list has a duplicate or a cycle, using two iterator """
  iter1 = iter(input_values)
  iter2 = iter(input_values)

  try:
    while True:
      value1 = next(iter1)
      next(iter2)               # Iter2 advances two elements per iteration
      value2 = next(iter2)
            
      if value1 == value2:
          return True        # Find & exit

  except StopIteration as e:
    return False

Test:
values1 = [2, 4, 6, 3, 11, 7, 9, 14, 17]
values2 = [2, 4, 6, 3, 11, 6, 9, 14, 17]

print(has_cycle(values1))  # False
print(has_cycle(values2))  # True


Intersection of sorted arrays

ProblemFind the intersection of two sorted lists list1 and list2 of integers.

Solution: Map the two lists of integer n to lists of tuples (n, list_index) and push the tuples into a priority queue using heaps module. Record two consecutive items, from two different list popped from the priority queue having the same value. The time complexity is O(long + n) ~ O(n)

Implementation:
def intersect_sorted_lists(list1: List[int], list2: List[int]) -> List[int]:
  """ 
    Extract the intersection of two sorted list of different size using 
    a priority queue and recursion
  """
    
  # Taken care of the basic case
  if list1[-1] < list2[0] or list1[0] > list2[-1]:
     return []

  else:
     # Otherwise convert integers, n into tuple (n, list_index)
     import heapq

     pqueue = []
     [heapq.heappush(pqueue, (item, 0)) for item in list1]
     [heapq.heappush(pqueue, (item, 1)) for item in list2]

     # Recursively popping up tuples from the priority queue
     def intersect(new_tuple: Tuple, tuples_list: List[Tuple]) -> List[Tuple]:
       if len(pqueue) == 0: # Our recursion exit condition
         return tuples_list
       else:
         # Next tuple in the priority queue
         item, index = heapq.heappop(pqueue)
                
         # If two consecutive integers from different list have the same value...
         if new_tuple[1] == item and index != new_tuple[0]:
           tuples_list.append(new_tuple)
         return intersect((index, item), tuples_list)


     first_item, first_index = heapq.heappop(pqueue)
     intersect_tuples = intersect((first_item, first_index), [])
        
     return [item for _, item in intersect_tuples]

Test:
values1 = [0, 2, 8, 10, 12, 34, 46, 48, 54, 99]
values2 = [3, 8, 6, 12, 14, 15, 18, 19, 22, 40, 41, 44, 45, 46, 50, 53]

print(intersect_sorted_lists(values1, values2))  # [8, 12, 46]


Sequence of consecutive integers with highest sum

Problem: Find the sequence of num_items consecutive integers from a given list, input_list which produces the highest sum. For example, extracting 3 consecutive integers with highest sum from the list [2, 1, 5, 9, 3, 2] will produce [5, 9, 3]

Solution: Implements an efficient tail recursion to generate a tuple (sum of the sequence, starting index of the  sequence).

Implementation:
def extract_seq_max_sum(input_list: List[int], num_items: int) -> (int, int):
  """ Extract the sequence of consecutive integers with the maximum summation """

  def _extract_seq_max_sum(
     input_list: List[int],
     num_items: int,
     max_sum: int,
     start_index: int,
     cnt: int) -> (int, int):
        
     # Condition to exit the recursion
     if len(input_list) < num_items:
       return max_sum, start_index
 
     new_sum = sum(input_list[:num_items])
     new_max_sum, new_start_index = \ 
        \(new_sum, cnt) if new_sum > max_sum \ 
         else (max_sum, start_index)
     
     return _extract_seq_max_sum(input_list[1:], num_items, new_max_sum, new_start_index, cnt + 1)

  return _extract_seq_max_sum(input_list, num_items, 0, 0, 0)



Test:
values = [4, 2, 8, 6, 12, 34, 6, 8, 4, 9, 11, 2, 17, 22, 5, 8, 6, 1, 4, 13, 19]

print(extract_seq_max_sum(values, 3))  # 52, 3  [6, 12, 34]
print(extract_seq_max_sum(values, 5))  # 66, 6  [8, 6, 12, 34, 6]


Longest sequence of increasing values

Problem: Extract the longest sequence of increasing values from an arbitrary list of integers. For instance the longest sequence of increasing value in [2, 1, 4, 5, 8, 3, 5, 0, 2] is [4, 5, 8].

Solution: Implements a recursion longest_increasing_seq over the input list of integers by tracking the sequence contains the current value and comparing with the current longest sequence of increasing value. The recursion walks through the input values using an iterator.

Implementation:
def longest_increasing_seq(input_values: List[int]) -> List[int]:
  """ Extract the longest increasing sequence of integer from a list using recursion."""
 
 def longest_increasing_seq(
    input_values_iter,
    cur_increasing_seq: List[int],
    longest_seq: List[int]) -> List[int]:

    while True:
      try:
         # Next element in the list
         next_element = next(input_values_iter)

         # If current increasing list empty or new element > last element
         # add the new element in the current list and continue
         if len(cur_increasing_seq) == 0 or next_element > cur_increasing_seq[-1]:
            cur_increasing_seq.append(next_element)
         
         # Otherwise complete the current increasing sequence and
         # update the longest list if necessary
         else:
            new_longest_seq = cur_increasing_seq.copy() \
               if len(cur_increasing_seq) > len(longest_seq) \
               else longest_seq

            # Re-initialize the current increasing list
            cur_increasing_seq.clear()
            cur_increasing_seq.append(next_element)
          
            # Invoke the next recursion
return longest_increasing_seq(input_values_iter, cur_increasing_seq, new_longest_seq)  
     except StopIteration as e: # Exit point for recursion
        return longest_seq

  return longest_increasing_seq(iter(input_values), [], [])


Test:
values = [6, 1, 4, 9, 11, 22, 17, 8, 6, 1, 4, 13, 19]  
print(str(longest_increasing_seq(values)))      # 1, 4, 9, 11, 22
 

List of items which value equals its index

Problem: Find the integers in a list which value equals its index. For example the algorithm should select the second item 1 from the list  [3, 1, 5, 0].

Solution: Simple traversal with a time complexity O(n).

Implementation:
def get_values_eq_index(input_list: List[int]) -> List[int]:
  """
    Retrieve the list of element for which the value is equal to its index in the list
  """
  match len(input_list):
    case 0:
      return []
    case 1:
      return input_list
    case _:
      return [el for index, el in enumerate(input_list) if index == el]


Test:
input_list = [2, 9, 2, 5, 4, 8, 1, 5, 8, 10]
print(get_values_eq_index(input_list))           # 8


Find first duplicate in a list

Problem: Find the first duplicate in a string.

Solution: Use a set to keep track of visited nodes. Worst case time complexity O(n). This is an example for which recursion is not warranted.

Implementation:
def get_first_duplicate(input_str: AnyStr) -> Optional[AnyStr]:
  """Get the first char duplicate in a string if found, None otherwise"""

  match len(input_str):
    case 0: return None
    case 1: return input_str[0]   # Return the only element
    case _:                                # After dealing with the first special cases
       unique_set = set()
       for ch in input_str:
          if ch in unique_set:
             return ch
          unique_set.add(ch)

       return None

Test:
input_str1 = "helo"
input_str2 = "hello"

print(get_first_duplicate(input_str1))  # None
print(get_first_duplicate(input_str2))  # 'l'


Check if a binary tree is balanced

Problem: Test whether a binary tree defined its node, Node, is balanced. Every path between the root and any leaf should have the same number of nodes.

Solution: Apply an in-order-traversal to collect the number of nodes of all the various lineages, root to leaves then compute the difference of longest and shortest lineages. The traversal of the tree, method, __walk uses recursion. Time complexity O(n). 

Implementation:
class Node(object):
  """ Basic binary tree node """
  def __init__(self, data: int):
    self.left = None
    self.right = None
    self.data = data


  def add(self, data: int) -> NoReturn:
     """
        Simple insertion to a binary tree, appending a new node if necessary
     """
    if data < self.data:
      if self.left:
        self.left.add(data)
      else:
        self.left = BinTreeNode(data)
    elif data > self.data:
        if self.right:
          self.right.add(data)
        else:
          self.right = BinTreeNode(data)
    else:
        self.data = data


  def is_balanced(self) -> bool:
    path_acc = []
    self.__walk('', path_acc)

    if path_acc:
      # Measure the length of the various paths from root to leaves
      path_sizes = [len(x) for x in path_acc if x != '']
      return max(path_sizes) - min(path_sizes) < 1

    else:
      return True


    # ---------   Private helper method ---------

  def __walk(self, path: AnyStr, lineages: List[AnyStr]):
    """ DFS walk """
    if self.left:   # This node has a left child
      self.left.__walk(f'{path}L', lineages)
      lineages.append(path)
        
    if self.right:   # This node has a right childe
      self.right.__walk(f'{path}R', lineages)
      lineages.append(path)


Test:
root = Node(1)
values = [2, 9, 8, 10, 13, 7]
[root.add(n) for n in values]
print(root.is_balanced())        # False

root = Node(10)
values = [6, 14, 4, 8, 12, 16]
[root.add(n) for n in values]
print(root.is_balanced())        # True


Thank you for reading this article. For more information ...

References


---------------------------
Patrick Nicolas has over 25 years of experience in software and data engineering, architecture design and end-to-end deployment and support with extensive knowledge in machine learning. 
He has been director of data engineering at Aideo Technologies since 2017 and he is the author of "Scala for Machine Learning" Packt Publishing ISBN 978-1-78712-238-3