Recent Updates Page 2 Toggle Comment Threads | Keyboard Shortcuts

  • loctv 9:06 pm on February 14, 2017 Permalink | Reply
    Tags: ,   

    Learn OpenCV (Python): Basic Video Operations 

    System information:

    • Ubuntu: 16.04
    • Opencv: 3.1.0

    To work with video in opencv, you just only need to care about these two attributes:

    • cv2.VideoCapture(video_path)
    • cv2.VideoWriter(video_path, codec, fps, size, is_color)

    About codec, depends on operating system you have, choose the appropriate one:

    • In Fedora (Linux): DIVX, XVID, MJPG, X264, WMV1, WMV2
    • In Windows: DIVX
    • In OS X: Dunno :V

    Depends on what video codec you use, different file extension will be supported.
    You can read more here .

    • Read Video
    import numpy as np
    import cv2 
    
    ESCAPE_KEY = 27
    # capture video
    video_capture = cv2.VideoCapture('/home/loctv/Python/cv/data/pycv-master/first_edition/chapter2/miscellaneous/MyInputVid.avi')
    
    # while video has not been released yet (or still opened)
    while video_capture.isOpened():
        # read video frame by frame
        ret, frame = video_capture.read()
        # convert to gray image
        gray = cv2.cvtColor(frame, cv2.COLOR_BGR2GRAY)
        # display
        cv2.imshow("frame", gray)
    
        # wait to press 'ESC' key
        # 27 means every 27 ms, this if block will be called again
        # you can alter this to change FPS (Frame Per Second)
        if cv2.waitKey(27) == ESCAPE_KEY:
            break
    
    # close video stream
    video_capture.release()
    # as it describes, destroy all windows has been opened by opencv
    cv2.destroyAllWindows()
    
    • Write Video
    import cv2
    
    # 'capture' video
    videoCapture = cv2.VideoCapture('MyInputVid.avi')
    # set frame per second
    fps = videoCapture.get(cv2.CAP_PROP_FPS)
    # size of the copied video
    size = (
        int(videoCapture.get(cv2.CAP_PROP_FRAME_WIDTH)),
        int(videoCapture.get(cv2.CAP_PROP_FRAME_HEIGHT))
    )
    # create video writer
    # video codec = WMV1
    # you can try others video codec
    videoWriter = cv2.VideoWriter(
        'MyOutputVid.avi', cv2.VideoWriter_fourcc(*"WMV1"), fps, size
    )
    
    # read first frame
    success, frame = videoCapture.read()
    # loop until there is no more frame
    while success:
        # write frame by frame
        videoWriter.write(frame)
        # read next frame
        success, frame = videoCapture.read()
    
    • Capture camera frames
    import numpy as np
    import cv2
    
    ESCAPE_KEY = 27
    # capture  frame from camera (webcam)
    # 0 is the index to specify which camera you want to capture
    # in this case, there only one camera
    camera_capture = cv2.VideoCapture(0)
    
    # # read the first frame
    success, frame = camera_capture.read()
    # while still more frame to read
    while success:
        # display frame
        # if you want you can convert frame from BGR to gray-scale
        # for faster processing
        cv2.imshow("frame", frame)
    
        # 25 means this if block will be called every 25 ms
        # help the frames displayed slow enough to be processed
        # wait for 'ESC' key to be pressed
        # then program will be stoped
        if cv2.waitKey(25) == ESCAPE_KEY:
            break
    
        # read another frame
        success, frame = camera_capture.read()
    
    # turn off webcam (by releasing capturer)
    camera_capture.release()
    cv2.destroyAllWindows()
    
    • Capture camera frames and writer to file
    import numpy as np
    import cv2
    
    ESCAPE_KEY = 27
    # capture  frame from camera (webcam)
    # 0 is the index to specify which camera you want to capture
    # in this case, there only one camera
    camera_capture = cv2.VideoCapture(0)
    # roughly estimate fps
    fps = 25
    # size of new video will be the same size with capture frames
    size = (
        int(camera_capture.get(cv2.CAP_PROP_FRAME_WIDTH)),
        int(camera_capture.get(cv2.CAP_PROP_FRAME_HEIGHT))
    )
    # set video codec
    # after trying several video codecs
    # this one works for me
    # if it does not work, let's try another one
    fourcc = cv2.VideoWriter_fourcc(*"MJPG")
    # create video writer object
    video_writer = cv2.VideoWriter(
        'CameraCapture.avi', fourcc, fps, size
    )
    
    # # read the first frame
    success, frame = camera_capture.read()
    # while still more frame to read
    while success:
        # instead of displaying frame like we did before
        # write it to file
        video_writer.write(frame)
        cv2.imshow("frame", frame)
    
        # 25 means this if block will be called every 25 ms
        # help the frames displayed slow enough to be processed
        # wait for 'ESC' key to be pressed
        # then program will be stoped
        if cv2.waitKey(25) == ESCAPE_KEY:
            break
    
        # read another frame
        success, frame = camera_capture.read()
    
    # turn off webcam (by releasing capturer)
    camera_capture.release()
    # and release video writer
    # video_writer.release()
    cv2.destroyAllWindows()
    

    ‘The number of camera and their order is system dependently, but opencv does not give us any way to query the number of cameras or their order. Fortunately, we can use VideoCapture‘s method isOpened() to check if we successfully connect to a real camera.

    • Work with multiple cameras:

    In the examples above, you can use read() method of VideoCapture to read frames of one camera, but it cant be use for reading frame of multiple cameras. In that case, you have to use grab() and retrieve():
    Suppose you already have two camera capture object for two camera

    success_0 = camera_capture_0.grab()
    success_1 = camera_capture_1.grab()
    while success_0 and success_1:
        frame_0 = camera_capture_0.retrieve()
        frame_1 = camera_capture_1.retrieve()
    

    Those are basic operations that opencv supports for video reading and writing.

     

     
  • loctv 4:39 pm on February 13, 2017 Permalink | Reply
    Tags: ,   

    Learn OpenCV (Python): Basic image manipulations / Operations 

    System information:

    • OS: Ubuntu 16.04
    • OpenCV: 3.1.0
    • Convert Array to Image
    import numpy
    import os
    import cv2
    
    random_byte_array = bytearray(os.urandom(120000))
    # or random_byte_array = numpy.random.randint(0, 256, 120000)
    flat_numpy_array = numpy.array(random_byte_array)
    
    # reshape to an grayscale image with 300px in height, 400px in width
    # which is a 2D array
    gray_image = flat_numpy_array.reshape(300, 400)
    cv2.imwrite('../data/random_gray.png', gray_image)
    
    # reshape to an BGR image with  100px in heigth, 400px in width
    # and 3 channels (BGR)
    # which is a 3D array
    bgr_image = flat_numpy_array.reshape(100, 400, 3)
    cv2.imwrite('../data/random_bgr.png', bgr_image)
    
    # *Note: this is only an example, the paths is not necessarily to be
    # the same on your system
    
    • Change pixel values in gray-scale image
    import numpy as np
    import cv2
    import random
    import datetime
    
    # seed the current time for random every time program starts
    random.seed(datetime.datetime.now())
    # help code more readable
    ESCAPE_KEY = 27
    
    # read image and change to gray scale
    img = cv2.imread('../../data/planet_glow.jpg', cv2.IMREAD_GRAYSCALE)
    # img.shapre on a gray-scale image return (row, col)
    row_count, column_count = img.shape
    
    # change all pixels value to random value from 0-255
    for i in xrange(row_count):
    	for j in xrange(column_count):
    		img[i, j] = random.randint(0, 255)
    
    # show image with title "show"
    cv2.imshow("show", img)
    
    # pause the program
    # if you remove this if block
    # the window will close immediately after the program starts
    # causing you see nothing
    if cv2.waitKey() == ESCAPE_KEY:
    	cv2.destroyAllWindows()
    
    • Change pixel values in BGR image (in open cv, BGR = RGB, weird!)
    import numpy as np
    import cv2
    import random
    import datetime
    
    # help code more readable
    ESCAPE_KEY = 27
    # seed every time start a new program
    random.seed(datetime.datetime.now())
    
    # read image
    img = cv2.imread('../../data/planet_glow.jpg', cv2.IMREAD_COLOR)
    # with color image, img.shape returns (row, column, channels)
    row, column, channels = img.shape
    
    # change all pixels to random value
    for i in xrange(row):
    	for j in xrange(column):
    		B_random = random.randint(0, 255)
    		G_random = random.randint(0, 255)
    		R_random = random.randint(0, 255)
    		img[i, j] = [B_random, G_random, R_random]
    
    # show image
    cv2.imshow("Image", img)
    
    # pause program, to help you see the image
    # press ESC key to exit
    if cv2.waitKey() == ESCAPE_KEY:
    	cv2.destroyAllWindows()
    

    But changing pixel values by indexing is not an appropriate way to do, instead using item (to retrieve value) and itemset (to change pixel value) method.

    import numpy as np
    import cv2
    
    ESCAPE_KEY = 27
    # B, G, R = 0, 1, 2 respectively
    B, G, R = 0, 1, 2 
    
    # read image
    img = cv2.imread('../../data/planet_glow.jpg', cv2.IMREAD_COLOR)
    # img.shape return (row, col, channels)
    row, col, channels = img.shape
    
    # for example
    # we want to set all B values of each pixel to 0
    # itemset((i, j, channel), new_val), channel could be B, G, R (or 0, 1, 2)
    for i in xrange(row):
    	for j in xrange(col):
    		new_val = 0
    		img.itemset((i, j, B), new_val)
    
    # show image
    cv2.imshow("Tittle", img)
    
    if cv2.waitKey() == ESCAPE_KEY:
    	cv2.destroyAllWindows()
    

    Here’s how you can change all pixel values without for loop, using numpy array syntax.

    import cv2
    import numpy as np
    import random
    import datetime
    
    ESCAPE_KEYS = 27
    random.seed(datetime.datetime.now())
    B, G, R = 0, 1, 2
    
    img = cv2.imread('../../data/planet_glow.jpg', cv2.IMREAD_COLOR)
    
    # change all pixels in original image to a random color
    # create a solid-random-color image
    B_random = random.randint(0, 255)
    G_random = random.randint(0, 255)
    R_random = random.randint(0, 255)
    img[:, :] = [B_random, G_random, R_random]
    
    # or change only channel B to random value
    img[:, :, B] = B_random
    # or change channels B, G to random value
    img[:, :, (B, G)] = (B_random, G_random)
    # or change all three channels
    # this have the same effect with line 17
    img[:, :, (B, G, R)] = (B_random, G_random, R_random)
    cv2.imshow("show", img)
    if cv2.waitKey() == ESCAPE_KEYS:
    	cd2.destroyAllWindows()
    
    • Copy a portion of an image, and place it overlap to other portion

    The code below copy all pixel values in a 100×100 portion, starting index (0,0) and place overlap it on portion with starting index (300, 300)

    import numpy as np
    import cv2
    
    ESCAPE_KEY = 27
    
    img = cv2.imread('../../data/planet_glow.jpg', cv2.IMREAD_COLOR)
    # get 100x100 portion with starting index at (0, 0)
    # and place it overlap portion with starting index at (300, 300)
    my_roi = img[0:100, 0:100]
    img[300:400, 300:400] = my_roi
    
    cv2.imshow("show", img)
    if cv2.waitKey() == ESCAPE_KEY:
    	cv2.destroyAllWindows()
    
     
  • loctv 8:54 am on February 13, 2017 Permalink | Reply
    Tags: ,   

    Problem: Word Boggle 

    *Difficulty: Medium

    Given a dictionary, a method to do lookup in dictionary and a M x N board where every cell has one character. Find all possible words that can be formed by a sequence of adjacent characters. Note that we can move to any of 8 adjacent characters, but a word should not have multiple instances of same cell.

    Example:

    Input: dictionary[] = {"GEEKS", "FOR", "QUIZ", "GO"};
           boggle[][]   = {{'G','I','Z'},
                           {'U','E','K'},
                           {'Q','S','E'}};
    
    Output:  Following words of dictionary are present
             GEEKS, QUIZ
    
    

    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 an integer x denoting the no of words in the dictionary. Then in the next line are x space separated strings denoting the contents of the dictinory. In the next line are two integers N and M denoting the size of the boggle. The last line of each test case contains NxM space separated values of the boggle.

    Output:
    For each test case in a new line print the space separated sorted distinct words of the dictionary which could be formed from the boggle. If no word can be formed print -1.

    Constraints:
    1<=T<=10
    1<=x<=10
    1<=n,m<=7

    Example:
    Input:

    1
    4
    GEEKS FOR QUIZ GO
    3 3
    G I Z U E K Q S E

    Output:
    GEEKS QUIZ

    *Approach: This problem is almost the same with this.
    The mechanism gonna be used here is back tracking. There are only two main parts in the algorithm:

    • With each cell in boggle matrix (two for loops)
      • Check all possible words that can be generated with that cell
      • While generating, if a generated word can be found in dictionary, add to result
      • if the length of generated word equal the length of longest word in dictionary, return (base case)
    • After getting all words, put them into a set to eliminate duplicate words, then sorted them alphabetically before output

    Suppose max_level is the length of longest word in dictionary, as soon as the length of a generated word exceeds max_level, we return. Why? Because if we still continue generating, there is no word will match anything in dictionary.

    Implementation: Python 2.7

    from __future__ import print_function
    
    def generate_words(x, y, dictionary, boggle, visited_cells, level, max_level, result, word):
    	visited_cells.append((x, y))
    	word += boggle[x][y]
    	#print word
    	if word in dictionary:
    		result.append(word)
    	eight_directions = ((x+1, y), (x-1, y), (x, y+1), (x, y-1),
    						(x+1, y+1), (x+1, y-1), (x-1, y+1), (x-1, y-1))
    	eight_directions = [(new_x,new_y) for new_x,new_y in eight_directions 
    		if in_bound(new_x, new_y, boggle) and (new_x, new_y) not in visited_cells]
    	if level > max_level:
    		return
    	for new_x, new_y in eight_directions:
    		generate_words(new_x, new_y, dictionary, boggle, 
    			visited_cells, level+1, max_level, result, word)
    		visited_cells.pop()
    
    def find_all_possible_words(dictionary, boggle):
    	max_level = get_max_level(dictionary)
    	overall_result = []
    	for x in xrange(len(boggle)):
    		for y in xrange(len(boggle[x])):		
    			result = []
    			visited_cells = []
    			level = 0
    			word = ""
    			generate_words(x, y, dictionary, boggle, visited_cells, level, max_level, result, word)
    			if result:
    				overall_result.extend(result)
    	overall_result = set(overall_result)
    	overall_result = list(sorted(overall_result))
    	if overall_result:
    	    print(*overall_result, sep=" ")
    	else:
    	    print(-1)
    
    def get_max_level(dictionary):
    	return max(len(x) for x in dictionary)
    
    def in_bound(x, y, boggle):
    	return (x >= 0 and x < len(boggle)) and (y >= 0 and y < (len(boggle[0])))
    
    if __name__ == '__main__':
    	t = input()
    	for _ in range(t):
    		n = input()
    		dictionary = raw_input().strip().split()
    		n, m = map(int, raw_input().strip().split())
    		boggle = []
    		temp = raw_input().strip().split()
    		for i in range(0, len(temp), m):
    			boggle.append(temp[i:i+m])
    		#print(dictionary)
    		#print(boggle)
    		find_all_possible_words(dictionary, boggle)
    

     

     

     
  • loctv 5:24 pm on February 9, 2017 Permalink | Reply
    Tags: ,   

    Fix: ‘pymysql.err.OperationalError: (2003 ‘ on Ubuntu 16.04 

    I’ve been learning web scraping with Python, and try using pymysql package.
    Here’s the script:

    import pymysql
    # connect with mysql
    conn = pymysql.connect(host='127.0.0.1', unix_socket='/tmp/mysql.sock',
    					user='root', passwd='02390128', db='mysql')
    cur = conn.cursor()
    cur.execute("USE scraping;")
    cur.execute("SELECT * FROM pages WHERE id=1")
    print(cur.fetchone())
    cur.close()
    conn.close()
    

    I run this script through terminal command:

    python xxx.py
    

    and getting this error:

    Traceback (most recent call last):
      File "ConnectMYSQL.py", line 4, in <module>
        user='root', passwd=None, db='mysql')
      File "/home/loctv/Documents/Python/WebCrawling/scarpingEnv/local/lib/python2.7/site-packages/PyMySQL-0.6.2-py2.7.egg/pymysql/__init__.py", line 88, in Connect
        return Connection(*args, **kwargs)
      File "/home/loctv/Documents/Python/WebCrawling/scarpingEnv/local/lib/python2.7/site-packages/PyMySQL-0.6.2-py2.7.egg/pymysql/connections.py", line 626, in __init__
        self._connect()
      File "/home/loctv/Documents/Python/WebCrawling/scarpingEnv/local/lib/python2.7/site-packages/PyMySQL-0.6.2-py2.7.egg/pymysql/connections.py", line 818, in _connect
        2003, "Can't connect to MySQL server on %r (%s)" % (self.host, e))
    pymysql.err.OperationalError: (2003, "Can't connect to MySQL server on '127.0.0.1' ([Errno 2] No such file or directory)")
    

    Here’s my way to fix this shit:
    I figured out that the reason is not because MySQL server cannot connect on ‘127.0.0.1’, the reason is the socket name, which is ‘/tmp/mysql.sock’ is wrong.
    To fix this, type this command in terminal

    mysqladmin -u root -p variables | grep socket
    

    Then enter your password
    This is what I get:

    screenshot-from-2017-02-09-17-19-04

    As you can see, the socket name is not ‘/tml/mysql.sock’, it is ‘/var/run/mysqld/mysqld.sock’
    So I copy that name, and change the script into:

    import pymysql
    # connect with mysql
    conn = pymysql.connect(host='127.0.0.1', unix_socket='/var/run/mysqld/mysqld.sock',
    					user='root', passwd='02390128', db='mysql')
    cur = conn.cursor()
    cur.execute("USE scraping;")
    cur.execute("SELECT * FROM pages WHERE id=1")
    print(cur.fetchone())
    cur.close()
    conn.close()
    

    Notice that this is one of the many solutions to fix this, it’s just that this works for me. So if you get into the same issue, and still not be able to fix it, let’s try this out.

     
  • 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:56 pm on February 6, 2017 Permalink | Reply
    Tags: ,   

    Problem: Longest K unique characters substring 

    *Difficulty: easy

    Given a string you need to print the size of the longest possible substring that has exactly k unique characters. If there is no possible substring print -1.
    Example
    For the string aabacbebebe and k = 3 the substring will be cbebebe with length 7.
    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 each test case contains a string s and the next line conatains an integer k.

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

    Constraints:
    1<=T<=100
    1<=k<=10

    Example:
    Input:

    2
    aabacbebebe
    3
    aaaa
    1
    Output:
    7
    4

    Implementation: Python 2.7

    #code
    def all_sub_string(k, string, all_substr):
        if k > len(string):
            return 
        elif k == len(string):
            all_substr.append(string)
            return
        else:
            for i in range(len(string)):
                if i + k > len(string):
                    break
                all_substr.append(string[i:i+k])
            all_sub_string(k+1, string, all_substr)
    
    def longest_k_unique_char_substr(all_substr, k):
        if k > len(all_substr[-1]):
            return -1
        max_length = -1
        for substr in all_substr:
            if len(substr) >= k and len(set(substr)) == k:
                if len(substr) > max_length:
                    max_length = len(substr)
        return max_length
                
    
    def main():
        t = input()
        for _ in xrange(t):
            string = raw_input().strip()
            k = input()
            all_substr = []
            all_sub_string(1, string, all_substr)
            print longest_k_unique_char_substr(all_substr, k)
    
    if __name__ == '__main__':
        main()
    
     
  • loctv 3:35 pm on February 6, 2017 Permalink | Reply
    Tags: ,   

    Simple Python script for unzipping 

    import sys
    import zip file
    
    def unzip(zipfile_path, tofolder_path):
        zip_ref = zipfile.ZipFile(zipfile_path, 'r')
        zip_ref.extractall(tofolder_path)
        zip_ref.close()
    
    def main():
        if len(sys.argv) != 3:
            raise Exception('Must be 3 arguments')
        else:
            zipfile_path, tofolder_path = sys.argv[1:]
            unzip(zipfile_path, tofolder_path)
    
    if __name__ == '__main__':
    main()
    

    Github:

     
  • loctv 9:33 pm on February 4, 2017 Permalink | Reply
    Tags: ,   

    Problem: Kth Prime factor of a Number 

    • Difficulty: Easy

    Given two numbers n and k, print Kth prime factor among all prime factors of n.

    Note: if k > all the count of prime factor of n, then print -1

    Input:

    The first line of input contains an integer denoting the no of test cases. Then T test cases follow. Each test case contains two space seperated integers n and k respectively.
    Output:

    For each test case ouput a simple line containing a single integer denoting kth prime factor of n.
    Constraints:

    1<=T<=100
    0<=N<=104
    1<=K<=50
    Example:

    Input:

    2
    225 2
    81 5

    Ouput:

    3
    -1

    Explanation:

    Test Case 1:  n=225 and k=2

    Prime factor of 225 are: 3,3,5,5

    Kth prime factor is 3

    Test Case 2: n=81 and k=5

    Prime factor of 81 is 3,3,3,3

    since k is greater than all the count of prime factor, hence we print -1

    Approach: This is not the fastest solution, but it’s fairly fast. Enough to paste the biggest test case in less than 100 ms. Using sieve of Eratosthenes to generate first 10000 primes, then use it as a dictionary to find all prime factors of a number. There are multiple ways to solve this problem, since the constraints is not big, so this solution is not only simple but fast.

    Implementation: Python 2.7

    #code
    import math
    def sieveOfEratosthenes(n):
        sieve = [True]*(n+1)
        sieve[0] = sieve[1] = False
        for i in range(2, int(math.sqrt(n))):
            if sieve[i]:
                for j in range(i+i, len(sieve), i):
                    sieve[j] = False
        return [i for i in range(len(sieve)) if sieve[i]]
    
    def primeFactors(number, primes):
        factors, i = [], 0
        while number > 1:
            if number % primes[i] == 0:
                factors.append(primes[i])
                number /= primes[i]
            else:
                i += 1
        return factors
    
    def main():
        t = input()
        primes = sieveOfEratosthenes(10000)
        for _ in range(t):
            number, k = map(int, raw_input().strip().split())
            factors = primeFactors(number, primes)
            print -1 if k > len(factors) else factors[k-1]
            
    if __name__ == '__main__':
        main()
    
     
  • loctv 3:24 pm on February 4, 2017 Permalink | Reply
    Tags: ,   

    DynamicArray in Python 

    Using ctypes module, we can create a new DynamicArray type. See more ctypes documentation to understand.

    import ctypes 
    
    class DynamicArray:
        def __init__(self):
            """ Create an empty array """
            self._n = 0 # count actual elements in array
            self._capacity = 1
            self._A = self._make_array(self._capacity)
        
        def __len__(self):
            """ Return number of elements stored in array """
            return self._n
        
        def __getitem__(self, k):
            """ return element at index k """
            if not 0 <= k < len(self):
                raise IndexError('invalid index')
            return self._A[k] # retrieve from array
        
        def append(self, obj):
            """ Add object to the end of array """
            if len(self) == self._capacity: # not enough room
                self._resize(2 * self._capacity) # so double capacity
            self._A[self._n] = obj
            self._n += 1
        
        def _resize(self, c):
            """ Resize the old array to capacity c """
            print 'Call resize'
            B = self._make_array(c) # new bigger array
            for k in xrange(self._n): # copy the old array to bigger array
                B[k] = self._A[k]
            self._A = B
            self._capacity = c
        
        def _make_array(self, c):
            """ Return a new array with capacity c """
            return (c * ctypes.py_object)() # see ctypes documentation
        
        def insert(self, k, value):
            """ Insert value at index k in array by shifting rightmost elements to the right """
            if not 0 <= k < len(self):
                raise IndexError('invalid index')
            if self._n == len(self): # not enough room
                self.resize(2 * self._capacity) # double capacity
            for j in range(self._n, k, -1): # shift rightmost first
                self._A[j] = self._A[j-1]
            self._A[k] = value # get new element
            self._n += 1
        
        def remove(self, value):
            """ remove the first occurence of value """
            for k in xrange(len(self)):
                if self._A[k] == value: # found 
                    for j in range(k, len(self)-1): # shift all elements on the right side to left
                        self._A[j] = self._A[j+1]
                    self._A[len(self)-1] = None # garbage collection
                    self._n -= 1 # reduce n 
                    return # exit immediately
            raise ValueError('value not found') 
    
        def __str__(self):
            """ presentation of dynamic array (user friendly form) """
            pre = "["
            for i in xrange(len(self)):
                pre += str(self[i]) + (", " if i < len(self)-1 else "]")
            return pre
    
    # test out the DynamicArray
    if __name__ == '__main__':
        arr = DynamicArray()
        for i in range(100):
            arr.append(i)
        # print call resize 7 times
        print arr
    

    An attribute (instance, method) with zero underscore is considered as public. One underscore is protected and two is private. Try it yourself, if you use two underscore, you cannot access the object’s attributes outside of class.

     
  • 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()
    
     
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