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.

 

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

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)

 

 

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:

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.

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.

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

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:

Simple-Script-For-Unzipping-File/Main.py

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<=10⁴
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()

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.

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

 

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