python – Page 4 – Code Says

Solution to Peaks by codility

26 Jan

Question: http://codility.com/demo/take-sample-test/peaks Question Name: Peaks UPDATE on July 18th 2015: Many thanks to @Antonio Correia (https://34.145.67.234/2014/solution-to-peaks-by-codility/#comment-11725) !!! @Antonio Correia found a huge bug in my solution, even though it passed the codility.com. The bug has been fixed.

def solution(A):

from math import sqrt

A_len = len(A)

peaks_until_here = [0]*A_len

# Retrieve how many peaks exist from beginning to current

# position.

for index in range(1, A_len-1):

peaks_until_here[index] = peaks_until_here[index-1]

if A[index] > A[index-1] and A[index] > A[index+1]:

peaks_until_here[index] += 1

if A_len < 3 or peaks_until_here[-2] == 0:

# The array is too short to have a peak. OR

# There is no peak in this array.

return 0

peaks_until_here[-1] = peaks_until_here[-2]

max_blocks = 0

# Compute every possible partition plan, and find out the

# one with most blocks.

for candidate in range(1, int(sqrt(A_len))+1, 1):

if A_len % candidate == 0:

blocks, block_size = candidate, A_len//candidate

# Check the first block.

if peaks_until_here[0] < peaks_until_here[block_size-1]:

# Check the following blocks.

for each_block in range(block_size, A_len, block_size):

if peaks_until_here[each_block-1] == \

peaks_until_here[each_block+block_size-1]:

# No peak is found in the next block

# This partition plan is not accepted

break

else:

max_blocks = blocks

if candidate * candidate == A_len:

# If candidate is equal to sqrt(A_len) exactly,

# candidate would equal to A_len//candidate.

continue

block_size, blocks = candidate, A_len//candidate

# Check the first block.

if peaks_until_here[0] < peaks_until_here[block_size-1]:

# Check the following blocks.

for each_block in range(block_size, A_len, block_size):

if peaks_until_here[each_block-1] == \

peaks_until_here[each_block+block_size-1]:

# No peak is found in the next block

# This partition plan is not accepted

break

else:

return blocks

return max_blocks

Solution to Min-Perimeter-Rectangle by codility

26 Jan

Question: http://codility.com/demo/take-sample-test/min_perimeter_rectangle Question Name: MinPerimeterRectangle Let the length of one side be len_1, and the length of one adjacent side be len_2. For a rectangle with a constant area, the perimeter is minimized when the difference between len_1 and len_2, … Read More »

Solution to Max-Slice-Sum by codility

26 Jan

Question: http://codility.com/demo/take-sample-test/max_slice_sum Question Name: MaxSliceSum The classic maximum subarray problem. It should be the very first question in this lesson.

def solution(A):

max_slice_ending_here = A[0]

max_slice = A[0]

for element in A[1:]:

max_slice_ending_here = max(element, max_slice_ending_here+element)

max_slice = max(max_slice, max_slice_ending_here)

return max_slice

Solution to Max-Profit by codility

25 Jan

Question: http://codility.com/demo/take-sample-test/max_profit Question Name: MaxProfit For this question, we have to travel from the last element to the first one.

def solution(A):

days = len(A)

# If the number of days is zero or one, there

# is no time to get profit.

if days < 2:

return 0

max_price_from_here = A[days-1]

max_profit = 0

for index in xrange(days-2, -1, -1):

# max_price_from_here-A[index] means the maximum

# profit from current day to end.

max_profit = max(max_profit, max_price_from_here-A[index])

max_price_from_here = max(A[index], max_price_from_here)

return max_profit

Solution to Max-Double-Slice-Sum by codility

25 Jan

Question: http://codility.com/demo/take-sample-test/max_double_slice_sum Question Name: MaxDoubleSliceSum A variant of the classic maximum subarray problem. We should travel the array twice. For the first travel, we compute and record the maximum sub-array sum, which ends at each position. At the second reverse … Read More »

Solution to Equi-Leader by codility

24 Jan

Question: http://codility.com/demo/take-sample-test/equi_leader Question Name: EquiLeader A variant of the previous question.

