## Thug life creator

Demo:

Source code:

https://github.com/MrNocTV/ThugLifeCreator

## Problem:

*Difficulty: Easy

Problem:

ctci-find-the-running-median-english

Approach:
Since the constraints is so high, we need a way to insert and sort the array (or list) that has the complexity equal or lower than O(logn). With n loop and each loop costs O(logn) we have the complexity O(nlogn), which is acceptable. Using linked list and binary search is one of the possible ways. But If you know Python, this problem can be solved in 10 lines of code, using insort method from bisect module.

Implementation: Python 3

```import bisect

n = int(input())
l = []
for _ in range(n):
ai = int(input())
bisect.insort(l, ai)
if len(l) % 2 == 0:
print('%.1f' % ((l[len(l)//2-1]+l[len(l)//2])/2))
else:
print('%.1f' % (l[len(l)//2]))
```

## Problem: Separate the Numbers

*Difficulty: Easy

Problem:
separate-the-numbers-english

Approach:
Here’s how I did it, and I think example is the best way to explain it:
Example:
s = 1011121314
Start with first number = 10, next is 11, next is 12, …..
Eventually, return True
The maximum length of first number will be equal len(s) // 2 (if length s is even), or len(s) // 2 + 1 (length s is odd)
Let’s take another example:
10000001000001
First number: 1, next 0 => False
First number: 10, next 00=> False
First number: 100, next 000=>False
First number: 1000. next 000=>False
….
First number:1000000 next 1000001 => True
Hope you get the idea :>

Implementation: Python 3

```def is_beautiful(number):
if number == '' or number[0] == '0' or len(number) <= 2:
return [False]
bound = len(number) // 2
start_length = 1
while start_length <= bound:
first_str = number[:start_length]
first_int = int(first_str)
i = start_length
try:
while i < len(number):
next = next_str(i, first_str, first_int, number)
if next is None:
break
else:
changed = False
next_1, next_2 = next
if int(next_1) == first_int+1:
first_str = next_1
first_int = int(next_1)
i += len(next_1)
changed = True
else:
if next_2:
if int(next_2) == first_int+1:
first_str = next_2
first_int = int(next_2)
i += len(next_2)
changed = True
# cant found next number
if not changed:
break
# check out of bound
if i > len(number):
break
# all numbers statisfy the condition
if i == len(number):
return True, number[:start_length]
except Exception:
pass
start_length += 1
return [False]

def next_str(i, first_str, first_int , number):
# get the next number
# check if it has equal or longer length
# return two next, but only one of them is usable
next_1 = ""
next_2 = ""
if i < len(number):
if number[i] == '0':
return None
else:
if i + len(first_str) <= len(number):
next_1 = number[i:i+len(first_str)]
if i + len(first_str) + 1 <= len(number):
next_2 = number[i:i+len(first_str)+1]
return next_1, next_2
return None

def main():
t = int(input())
for _ in range(t):
number = str(input().strip())
result = is_beautiful(number)
if result[0]:
print('YES', result[1])
else:
print('NO')

if __name__ == '__main__':
main()
```

## 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))
```

## Problem: Arrays Left Rotation

• Difficulty: Easy

Problem description:
Array Left Rotation pdf

All approaching ideas is inspired by Python.
Approach: The first thing come in my mind is using a for loop, using Python list slice notation. But it’s too expensive both in computing muscle and memory usage. With the constraints, it will get TLE. Another approach is using modular arithmetic. Basically, rotate array d times means that we start iterating at index d. We have to use modular arithmetic to wrap around the array in case of reaching the end of array but still haven’t iterated through all elements yet.

Implementation: Python 3

```def rotate(arr, d):
count = 0
start = d % len(arr)
while count < len(arr):
print(arr[start], end=' ')
count += 1
start = (start + 1) % len(arr)
print()

