Codility – Code Says

Solution to Rectangle-Builder-Greater-Area by codility

20 Nov

Question: https://codility.com/demo/take-sample-test/rectangle_builder_greater_area/ Question Name: Rectangle-Builder-Greater-Area or RectangleBuilderGreaterArea This key is the binary search.

def solution(A, X):

fence_count = {}

for fence in A:

fence_count[fence] = fence_count.get(fence, 0) + 1

num_of_pens = 0

usable_fences = []

for fence in fence_count:

if fence_count[fence] < 2:

# Less than one pair. We cannot use it.

continue

elif fence_count[fence] < 4:

usable_fences.append(fence)

else:

usable_fences.append(fence)

# We consider the square pen here.

if fence * fence >= X:

num_of_pens += 1

# We consider the non-square pen here.

usable_fences.sort()

candidate_size = len(usable_fences)

for i in xrange(candidate_size):

# Use binary search to find the first fence pair, that

# could be used with current pair to form a pen.

begin = i + 1

end = candidate_size - 1

while begin <= end:

mid = (begin + end) // 2

if usable_fences[mid] * usable_fences[i] >= X:

end = mid - 1

else:

begin = mid + 1

# Now the usable_fences[end + 1] is the first qualified

# fence.

combination_num = candidate_size - (end + 1)

num_of_pens += combination_num

if num_of_pens > 1000000000:

return -1

return num_of_pens

Solution to Dwarfs-Rafting by codility

19 Nov

Question: https://codility.com/demo/take-sample-test/dwarfs_rafting/ Question Name: Dwarfs-Rafting or DwarfsRafting Need some simple mathematical knowledge. The code is unnecessarily long. A 2-d array is better to write much shorter code. However, I keep the long version for better readability.

def solution(N, S, T):