def solution(A):

A_len = len(A)

candidate = -1

candidate_count = 0

candidate_index = -1

# Find out a leader candidate

for index in xrange(A_len):

if candidate_count == 0:

candidate = A[index]

candidate_index = index

candidate_count += 1

else:

if A[index] == candidate:

candidate_count += 1

else:

candidate_count -= 1

# Make sure the candidate is the leader

leader_count = len([number for number in A if number == candidate])

if leader_count <= A_len//2:

# The candidate is not the leader

return 0

else:

leader = candidate

equi_leaders = 0

leader_count_so_far = 0

for index in xrange(A_len):

if A[index] == leader:

leader_count_so_far += 1

if leader_count_so_far > (index+1)//2 and

leader_count-leader_count_so_far > (A_len-index-1)//2:

# Both the head and tail have leaders of the same value

# as "leader"

equi_leaders += 1

return equi_leaders

Solution to Dominator by codility

24 Jan

Question: http://codility.com/demo/take-sample-test/dominator Question Name: Dominator Same question in the introduction pdf.

def solution(A):

A_len = len(A)

candidate = -1

candidate_count = 0

candidate_index = -1

for index in xrange(A_len):

if candidate_count == 0:

candidate = A[index]

candidate_index = index

candidate_count += 1

else:

if A[index] == candidate:

candidate_count += 1

else:

candidate_count -= 1

if len([number for number in A if number == candidate]) <= A_len//2:

return -1

else:

return candidate_index

Solution to Fish by codility

23 Jan

Question: http://codility.com/demo/take-sample-test/fish Question Name: Fish UPDATE 03-14-2014: “downstream_count” is a redundant variable. It could be replaced with len(downstream) safely. (Thanks to the reminder from Max)

def solution(A, B):

alive_count = 0 # The number of fish that will stay alive

downstream = [] # To record the fishs flowing downstream

downstream_count = 0 # To record the number of elements in downstream

for index in xrange(len(A)):

# Compute for each fish

if B[index] == 1:

# This fish is flowing downstream. It would

# NEVER meet the previous fishs. But possibly

# it has to fight with the downstream fishs.

downstream.append(A[index])

downstream_count += 1

else:

# This fish is flowing upstream. It would either

# eat ALL the previous downstream-flow fishs,

# and stay alive.

# OR

# be eaten by ONE of the previous downstream-

# flow fishs, which is bigger, and died.

while downstream_count != 0:

# It has to fight with each previous living

# fish, with nearest first.

if downstream[-1] < A[index]:

# Win and to continue the next fight

downstream_count -= 1

downstream.pop()

else:

# Lose and die

break

else:

# This upstream-flow fish eat all the previous

# downstream-flow fishs. Win and stay alive.

alive_count += 1

# Currently, all the downstream-flow fishs in stack

# downstream will not meet with any fish. They will

# stay alive.

alive_count += len(downstream)

return alive_count

Solution to sigma2012 (Stone-Wall) by codility

23 Jan

Question: http://codility.com/demo/take-sample-test/stone_wall Question Name: sigma2012 or StoneWall

def solution(H):

stack = []

block_count = 0 # The number of needing blocks

for height in H:

while len(stack) != 0 and height < stack[-1]:

# If the height of current block is less than

# the previous ones, the previous ones have

# to end before current point. They have no

# chance to exist in the remaining part.

# So the previous blocks are completely finished.

stack.pop()

block_count += 1

if len(stack) == 0 or height > stack[-1]:

# If the height of current block is greater than

# the previous one, a new block is needed for

# current position.

stack.append(height)

# Else (the height of current block is same as that

# of previous one), they should be combined to

# one block.

# Some blocks with different heights are still in the stack.

block_count += len(stack)

return block_count

Solution to Nesting by codility

22 Jan

Question: http://codility.com/demo/take-sample-test/nesting Question Name: Nesting This question is nearly the same as the previous one, but does not need a stack.

def solution(S):

parentheses = 0

for element in S:

if element == "(":

parentheses += 1

else:

parentheses -= 1

if parentheses < 0:

return 0

if parentheses == 0:

return 1

else:

return 0

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