if __name__ == '__main__':
n, d = list(map(int, input().strip().split()))
arr = list(map(int, input().strip().split()))
rotate(arr, d)
```

## Learn openCV3 (Python): Contours, Convex Contours, Bounding Rect, Min Area Rect, Min Enclosing Circle, Approximate Bounding Polygon.

Beside edges detection, contour detection is also one of the vital tasks in computer vision. One thing to notice here is that when find contours, we usually work with thresholded image. What is thresholding image? Just Google it, it’s simply putting a threshold value for pixels, if those pixels have value bigger than threshold value, they’re gonna be set to a new value.

This is a very simple example, when we find contour in an image that have black background and a white rectangle in its center.

First we create a 200×200 grayscale image having black background by using numpy.zeros method. Then we create a 100×100 white squares in that image. Next we threshold the image, every pixels that have values higher than 127 will be set to 255. Then we use opencv’s findContours() method to find all contours in the image. cv2.RETR_TREE basically means you want to get all contours. This method returns a tuple with 3 elements,  we only need to focus on the second one, contours. Keep in mind that findContours(), as well as many other methods in opencv, usually only work well with gray scale images. Finally we use drawContours() with green color to make all contours visible.

```import cv2
import numpy as np

ESC = 27

# create a black image with size 200x200 (in grayscale)
img = np.zeros((200, 200), dtype=np.uint8)
# set the center of image to be a 50x50 white rectangle
img[50:150, 50:150] = 255

# threshold the image
# if any pixels that have value higher than 127, assign it to 255
ret, threshed_img = cv2.threshold(img, 127, 255, 0)

# find contour in image
# cv2.RETR_TREE retrieves the entire hierarchy of contours in image
# if you only want to retrieve the most external contour
# use cv.RETR_EXTERNAL
image, contours, hierarchy = cv2.findContours(threshed_img, cv2.RETR_TREE,
cv2.CHAIN_APPROX_SIMPLE)
# convert image back to BGR
color_img = cv2.cvtColor(img, cv2.COLOR_GRAY2BGR)
# draw contours onto image
img = cv2.drawContours(color_img, contours, -1, (0, 255, 0), 2)

cv2.imshow("contours", img)

while True:
keycode = cv2.waitKey()
if keycode != -1:
keycode &amp;= 0xFF
if keycode == ESC:
break

cv2.distroyAllWindows
```

Result:

Next, we will see how to find a bounding box, minimum area rectangle, and minimum enclosing circle. (There is a tutorial on opencv website talking about this, you can check it out now or later)

Let’s take this image as an example.

You already know how to find contours in an image, so we won’t talk detailedly about that anymore. What we’re gonna talk about is finding bounding rect, min area rect, and enclosing circle of the ‘object’ in that image.

First let’s write code to find contours .

```import cv2
import numpy as np

# read and scale down image

# threshold image
ret, threshed_img = cv2.threshold(cv2.cvtColor(img, cv2.COLOR_BGR2GRAY),
127, 255, cv2.THRESH_BINARY)
# find contours and get the external one
image, contours, hier = cv2.findContours(threshed_img, cv2.RETR_EXTERNAL,
cv2.CHAIN_APPROX_SIMPLE)

cv2.drawContours(img, contours, -1, (255, 255, 0), 1)

cv2.imshow("contours", img)

ESC = 27
while True:
keycode = cv2.waitKey()
if keycode != -1:
keycode &amp;= 0xFF
if keycode == ESC:
break
cv2.destroyAllWindows()
```

There is a different here. Instead of retrieving all contours, we only retrieve the outermost contour. Here’s the result:

The contour wrap the ‘object’ is drawn in (255, 255, 0) color. The thickness is only 1, you can change the thickness by altering the last argument in cv2.drawContours().
Here’s how cv2.RETR_TREE will look like:

It’s time to find the bounding rect, min area rect, and min enclosing circle.

```import cv2
import numpy as np

# read and scale down image

# threshold image
ret, threshed_img = cv2.threshold(cv2.cvtColor(img, cv2.COLOR_BGR2GRAY),
127, 255, cv2.THRESH_BINARY)
# find contours and get the external one
image, contours, hier = cv2.findContours(threshed_img, cv2.RETR_TREE,
cv2.CHAIN_APPROX_SIMPLE)

# with each contour, draw boundingRect in green
# a minAreaRect in red and
# a minEnclosingCircle in blue
for c in contours:
# get the bounding rect
x, y, w, h = cv2.boundingRect(c)
# draw a green rectangle to visualize the bounding rect
cv2.rectangle(img, (x, y), (x+w, y+h), (0, 255, 0), 2)

# get the min area rect
rect = cv2.minAreaRect(c)
box = cv2.boxPoints(rect)
# convert all coordinates floating point values to int
box = np.int0(box)
# draw a red 'nghien' rectangle
cv2.drawContours(img, [box], 0, (0, 0, 255))

