Updates from January, 2017 Toggle Comment Threads | Keyboard Shortcuts

  • loctv 11:43 pm on January 31, 2017 Permalink | Reply
    Tags: ,   

    Problem: Partition a number into two divisible parts 

    *Difficulty: Easy
    Given a number (as string) and two integers a and b, divide the string in two non-empty parts such that the first part is divisible by a and second part is divisible by b. If string can not be divided into two non-empty parts, output “-1”, else print the two parts.

    Input:

    The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consists of single line containing 3 space seperated number denoting the respective values of  n, a and b.
    Output:

    For each test case output a single line containing the two space seperated non-empty parts else print -1.
    Constraints:

    1<=T<=100

    1<=N<=106

    1<=a,b<=N
    Example:

    Input:

    3
    1200 4 3
    123 12 3
    125 12 5

    Ouput:

    12 00
    12 3
    -1

    Approach:
    With Python in my pocket, I don’t think this problem deserves a medium-hard rank. The constraints is not hard, 10^6 means the length of the longest input number is just 6. The only thing to keep in mind is alway think of exceptions. Exceptions here are two case, number with length 1 and 2.

    Implementation: Python2.7

    #code
    def partitionToTwoPart(number, a, b):
        number = str(number)
        if len(number) < 2:
            return -1
        elif len(number) == 2:
            first, second = number[0], number[1]
            if int(first) % a == 0 and int(second) % b == 0:
                return first, second
            else:
                return -1
        else:
            for i in range(1, len(number)):
                first, second = number[:i], number[i:]
                if int(first) % a == 0 and int(second) % b == 0:
                    return first, second
            else:
                return -1
    
    def main():
        t = input()
        for _ in range(t):
            n, a, b = map(int, raw_input().strip().split())
            result = partitionToTwoPart(n, a, b)
            if result != -1:
                print result[0], result[1]
            else:
                print -1
    if __name__ == '__main__':
        main()
    
    Advertisements
     
  • loctv 5:49 pm on January 30, 2017 Permalink | Reply
    Tags: ,   

    Problem: Replace O’s with X’s 

    *Difficulty: Medium
    Given a matrix of size NxM where every element is either ‘O’ or ‘X’, replace ‘O’ with ‘X’ if surrounded by ‘X’. A ‘O’ (or a set of ‘O’) is considered to be by surrounded by ‘X’ if there are ‘X’ at locations just below, just above, just left and just right of it.

    Examples:

    Input: mat[N][M] =  {{'X', 'O', 'X', 'X', 'X', 'X'},
                         {'X', 'O', 'X', 'X', 'O', 'X'},
                         {'X', 'X', 'X', 'O', 'O', 'X'},
                         {'O', 'X', 'X', 'X', 'X', 'X'},
                         {'X', 'X', 'X', 'O', 'X', 'O'},
                         {'O', 'O', 'X', 'O', 'O', 'O'},
                        };
    Output: mat[N][M] =  {{'X', 'O', 'X', 'X', 'X', 'X'},
                          {'X', 'O', 'X', 'X', 'X', 'X'},
                          {'X', 'X', 'X', 'X', 'X', 'X'},
                          {'O', 'X', 'X', 'X', 'X', 'X'},
                          {'X', 'X', 'X', 'O', 'X', 'O'},
                          {'O', 'O', 'X', 'O', 'O', 'O'},
                        };
    
    
    Input: mat[N][M] =  {{'X', 'X', 'X', 'X'}
                         {'X', 'O', 'X', 'X'}
                         {'X', 'O', 'O', 'X'}
                         {'X', 'O', 'X', 'X'}
                         {'X', 'X', 'O', 'O'}
                        };
    Input: mat[N][M] =  {{'X', 'X', 'X', 'X'}
                         {'X', 'X', 'X', 'X'}
                         {'X', 'X', 'X', 'X'}
                         {'X', 'X', 'X', 'X'}
                         {'X', 'X', 'O', 'O'}
                        };

    Input:
    The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains two integers N and M denoting the size of the matrix. Then in the next line are N*M space separated values of the matrix.

    Output:
    For each test case print the space separated values of the new matrix.

    Constraints:
    1<=T<=10
    1<=mat[][]<=100
    1<=n,m<=20

    Example:
    Input:

    2
    1 5
    X O X O X
    3 3
    X X X X O X X X X
    Output:
    X O X O X
    X X X X X X X X X

    Approach:
    The problem’s description is not clear enough. Just imagine that you’re playing Go, O is black and X is white, if a territory of black is surrounded by white, then all cells in that territory are replaced by white.
    Problem’s difficulty is medium because the code is pretty long (I suppose)

    Algorithm:
    1. Get all O groups
    2. From those groups, get groups that are surrounded by X
    3. Replace O groups by X
    Simple, isn’t it?

    Implementation: Python 2.7

    def getAllOGroups(matrix):
        markedO, groups = [], []
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if not (i, j) in markedO and matrix[i][j] == 'O':
                    tempGroup = []
                    #get all adjacent O
                    getAllAdjacentOFrom(i, j, matrix, tempGroup, markedO)
                    groups.append(tempGroup)
        return groups
    
    def getAllAdjacentOFrom(i, j, matrix, tempGroup, markedO):
        tempGroup.append((i, j))
        markedO.append((i, j))
        #up
        i_up, j_up = i-1, j
        if isInBound(i_up, j_up, matrix) and (i_up, j_up) not in markedO and matrix[i_up][j_up] == 'O':
            getAllAdjacentOFrom(i_up, j_up, matrix, tempGroup, markedO)
        #down
        i_down, j_down = i+1, j
        if isInBound(i_down, j_down, matrix) and (i_down, j_down) not in markedO and matrix[i_down][j_down] == 'O':
            getAllAdjacentOFrom(i_down, j_down, matrix, tempGroup, markedO)
        #left
        i_left, j_left = i, j-1
        if isInBound(i_left, j_left, matrix) and (i_left, j_left) not in markedO and matrix[i_left][j_left] == 'O':
            getAllAdjacentOFrom(i_left, j_left, matrix, tempGroup, markedO)
        #right
        i_right, j_right = i, j+1
        if isInBound(i_right, j_right, matrix) and (i_right, j_right) not in markedO and matrix[i_right][j_right] == 'O':
            getAllAdjacentOFrom(i_right, j_right, matrix, tempGroup, markedO)
    
    def getGroupsSurroundedByX(groups, matrix):
        surroundedGroups = []
        for groupO in groups:
            if len([(i, j) for (i,j) in groupO if isSurroundedByX(i, j, matrix)]) == len(groupO):
                surroundedGroups.append(groupO)
        return surroundedGroups
    
    def isSurroundedByX(i, j, matrix):
        xUp = False
        for _ in range(i-1, -1, -1):
            if matrix[_][j] == 'X':
                xUp = True
                break
        xDown = False
        for _ in range(i+1, len(matrix)):
            if matrix[_][j] == 'X':
                xDown = True
                break
        xLeft = False
        for _ in range(j-1, -1, -1):
            if matrix[i][_] == 'X':
                xLeft = True
                break
        xRight = False
        for _ in range(j+1, len(matrix[0])):
            if matrix[i][_] == 'X':
                xRight = True
                break
        return xUp == xDown == xLeft == xRight == True
    
    def isInBound(i, j, matrix):
        return i >= 0 and i < len(matrix) and j >= 0 and j < len(matrix[0])
    
    def replaceOByX(surroundedGroups, matrix):
        for group in surroundedGroups:
            for (i, j) in group:
                matrix[i][j] = 'X'
    
    def printFormated(matrix):
        for row in matrix:
            for cell in row:
                print cell,
        print
    
    def main():
        t = input()
        for _ in range(t):
            n, m = map(int, raw_input().strip().split())
            arr = raw_input().strip().split()
            matrix = [arr[i:i+m] for i in range(0, len(arr), m)]
            #get all O-groups
            groups = getAllOGroups(matrix)
            #get groups that are surrounded by X
            surroundedGroups = getGroupsSurroundedByX(groups, matrix)
            #replace O with X
            replaceOByX(surroundedGroups, matrix)
            printFormated(matrix)
            
            
    if __name__ == '__main__':
        main()
    
    
     
  • loctv 8:14 pm on January 29, 2017 Permalink | Reply
    Tags: ,   

    Problem: Help a Thief!!! 

    *Difficulty: Basic

    You have to help a thief to steal as many as GoldCoins as possible from a GoldMine. There he saw N Gold Boxes an each Gold Boxes consists of Ai Plates each plates consists of Aj Gold Coins, Each Box consist of plates with exactly same number of GoldCoins per plate. Your task is to print the maximum gold coins theif can steal.

    Input:
    First line consists of T test cases. Each test case consists of three lines.
    First line of each test case consistss of an Integer nT denoting the number of plates theif can steal.
    Second line of each test case consists of an Integer N denoting the number of Gold Boxes available in the gold mine.
    Third line of each test case consists of 2*N spaced Integers Ai,Aj dentoning number of plates in each box and number of gold coins in each plates respectively.

    Output:
    Print the respective result in each line.

    Constraints:
    1<=T<=20
    1<=nT,Ai<=20
    1<=N<=20
    1<=Aj<=100

    Example:
    Input:

    1
    3
    3
    1 3 2 2 3 1
    Output:
    7

    Implementation: Python 2.7

    #code
    def sortByGoldCoins(goldBoxes):
        return sorted(goldBoxes, key=lambda goldBox: goldBox[1], reverse=True)
    
    def helpThief(goldBoxes, platesCanSteal):
        maxGoldCoins, i = 0, 0
        while platesCanSteal > 0:
            if platesCanSteal >= goldBoxes[i][0]:
                maxGoldCoins += goldBoxes[i][1] * goldBoxes[i][0]
                platesCanSteal -= goldBoxes[i][0]
                i += 1
            else:
                maxGoldCoins += platesCanSteal * goldBoxes[i][0]
                platesCanSteal = 0
        return maxGoldCoins
    
    def main():
        t = input()
        for _ in range(t):
            nT = input()
            N = input()
            goldBoxes = map(int, raw_input().strip().split())
            plates = [goldBoxes[i] for i in range(len(goldBoxes)) if i % 2 == 0]
            goldCoins = [goldBoxes[i] for i in range(len(goldBoxes)) if i % 2 != 0]
            goldBoxes = zip(plates, goldCoins)
            goldBoxes = sortByGoldCoins(goldBoxes)
            #print goldBoxes
            print helpThief(goldBoxes, nT)
    
    if __name__ == '__main__':
        main()
    

     

     
  • loctv 1:52 pm on January 27, 2017 Permalink | Reply
    Tags: ,   

    Problem: Tom and String 

    *Difficulty: Very Easy

    Tom is a Geek, he has a following string Initial which consists of the following letters in the mentioned order:“abcdefghijklmnopqrstuvwxyz1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ”.

    He also has various lists of strings, and now he wants to compute the Hash value of each list of strings.
    So, the Hash is the summation of all the character values in the input:(currentIndex + (position of the character In the string initial) ). And then this hash is multiplied by the Number of strings in the list.

    Let’s assume that the list of strings is: [“aA1”, “b”]. So, his answer would be:
    a: 0 + 0 = 0.
    A: 1 + 36 = 37.
    1: 2 + 26 = 28.
    b: 0 + 1 = 1

    .So, 2 * (0 + 1 + 37 + 28) = 2 * (66) = 132.

     

    Input:

    The first line will contain number of test cases T. Then T Test cases follow. For every test case, on a single line, there will be N number of string s all of them separated by a space, denoting all the strings of that particular list of strings.

     

    Output:

    Print the required hash for each of the mentioned list of strings.

     

    Constraints:

    1 ≤ Test Cases ≤ 50
    1 ≤ Length of a string ≤ 30
    1 ≤ Number of strings in a list ≤ 20

     

    Example:

    Input           
    3
    aA1 b
    a b c d
    aa BB cc DD
    Output
    132
    24
    640

     

    Explanation:

    For the First Test Case
    (0 + 1 + 37 + 28) = 2 * (66) = 132

    For the Second Test Case

    a: 0 + 0 = 0
    b: 0 + 1 = 1
    c: 0 + 2 = 2
    d: 0 + 3 = 3

    .So, 4* (0 + 1 + 3 + 4) = 4 * (6) = 24

    For the Third Test Case

    a: 0 + 0 = 0
    a: 1 + 0 = 1

    B: 0 + 37 = 37
    B: 1 + 37 = 38

    c: 0 + 2 = 2
    c: 1 + 2 = 3

    D: 0 + 39 = 39
    D: 1 + 39 = 40

    So, 4* (0 + 1 + 37+ 38 + 2 + 3 + 39 + 40) = 4 * (160) = 640

    Implementation: Python 2.7

    #code
    def hashValOf(listStrings, initString="abcdefghijklmnopqrstuvwxyz1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ"):
        hashVal = 0
        for string in listStrings:
            for index, c in enumerate(string):
                hashVal += index + initString.find(string[index]) 
        return hashVal*len(listStrings)
    
    def main():
        t = input()
        for _ in range(t):
            listStrings = raw_input().strip().split()
            print hashValOf(listStrings)
    
    if __name__ == '__main__':
        main()
    
    
     
  • loctv 12:33 pm on January 27, 2017 Permalink | Reply
    Tags: ,   

    Problem: Reverse Coding 

    *Difficulty: Easy
    Sherlock Being tired with the usual coding rounds started growing his interest towards reverse coding when he won the event in his college symposium. He wondered if his friend has the brain to quickly identify the pattern and verify if his inputs are correct or not. From the example portion given below, where you will be given a number(n) and its output, Using this find the pattern. Your task is that from the pattern you identified above, You have to tell if for the given n whether the given m is the correct answer or not…

    Input:
    The first line consists of T, the number of test cases. then T lines follow. Each line consists of n and m.

    Output:
    For each n and m output 1 if m is the corresponsing input for the value of n and 0 otherwise.

    Constraints:
    1<=t<=50
    0<=n<=1000
    0<=m<=10^6

    Example to identify the pattern :

    Input                            Output

    10                                 55

    20                                 210

    5                                   15

    0                                    0

    1                                    1

    2                                    3

    Example:
    Input:
    4
    10 55
    4 11
    2  3
    6 21

    Output:
    1
    0
    1
    1

    Hint:
    Pattern here is : Sum of first n natural numbers
    Sn = n*(n+1)/2

    Implementation: Python 2.7

    #code
    def isCorrect(n, m):
        correctValue = (n*(n+1))//2
        return m == correctValue
    
    def main():
        t = input()
        for _ in range(t):
            n, m = map(int, raw_input().strip().split())
            print 1 if isCorrect(n, m) else 0
    
    if __name__ == '__main__':
        main()
    
     
  • loctv 8:59 pm on January 26, 2017 Permalink | Reply
    Tags: ,   

    Problem: Flood Fill Algorithm 

    *Difficulty: Easy

    Given a 2D screen, location of a pixel in the screen ie(x,y) and a color(K), your task is to replace color of the given pixel and all adjacent same colored pixels with the given color K.

    Input:
    The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains Two integers N and M denoting the size of the matrix. Then in the next line are N*M space separated values of the matrix. Then in the next line are three values x, y and K.

    Output:
    For each test case print the space separated values of the new matrix.

    Constraints:
    1<=T<=10
    1<=M[][]<=100

    Example:
    Input:

    2
    3 4
    0 1 1 0 1 1 1 1 0 1 2 3
    0 1 5
    2 2
    1 1 1 1
    0 1 8

    Output:
    0 5 5 0 5 5 5 5 0 5 2 3
    8 8 8 8

    Implementation: Python 2.7

    def floodFill(rootColor, visited, screen, replaceColor, x, y):
        # set color of x,y on the screen
        screen[x][y] = replaceColor
        # mark them as visited
        visited.append((x, y))
        # get all 4 directions 
        # first I make a mistake, I get all 8 directions
        # but in the end, it's wrong
        all_directions = [(x-1, y), (x, y+1),
                            (x+1, y), (x, y-1)]
        # filter those 4 directions
        # only get which one is in screen, not yet visited and has rootColor
        all_directions = filter(lambda coor: isInScreen(coor[0], coor[1], screen) and not (coor[0], coor[1]) in visited and screen[coor[0]][coor[1]] == rootColor , all_directions)
        # recursive call for those all directions
        for (next_x,next_y) in all_directions:
            floodFill(rootColor, visited, screen, replaceColor, next_x, next_y)
        
    
    # check if (x, y) is in screen (not out of bound)
    def isInScreen(x, y, screen):
        return x >= 0 and x < len(screen) and y >= 0 and y < len(screen[0])
    
    def printScreen(screen):
        for row in screen:
            for col in row:
                print col,
        print
    
    def main():
        t = input()
        for _ in range(t):
            n, m = map(int, raw_input().strip().split())
            arr = map(int, raw_input().strip().split())
            x, y, replaceColor = map(int, raw_input().strip().split())
            screen, visited = [], []
            # convert list-like array to matrix (actually is a list of list)
            for i in range(0, len(arr), m):
                screen.append(arr[i:i+m])
            rootColor = screen[x][y]
            floodFill(rootColor, visited, screen, replaceColor, x, y)
            printScreen(screen)
            
    if __name__ == '__main__':
        main()
    
     
  • loctv 1:43 am on January 26, 2017 Permalink | Reply  

    Problem: Sum of All Subarrays 

    *Difficulty: Medium

    Given an array A with N elements , you need to find the sum all sub arrays of array A. Since the sum could be very large print the sum modulo (10^9+7).

    Input :
    The first line contains integer T, denoting number of test cases. The first line of each test case contains an integer N, denoting the number of elements.The second line of each test case contains N space separated integers denoting values of the array A.
    Output :
    Print the answer of each test case in a new line.

    Constraints :
    1<=T<=10
    1<=N<=10^5

    Example
    Input :

    2
    3
    1 2 3
    2
    1 3

    Output :
    20
    8

    *Approach 1:

    Generate all sub arrays
    This is O(n^3) complexity solution

    Code: Python 2.7

    def sum_all_sub_arrs(arr):
        if len(arr) == 1:
            return arr[0]
        elif len(arr) == 2:
            return arr[0] + arr[1] + sum(arr)
        elif len(arr) == 3:
            return sum(arr)*2 + arr[0] + arr[1] + arr[1] + arr[2]
        else:
            sum_all = 0
            for i in range(2, len(arr)):
                for j in range(len(arr)):
                    #print arr[j:j+i]
                    sum_all += sum(arr[j:j+i])
                    if j+i == len(arr):
                        break
            return sum_all + sum(arr)*2
    
    if __name__ == '__main__':
        t = input()
        for _ in range(t):
            n = input()
            arr = map(int, raw_input().strip().split())
            print sum_all_sub_arrs(arr) % (10**9+7)
    

    It cant be applied to solve this problem, since if using C++, I can barely pass this problem with runtime nearly reach 5 seconds. (This is Python, so it’s impossible)

    After 30 minutes working on papers, I figured out something’s interesting.
    Example with input array’s length is odd
    Array: 1 2 3 4 5
    Sum of all sub-arrays:
    1 + 2 + 3 + 4 + 5 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 1 + 2 + 3 + 2 + 3 + 4+ 3 + 4 + 5 + 1 + 2 + 3 + 4 + 2 + 3 + 4 + 5 + 1 + 2 + 3 +4 + 5 = 105
    Here’s is the array and the number of times of each element in the equation above:
    Array:              1 – 2 – 3 – 4 – 5
    Frequency:     5 – 8 – 9 – 8 – 5
    Example with input array’s length is even
    Array: 1 2 3 4
    Sum of all sub-arrays:
    1 + 2 + 3 + 4 + 1 + 2 + 2 + 3 + 3 +4 + 1 +2 +3 + 2 + 3 + 4 + 1 +2 + 3 + 4 = 50
    Array:           1 – 2 – 3 – 4
    Frequency: 4 – 6 – 6 – 4
    In general:
    + if length of input array is odd, and n is the length
    Frequency: n –  prev+(n-2)  – prev+(n-4) – … – prev+1  – … – prev+(n-4)  – prev+(n-2) – n
    + if length of input array is even, and n is the length
    Frequency: n – prev+(n-2) – prev+(n-4) – ….. – prev+(n-4) – prev+(n-2) – n

    Code: Python 2.7

    def sum_all_sub_arrs(arr):
        # input array contains only one element
        if len(arr) == 1:
            return arr[0]
        # init steps
        frequency = [0]*len(arr)
        dif = len(arr)-2
        # because frequency values are symmetric
        # example: 4 6 6 4
        #          3 4 3
        #          etc
        # we need to traverse only half first of the input array
        # and work out the frequency of each value
        for i in range(0, len(arr)//2 + 1 if len(arr) % 2 != 0 else len(arr)//2):
            # first frequency = len(arr)
            if i == 0:
                frequency[i] = len(arr)
            # then, each of next element is its previous cell plus difference
            # and decrease the difference by 2
            else:
                frequency[i] += (frequency[i-1] + dif)
                dif -= 2
        # half left of frequency
        for i in range(len(arr)//2+1 if len(arr) % 2 != 0 else len(arr)//2, len(arr)):
            offset = len(arr) - i - 1 
            frequency[i] = frequency[offset]
        return sum(x*y for (x,y) in zip(arr, frequency))
    
    if __name__ == '__main__':
        t = input()
        mod = 10**9 + 7
        for _ in range(t):
            n = input()
            arr = map(int, raw_input().strip().split())
            print sum_all_sub_arrs(arr) % mod
    

    Solution took: 94ms

     
  • loctv 11:33 pm on January 23, 2017 Permalink | Reply  

    Feeling tired!zzzzZz!!!

     
  • loctv 11:22 pm on January 23, 2017 Permalink | Reply
    Tags: ,   

    Problem: Largest Divisibility Test 

    *Difficulty: Medium

    Babul’s favourite number is 17. He likes the numbers which are divisible by 17. This time what he does is that he takes a number N and tries to find the largest number which is divisible by 17, by rearranging the digits. As the number increases he gets puzzled with his own task. So you as a programmer have to help him to accomplish his task.

    Note: If the number is not divisible by rearranging the digits, then print “Not Possible”. N may have leading zeros.

    Input:
    The first line of input contains an integer T denoting the no of test cases. Each of the next T lines contains the number N.

    Output:
    For each test case in a new line print the desired output.

    Constraints:
    1<=T<=100
    1<=N<=10^10

    Example:
    Input:

    4
    17
    43
    15
    16

    Output:
    17
    34
    51
    Not Possible

    My approach: (it might be not an elegant, efficient solution, but it works).

    Generate all permutations of number n, then check each permutation for 17-divisibility.
    If there is no number divisible by 17, return None, otherwise, return max of those numbers.

    I dont consider my solution is not cheating. I use Python since it has an enormous  amount of packages that support problem solving.
    **’Life is short, why haven’t you learned Python yet?’ 🙂

    Implementation: Python 2.7

    import itertools
    
    def largest_divisible_of(number):
        """
            generate all permutations of a number and 
            check each permutation if it is divisible by 17
            number: type string
            return: None if there is no number divisible by 17,
                    otherwise, return max
        """
        divisibles = list(''.join(x) for x in itertools.permutations(list(number)) if int(''.join(x)) % 17 == 0)
        return None if len(divisibles) == 0 else max(divisibles)
        
    if __name__ == '__main__':
        t = input()
        for _ in range(t):
            n = raw_input().strip()
            result = largest_divisible_of(n)
            print result if result is not None else 'Not Possible'
    

    Solution took: 3.112 seconds (still < 5s)

     
  • loctv 2:11 am on January 23, 2017 Permalink | Reply
    Tags: ,   

    Problem: 

    *Difficulty: Medium

    Given a matrix containing lower alphabetical characters only, we need to count number of palindromic paths in given matrix. A path is defined as a sequence of cells starting from top-left cell and ending at bottom-right cell. We are allowed to move to right and down only from current cell.

    Input:
    The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consists of two lines.
    First line of each test case consist of two space separated integers R and C, denoting the number of element in a row and column respectively.
    Second line of each test case consists of R*C space separated chars denoting the elements in the matrix in row major order.

    Output:
    It should be single line output, Print the respective output in the respective line.

    Constraints:
    1<=T<=20
    1<=R,C<=10

    Example:
    Input:

    1
    3 4
    a a a b b a a a a b b a

    Output:
    3

    Approach: Recursion

    Source: Algorithms

    Example:

    print-all-paths-example

    As we can only move right or down, we need to keep track of when we reach the bottom or the right side. As soon as we reach those, we either go right straight to the destination or go down straight to the destination (As described in the photo above). So the recursion will have two recursion calls and two base cases. One recursion call to move right (increase col), and one to move down (increase row), one base case when we reach bottom and one when we reach right side. In my opinion, it’s easier to implement problem solving in Python, so let’s get started.
    But before we jump in to the code, here’s the picture shows how the recursion works under the hood:

    PrintAllPaths.png

    Implementation: Python 2.7

    def all_paths(matrix, row, col, path, paths):
        """
            generate all possible paths from top-left to botrom right
            by only moving right and down from current cell.
        """
        # touch the bottom, go all the way right to destination
        if row == len(matrix)-1: 
            for i in range(col, len(matrix[0])):
                path += matrix[row][i]
            paths.append(path)
            return
        # touch the right side, go all the way down to destination
        if col == len(matrix[0])-1:
            for i in range(row, len(matrix)):
                path += matrix[i][col]
            paths.append(path)
            return
        path += matrix[row][col]
        # go right
        all_paths(matrix, row+1, col, path, paths)
        # and go down
        all_paths(matrix, row, col+1, path, paths)    
    
    def is_palindrom(string):
        bound = len(string) // 2
        for i in range(bound):
            if string[i] != string[len(string)-1-i]:
                return False
        return True
    
    if __name__ == '__main__':
        t = input()
        for _ in range(t):
            n, m = map(int, raw_input().strip().split())
            line = raw_input().strip().split()
            matrix = []
            for i in range(0, len(line), m):
                matrix.append(line[i:i+m])
            all_possible_paths, count_palindroms = [], 0
            all_paths(matrix, 0, 0, "", all_possible_paths)
            for path in all_possible_paths:
                if is_palindrom(path):
                    count_palindroms += 1
            print count_palindroms
    
    
     
c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel