EPI-BootCamp-Recursion-Triominoes

Triominoes.py

"""
EPI - Recursion

Review:
1. Recursion is suitable for problems:
    decomposing a complex problem into a set of similar instances,
    searching, enumeratation, divide-and-conquer, etc. 
2. Recursion is consits of 
    1) base cases; 2) recursion stack, i.e. calling the same 
    function with different arguments
3. Divide-and-Conquer (DnC): decomposing a problem into smaller,
    *independent* smaller problems such as MergeSort, QuickSort
4. Recursion is more general than DnC:
    a single subproblem, such as binary tree
    overlapping subproblems (i.e. recursion with same argument
    more than once), then Dynamic Programming with memoization
    not be same type as original, such as regular expressoin matching
5. Use recursion as an alternative to deeply nested iterations,
    in case of undefined number of levels, e.g. IP address problems
    generalized to k substring. 
6. Sometimes, to improved runtime with reduced space,  
    DnC is implemented using iteration over recursion
"""
"""
BootCamp Question 1:
1) Write a GCD function of x and y
   if y > x, GCD(x,y) = GCD(y-x,x) = GCD(y%x,x)

def GCD(x, y):
    # base case
    if y == 0:
        return x
    return GCD(y % x, x)
"""
"""
BootCamp Question 2:

Trinomino Puzzle: 
Divide-and-Conquer into 4 identical subproblems.
Every 2**n x 2**n chessboard with one square removed can be tiled 
using L-shaped triominoes, each covering three squares at a time.

Task: 
Given an integer power, constructs 2**power x 2**power chessboard.
Also given coordinate of missing squre, assign it with maximum possible
unique Trinomino ID.

Example:
Input: 
    power = 2, 
    missingXY=(2**power-1, 2**power-1)

Construct
board = [ [0,0,0,0],
          [0,0,0,0],
          [0,0,0,0],  
          [0,0,0,6] ]

Output:
board = [ [1,1,2,2],
          [1,3,3,2],
          [4,3,5,5],  
          [4,4,5,6] ]
where 1,2,3,4 and 5 are unique triomino IDs,
6 indicates the missing squre. 

"""
def Trinomino(board, n, missingXY):
    def DnC(board, n):
        # base case
        if n == 1:
            return

        # for tracking unique trinomino (L-shaped) ID
        global ID
        upperL, upperR = board[:n//2, :n//2 ], board[n//2:, :n//2 ]
        lowerL, lowerR = board[:n//2,  n//2:], board[n//2:,  n//2:]

        ID += 1
        if upperL.any():
            #ID += 1             #[[6 0 0 0]
            upperR[0, -1] = ID  # [0 0 1 0]
            lowerL[-1, 0] = ID  # [0 1 1 0]
            lowerR[0, 0] =  ID  # [0 0 0 0]]

        lowerL[0, -1] = 1
        upperR[-1, 0] = 1
        lowerR[0, 0] = 1
        elif lowerL.any():
            #ID += 1
            upperL[-1, -1] = ID
            upperR[0, -1] =  ID
            lowerR[0, 0] =   ID
        elif upperR.any():
            #ID += 1
            upperL[-1, -1] = ID
            lowerL[-1, 0] = ID
            lowerR[0, 0] =   ID
        else:
            #ID += 1
            upperL[-1, -1] = ID
            lowerL[-1, 0] = ID
            upperR[0, -1] =  ID

        DnC(upperL, n//2)
        DnC(lowerL, n//2)
        DnC(upperR, n//2)
        DnC(lowerR, n//2)
        return board
    ### main in Trinomino()
    return DnC(board, n)
### main
import numpy as np
power = 2
N = 2**power
#missingXY = (0, 0)
missingXY = (N-1, N-1)
ID = 0
maxID = N*N//3+1
board = np.array([[ maxID if (x, y) == missingXY else 0 \
                    for x in range(N)]
                    for y in range(N)])
print(Trinomino(board, N, missingXY))