# finally, get the min enclosing circle
# convert all values to int
center = (int(x), int(y))
# and draw the circle in blue
img = cv2.circle(img, center, radius, (255, 0, 0), 2)

print(len(contours))
cv2.drawContours(img, contours, -1, (255, 255, 0), 1)

cv2.imshow("contours", img)

ESC = 27
while True:
keycode = cv2.waitKey()
if keycode != -1:
keycode &amp;= 0xFF
if keycode == ESC:
break
cv2.destroyAllWindows()
```

Use cv2.boundingRect to get the bounding rectangle (in green), cv2.minAreaRect to get the minimum area rectangle (in red), and cv2.minEnclosingCircle to get minimum enclosing circle (in blue).

Result:

More on contours, convex hull.

```import cv2
import numpy as np

# threshold image
ret, threshed_img = cv2.threshold(cv2.cvtColor(img, cv2.COLOR_BGR2GRAY),
127, 255, cv2.THRESH_BINARY)
# get contours from image
image, contours, hier = cv2.findContours(threshed_img, cv2.RETR_EXTERNAL,
cv2.CHAIN_APPROX_SIMPLE)

# for each contour
for cnt in contours:
# get convex hull
hull = cv2.convexHull(cnt)
# draw it in red color
cv2.drawContours(img, [hull], -1, (0, 0, 255), 1)

cv2.imshow("contours", img)

ESC = 27
while True:
keycode = cv2.waitKey(25)
if keycode != -1:
keycode &amp;= 0xFF
if keycode == ESC:
break

cv2.destroyAllWindows()
```

Result:

With the demonstration, you can figure out what ‘convex hull’ is.

Besides convex hull, there is one more thing you need to know is ‘approximate polygon’. I consider an approximate polygon is a basic shape of an object. In OpenCV, approximate bounding polygon can be calculated by using cv2.approxPolyDP. This method use Douglas-Peucker algorithm.

```import numpy
import cv2

# threshold image
# this step is neccessary when you work with contours
ret, threshed_img = cv2.threshold(cv2.cvtColor(img, cv2.COLOR_BGR2GRAY),
127, 255, cv2.THRESH_BINARY)
# find contours in image
image, contours, hier = cv2.findContours(threshed_img, cv2.RETR_EXTERNAL,
cv2.CHAIN_APPROX_SIMPLE)

for cnt in contours:
# calculate epsilon base on contour's perimeter
# contour's perimeter is returned by cv2.arcLength
epsilon = 0.01 * cv2.arcLength(cnt, True)
# get approx polygons
approx = cv2.approxPolyDP(cnt, epsilon, True)
# draw approx polygons
cv2.drawContours(img, [approx], -1, (0, 255, 0), 1)

# hull is convex shape as a polygon
hull = cv2.convexHull(cnt)
cv2.drawContours(img, [hull], -1, (0, 0, 255))

cv2.imshow('contours', img)
ESC = 27

while True:
keycode = cv2.waitKey()
if keycode != -1:
keycode &amp;= 0xFF
if keycode == ESC:
break

