## A little talk for my comeback!

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

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

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

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

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

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

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


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


• #### Gulsah Ayhan 11:36 pm on November 8, 2017 Permalink | Reply

Thanks for the solution, however I still have the same error

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


## Problem: Find all four sum numbers

*Difficulty: Medium

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

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

Output:
For each test case in a new line print all the quadruples present in the array separated by space which sums up to value of K. Each quadruple is unique which are separated by a delimeter “$” and are in increasing order. Constraints: 1<=T<=100 1<=N<=100 -1000<=K<=1000 -100<=A[]<=100 Example: Input: 2 5 3 0 0 2 1 1 7 23 10 2 3 4 5 7 8 Output: 0 0 1 2$
2 3 8 10 $2 4 7 10$3 5 7 8 $Approach: Using itertools in Python, I can easily quickly generate all combination-length-four of an arr. #code from __future__ import print_function import itertools def allFourSumNumber(arr, K): result = [] for four in itertools.combinations(arr, 4): if sum(four) == K: if four not in result: result.append(four) return result def main(): t = input() for _ in range(t): n, K = map(int, raw_input().strip().split()) arr = map(int, raw_input().strip().split()) found = False for four in allFourSumNumber(sorted(arr), K): found = True print(four[0], four[1], four[2], four[3], '$', end='')

if __name__ == '__main__':
main()


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

## Problem: Sum of All Subarrays

*Difficulty: Medium

Given an array A with N elements , you need to find the sum all sub arrays of array A. Since the sum could be very large print the sum modulo (10^9+7).

Input :
The first line contains integer T, denoting number of test cases. The first line of each test case contains an integer N, denoting the number of elements.The second line of each test case contains N space separated integers denoting values of the array A.
Output :
Print the answer of each test case in a new line.

Constraints :
1<=T<=10
1<=N<=10^5

Example
Input :

2
3
1 2 3
2
1 3

Output :
20
8

*Approach 1:

Generate all sub arrays
This is O(n^3) complexity solution

Code: Python 2.7

def sum_all_sub_arrs(arr):
if len(arr) == 1:
return arr[0]
elif len(arr) == 2:
return arr[0] + arr[1] + sum(arr)
elif len(arr) == 3:
return sum(arr)*2 + arr[0] + arr[1] + arr[1] + arr[2]
else:
sum_all = 0
for i in range(2, len(arr)):
for j in range(len(arr)):
#print arr[j:j+i]
sum_all += sum(arr[j:j+i])
if j+i == len(arr):
break
return sum_all + sum(arr)*2

if __name__ == '__main__':
t = input()
for _ in range(t):
n = input()
arr = map(int, raw_input().strip().split())
print sum_all_sub_arrs(arr) % (10**9+7)


It cant be applied to solve this problem, since if using C++, I can barely pass this problem with runtime nearly reach 5 seconds. (This is Python, so it’s impossible)

After 30 minutes working on papers, I figured out something’s interesting.
Example with input array’s length is odd
Array: 1 2 3 4 5
Sum of all sub-arrays:
1 + 2 + 3 + 4 + 5 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 1 + 2 + 3 + 2 + 3 + 4+ 3 + 4 + 5 + 1 + 2 + 3 + 4 + 2 + 3 + 4 + 5 + 1 + 2 + 3 +4 + 5 = 105
Here’s is the array and the number of times of each element in the equation above:
Array:              1 – 2 – 3 – 4 – 5
Frequency:     5 – 8 – 9 – 8 – 5
Example with input array’s length is even
Array: 1 2 3 4
Sum of all sub-arrays:
1 + 2 + 3 + 4 + 1 + 2 + 2 + 3 + 3 +4 + 1 +2 +3 + 2 + 3 + 4 + 1 +2 + 3 + 4 = 50
Array:           1 – 2 – 3 – 4
Frequency: 4 – 6 – 6 – 4
In general:
+ if length of input array is odd, and n is the length
Frequency: n –  prev+(n-2)  – prev+(n-4) – … – prev+1  – … – prev+(n-4)  – prev+(n-2) – n
+ if length of input array is even, and n is the length
Frequency: n – prev+(n-2) – prev+(n-4) – ….. – prev+(n-4) – prev+(n-2) – n

Code: Python 2.7