quadrant_left_front = (N // 2) * (N // 2)

quadrant_left_back = (N // 2) * (N // 2)

quadrant_right_front = (N // 2) * (N // 2)

quadrant_right_back = (N // 2) * (N // 2)

boundary = N // 2

# Compute how many slots are available in each quadrant.

for barrel in S.split():

# Adjust to 0-based index.

row = int(barrel[:-1]) - 1

column = ord(barrel[-1]) - ord("A")

if row < boundary:

# The barrel is in the front.

if column < boundary:

# The barrel is in the left.

quadrant_left_front -= 1

else:

# The barrel is in the right.

quadrant_right_front -= 1

else:

# The barrel is in the back.

if column < boundary:

# The barrel is in the left.

quadrant_left_back -= 1

else:

# The barrel is in the right.

quadrant_right_back -= 1

# lf is short for left front, etc.

# To keep balance, we need:

# 1. weight_lf + weight_lb = weight_rf + weight_rb

# 2. weight_lf + weight_rf = weight_rf + weight_rb

# Solve the equations and we can get the answer:

# 1. weight_lf = weight_rb

# 2. And weight_rf = weight_lb

allowance_lf = min(quadrant_left_front, quadrant_right_back)

allowance_rb = min(quadrant_left_front, quadrant_right_back)

allowance_lb = min(quadrant_left_back, quadrant_right_front)

allowance_rf = min(quadrant_left_back, quadrant_right_front)

# Minus the seats, which are already occupied by dwarfs.

for dwarf in T.split():

# Adjust to 0-based index.

row = int(dwarf[:-1]) - 1

column = ord(dwarf[-1]) - ord("A")

if row < boundary:

# The dwarf is in the front.

if column < boundary:

# The dwarf is in the left.

allowance_lf -= 1

if allowance_lf < 0: return -1

else:

# The dwarf is in the right.

allowance_rf -= 1

if allowance_rf < 0: return -1

else:

# The dwarf is in the back.

if column < boundary:

# The dwarf is in the left.

allowance_lb -= 1

if allowance_lb < 0: return -1

else:

# The dwarf is in the right.

allowance_rb -= 1

if allowance_rb < 0: return -1

return allowance_lf + allowance_rb + allowance_lb + allowance_rf

Solution to Slalom-Skiing by codility

22 Oct

Question: https://codility.com/programmers/lessons/90-tasks_from_indeed_prime_2015_challenge/slalom_skiing/ Question Name: Slalom-Skiing or SlalomSkiing This is a wonderful variant of longest increasing subsequence. Because the longest increasing subsequence is a very classic question withe O(NlogN) solution, the key point to solve this question is to covert its original form … Read More »

Solution to Flood-Depth by codility

25 Sep

Question: https://codility.com/demo/take-sample-test/flood_depth/ Question Name: Flood-Depth or FloodDepth This is a variant of Trapping Rain Water by LeetCode. The undergoing concept is the same. However, the implementation is a bit different.

from collections import namedtuple

def solution(A):

if len(A) < 3:

return 0

# The blocks in the stack is in strictly height descending order.

# For the first block in the stack, its max_depth is maximum water

# depth of its (exclusive) left area.

# The other blocks' max_depth is the maximum water depth between its

# previous block in the stack and itself, both exclusive.

Block = namedtuple("Block", ["height", "max_depth"])

stack = [Block(A[0],0)]

for height in A[1:]:

if height == stack[-1].height:

# These two adjacent blocks have the same height. They act

# totally the same in building any water container.

continue

elif height < stack[-1].height:

stack.append(Block(height, 0))

else:

max_depth = 0

# Let the current iterating block be C, the previous two

# blocks in the stack be A and B. And their positions are

# demoed as:

# C

# A C

# A ... B ... C

# while the blocks between A and B are omitted. So do the

# blocks between B and C.

# The additional_depth consider the blocks A, B, and C only,

# and igonres all the omitted blocks, such as:

# C

# A C

# A B C (no block is between A and B, or B and C)

# HOWEVER, the additional_depth is not always the maximum

# water depth between A and C, because there may be some

# water between A and B, or B and C, as exists in the omitted

# blocks. We need to adjust the additional_depth to get the

# maximum water depth between A and C, both exclusive.

while len(stack) > 1 and height > stack[-1].height:

additional_depth = min(stack[-2].height, height) - \

stack[-1].height

max_depth = max(max_depth, stack[-1].max_depth) + \

additional_depth

stack.pop()

# Combine leftward same-or-less-height blocks. These dropped

# blocks are never going to be part of the remaining water

# container.

while len(stack) > 0 and height >= stack[-1].height:

max_depth = max(max_depth, stack[-1].max_depth)

stack.pop()

stack.append(Block(height, max_depth))

overall_max_depth = 0

for block in stack:

if block.max_depth > overall_max_depth:

overall_max_depth = block.max_depth

return overall_max_depth

Solution to Longest-Password by codility

22 Sep

Question: https://codility.com/demo/take-sample-test/longest_password/ Question Name: Longest-Password or LongestPassword The solution could be more Pythonic with some additional space.

def solution(S):

longest = -1

num_of_letters = 0

num_of_digits = 0

num_of_others = 0

for letter in S:

if letter.isalpha():

num_of_letters += 1

elif letter.isdigit():

num_of_digits += 1

elif letter == " ":

# Check whether it's a valid password.

if num_of_others == 0 and \

num_of_letters % 2 == 0 and \

num_of_digits % 2 == 1:

if longest < num_of_letters + num_of_digits:

longest = num_of_letters + num_of_digits

# Reset the counters for the next word.

num_of_letters = 0

num_of_digits = 0

num_of_others = 0

else:

num_of_others += 1

# Check whether the last word is a valid password.

if num_of_others == 0 and \

num_of_letters % 2 == 0 and \

num_of_digits % 2 == 1:

if longest < num_of_letters + num_of_digits:

longest = num_of_letters + num_of_digits

return longest

Solution to Sql-Sum by codility

21 Sep

Question: https://codility.com/demo/take-sample-test/sql_sum/ Question Name: Sql-Sum or SqlSum This question is too easy to be a serious training lesson. Most likely, it’s a live test for SQL challenges on Codility.com. The following solution works in both PostgreSQL and SQLite.

1	SELECT SUM(v) FROM elements

Solution to Cyclic-Rotation by codility

9 Feb

Question: https://codility.com/demo/take-sample-test/cyclic_rotation/ Question Name: Cyclic-Rotation or CyclicRotation With Python’s syntactic sugar, the solution is pretty short.

def solution(A, K):

# write your code in Python 2.7

if len(A) == 0:

return A

K = K % len(A)

return A[-K:] + A[:-K]

Well, kind of too easy. Let’s try a C++ solution to demo the details better. Thanks to @micropentium6, the original C++ solution is … Read More »

Solution to Polygon-Concavity-Index by codility

18 Oct

Question: https://codility.com/demo/take-sample-test/polygon_concavity_index/ Question Name: Polygon-Concavity-Index or PolygonConcavityIndex Thanks to Robert Sedgewick, the Youtube video (Algorithms, Part I – Convex Hull) tells everything about this problem.

def _IsClockwise(point_A, point_B, point_C):

''' Return the direction from points A -> B -> C.

'''

result = (point_B.x - point_A.x) * (point_C.y - point_A.y) -

(point_B.y - point_A.y) * (point_C.x - point_A.x)

# The direction of a->b->c is:

if result > 0: return 1 # counter-clockwise

elif result < 0: return -1 # clockwise

else: return 0 # a staight line

def solution(A):

''' The solution refers to:

https://www.youtube.com/watch?v=0HZaRu5IupM

'''

# Find the lowest point(s) in y-axis.

lowest_y = A[0].y

lowest_y_index = []

for i in xrange(len(A)):

if A[i].y < lowest_y:

lowest_y = A[i].y

lowest_y_index = [i]

elif A[i].y == lowest_y:

lowest_y_index.append(i)

else:

continue

# Find a point, which is not the lowest in y-axis and immediately

# after a lowest-in-y-axis point.

start_point = lowest_y_index[0]

lowest_y_array = [False] * len(A)

for i in lowest_y_index: lowest_y_array[i] = True

while lowest_y_array[start_point] == True:

start_point = (start_point + 1) % len(A)

start_point = (start_point - 1 + len(A)) % len(A)

# Re-organize the points so that, it is easier to check every three

# consecutive points in one loop (without module operation %).

rotated_A = A[start_point : ] + A[ : start_point]

# We find the start point such that, the direction is non-zero.

direction = _IsClockwise(rotated_A[-1], rotated_A[0], rotated_A[1])

extened_A = rotated_A + rotated_A[:2]

for i in xrange(len(A)):

temp = _IsClockwise(extened_A[i], extened_A[i+1], extened_A[i+2])

if temp * direction < 0:

# Compute the original index and return

return (i + 1 + start_point)%len(A)

# Every point is on the convex hull.

return -1

Solution to Odd-Occurrences-In-Array by codility

18 Sep

Question: https://codility.com/programmers/task/odd_occurrences_in_array Question Name: Odd-Occurrences-In-Array or OddOccurrencesInArray This question is completely the same as the Perm-Missing-Elem by codility. The comment from Kim is very helpful.

def solution(A):

result = 0

for number in A:

result ^= number

return result

Solution to Number-Solitaire by codility

6 Sep

Question: https://codility.com/demo/take-sample-test/number_solitaire/ Question Name: Number-Solitaire or NumberSolitaire The key point is: to achieve the position i, we can only come from the positions i-6, i-5, i-4, i-3, i-2, and i-1.

def solution(A):

# The first six items are used for padding only, so that we can have

# a unified for loop, no matter how many squares are there in input.

# The first item is never accessed.

max_so_far = [A[0]] * (len(A) + 6)

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

# Because we have a fixed length of window as 6, the time

# complexity of max(max_so_far[index : index + 6]) is O(1).

max_so_far[index + 6] = max(max_so_far[index : index + 6]) +

A[index]

return max_so_far[-1]

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