Updates from loctv Toggle Comment Threads | Keyboard Shortcuts

  • loctv 2:02 pm on March 3, 2019 Permalink | Reply
    Tags:   

    Hackerrank: Waiter 

    You are a waiter at a party. There are  stacked plates on pile A0. Each plate has a number written on it. Then there will be Q iterations. In i-th iteration, you start picking up the plates in  Ai-1 from the top one by one and check whether the number written on the plate is divisible by the i-th prime. If the number is divisible, you stack that plate on pile Bi . Otherwise, you stack that plate on pile Ai. After Q iterations, plates can only be on pile B1,B2,..,Bq,Aq. Output numbers on these plates from top to bottom of each piles in order of B1,B2,…,Bq,Aq.

    Input Format

    The first line contains two space separated integers, N and Q.
    The next line contains N space separated integers representing the initial pile of plates, i.e., A0. The leftmost value represents the bottom plate of the pile.

    Constraints

    • 1 <= N <=5 * 10^4
    • 2 <= number_ith <= 10^4
    • 1 <= Q <= 1200

    Output Format

    Output N lines. Each line contains a number written on the plate. Printing should be done in the order defined above.

    Sample Input 0

    5 1
    3 4 7 6 5
    

    Sample Output 0

    4
    6
    3
    7
    5
    

    Explanation 0

    Initially:

     A0 = [3, 4, 7, 6, 5]<-TOP

    After 1 iteration:

     A0 = []<-TOP

     B1 = [6, 4]<-TOP

     A1 = [5, 7, 3]<-TOP

    We should output numbers in B1  first from top to bottom, and then output numbers in A1 from top to bottom.

    Sample Input 1

    5 2
    3 3 4 4 9
    

    Sample Output 1

    4
    4
    9
    3
    3
    

    Explanation 1

    Initially:

    A0 = [3, 3, 4, 4, 9]<-TOP

    After  iteration:

    A0 = []<-TOP

    B1 = [4, 4]<-TOP

    B2 = [9, 3, 3]<-TOP

    After  iteration:

    A1 = []<-TOP

    B1 = [4, 4]<- TOP

    B2 = [3, 3, 9]<-TOP

    We should output numbers in B1  first from top to bottom, and then output numbers in B2 from top to bottom.


    You can tell that the Explanation 1 is wrong but it doesn’t matter. The problem description is quite confusing, but it’s really simple.

    You’re given a set and you have to split that set into two separate parts, one that is divisible by some prime numbers, and the other isn’t. The visible part are constructed by multiple stacks. Each iteration i-th, you go through the stack A, if any element in stack A is divisible by i-th prime, put it into a stack B i-th, otherwise put it back in a new stack of A, which will reverse the original stack.

    Later on, either when new stack A is empty or we run out of the iteration loop, we go through the stacks B, pop out each element in each stack and print it out. Then go through the final stack A, which might or might not be empty.


    This my the solution in Java.

    https://github.com/MrNocTV/Algorithms/blob/master/SolvedProblems/HackerRank/src/Waiter.java

    Advertisements
     
  • loctv 10:20 am on March 3, 2019 Permalink | Reply  

    Hackerrank: Game of Two Stacks 

    Alexa has two stacks of non-negative integers, stack A = [a0, a1, …, an-1]  and stack  B = [b0, b1, …, bm-1] where index 0 denotes the top of the stack. Alexa challenges Nick to play the following game:

    • In each move, Nick can remove one integer from the top of either stack  A or stack B.
    • Nick keeps a running sum of the integers he removes from the two stacks.
    • Nick is disqualified from the game if, at any point, his running sum becomes greater than some integer  given at the beginning of the game.
    • Nick’s final score is the total number of integers he has removed from the two stacks.

    Given A, B, and x for g games, find the maximum possible score Nick can achieve (i.e., the maximum number of integers he can remove without being disqualified) during each game and print it on a new line.

    Input Format

    The first line contains an integer, g (the number of games). The 3*g subsequent lines describe each game in the following format:

    1. The first line contains three space-separated integers describing the respective values of n (the number of integers in stack A), m  (the number of integers in stack B), and x (the number that the sum of the integers removed from the two stacks cannot exceed).
    2. The second line contains n  space-separated integers describing the respective values of a0, a1, …, an-1.
    3. The third line contains m space-separated integers describing the respective values of b0, b1, …, bm-1.

    Constraints

    • 1 <= g <= 50
    • 1 <= n,m <= 10^5
    • 0 <= ai, bj <= 10^6
    • 1 <= x <= 10^9

    Subtasks

    • 1 <= n,m <= 100 for 50% for  of the maximum score.

    Output Format

    For each of the g  games, print an integer on a new line denoting the maximum possible score Nick can achieve without being disqualified.

    Sample Input 0

    1
    5 4 10
    4 2 4 6 1
    2 1 8 5
    

    Sample Output 0

    4
    

    Explanation 0

    The two stacks initially look like this:

    image

    The image below depicts the integers Nick should choose to remove from the stacks. We print  as our answer, because that is the maximum number of integers that can be removed from the two stacks without the sum exceeding .

    image

    (There can be multiple ways to remove the integers from the stack, the image shows just one of them.)


    To be honest, I spent an hour on this problem and couldn’t find the optimal solution. Obviously, you can say that there is a brute force solution, but it takes O(2^k), k is the longest steps that can be achieved. Because for each step, we can either go with the top of A or B. Hence, we need two recursive call each steps, or two “branches” each steps. According to Cracking the Coding Interview, time complexity for these problems is O(branches^depth). Replace depth with k, branches with 2.

    I was just thinking, to get the longest path, can we just chose the number from either A or B that from that point, we can continue with the furthest distance. Let say we can choose either 5 from A or 6 from B, if we choose 5, we can chop out 5 more elements in A, but if we choose 6 we can chop out 6 elements in B, hence we will choose B. This is short of a greedy solution, and greedy won’t yield optimal result all the time.

    So I click on the Editorial part. The editorial doesn’t tell you exactly what is the idea behind the solution, it just says “here is how you solve it”.

    The idea is, the longest sequence we can achieve can be formed by either chopping top of A or B continuously until we run out of gas. The format of the final sequence can be:

    + 5 top elements of A, 4 top elements of B
    + 4 top elements of A, 0 top elements of B

    The final form is:
    + k1 top elements of A, k2 top elements of B

    I think until this point you can probably think of a solution, but if you can’t, let’s continue reading.

    To get:
    + 5 top of A, 4 top of B.
    We can go from
    + 9 top of A, 0 top of B.
    + 8 top of A, 1 top of B.
    ….
    + 5 top of A, 4 top of B.

    You got the idea, right?


    This is the solution in Java, it might not be the most elegant solution but it gets the job done.

    https://github.com/MrNocTV/Algorithms/blob/master/SolvedProblems/HackerRank/src/GameOfTwoStacks.java

     
  • loctv 5:22 pm on February 27, 2019 Permalink | Reply
    Tags:   

    Hackerrank : Maximum Element 

    You have an empty sequence, and you will be given N queries. Each query is one of these three types:

    1 x  -Push the element x into the stack.
    2    -Delete the element present at the top of the stack.
    3    -Print the maximum element in the stack.
    

    Input Format

    The first line of input contains an integer, N. The next N lines each contain an above mentioned query. (It is guaranteed that each query is valid.)

    Constraints
    1 <= N <= 10^5
    1 <= x <= 10^9
    1 <= type <= 3

    Output Format

    For each type  query, print the maximum element in the stack on a new line.

    Sample Input

    10
    1 97
    2
    1 20
    2
    1 26
    1 20
    2
    3
    1 91
    3
    

    Sample Output

    26
    91

    First thing you should notice is the constraint:
    1 <= N <= 10^5
    Most of the time, if you see the constraint is 10^5 (ten to the power of 5), it means your solution must be at most O(n log n) or better.

    Okey, since it’s marked as “Easy” so there will be no hidden things that you need to figure out. Basically you need to build a stack and get the biggest elements in the stack and quick / fast as possible, so this is all about data structure.

    Obviously we need a stack, to push and pop items as required. But how can we tell which item in the stack is biggest.

    The easiest solution is go through the stack and get the max item. It works but it’s too slow. The time complexity will be O(n^2), roughly.

    Method1: 
    We can use an additional collection, like a Heap, more specifically, a MaxHeap to store the elements in order. To insert an item to a Heap, it is O(n log n), to remove an item in a heap, it’s aso O(n log n). Finally, this is what we want, to get the biggest element as fast as possible. Specifically for MaxHeap, the top will be the biggest element. Overall this will work and the time complexity will be roughly O(n log n). The hardest thing is to implement the MaxHeap yourself.

    Method2:
    This is more “language-oriented”. It removes the “re-invent the wheel” part, no need to implement MaxHeap yourself.
    In Java we have a SortedSet, it’s really fast for adding item as well as lookup smallest/largest item. The only problem though, is duplicated items. We need to watch out for duplicated items. Obviously, because set only stores non duplicated items. We can use a Map to store the item and its frequency. When the frequency goes down to 1, we know that we can remove the item from the set, as well as the frequency map. This is relatively fast, but it consumes a lot of spaces. It’s O(n) in space complexity.

    Method3:
    This is when “algorithm” comes to handy. Let’s say we need to insert an item, and also we need to know what is the maximum value after we insert the new item. If this still isn’t enough for you then please continue reading. So instead of just saving an item, you can also save the max value so far given the new item, also we need a global max variable to know the max value so far. The item on the top of the stack is guaranteed to be paired with the biggest element. When the stack is empty we need to reset the maximum value and when popping item out of stack, we need to update the global max value (if needed).

    There may be more solutions for this problem but these are what I’ve come up with.

    Here’s the sample code if you get trouble implementing the mentioned solutions.


    Method2:
    https://github.com/MrNocTV/Algorithms/blob/master/SolvedProblems/HackerRank/src/MaximumElement1.java

    Method3:
    https://github.com/MrNocTV/Algorithms/blob/master/SolvedProblems/HackerRank/src/MaximumElement2.java

     
  • loctv 3:58 pm on February 27, 2019 Permalink | Reply  

    A little talk for my comeback! 

    Hi every one, long time no see. It’s been a long time since the last time I did write some blogs. Recently I’ve just quit my job and I’ve been looking for a new one, so it’s about time to get back to problem solving.

    The best way to repair for coding test is to solve problems. The more problems you solve, the better and quicker you will perform. This time though, even if I get a new job, I’ll still continue keep practicing more and write more blogs.

    There are also some changes. For the “Problem solving” section, from now on, I will try to come up with the most elegant, succinct and easy to understand write-up that I can possibly think of.

    I consider myself to be an average problem solver, but no one is good without learning and practicing, right?

    I hope that the content on this site can help you to get an idea on solving some problems, also I will show case some of my projects that I’ve done, feel free to ping me for the source code. To be honest, the current projects on this site are quite “dump”, it’s my university projects, most of them use outdated technology, back-then I even didn’t know how to use git and github so I saved my code on GoogleDrive :V

    Please considering donating if you feel it’s worth:
    https://www.paypal.me/TruongLoc

     

     

     
  • loctv 8:54 pm on January 3, 2018 Permalink | Reply  

    The Power Sum 

    Find the number of ways that a given integer, X, can be expressed as sum of the Nth powers of unique, natural numbers.

    Input format:
    The first line contains an integer X
    The second line contains an integer N

    Constraints:
    1 <= X <= 1000
    2 <= N <= 10

    Output format:
    Output a single integer, the answer to the problem explained above.

    Sample Input 0

    10
    2
    

    Sample Output 0

    1
    

    Explanation 0

    If X = 10 and N = 2, we need to find the number of ways that 10 can be represented as the sum of squares of unique numbers.
    10 = 1^2 + 3^2
    This is the only way in which 10 can be expressed as the sum of unique square.

    Sample Input 1

    100
    2

    Sample Output 1

    3

    Explanation 1

    100 = 10^2 = 6^2 + 8^2 = 1^2 + 3^2 + 4^2 + 5^2 + 7^2

    Sample Input 2

    100
    3

    Sample Output 2

    1

    Explanation 2

    100 can be expressed as the sum of the cubes of 1,2,3,4.
    (1 + 8 + 27 + 64) = 100. There is no other way to express 100 as the sum of cubes.

    Approach 1:
    With X = 10, and N = 2, this approach will generate sequences like:
    [1]
    [1, 4]
    [1, 4, 9]
    [1, 9]
    [4]
    [4, 9]
    [9]
    [9, 4]
    and you can easily spot out the problem of this approach is it produces duplicated sequences. Here is the code:
    def powerSum1(X, N):
        max_base = int(math.sqrt(X))
        sequence = list()
        ways = set()
        base = 1
        _recursive_sum1(X, N, base, max_base, sequence, ways)
        return len(ways)
        
    def _recursive_sum1(X, N, base, max_base, sequence, ways):
        if sum(sequence) == X:
            # if set(sequence) not in ways:
            ways.add(tuple(sorted(sequence)))
            return False
        elif sum(sequence) > X:
            return False
        else:
            for i in range(base, max_base+1):
                tmp_val = i**N
                if tmp_val not in sequence:
                    sequence.append(tmp_val)
                    print(sequence)
                    if _recursive_sum1(X, N, base+1, max_base, sequence, ways):
                        return True
                    sequence.pop()
            return False
    
     If you remove the comment from the if statement, indent 1 tab to the right for the line above, it will work perfectly, but only for all possible small-enough numbers. Because it generates on possible sequences, sequences that are subsequently increment.
    Approach 2:
    This recursion type generate non-repeated sequences that are subsequently increment.
    1]
    [1, 2]
    [1, 2, 3]
    [1, 2, 3, 4]
    [1, 2, 3, 4, 5]
    [1, 2, 3, 4, 5, 6]
    [1, 2, 3, 4, 6]
    [1, 2, 3, 4, 7]
    [1, 2, 3, 4, 8]
    [1, 2, 3, 5]
    [1, 2, 3, 5, 6]
    [1, 2, 3, 5, 7]
    [1, 2, 3, 6]
    [1, 2, 3, 6, 7]
    [1, 2, 3, 7]
    [1, 2, 3, 8]
    [1, 2, 3, 9]
    [1, 2, 4]
    def powerSum(X, N):
        sequence = list()
        base = 1
        look_up = [0]*(101)
        for i in range(1, 101):
            look_up[i] = i**N
        cur_sum = 0
        ways = _recursive_sum(X, N, base, look_up, cur_sum, sequence)
        return ways
    
    def _recursive_sum(X, N, base, look_up, cur_sum, seq):
        ways = 0
        tmp_val = look_up[base]
        
        while cur_sum + tmp_val < X:
            seq.append(base)
            print(seq)
            ways += _recursive_sum(X, N, base+1, look_up, cur_sum+tmp_val, seq)
            seq.pop()
            base += 1
            tmp_val = look_up[base]
    
        if cur_sum + tmp_val == X:
            ways += 1
            seq.append(base)
            seq.pop()
        return ways
    

     

     
  • loctv 4:21 pm on January 3, 2018 Permalink | Reply  

    Problem: Connected Cells in a Grid (Python3) 

    Consider a matrix with n rows and m columns, where each cell contains either a 0 or a 1 and any cell containing a 1 is called a filled cell. Two cells are said to be connected if they are adjacent to each other horizontally, vertically, or diagonally; in other words, cell [i][j]  is connected to cells [i-1][j-1], [i-1][j], [i-1][j+1], [i][j+1], [i+1][j+1], [i+1][j], [i+1][j-1], and [i][i-1], provided that the location exists in the matrix for that [i][j].

    If one or more filled cells are also connected, they form a region. Note that each cell in a region is connected to zero or more cells in the region but is not necessarily directly connected to all the other cells in the region.

    Task
    Given an nxm matrix, find and print the number of cells in the largest region in the matrix. Note that there may be more than one region in the matrix.

    Input Format

    The first line contains an integer, n, denoting the number of rows in the matrix.
    The second line contains an integer, m, denoting the number of columns in the matrix.
    Each line i of the n subsequent lines contains m space-separated integers describing the respective values filling each row in the matrix.

    Constraints

     0 < n,m < 10

    Output Format

    Print the number of cells in the largest region in the given matrix.

    Sample Input

    4
    4
    1 1 0 0
    0 1 1 0
    0 0 1 0
    1 0 0 0
    

    Sample Output

    5
    

    Explanation

    The diagram below depicts two regions of the matrix; for each region, the component cells forming the region are marked with an X:

    X X 0 0     1 1 0 0
    0 X X 0     0 1 1 0
    0 0 X 0     0 0 1 0
    1 0 0 0     X 0 0 0
    

    The first region has five cells and the second region has one cell. Because we want to print the number of cells in the largest region of the matrix, we print 5.

    Approach:
    Since the constrains are small, we can use brute-force algorithm. The hole algorithm can be described in three lines.

    With each cell in the grid:
    —- if it is 1 and not visited:
    ——– get all of it neighbors into a group (if any)

    We need to implement the hard part. We need a groups list to store a list of groups (this is optional, you can use a list of group’s size), a collection to store visited cell (this should be set because in Python, O(1) is time complexity requires to check if a value in a set). We explore all 8 directions of a given cell, recursively call that method until we cant explore anymore. The algorithm has time complexity O(nxm), since we will never revisit a cell that is added into a group. Each cell is ensured to be visited only one.

     

    EIGHT_DIRECTIONS = [
        (-1, -1),
        (-1, 0),
        (-1, 1),
        (0, 1),
        (1, 1),
        (1, 0),
        (1, -1),
        (0, -1)
    ]
    
    def explore(grid, x, y, visited, groups):
        groups[-1].append((x, y))
        visited.add((x, y))
        for i, j in EIGHT_DIRECTIONS:
            next_x = x + i
            next_y = y + j
            if in_bound(grid, next_x, next_y) and \
               grid[next_x][next_y] == 1 and (next_x, next_y) not in visited:
               explore(grid, next_x, next_y, visited, groups)
    
    def in_bound(grid, i, j):
        return i >= 0 and i < len(grid) and \
               j >= 0 and j < len(grid[0])
    
    def connected_cells(grid, visited, groups):
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == 1 and (i,j) not in visited:
                    groups.append(list())
                    explore(grid, i, j, visited, groups)
    
    def largest_region(groups):
        return max(len(group) for group in groups)
    
    if __name__ == '__main__':
        n = int(input())
        m = int(input())
        grid = list()
        for i in range(n):
            line = input()
            grid.append([int(x) for x in line.strip().split()])
        groups = list()
        visited = set()
        connected_cells(grid, visited, groups)
        # for group in groups:
        #     print(group)
        print(largest_region(groups))
    
     
  • loctv 6:23 pm on December 31, 2017 Permalink | Reply  

    Eight queens problem, backtracking, Python3 

    • Problem:

    Given an 8×8 board, your job is to place 8 queens on the board such that none of them can attack each other (If you are not familiar with chess, then google it first). The problem can be more general, given a n x n (n > 3) board, place n queens on the board such that there is no way a queen can attack the others. There are 92 solutions to this problem.

    Screen Shot 2017-12-30 at 3.52.52 PM

    • Solutions

    The way to solve this problem is already described in the title. Here’s let solve it step by step. First let’s try some thoughts on a small board to see if we can apply the approach which we are about to come up with on small board to a wider one.

    To develop an algorithm for this problem, we can first study a smaller instance of the problem by using just four queens and a 4 * 4 board. How would you go about solving this smaller problem? You may attempt to randomly place the queens on the board until you find a solution that may work for this smaller case. But when attempting to solve the original eight-queens problem, this approach may lead to chaos.

    Consider a more organized approach to solving this problem. Since no two queens can occupy the same column, we can proceed one column at a time and attempt to position a queen in each column. We start by placing a queen in the upper-left square or position (0, 0) using the 2-D array notation:

    With this move, we now eliminate all squares horizontally, vertically, and diagonally from this position for the placement of additional queens since these positions are guarded by the queen we just placed.

    With the first queen placed in the first column, we now move to the second column. The first open position in this column where a queen can be placed without being attacked by the first queen we placed is at position (2,1). We can place a queen in this position and mark those squares that this queen guards, removing yet more positions for the placement of additional queens.

    We are now ready to position a queen in the third column. But you may notice there are no open positions in the third column. Thus, the placement of the first two queens will not result in a valid solution. At this point, you may be tempted to remove all of the existing queens and start over. But that would be a drastic move.

    We first return to the second column and try alternate positions for that queen before possibly having to return all the way back to the first column.
    The next step is to return to the second column and pick up the queen we placed at position (2,1) and remove the markers that were used to indicate the squares that queen was guarding.
    We then place the queen at the next available square within the same column (3, 1) and mark the appropriate squares guarded from this position, as shown here:
    Now we can return to the third column and try again. This time, we place a queen at position (1, 2), but this results in no open squares in the fourth column.
    We could try other squares in the same column, but none are open. Thus, we must pick up the queen from the third column and again backtrack to try other combinations. We return to the second column and pick up the queen we placed earlier at position (3, 1) so we can try other squares within this column.

    But there are no more open squares in the second column to try, so we must back up even further, returning to the first column. When returning to a column, the first step is always to pick up the queen previously placed in that column.

    After picking up the queen in the first column, we place it in the next position (1, 0) within that column.

    We can now repeat the process and attempt to find open positions in each of the remaining columns. These final steps, which are illustrated here, results in a solution to the four-queens problem.

    Having found a solution for the four-queens problem, we can use the same approach to solve the eight-queens problem. The only difference between the two is that there is likely to be more backtracking required to find a solution. In addition, while the four-queens problem has two solutions, the eight-queens problem has 92 solutions.

    The original problem definition only considered finding a solution for a normal 8 * 8 chessboard. A more general problem, however, is known as the n-queens problem, which allows for the placement of n queens on a board of size n*n where n > 3. The same backtracking technique described earlier can be used with the n-queens problem, although finding a solution to larger-sized boards can be quite time consuming.

    The possible data structures for representing the actual board.

    The most obvious choice is a 2-D array of size n * n. The elements of the array can contain boolean values with True indicating the placement of the queens. To determine if a given square is unguarded, loops can be used to iterate over all of the squares to which a queen can move from that position. If a queen is found in any of the squares searched during the loop iterations, then we know the square is currently guarded by at least one queen. The placement and removal of the queens is also quite easy to implement using the 2-D array structure.

    As an alternative, we can actually use a 1-D array consisting of n elements. Each element of the 1-D array corresponds to one column on the board. The elements of the 1-D array will contain row indices indicating the positions of the queens on the board.

    Since only one queen can be placed within a given column, we need only keep track of the row containing the queen in the column. When determining if a square is unguarded, we can iterate through the row and column indices for the preceding columns on the board from which the given square can be attacked by a queen. Instead of searching for a True value within the elements of a 2-D array, we need only determine if the elements of the 1-D array contain one of the row indices being examined.

    When searching horizontally backward, we examine the elements of the 1-D array looking for an index equal to that of the current row. If one is found, then there is a queen already positioned on the current row as is the case in the above example. If a queen was not found on the current row, then we would have to search diagonally to the upper left and to the lower left. We only search in this two directions because we place the queen from left to right, column by column. In these two cases, we search the squares indicated by the arrows and examine the row indices of each and compare them to the entries in the 1-D array. If any of the indices match, then a queen is currently guarding the position and it is not a legal move.

    Code using backtracking to solve n-queens problem.

    from board import Board
    
    def solve_n_queens(board, col, ways):
        # check if n-queens has been placed on the board
        # base case
        if board.num_queens() == board.size():
            ways.append([x for x in board._board])
            return False
        else:
            for row in range(board.size()):
                if board.unguarded(row, col):
                    # place a queen in that square
                    board.place_queen(row, col)
                    # continue placing queens in the following columns
                    if solve_n_queens(board, col+1, ways):
                        # we are finished if a solution was found
                        return True
                    else:
                        # no solution was found with the queen in this square
                        # so it has to be removed from the board
                        # and try the next row in this col
                        if board._board[0] == 1:
                            print(board._board)
                        board.remove_queen(row, col)
    
            # If the loop terminates no queen can be placed within this column
            return False
    
    if __name__ == '__main__':
    
        for col in range(0, 1):
            ways = []
            board = Board(8)
            res = solve_n_queens(board, col, ways)
            print(*ways, sep='\n')
            print(len(ways))
    

    The board

    from array import Array
    
    class Board:
        def __init__(self, size):
            self._size = size
            self._board = Array(size)
    
        def size(self):
            return self._size
    
        def num_queens(self):
            return len([x for x in self._board if x is not None])
    
        def place_queen(self, row, col):
            self._board[col] = row
    
        def remove_queen(self, row, col):
            self._board[col] = None
    
        def unguarded(self, row, col):
            # first check if this row is guarded
            if row in self._board:
                return False
            # check up left diagonal
            up_left_row = row - 1
            up_left_col = col - 1
            while self._in_bound(up_left_row, up_left_col):
                if self._board[up_left_col] is not None and \
                   self._board[up_left_col] == up_left_row:
                       return False
                up_left_row -= 1
                up_left_col -= 1
            # check lower left diagonal
            low_left_row = row + 1
            low_left_col = col - 1
            while self._in_bound(low_left_row, low_left_col):
                if self._board[low_left_col] is not None and \
                   self._board[low_left_col] == low_left_row:
                       return False
                low_left_row += 1
                low_left_col -= 1
    
            return True
    
        def _in_bound(self, row, col):
            return row >= 0 and row < self.size() and \
                   col >= 0 and col < self.size()
    

    And the Array that’s used to construct Board

    import ctypes
    
    class Array:
        def __init__(self, size):
            assert size > 0, "Array size must be > 0"
            self._size = size
            PyArrayType = ctypes.py_object * size
            self._elements = PyArrayType()
            self.clear(None)
    
        def __len__(self):
            return self._size
    
        def __getitem__(self, index):
            assert index >= 0 and index < len(self), "Array subcript out of range"
            return self._elements[index]
    
        def __setitem__(self, index, value):
            assert index >= 0 and index < len(self), "Array subcript out of range"
            self._elements[index] = value
    
        def clear(self, value):
            for i in range(len(self)):
                self._elements[i] = value
    
        def __iter__(self):
            return _ArrayIterator(self._elements)
    
        def __str__(self):
            str_template = ""
            for item in self:
                    str_template += " %4s "
            str_template = str_template.strip()
            return "[" + str_template % tuple(self) + "]"
    
        def __contains__(self, val):
            for i in self:
                if i is not None and i == val:
                    return True
            return False
    

     

     
  • loctv 7:24 pm on December 26, 2017 Permalink | Reply  

    Check if a number is palindromic, O(1) space complexity (Python3) 

    • Reverse digits

    Since this is a simple problem so I don’t explain much here. You can either convert to string and then reverse that string or using mod 10. Here a chunk of code that uses the mod 10 approach:

    def reverse(x):
        result, x_remaining = 0, abs(x)
        while x_remaining:
            result = result * 10 + x_remaining % 10
            x_remaining //= 10
        return -result if x < 0 else result
    
    • Check palindrome

    We can easily solve this problem by converting the number into string and pairwise comparing digits starting from the least significant digit and the most significant digit, and working inwards, stopping if there is a mismatch. But time and space complexity of this approach is O(n).

    We already know how to extract the least significant digit using mod 10, but how can we extract the most significant digit? The answer is using log base 10. To calculate the number of digits of a decimal integer, we have the formula:

    num_digits = math.floor(math.log10(n)) +1

    Everything works the same with the converting approach, which is pairwise comparing.

    import math
    
    def is_palindrome_number(x):
        # since string representation of negative numbers
        # is not palindromic
        if x <= 0:
            return x == 0
    
        num_digits = math.floor(math.log10(x)) + 1
        # msd : most significant digit
        # msd is used to remove the msd from x
        msd_mask = 10**(num_digits - 1)
        for i in range(num_digits // 2):
            # check equality of msd and lsd
            if x // msd_mask != x % 10:
                return False
            x %= msd_mask # get rid of the msd of x
            x //= 10 # get rid of the lsd of x
            msd_mask //= 100 # 100 because msd and lsd removal
        # all pair of msd and lsd match
        return True
    
    # another solution could be reverse the digit and check if
    # it equals with the original one (or they are the same)
    
     
  • loctv 6:14 pm on December 26, 2017 Permalink | Reply  

    Compute x/y (quotient) using only the addition, subtraction and shifting operators (Python3) 

    Solutions:

    • Brute-force:

    A brute-force approach is to iteratively subtract y from x until what remains is less than y. The number of such subtractions is exactly the quotient, x/y, and the remainder is the term that’s less than y. The complexity of the brute-force approach is very high, when y=1 and x = K, it will take K iterations. K could be 1, 100, or even 10^20, etc.

    • The grade-school division algorithm to binary numbers

    A better approach is to try and get more work done in each iteration. We can compute the largest k such that pow(2,k)*y <= x, subtract pow(2k,)*y from x, and pow(2,k) to the quotient. For example, if x = 1011 (base 2), y = 10 (base 2), then k = 2. We subtract 1000 from 1011 to get 11, add pow(2,k) = 100 (base 2) to the quotient, and continue by updating x to 11.

    The advantage of using pow(2,k)*y is that it can be compute very efficiently using shifting. If it takes n bits to represent x/y, there are O(n) iterations. If the largest k such that pow(2,k)*y <= x is computed by iterating through k, each iteration has time complexity O(n). This leads to an O(n^2) algorithm.

    A better way to find the largest k in each iteration is to recognize that it keeps decreasing. Therefore, instead of testing in each iteration whether 2^0 * y, 2^1 * y, 2^2 * y, …. is less than or equal to x, after we initially find the largest k such that pow(2,k)*y <= x, in subsequent iterations we test 2^k-1 * y, 2^k-2 *y, 2^k-3 *y, …

    For the example given earlier, after setting the quotient to 100 (binary), we continue with 11. Now the largest k such that pow(2, k)*y <= 11 is 0, so we add 2*0 to the quotient, which is now 101. We continue with 11 – 10 = 1. Since 1 < y, we are done, the quotient is 101, and the remainder is 1 (binary).

    def divide(x, y):
        result, power = 0, 32
        # starting at 2^32 y
        y_power = y << power
        while x >= y:
            # searching for biggest k such that
            # 2^k * y <= x
            while y_power > x:
                y_power >>= 1
                power -= 1
    
            # add 2^k to quotient
            result += 1 << power
            # subtract 2^k * y from x
            x -= y_power
        return result
    

    With each iteration, we process an additional bit. Therefore, assuming individual shift and add operation take O(1), the time complexity is O(n).

     
  • loctv 4:59 pm on December 24, 2017 Permalink | Reply  

    Compute x * y without arithmetic operator (Python3) 

    Problem:

    Write a program that multiplies two nonnegative integers. The only operator you are allowed to use are:

    • Assignment
    • the bitwise operator >>, <<, |, &, ^ and
    • equality check

    Solution:

    A brute-force approach would be to perform repeated addition. Initialize the result to 0 and then ad x to it y times. The time complexity is very high.

    The algorithm taught in grade-school for decimal multiplication does not use repeated addition – it uses shift and add to achieve a much better time complexity. We can do the same with binary numbers – to multiply x and y we initialize the result to 0 and iterate through the bits of x, adding pow(2, k)*k to the result if kth bit of x is 1.

    The value pow(2,k)*y can be computed by left-shifting y by k. Since we cannot use add, we have to implement it. We apply the grade-school algorithm for addition to the binary case, compute the sum of bit-by-bit, and ‘rippling’ the carry along.

    Example: 13(1101) * 9(1001), using the algorithm described above.
    In the first iteration, since the LSB of 13 is 1, we set the result to 1001. The second bit of 13(1101) is 0 so we move on to the third bit. This bit is 1, so we shift 1001 to the left by 2 to obtain 100100, which we add to 1001 to get 101101. The final bit of 1101 is 1, so we shift 1001 to the left by 3 (this is calculate pow(2, k)*y) to obtain 1001000, which we add to 101101 to get 1110101 = 117.

    Each addition is itself performed bit-by-bit. For example when adding 101101 and 1001000, the LSB of the result is 1. The next bit is 1 (since the next bit of the operands are 0). The next bit is 1 (since exactly one of the next bits of the operands is 1). The next bit is 0 (since both the next bits of the operands are 1). We also ‘carry’ a 1 to the next position. The next bit is 1 (since the carry-in is 1 and both the next bits of the operands are 0). The remaining bits are assigned similarly.

    def multiply(x, y):
    	# dont ask me details about this function
    	# just note it somewhere and when you need to 
    	# do bit-addition quickly, you know where to find it
    	def add(a, b):
    		running_sum, carryin, k, temp_a, temp_b = 0, 0, 1, a, b
    		while temp_a or temp_b:
    			ak, bk = a & k, b & k
    			carryout = (ak & bk) | (ak & carryin) | (bk & carryin)
    			running_sum |= ak ^ bk ^ carryin
    			carryin, k, temp_a, temp_b = (carryout << 1, k << 1, temp_a >> 1, temp_b >> 1)
    		return running_sum | carryin
    
    	# first initialize result to 0
    	running_sum = 0
    	while x: # examines each bit of x
    		if x & 1: # the current bit is 1
    			# first iteration will make result = y
    			# as in the example 
    			running_sum = add(running_sum, y)
    		# right shift x to get next LSB
    		# left shift y to get pow(2, k)
    		x, y = x >> 1, y << 1
    	return running_sum
    

    Time complexity: O(n^2), where n is the number of bits.

     

     
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