Python – Page 24 – Code Says

Solution to gamma2011 (Count-Palindromic-Slices) by codility

5 Feb

Question: https://codility.com/demo/take-sample-test/count_palindromic_slices Question Name: CountPalindromicSlices This task is based on the longest palindromic substring question, which has a good solution naming Manacher’s algorithm. Some explanation about the algorithm could be found here (English) and here (Chinese).

def palindrome_substring(str):

''' Input: string

Attention: the input string will be extended. For example,

original string abc would be converted into #a#b#c#.

Output: array, to say palindrome_len.

palindrome_len[i] records the half width (include

the element in position i) of palindrome substring,

which centers in position i.

Method: Manacher's algorithm

Time complexity: O(n)

'''

str = "#" + "#".join(str) + "#" # Convert the original string so

# that, every palindrome substring

# in the new string has odd number

# of elements.

palindrome_len = [0] * len(str) # Store the half width (include the

# center point) of the longest

# palindrome substring with index

# being the substring's center.

# palindrome_len[i]-1 means the full

# length of palindrome substring in

# the original string.

bound = 0 # Record the first positin, that the previous computed

# palindrome substrings chould NOT achieve.

center = 0 # Record the center position of the substring, which

# is corresponding to "bound".

for index in xrange(len(str)):

if bound > index:

# Part of current substring has already been compared.

# For point "index", 2*center-index is the point

# symmetrical to the points "center".

palindrome_len[index] =

min( palindrome_len[2*center-index], bound-index )

else:

# None of current substring has been compared.

palindrome_len[index] = 1

# Compare the uncompared elements one by one.

while index-palindrome_len[index] >= 0 and

index+palindrome_len[index] < len(str) and

str[index-palindrome_len[index]] ==

str[index+palindrome_len[index]]:

palindrome_len[index] += 1

if bound < palindrome_len[index] + index:

# The bound has been extended.

center = index

bound = palindrome_len[index] + index

return palindrome_len

def solution(S):

# With center point i, if the longest palindrome substring

# has length of j, the number of palindrome substrings,

# with the same center, is j//2.

count = sum([

(length-1)/2 for length in palindrome_substring(S) if length>2

])

if count > 100000000:

return -1

else:

return count

Solution to Array-Inversion-Count by codility

4 Feb

Question: https://codility.com/demo/take-sample-test/array_inversion_count Question Name: ArrayInversionCount

def mergesort( aList, first, last ):

''' Modified merge sort algorithm.

Record the inversion count during sort.

'''

mid = ( first + last ) / 2

if first < last:

# Recursive calling

left_inver = mergesort( aList, first, mid )

right_inver = mergesort( aList, mid + 1, last )

else:

# Terminate condition

return 0

first_index = first # The index for the left part

second_index = mid + 1 # The index for the right part

temp = [0] * (last-first+1) # To hold the sorted content

temp_index = 0

merge_inver = 0 # Number of inversion in merging

while first_index <= mid and second_index <= last:

if aList[first_index] <= aList[second_index]:

# Less index indicates less value. No inversion.

temp[temp_index] = aList[first_index]

first_index += 1

else:

# Greater index has less value. Inversion exists.

# For exampe:

# [ 4, 5, 2, 3 ]

# | Left part | |Right Part|

# and first_index = 1, second_index = 3, mid = 2

# We need the item "2" to be the position 0. So it

# has to pass all the unwritten items in left part.

# Here these unwritten items are "4" and "5". So

# two more inversions are involved.

# In general, the left part is sorted. So all the

# elements, being and after first_index, are greater

# than element in position second_index. AND all of

# them have less indexes. As the result,

# there are mid-first_index+1 new reversions.

temp[temp_index] = aList[second_index]

second_index += 1

merge_inver += mid - first_index + 1

temp_index += 1

if first_index != mid+1:

# Some element in the left part left. They have less

# indexes, but greater values. Inversion involves.

# BUT these inversions have already been counted.

while first_index <= mid:

temp[temp_index] = aList[first_index]

first_index += 1

temp_index += 1

if second_index != last+1:

# Some element in the right part left. They have both

# greater indexes and values than all in the left part.

# No inversion is involved.

while second_index <= last:

temp[temp_index] = aList[second_index]

second_index += 1

temp_index += 1

# Rewrite the sorted content into the original array

aList[first:last+1] = temp[:]

return merge_inver + left_inver + right_inver

def solution(A):

return mergesort( A * 1, 0, len(A)-1)

UPDATE on July 18, 2014: Thanks to @Andrew, there is another solution with Binary Indexed Tree. UPDATE on October 8, 2014: Thanks to @Piotrek Martynowicz, there was a bug for the statement: “computes the … Read More »

Solution to omega2013 (Falling-Disks) by codility

4 Feb

Question: https://codility.com/demo/take-sample-test/falling_disks Question Name: omega2013 or FallingDisks

def solution(A, B):

# Find the smallest diameter to achieve each position

min_diameter_so_far = [A[0]] * len(A)

for index in xrange(1, len(A)):

min_diameter_so_far[index] = min(min_diameter_so_far[index-1], A[index])

rings_index = len(A) - 1 # Travel the well from bottom to top

fit_disks = 0 # The number of fitted disks

for disks_index in xrange(len(B)):

while min_diameter_so_far[rings_index] < B[disks_index]:

rings_index -= 1

if rings_index == -1:

# No way to fit into the well for current disk, and

# therefore the remaining disks.

return fit_disks

fit_disks += 1 # Current disk occupies this ring of well

rings_index -= 1

if rings_index == -1:

# The toppest ring of well is used. No way to fit any

# more disk.

break

return fit_disks

Solution to Equi by codility

2 Feb

Question: https://codility.com/demo/take-sample-test/equi Question Name: Equi The expected worst-case space complexity could be less than required.

def solution(A):

heading = 0 # The sum of A[0] + A[1] + ... + A[P-1]

tailing = sum(A) # The sum of A[P] + A[P+1] + ... + A[N-2] + A[N-1]

for index in xrange(len(A)):

tailing -= A[index] # The sum of A[P+1] + ... + A[N-2] + A[N-1]

if heading == tailing:

# A[0] + A[1] + ... + A[P-1] == A[P+1] + ... + A[N-2] + A[N-1]

return index

heading += A[index]

else:

# No equilibrium is found.

return -1

Solution to lithium2013 (Clocks) by codility

2 Feb

Question: https://codility.com/demo/take-sample-test/clocks Question Name: lithium2013 or Clocks At the very beginning, I found this task is very similar with the string rotation question in CTCI. And I did transfer this question into a string rotation one. The string rotation solution … Read More »

Solution to Tree-Height by codility

29 Jan

Question: https://codility.com/demo/take-sample-test/tree_height Question Name: TreeHeight Classic recursion problem.

def solution(T):

if T.l == None and T.r == None:

# Has no subtree

return 0

elif T.l == None:

# Only has right subtree

return 1 + solution(T.r)

elif T.r == None:

# Only has left subtree

return 1 + solution(T.l)

else:

# Have two subtrees

return 1 + max(solution(T.l), solution(T.r))

Solution to Abs-Distinct by codility

29 Jan

Question: https://codility.com/demo/take-sample-test/abs_distinct Question Name: AbsDistinct In the original requirement, expected worst-case space complexity is O(N). But actually, O(1) is enought.

def solution(A):

abs_distinct = 1

current = max(abs(A[0]), abs(A[-1]))

index_head = 0

index_tail = len(A)-1

while index_head <= index_tail:

# We travel the array from the greatest

# absolute value to the smallest.

former = abs(A[index_head])

if former == current:

# Skip the heading elements, whose

# absolute values are the same with

# current recording one.

index_head += 1

continue

latter = abs(A[index_tail])

if latter == current:

# Skip the tailing elements, whose

# absolute values are the same with

# current recording one.

index_tail -= 1

continue

# At this point, both the former and

# latter has different absolute value

# from current recorded one.

if former >= latter:

# The next greatest value is former

current = former

index_head += 1

else:

# The next greatest value is latter

current = latter

index_tail -= 1

# Meet with a new absolute value

abs_distinct += 1

return abs_distinct

Solution to Binary-Gap by codility

29 Jan

Question: https://codility.com/demo/take-sample-test/binary_gap Question Name: BinaryGap

def solution(N):

max_gap = 0

current_gap = 0

# Skip the tailing zero(s)

while N > 0 and N%2 == 0:

N //= 2

while N > 0:

remainder = N%2

if remainder == 0:

# Inside a gap

current_gap += 1

else:

# Gap ends

if current_gap != 0:

max_gap = max(current_gap, max_gap)

current_gap = 0

N //= 2

return max_gap

Solution to alpha2010 (Prefix-Set) by codility

29 Jan

Question: https://codility.com/demo/take-sample-test/prefix_set Question Name: alpha2010 or PrefixSet At the first glance, I think the set of Python is the best choice. Actually, the set solution passed all the test, and got 100/100 grade.

def solution(A):

alphabet = set()

for element in A:

alphabet.add(element)

for index in xrange(len(A)):

alphabet.discard(A[index])

if len(alphabet) == 0:

return index

