Updates from February, 2017 Toggle Comment Threads | Keyboard Shortcuts

  • loctv 3:28 pm on February 20, 2017 Permalink | Reply
    Tags: ,   

    Problem: Making Anagrams 

    *Difficulty: Easy

    Problem:

    ctci-making-anagrams-english

    Approach: To be able to make anagrams from two string, we have to find their common characters first. For example, if we have abccd and cdcc, then their common characters is c and d. Then we build two string contains only character that is in both string a and string b. In the previous example, string a = ccd and string b = cdcc. The last thing we need to do is make them anagrams. We do that by iterating through either string a or string b, with each character d, if there are more d in string a than string b, we remove d from a to make the number of d equal in both a and b. In our example, string b will remove 1 ‘c’, then a = ccd and b = dcc. Notice that we don’t have to do this on string, we rather do this on dictionary of string. Since the input only contains lower English alphabet, the maximum size of the dictionary will contain only 26 keys and 26 corresponding values. If key ‘c’ in a has higher value than key ‘c’ in b, then set its value to ‘c’ in b.

    Implementation: Python 2.7

    from collections import Counter
    
    def make_anagrams(a, b):
        a_set = set(list(a))
        b_set = set(list(b))
        a_counter = Counter()
        b_counter = Counter()
        # get char in common 
        for c in a:
            if c in b_set:
                a_counter[c] += 1
        for c in b:
            if c in a_set:
                b_counter[c] += 1
        # make anagrams 
        for key in a_counter.keys():
            a_val = a_counter.get(key)
            b_val = b_counter.get(key)
            if a_val > b_val:
                a_counter[key] = b_val
            else:
                b_counter[key] = a_val
        # calculate removed char
        a_lost = len(a) - sum([a_counter.get(x) for x in a_counter.keys()])
        b_lost = len(b) - sum([b_counter.get(x) for x in b_counter.keys()])
        return a_lost + b_lost
    
    if __name__ == '__main__':
        a = input().strip()
        b = input().strip()
        print(make_anagrams(a, b))
    
     
  • loctv 10:50 am on February 7, 2017 Permalink | Reply
    Tags: ,   

    Fix: ImportError: cannot import name PDFDocument (when using slate) 

    I  spent over an hour to fix this problem. I write this post to avoid searching again and share the solution I used. Up to this point, this solution still works perfectly, I don’t know if it still work in the future, since the owner of slate package said he’s gonna change the code.

    After installing slate, and you type in

    import slate
    

    and you get this error

    Traceback (most recent call last):
    File "<console>", line 1, in <module>
    File "/usr/local/lib/python2.7/dist-packages/slate/__init__.py", line 48, in <module>
    from slate import PDF
    File "/usr/local/lib/python2.7/dist-packages/slate/slate.py", line 3, in <module>
    from pdfminer.pdfparser import PDFParser, PDFDocument
    ImportError: cannot import name PDFDocument
    

    In this post, there are many ways to solve this problem, but not all of them can be applied. And I found the solution from rdpickard .  It’s not quite elegant, but it fixes shit.

    If you’re afraid of clicking the link above, here’s what he wrote:

    Not sure if editing the slate.py is an option for people’s environment, but if you change

    line 3

    from pdfminer.pdfparser import PDFParser, PDFDocument
    

    to

    from pdfminer.pdfparser import PDFParser
    from pdfminer.pdfdocument import PDFDocument
    from pdfminer.pdfpage import PDFPage
    

    line 38

            self.doc = PDFDocument()
    

    to

            self.doc = PDFDocument(self.parser)
    

    comment out lines 40 & 41

    line 49

                for page in self.doc.get_pages():
                    self.append(self.interpreter.process_page(page))
    

    to

                for page in PDFPage.create_pages(self.doc):
                    self.append(self.interpreter.process_page(page))
    

    it works.

    Here are the versions of libraries I am using

    cssselect==0.9.1
    lxml==3.6.0
    pdfminer==20140328
    pyquery==1.2.13
    slate==0.3
    wheel==0.24.0
    

    That’s it.

    If you cant change the code inside slate.py, it probably means you don’t have permission. If you’re using Linux, type this line into terminal

    sudo chown yourusername:yourusername path_to_file_or_folder_you_want_to_get_permission
    

    and then enter your password.

     
  • loctv 9:04 pm on February 3, 2017 Permalink | Reply
    Tags: ,   

    Problem: A or B 

    *Difficulty: Medium
    Consider four numbers: A, B, C, and K. You must change at most K bits in A and B to form the numbers A’ and B’ satisfying the equation A’ | B’ = C. Here, the | symbol denotes the bitwise OR operation.

    Given Q sets of the numbers defined above, find and print the respective values of A’ and B’ on new lines; if no such value exists, print -1 instead. If there are multiple solutions, make A’ as small as possible; if there are still multiple solutions, make B’ as small as possible.

    Notes:

    • A, B and C are given in Hexadecimal (base 16), and K is given in decimal (base 10).
    • If the number of bits changed in A is kA and the number of bits changed in B is kB , then kA + kB must be <= K.

    Input Format

    The first line contains an integer, Q , denoting the number of queries. The subsequent lines describe each respective query as follows:

    • The first line contains a single integer denoting the value of K.
    • Each of the next 3 lines contains a Hexadecimal (base 16) number describing the respective values of A, B, and C.

    Constraints

     screenshot-from-2017-02-03-20-49-42

    Output Format

    Print two lines of output for each query:

    1. The first line should contain a Hexadecimal (base 16) number denoting the value of A’ .
    2. The second line must contain a Hexadecimal (base 16) number denoting the value of B’.

    If no valid answer exists, you must instead print one line of output with the integer -1.

    Note: The letters in Hexadecimal numbers must be in uppercase.

    Sample Input

    3
    8
    2B
    9F
    58
    5
    B9
    40
    5A
    2
    91
    BE
    A8
    

    Sample Output

    8
    58
    18
    42
    -1
    

    Explanation

    Query 0:
    In this query, K = 8.
    Change to A = 2B(16) to A’ = 8(16). 3 bits are changed.

    Change B = 9F(16) to B’= 58(16) . 5 bits are changed.

    Query 1:
    In this query, K = 5.
    Change A = B9(16) to A’ = 18(16). 3 bits are changed.
    Change B = 40(16) to B’ = 42(16). Only 1 bit is changed.

    Query 2:
    There is no valid answer, so we print -1.

    Approach:

    There are two parts of the solution. The first is the one that I figured out, but I sucked at the second part.
    Let’s me explain. The solution complexity is O(n).
    Part 1: Convert A,B,C to binary, and equalize their length (calculate max length, then append 0 before the ones that are shorter). Traverse through each bit in C.
    If C[i] == 0:
    + if A[i] = 1 => A[i] = 0, reduce K by 1
    + if B[i] = 1 => B[i] = 0, reduce K by 1
    If C[i] == 1:
    + if A[i] == 0 and B[i] == 0 => B[i] = 1, reduce K by 1
    While iterating through C, if K == 0 but still not A’ | B’ = C, then return -1
    Note: in case C[i] == 1, we let B[i] = 1 since we want to minimize A first.

    Part 2: Since not fully understood the description of the problem (my bad English), I had to see the tutorial, which then made me surprised. The second part when we minimize even further A. If K still bigger than 0.
    i -> 0
    while K > 0:
    if C == [1]: # since if C[i] == 0 we cant change anything
    + if A[i] == 1 and B[i] == 1 => A[i] = 0 #minimize A, reduce K by 1
    + if A[i] == 1 and B[i] == 0 => A[i] = 0 and B[i] = 1, reduce K by 2

    That’s it. How silly I am 😦

    Implementation: Python 2.7

    def figureOut(A, B, C, K):
        # convert from base 16 to base 10
        # in binary format
        A = bin(int(A, 16))[2:]
        B = bin(int(B, 16))[2:]
        C = bin(int(C, 16))[2:]
        maxLength = max(len(A), len(B), len(C))
    
        #equalize A,B,C length
        if len(A) < maxLength:
            A = '0'*(maxLength-len(A)) + A
        if len(B) < maxLength:
            B = '0'*(maxLength-len(B)) + B
        if len(C) < maxLength:
            C = '0'*(maxLength-len(C)) + C
        A, B, C = list(A), list(B), list(C)
    
        # 1. found result
        result = []
        for i in range(len(C)):
            if C[i] == '0':
                if A[i] == '1':
                    A[i] = '0'
                    K -= 1
                if B[i] == '1':
                    B[i] = '0'
                    K -=1
            elif C[i] == '1':
                if A[i] == '0' and B[i] == '0':
                    B[i] = '1'
                    K -= 1
            # not found, return -1
            if K < 0:
                return -1
        
        # found result,
        # minimize A
        i = 0
        while K > 0:
            if C[i] == '1':
                if A[i] == '1' and B[i] == '1':
                    A[i] = '0'
                    K -= 1
                elif A[i] == '1' and B[i] == '0':
                    if K > 1:
                        A[i] = '0'
                        B[i] = '1'
                        K -= 2
                    
            i += 1
            if i == len(C):
                break
    
        return '{:X}'.format(int(''.join(A), 2)), '{:X}'.format(int(''.join(B), 2))
        
    
    def main():
        t = input()
        for _ in range(t):
            K = input()
            A = raw_input().strip()
            B = raw_input().strip()
            C = raw_input().strip()
            
            result = figureOut(A, B, C, K)
            if result != -1:
                print result[0]
                print result[1]
            else:
                print -1
    
    if __name__ == '__main__':
        main()
    
     
  • loctv 10:09 pm on February 2, 2017 Permalink | Reply
    Tags: ,   

    Problem: Find all four sum numbers 

    *Difficulty: Medium

    Given an array A of size N, find all combination of four elements in the array whose sum is equal to a given value K. For example, if the given array is {10, 2, 3, 4, 5, 9, 7, 8} and K = 23, one of the quadruple is “3 5 7 8” (3 + 5 + 7 + 8 = 23).

    Input:
    The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains two lines. The first line of input contains two integers N and K. Then in the next line are N space separated values of the array.

    Output:
    For each test case in a new line print all the quadruples present in the array separated by space which sums up to value of K. Each quadruple is unique which are separated by a delimeter “$” and are in increasing order.

    Constraints:
    1<=T<=100
    1<=N<=100
    -1000<=K<=1000
    -100<=A[]<=100

    Example:
    Input:

    2
    5 3
    0 0 2 1 1
    7 23
    10 2 3 4 5 7 8
    Output:
    0 0 1 2 $
    2 3 8 10 $2 4 7 10 $3 5 7 8 $

    Approach:
    Using itertools in Python, I can easily quickly generate all combination-length-four of an arr.

    #code
    from __future__ import print_function
    import itertools
    
    def allFourSumNumber(arr, K):
        result = []
        for four in itertools.combinations(arr, 4):
            if sum(four) == K:
                if four not in result:
                    result.append(four)
        return result
    
    def main():
        t = input()
        for _ in range(t):
            n, K = map(int, raw_input().strip().split())
            arr = map(int, raw_input().strip().split())
            found = False
            for four in allFourSumNumber(sorted(arr), K):
                found = True
                print(four[0], four[1], four[2], four[3], '$', end='')
            print(-1 if not found else '')
    
    if __name__ == '__main__':
        main()
    

    “Life is short, why haven’t you learned Python yet?”

     
  • 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 10:37 pm on December 27, 2016 Permalink | Reply
    Tags: ,   

    Problem: Deficient Number 

    *Difficulty: Easy

    iven a number x, your task is to find if this number is Deficient number or not. A number x is said to be Deficient Number if sum of all the divisors of the number denoted by divisorsSum(x) is less than twice the value of the number x. And the difference between these two values is called the deficiency.

    Mathematically, if below condition holds the number is said to be Deficient:
    divisorsSum(x) < 2*x
    deficiency = (2*x) – divisorsSum(x)
    Examples:

    Input: 21
    Output: YES
    Divisors are 1, 3, 7 and 21. Sum of divisors is 32.
    This sum is less than 2*21 or 42.
    
    Input: 12
    Output: NO
    
    Input: 17
    Output: YES

     

    Input:
    The first line of input contains an integer T denoting the no of test cases.
    Then T test cases follow. Each line contains an integer x.

    Output:
    For each test case in a new line print 1 if the no is a Deficient number else print 0.

    Constraints:
    1<=T<=10000
    1<=x<=10000
    Example:
    Input:

    3
    21
    12
    17
    Output:
    1
    0
    1

     

    How to solve:
    Using prime factorization 

    Implementation: Python 2.7

    def get_primes():
        """
            an efficient way to calculate prime numbers
        """
        yield 2
        yield 3
        i = 5
        while True:
            yield i
            if i%6 == 1:
                i += 2
            i += 2
    
    def get_prime_factors(n):
        """
            get prime factors of a number
        """
        d = {}
        primes = get_primes()
        for p in primes:
            while n % p == 0:
                n /= p
                d[p] = d.setdefault(p, 0) + 1
            if n == 1:
                return d 
    
    def sum_of_divisors(d, n):
        if len(d) == 1: #n is a prime number
            return n+1
        s = 1
        for factor in d.keys():
            s *= ((1-pow(factor, d[factor]+1))/(1-factor))
        return s
    
    if __name__ == '__main__':
        t = input()
        for _ in range(t):
            n = input()
            prime_factors = get_prime_factors(n)
            if sum_of_divisors(prime_factors, n) < n*2:
                print 1
            else:
                print 0
    
    
     
  • loctv 10:47 am on October 8, 2016 Permalink | Reply
    Tags:   

    Micro Project: Reversi 

    This is the 3rd game in series game I intend to make.
    For those who don’t know how to play Reversi, go here. You have to know how to play the game in order to code it, otherwise you will not understand what I’m gonna talk.
    Basically, this is a take-turn game. In this game you play against a simple AI. Although it’s simple, but it will beat you almost every game you play. I’ve tried very hard, but can only make a tie game with it (I rarely win it).
    Ok, after you know how to play, I’ll show you the code and then explain every single line.

    Here’s the code: (Python 2.7)

    import sys
    import random
    
    class Reversi:
        def __init__(self):
            self.player_tile = ''
            self.computer_tile = ''
            self.board = self.get_new_board()
            self.game_state = 'CONTINUE'
            self.reset_board(self.board)
    
        def draw_board(self, board):
            HLINE = '   ' + '+---'*8+'+'
    
            print '     ' + '   '.join(map(str, range(1, 9)))
            print HLINE
            for i in xrange(8):
                print str(i+1) + ' ',
                for j in xrange(8):
                    print '| %s' % (board[i][j]),
                print '|'
                print HLINE
    
        def reset_board(self, board):
            for i in xrange(8):
                for j in xrange(8):
                    board[i][j] = ' '
            board[3][3] = 'X'
            board[4][3] = 'O'
            board[3][4] = 'O'
            board[4][4] = 'X'
    
        def get_new_board(self):
            board = []
            for i in xrange(8):
                board.append([' ']*8)
            return board
    
        def is_valid_move(self, board, char, xstart, ystart):
            if not self.is_on_board(xstart, ystart) or board[xstart][ystart] != ' ':
                return False
            other_tile = 'X' if char == 'O' else 'O'
            tiles_to_flip = []
    
            for xdirection, ydirection in [[0,1], [1,1], [1,0], [1,-1], [0,-1], [-1,-1], [-1,0], [-1,1]]:
                x,y = xstart, ystart
                x += xdirection
                y += ydirection
    
                if self.is_on_board(x,y) and board[x][y] == other_tile:
                    x += xdirection
                    y += ydirection
                    if not self.is_on_board(x,y):
                        continue
    
                    while board[x][y] == other_tile:
                        x += xdirection
                        y += ydirection
                        if not self.is_on_board(x, y):
                            break
    
                    if not self.is_on_board(x, y):
                        continue
    
                    if board[x][y] == char:
                        while True:
                            x -= xdirection
                            y -= ydirection
                            if x == xstart and y == ystart:
                                break
                            tiles_to_flip.append([x,y])
            board[xstart][ystart] = ' '
            if len(tiles_to_flip) == 0:
                return False
            return tiles_to_flip
    
        def is_on_board(self, x, y):
            return x &gt;= 0 and x &lt;= 7 and y &gt;= 0 and y &lt;= 7     def get_valid_moves(self, board, tile):         valid_moves = []         for i in xrange(8):             for j in xrange(8):                 if self.is_valid_move(board,tile,i,j) != False:                     valid_moves.append([i,j])         return valid_moves     def get_board_with_validmoves(self, board, tile):         copy_board = self.get_board_copy(board)         for x,y in self.get_valid_moves(copy_board, tile):             copy_board[x][y] = '.'         return copy_board     def get_score(self, board):         x_score, o_score = 0, 0         for x in xrange(8):             for y in range(8):                 if board[x][y] == 'X':                     x_score += 1                 if board[x][y] == 'O':                     o_score += 1         return {'X':x_score, 'O':o_score}     def get_board_copy(self, board):         copy_board = self.get_new_board()         for x in xrange(8):             for y in xrange(8):                 copy_board[x][y] = board[x][y]         return copy_board     def player_choose_tile(self):         tile = ''         while not (tile == 'X' or tile == 'O'):             print 'Do you want to play \'X\' or \'O\'?'             tile = raw_input().strip()         self.player_tile = 'X' if tile == 'X' else 'O'         self.computer_tile = 'X' if self.player_tile == 'O' else 'O'     def who_goes_first(self):         if random.randint(0, 1) == 1:             return 'computer'         return 'player'     def play_again(self):         print 'Do you want to play again? (y,n)'         return raw_input().strip().startswith('y')     def make_move(self, board, tile, xstart, ystart):         tiles_to_flip = self.is_valid_move(board,tile,xstart,ystart)         if tiles_to_flip == False:             return False         board[xstart][ystart] = tile         for x,y in tiles_to_flip:             board[x][y] = tile         return True     def is_corner(self, x, y):         return (x == 0 and y == 0) or (x == 7 and y == 0) or (x == 0 and y == 7) or (x == 7 and y == 7)     def get_player_move(self, board, player_tile):         DIGITS = ' '.join(map(str, range(1, 9))).split()         while True:             print 'Enter your move, or type quit to end game, or hints to get hints'             move = raw_input().strip().lower()             if move == 'quit':                 return 'quit'             if move == 'hints':                 return 'hints'             if len(move) == 2 and move[0] in DIGITS and move[1] in DIGITS:                 x = int(move[0]) - 1                 y = int(move[1]) - 1                 if self.is_valid_move(board, player_tile, x, y):                     break             else:                 print 'That is not a valid move. Type the x digit(1-8), then the y digit (1-8)'                 print 'For example, 81 will be the bottom left corner'         return [x, y]     def get_computer_move(self, board, computer_tile):         possible_moves = self.get_valid_moves(board, computer_tile)         random.shuffle(possible_moves)         for x,y in possible_moves:             if self.is_corner(x,y):                 return [x, y]         best_score = -1         best_move = []         for x, y in possible_moves:             copy_board = self.get_board_copy(board)             self.make_move(copy_board, computer_tile, x, y)             score = self.get_score(copy_board)[computer_tile]             if score &gt; best_score:
                    best_move = [x,y]
                    best_score = score
            return best_move
    
        def show_points(self, player_tile, computer_tile, board):
            score = self.get_score(board)
            print 'You have %s points. The compute has %s points' % (score[player_tile], score[computer_tile])
    
        def reset(self):
            self.board = self.get_new_board()
            self.reset_board(self.board)
            self.player_tile = ''
            self.computer_tile = ''
    
        def start_game(self):
            while self.game_state == 'CONTINUE':
                self.reset()
                self.player_choose_tile()
                turn = self.who_goes_first()
                self.draw_board(self.board)
                while True:
                    if turn == 'player':
                        move = self.get_player_move(self.board, self.player_tile)
                        if move == 'quit':
                            print 'Thanks for playing'
                            sys.exit()
                        elif move == 'hints':
                            print 'Hints:'
                            self.draw_board(self.get_board_with_validmoves(self.board, self.player_tile))
                            print
                            continue
                        else:
                            self.make_move(self.board, self.player_tile, move[0], move[1])
                            self.draw_board(self.board)
                            self.show_points(self.player_tile, self.computer_tile, self.board)
                        if self.get_valid_moves(self.board, self.computer_tile) == []:
                            break
                        else:
                            turn = 'computer'
                    else:
                        raw_input('Press enter to see computer move')
                        x,y = self.get_computer_move(self.board, self.computer_tile)
                        print (x+1), (y+1)
                        self.make_move(self.board, self.computer_tile, x, y)
                        self.draw_board(self.board)
                        self.show_points(self.player_tile, self.computer_tile, self.board)
                        if self.get_valid_moves(self.board, self.player_tile) == []:
                            break
                        else:
                            turn = 'player'
    
                self.draw_board(self.board)
                scores = self.get_score(self.board)
                print 'X scored %s, O scored %s' % (scores['X'], scores['O'])
                if scores[self.player_tile] &gt; scores[self.computer_tile]:
                    print 'You beat the computer by %s points. Congratulations!' %  (scores[self.player_tile]-scores[self.computer_tile])
                    self.game_state = 'WIN'
                elif scores[self.player_tile] &lt; scores[self.computer_tile]:
                    print 'You lost. Computer beat you by %s points' % (scores[self.computer_tile] - scores[self.player_tile])
                    self.game_state = 'GAME_OVER'
                else:
                    print 'I don\'t know how but this was a tie'
                if self.play_again():
                    self.game_state == 'CONTINUE'
    
    if __name__ == '__main__':
        game = Reversi()
        game.start_game()
    

    Again, I made use of using OOP (Object-Oriented Programming), so the entire game is inside a class named Reversi. This way you can reuse the code later.

    • Init

    Initialize player_tile, computer_tile, board and game_state

    • draw_board:

    Simply draw the 8×8 board in console. The board will look like this:
    screen-shot-2016-10-08-at-10-12-59-am

    • reset_board:

    Reset the board so that the game can start. The board at start looks like this:

    screen-shot-2016-10-08-at-10-17-31-am

    • get_new_board:

    Create a 8×8 board, with all cells hold the value ‘ ‘

    • is_valid_move:

    Check if a move is valid.
    The move x,y is valid if x,y is on the board, and board[x][y] == ‘ ‘, and there must be at least one cell will be flipped.
    In order to check if there are any cells will be flipped, we check all 8 directions, starting from the move x,y.  In the for loop, first we move to the adjacent cell according to the direction. If that cell is not on the board, we continue to other direction. Otherwise, we keep moving until we hit the wall (x,y out side the board) or we meet the cell having the same tile. If we hit the wall, means nothing will be flipped, but if we meet the cell having same value, everything between the starting point and this point will be flipped. We do that by going backward, append the coordinates of those cells into a list. After traversing all 8 directions, we reset the move (just imagine we’ve just made a temporary move in order to check if we make that move, there are some cells can be flipped), and return the coordinates of all those cells that can be flipped. But before we return those coordinates, we check if there is no cell can be flipped, means that is not a valid move.
    Simple, hah?

    • is_on_board:

    This method is sort and simple, check if x,y is on the board. By checking if they are in the bound.

    • get_valid_moves:

    We make use of is_valid_move method above, traverse through all cells on the board, check if it is valid, then we append that coordinates into a list. Finally, return the list.

    • get_board_with_validmoves

    This method is used to give player some hints if they’re stuck. By marking all valid moves with ‘.’, player can easily make a new move.

    • get_score:

    Go through all cells on the board, count how many X there are, how many O there are. And return the result as a dictionary.

    • get_board_copy:

    The name says it all. This method is used to help computer AI make a move, you’ll see soon.

    • who_goes_first:

    Randomly pick computer or player.

    • play_again:

    Ahh, no need to explain. Just ask if player want to play again.

    • make_move:

    If xstart,ystart is an invalid move, return False. Otherwise mark board[xstart][ystart] = tile, and flip all cells in the tiles_to_flip list, and then return True.

    • is_corner:

    Check if a move is on the corner of the board. This is important, if you know how to play the game well, you can figure it out while we have to do this. We do this simply because we try to help our cell avoid being flipped. That’s all.

    • get_player_move:

    Just check until player enter a valid move.

    • get_computer_move:

    This is the brain of our AI. First we get all possible moves, then shuffle it, and check if one of the move is on the corner. If none of them are on the corner, we choose the best move of all possible moves. The best move is the move with the give the computer the best score after playing that move. You got the idea.

    I think you can understand the rest of the code now. One more thing, you can easily create a real game with graphics by using this code. Just use tkinter to make an 8×8 buttons grid. You know how to do it, right?

     

     
  • loctv 2:47 am on September 14, 2016 Permalink | Reply
    Tags: ,   

    Problem: Pallindrome Patterns 

    Given a string S, find out all the possible palindromes that can be generated using the letters of the string and print them in lexicographical order.

    Input
    The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains the string S.

    Output
    Print out all the combinations in lexicographical order, seprated by a space inside curly brackets, i.e { palindrome1 palindrome 2}. If no pallindromes can be formed, print empty braces { }.

    Constraints
    1 <= T <= 100
    0 < S <= 20

    Examples

    Input
    3
    abbab
    abcabc
    abc

    Output
    { abbba babab }
    { abccba acbbca baccab bcaacb cabbac cbaabc }
    { }

    Using itertools in python
    Python 2.7

    from itertools import *
    def pallindrome_permute(s):
        """
            return permutations of s that is a
            pallindrome string
        """
        res = set(list(permutations(s)))
        for x in res:
            x = ''.join(x)
            if is_pallindrome(x):
                yield x
    
    def is_pallindrome(s):
        """
        check if a string is pallindrome
        """
        length = len(s)
        length_2 = length/2
        for _ in range(length_2):
            if s[_] != s[length-1-_]:
                return False
        else:
            return True
    
    if __name__ == '__main__':
        t = input()
        for _ in range(t):
            s = raw_input().strip()
            print "{",
            for _ in sorted(list(pallindrome_permute(s))):
                print _,
            print "}"
    

     

     
  • loctv 1:21 pm on July 10, 2016 Permalink | Reply  

    Stop posting (temporarily) 

    I’ve been learning something, so I won’t post anything anytime soon.
    For those who are interested in my projects, please contact me via gmail

    I’m living in a poor country, lack of so many things, and my health is not good at the moment, so any donation will be a great help, and I appreciate that.

    Sincerely
    loctv

     
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