cv2.destroyAllWindows()
```

Result:

The approx bounding polygon is in green, and the convex hull is in red.

Again, you can find code example on OpenCV website, I post this because I want to share what I’ve learn. My explanations might be different than things that you get on opencv website, so you will not read the same thing twice.

## Learn OpenCV3 (Python): Simple Image Filtering

In image filtering, the two most basic filters are LPF (Low Pass Filter) and HPF(High Pass Filter).
LPF is usually used to remove noise, blur, smoothen an image.
Whereas HPF is usually used to detect edges in an image.
Both LPF and HPF use kernel to filter an image.
A kernel is a matrix contains weights, which always has an odd size (1,3,5,7,..).
In case of LPF, all values in kernel sum up to 1. If the kernel contains both negative and positive weights, it’s probably used to sharpen (or smoothen) an image. Example

```kernel_3x3 = numpy.array([
[-1, -1, -1],
[-1,  9, -1],
[-1, -1, -1]
])
```

If the kernel contains only positive weights and sum up to 1, it’s used to blur an image. Example

```kernel = numpy.array([
[0.04, 0.04, 0.04, 0.04, 0.04],
[0.04, 0.04, 0.04, 0.04, 0.04],
[0.04, 0.04, 0.04, 0.04, 0.04],
[0.04, 0.04, 0.04, 0.04, 0.04],
[0.04, 0.04, 0.04, 0.04, 0.04]
])
# or you can use nump.ones
kernel = numpy.ones((5, 5), numpy.float32) / 25
```

The last line of code in the example above can be visualize in this picture:

It first creates a 5×5 matrix with all weights 1, and then divides 25 to make all the weights sum up to 1.

In case of HPS, the kernel contains both negative and positive weights, sum up to 0. Example

```kernel_3x3 = numpy.array([
[-1, -1, -1],
[-1,  8, -1],
[-1, -1, -1]
])
```

These are three most basic and common kernels. You can create a kernel with left side is positive weights and right side is negative weights to make a new effect.

Now we’ve known about LPS, FPS and kernel. Let’s apply them with OpenCV.
A kernel is applied on an image with an operation call ‘convolve’.  There are multiple ways to convolve an image with a kernel.

• scipy.ndimage.convolve(img, kernel)
• cv2.filter2D(src_image, channel_depth, kernel, dst_image)

Examples:

```import scipy.ndimage
import cv2
import numpy as np

# create a 3x3 kernel
kernel_3x3 = np.array([
[-1, -1, -1],
[-1,  8, -1],
[-1, -1, -1]
])
# create a 5x5 kernel
kernel_5x5 = np.array([
[-1, -1, -1, -1, -1],
[-1,  1,  2,  1, -1],
[-1,  2,  4,  2, -1],
[-1,  1,  2,  1, -1],
[-1, -1, -1, -1, -1]
])

# convolve image with kernel
k3 = scipy.ndimage.convolve(img, kernel_3x3)
k3_1 = cv2.filter2D(img, -1, kernel_3x3)
k5 = scipy.ndimage.convolve(img, kernel_5x5)
k5_1 = cv2.filter2D(img, -1, kernel_5x5)

# show images
cv2.imshow("3x3", k3)
cv2.imshow("5x5", k5)
cv2.imshow("3x3_1", k3_1)
cv2.imshow("5x5_1", k5_1)

# wait for ESC to be pressed
ESC = 27
while True:
keycode = cv2.waitKey(25)
if keycode != -1:
keycode &= 0xFF
if keycode == ESC:
break

cv2.destroyAllWindows()
```

Result:

3×3

3x3_1

5×5

5x5_1

As you can see, the result is very different between cv2.filter2D and scipy.ndarray.convolve.

One last example I want to show you is stroking edges in an image. This involve bluring (using cv2.medianFilter), finding edge (using cv2.Laplacian), normalize and inverse image.

```import cv2
import numpy as np

def strokeEdge(src, dst, blurKSize = 7, edgeKSize = 5):
# medianFilter with kernelsize == 7 is expensive
if blurKSize >= 3:
# first blur image to cancel noise
# then convert to grayscale image
blurredSrc = cv2.medianBlur(src, blurKSize)
graySrc = cv2.cvtColor(blurredSrc, cv2.COLOR_BGR2GRAY)
else:
# scrip blurring image
graySrc = cv2.cvtColor(src, cv2.COLOR_BGR2GRAY)
# we have to convert to grayscale since Laplacian only works on grayscale images
# then we can apply laplacian edge-finding filter
# cv2.CV_8U means the channel depth is first 8 bits
cv2.Laplacian(graySrc, cv2.CV_8U, graySrc, ksize=edgeKSize)
# normalize and inverse color
# making the edges have black color and background has white color
normalizedInverseAlpha = (1.0 / 255) * (255 - graySrc)
channels = cv2.split(src)
# multiply normalized grayscale image with source image
# to darken the edge
for channel in channels:
channel[:] = channel * normalizedInverseAlpha
cv2.merge(channels, dst)
```

Result:

increase ksize of median and Laplacian you will get something like this:

## 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 .

```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
# 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
)

# loop until there is no more frame
while success:
# write frame by frame
videoWriter.write(frame)
```
• 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
# 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

# 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
# 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

# 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())
ESCAPE_KEY = 27

# read image and change to gray scale
# 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

ESCAPE_KEY = 27
# seed every time start a new program
random.seed(datetime.datetime.now())

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

# 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

# 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

# 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

# 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)
```

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r