BUT, acording to the time complexity … Read More »

Solution to Count-Semiprimes by codility

28 Jan

Question: https://codility.com/demo/take-sample-test/count_semiprimes Question Name: CountSemiprimes

def solution(N, P, Q):

from math import sqrt

# Find out all the primes with Sieve of Eratosthenes

prime_table = [False]*2+[True]*(N-1)

prime = []

prime_count = 0

for element in xrange(2, int(sqrt(N))+1):

if prime_table[element] == True:

prime.append(element)

prime_count += 1

multiple = element * element

while multiple <= N:

prime_table[multiple] = False

multiple += element

for element in xrange(int(sqrt(N))+1, N+1):

if prime_table[element] == True:

prime.append(element)

prime_count += 1

# Compute the semiprimes information

semiprime = [0] * (N+1)

# Find out all the semiprimes.

# semiprime[i] == 1 when i is semiprime, or

# 0 when i is not semiprime.

for index_former in xrange(prime_count-1):

for index_latter in xrange(index_former, prime_count):

if prime[index_former]*prime[index_latter] > N:

# So large that no need to record them

break

semiprime[prime[index_former]*prime[index_latter]] = 1

# Compute the number of semiprimes until each position.

# semiprime[i] == k means:

# in the range (0,i] there are k semiprimes.

for index in xrange(1, N+1):

semiprime[index] += semiprime[index-1]

# the number of semiprimes within the range [ P[K], Q[K] ]

# should be semiprime[Q[K]] - semiprime[P[K]-1]

question_len = len(P)

result = [0]*question_len

for index in xrange(question_len):

result[index] = semiprime[Q[index]] - semiprime[P[index]-1]

return result

tl;dr: Please put your code into a <pre>YOUR CODE</pre> section.

Hello everyone!

If you want to ask a question about the solution. DO READ the post and comments firstly.

If you had some troubles in debugging your solution, please try to ask for help on StackOverflow, instead of here.

If you want to post some comments with code or symbol, here is the guidline.

1. To post your code, please add the code inside a <pre> </pre> section (preferred), or <code> </code>. And inside the pre or code section, you do not need to escape < > and &, e.g. no need to use < instead of <.

2. To use special symbols < and > outside the pre block, please use "<" and ">" instead.

3. If you have a comment with lots of < and >, you could add the major part of your comment into a <pre class="decode:true crayon-inline "> YOUR COMMENTS </pre> section.

Finally, if you are posting the first comment here, it usually needs moderation. Please be patient and stay tuned. Thanks!

CodeSays.com Admin

Ovi February 12, 2024 at 11:14 pm on Solution to Min-Perimeter-Rectangle by codilityExactly my question too. I tried something very similar to Sheng's solution, importing the math module and using sqrt(). Codility marked it only as 80%,...
Doron Ben Ari February 11, 2024 at 4:10 am on Solution to Min-Avg-Two-Slice by codilityInspired by Sheng's great solution, I wrote the following proof: Assume you found the slice with minimal average. Assume the first two consecutive elements of...
Ovi February 4, 2024 at 9:03 am on Solution to sigma2012 (Stone-Wall) by codility def solution(H): heights = H # geometric logic: the blocks need to be cuboid, all sides are rectagular. Nothing fancy, means that the angles...
Ovidiu Oprea February 2, 2024 at 11:06 am on Solution to Fish by codilityIt's the reason why it took me 2 weeks to finish this task (in the context of adult life with non-dev job). I was trying...
Ovi January 15, 2024 at 2:40 pm on Solution to Brackets by codilityThanks for this blog post! I was banging my head against the wall thinking this is a simple / short solution, where you just build...
parikshit verma July 5, 2023 at 8:26 am on Solution to Missing-Integer by codility def missingnum(a): st=min(a) en=max(a) b=set(range(1,en+2)) if (en<1 or st>1) : return 1 else: return min(b-set(a))
Pavankumar Nandeshwar June 26, 2023 at 8:07 am on Solution to Dwarfs-Rafting by codilityOk fixed it. gives 100%: int solution(int N, string &S, string &T) { int q = N / 2 * N / 2; int lf...
Pavankumar Nandeshwar June 26, 2023 at 5:23 am on Solution to Dwarfs-Rafting by codilityCan someone explain what is wrong with my solution in C++ ? int solution(int N, string &S, string &T) { int q = N /...
Pavankumar Nandeshwar June 23, 2023 at 10:25 pm on Solution to Flood-Depth by codilityMy C++ Solution. O(N) #include <climits> int solution(vector<int> &A) { int max_depth {}; int max_lvl = {}; int min_lvl = INT_MAX; for (unsigned int i...