def sum_all_sub_arrs(arr):
# input array contains only one element
if len(arr) == 1:
return arr[0]
# init steps
frequency = [0]*len(arr)
dif = len(arr)-2
# because frequency values are symmetric
# example: 4 6 6 4
#          3 4 3
#          etc
# we need to traverse only half first of the input array
# and work out the frequency of each value
for i in range(0, len(arr)//2 + 1 if len(arr) % 2 != 0 else len(arr)//2):
# first frequency = len(arr)
if i == 0:
frequency[i] = len(arr)
# then, each of next element is its previous cell plus difference
# and decrease the difference by 2
else:
frequency[i] += (frequency[i-1] + dif)
dif -= 2
# half left of frequency
for i in range(len(arr)//2+1 if len(arr) % 2 != 0 else len(arr)//2, len(arr)):
offset = len(arr) - i - 1
frequency[i] = frequency[offset]
return sum(x*y for (x,y) in zip(arr, frequency))

if __name__ == '__main__':
t = input()
mod = 10**9 + 7
for _ in range(t):
n = input()
arr = map(int, raw_input().strip().split())
print sum_all_sub_arrs(arr) % mod


Solution took: 94ms

• #### loctv 11:33 pm on January 23, 2017 Permalink | Reply

Feeling tired!zzzzZz!!!

## Problem: Deficient Number

*Difficulty: Easy

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

Mathematically, if below condition holds the number is said to be Deficient:
Examples:

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

Input: 12
Output: NO

Input: 17
Output: YES

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

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

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

3
21
12
17
Output:
1
0
1

How to solve:
Using prime factorization

Implementation: Python 2.7

def get_primes():
"""
an efficient way to calculate prime numbers
"""
yield 2
yield 3
i = 5
while True:
yield i
if i%6 == 1:
i += 2
i += 2

def get_prime_factors(n):
"""
get prime factors of a number
"""
d = {}
primes = get_primes()
for p in primes:
while n % p == 0:
n /= p
d[p] = d.setdefault(p, 0) + 1
if n == 1:
return d

def sum_of_divisors(d, n):
if len(d) == 1: #n is a prime number
return n+1
s = 1
for factor in d.keys():
s *= ((1-pow(factor, d[factor]+1))/(1-factor))
return s

if __name__ == '__main__':
t = input()
for _ in range(t):
n = input()
prime_factors = get_prime_factors(n)
if sum_of_divisors(prime_factors, n) < n*2:
print 1
else:
print 0



## Micro Project: Reversi

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

Here’s the code: (Python 2.7)

import sys
import random

class Reversi:
def __init__(self):
self.player_tile = ''
self.computer_tile = ''
self.board = self.get_new_board()
self.game_state = 'CONTINUE'
self.reset_board(self.board)

def draw_board(self, board):
HLINE = '   ' + '+---'*8+'+'

print '     ' + '   '.join(map(str, range(1, 9)))
print HLINE
for i in xrange(8):
print str(i+1) + ' ',
for j in xrange(8):
print '| %s' % (board[i][j]),
print '|'
print HLINE

def reset_board(self, board):
for i in xrange(8):
for j in xrange(8):
board[i][j] = ' '
board[3][3] = 'X'
board[4][3] = 'O'
board[3][4] = 'O'
board[4][4] = 'X'

def get_new_board(self):
board = []
for i in xrange(8):
board.append([' ']*8)
return board

def is_valid_move(self, board, char, xstart, ystart):
if not self.is_on_board(xstart, ystart) or board[xstart][ystart] != ' ':
return False
other_tile = 'X' if char == 'O' else 'O'
tiles_to_flip = []

for xdirection, ydirection in [[0,1], [1,1], [1,0], [1,-1], [0,-1], [-1,-1], [-1,0], [-1,1]]:
x,y = xstart, ystart
x += xdirection
y += ydirection

if self.is_on_board(x,y) and board[x][y] == other_tile:
x += xdirection
y += ydirection
if not self.is_on_board(x,y):
continue

while board[x][y] == other_tile:
x += xdirection
y += ydirection
if not self.is_on_board(x, y):
break

if not self.is_on_board(x, y):
continue

if board[x][y] == char:
while True:
x -= xdirection
y -= ydirection
if x == xstart and y == ystart:
break
tiles_to_flip.append([x,y])
board[xstart][ystart] = ' '
if len(tiles_to_flip) == 0:
return False
return tiles_to_flip

def is_on_board(self, x, y):
return x &gt;= 0 and x &lt;= 7 and y &gt;= 0 and y &lt;= 7     def get_valid_moves(self, board, tile):         valid_moves = []         for i in xrange(8):             for j in xrange(8):                 if self.is_valid_move(board,tile,i,j) != False:                     valid_moves.append([i,j])         return valid_moves     def get_board_with_validmoves(self, board, tile):         copy_board = self.get_board_copy(board)         for x,y in self.get_valid_moves(copy_board, tile):             copy_board[x][y] = '.'         return copy_board     def get_score(self, board):         x_score, o_score = 0, 0         for x in xrange(8):             for y in range(8):                 if board[x][y] == 'X':                     x_score += 1                 if board[x][y] == 'O':                     o_score += 1         return {'X':x_score, 'O':o_score}     def get_board_copy(self, board):         copy_board = self.get_new_board()         for x in xrange(8):             for y in xrange(8):                 copy_board[x][y] = board[x][y]         return copy_board     def player_choose_tile(self):         tile = ''         while not (tile == 'X' or tile == 'O'):             print 'Do you want to play \'X\' or \'O\'?'             tile = raw_input().strip()         self.player_tile = 'X' if tile == 'X' else 'O'         self.computer_tile = 'X' if self.player_tile == 'O' else 'O'     def who_goes_first(self):         if random.randint(0, 1) == 1:             return 'computer'         return 'player'     def play_again(self):         print 'Do you want to play again? (y,n)'         return raw_input().strip().startswith('y')     def make_move(self, board, tile, xstart, ystart):         tiles_to_flip = self.is_valid_move(board,tile,xstart,ystart)         if tiles_to_flip == False:             return False         board[xstart][ystart] = tile         for x,y in tiles_to_flip:             board[x][y] = tile         return True     def is_corner(self, x, y):         return (x == 0 and y == 0) or (x == 7 and y == 0) or (x == 0 and y == 7) or (x == 7 and y == 7)     def get_player_move(self, board, player_tile):         DIGITS = ' '.join(map(str, range(1, 9))).split()         while True:             print 'Enter your move, or type quit to end game, or hints to get hints'             move = raw_input().strip().lower()             if move == 'quit':                 return 'quit'             if move == 'hints':                 return 'hints'             if len(move) == 2 and move[0] in DIGITS and move[1] in DIGITS:                 x = int(move[0]) - 1                 y = int(move[1]) - 1                 if self.is_valid_move(board, player_tile, x, y):                     break             else:                 print 'That is not a valid move. Type the x digit(1-8), then the y digit (1-8)'                 print 'For example, 81 will be the bottom left corner'         return [x, y]     def get_computer_move(self, board, computer_tile):         possible_moves = self.get_valid_moves(board, computer_tile)         random.shuffle(possible_moves)         for x,y in possible_moves:             if self.is_corner(x,y):                 return [x, y]         best_score = -1         best_move = []         for x, y in possible_moves:             copy_board = self.get_board_copy(board)             self.make_move(copy_board, computer_tile, x, y)             score = self.get_score(copy_board)[computer_tile]             if score &gt; best_score:
best_move = [x,y]
best_score = score
return best_move

def show_points(self, player_tile, computer_tile, board):
score = self.get_score(board)
print 'You have %s points. The compute has %s points' % (score[player_tile], score[computer_tile])

def reset(self):
self.board = self.get_new_board()
self.reset_board(self.board)
self.player_tile = ''
self.computer_tile = ''

def start_game(self):
while self.game_state == 'CONTINUE':
self.reset()
self.player_choose_tile()
turn = self.who_goes_first()
self.draw_board(self.board)
while True:
if turn == 'player':
move = self.get_player_move(self.board, self.player_tile)
if move == 'quit':
print 'Thanks for playing'
sys.exit()
elif move == 'hints':
print 'Hints:'
self.draw_board(self.get_board_with_validmoves(self.board, self.player_tile))
print
continue
else:
self.make_move(self.board, self.player_tile, move[0], move[1])
self.draw_board(self.board)
self.show_points(self.player_tile, self.computer_tile, self.board)
if self.get_valid_moves(self.board, self.computer_tile) == []:
break
else:
turn = 'computer'
else:
raw_input('Press enter to see computer move')
x,y = self.get_computer_move(self.board, self.computer_tile)
print (x+1), (y+1)
self.make_move(self.board, self.computer_tile, x, y)
self.draw_board(self.board)
self.show_points(self.player_tile, self.computer_tile, self.board)
if self.get_valid_moves(self.board, self.player_tile) == []:
break
else:
turn = 'player'

self.draw_board(self.board)
scores = self.get_score(self.board)
print 'X scored %s, O scored %s' % (scores['X'], scores['O'])
if scores[self.player_tile] &gt; scores[self.computer_tile]:
print 'You beat the computer by %s points. Congratulations!' %  (scores[self.player_tile]-scores[self.computer_tile])
self.game_state = 'WIN'
elif scores[self.player_tile] &lt; scores[self.computer_tile]:
print 'You lost. Computer beat you by %s points' % (scores[self.computer_tile] - scores[self.player_tile])
self.game_state = 'GAME_OVER'
else:
print 'I don\'t know how but this was a tie'
if self.play_again():
self.game_state == 'CONTINUE'

if __name__ == '__main__':
game = Reversi()
game.start_game()


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

• Init

Initialize player_tile, computer_tile, board and game_state

• draw_board:

Simply draw the 8×8 board in console. The board will look like this:

• reset_board:

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

• get_new_board:

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

• is_valid_move:

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

• is_on_board:

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

• get_valid_moves:

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

• get_board_with_validmoves

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

• get_score:

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

• get_board_copy:

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

• who_goes_first:

Randomly pick computer or player.

• play_again:

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

• make_move:

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

• is_corner:

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

• get_player_move:

Just check until player enter a valid move.

• get_computer_move:

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

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

## Problem: Pallindrome Patterns

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

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

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

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

Examples

Input
3
abbab
abcabc
abc

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

Using itertools in python
Python 2.7

from itertools import *
def pallindrome_permute(s):
"""
return permutations of s that is a
pallindrome string
"""
res = set(list(permutations(s)))
for x in res:
x = ''.join(x)
if is_pallindrome(x):
yield x

def is_pallindrome(s):
"""
check if a string is pallindrome
"""
length = len(s)
length_2 = length/2
for _ in range(length_2):
if s[_] != s[length-1-_]:
return False
else:
return True

if __name__ == '__main__':
t = input()
for _ in range(t):
s = raw_input().strip()
print "{",
for _ in sorted(list(pallindrome_permute(s))):
print _,
print "}"


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