Solution to Nailing-Planks by codility

8 Apr

April 8, 2014January 22, 2020 Sheng 15

Question: https://codility.com/demo/take-sample-test/nailing_planks

Question Name: Nailing Planks or NailingPlanks

This question is designed to be solved with binary search method (BUT there is a better solution! It is updated at the end of this post.). And the binary solution is as following:

def _findFirstNail(plankBegin, plankEnd, nails, preResult):

# Function: find the nails, that could nail this plank.

# Input: plankBegin: the begin position of current plank

# plankEnd: the end position of current plank

# nails: the nails' position and index

# preResult: for all of the previous planks, the

# first preResult+1 nails in original array

# could be sequentially used to nail them.

# Return: If all these nails are after the preResult's

# position, return the first nail's position in

# the original nails' array.

# Else, return the preResult as the result.

result = -1 # The index of nail in the original array

resultPos = -1 # The index of nail in the sorted array

nailLower = 0

nailUpper = len(nails) - 1

nailMid = 0

# Find the first nail, whose postion >= plankBegin and

# position <= plankEnd, with binary search algorithm

while nailLower <= nailUpper:

nailMid = (nailLower + nailUpper) / 2

nailPosMid = nails[nailMid][1]

if nailPosMid < plankBegin:

nailLower = nailMid + 1

elif nailPosMid > plankEnd:

nailUpper = nailMid - 1

else:

nailUpper = nailMid - 1

result = nails[nailMid][0]

resultPos = nailMid

# Cannot find one, which could nail the plank

if result == -1: return -1

# Linear search all the quanlified nails, and find

# out the one with the earliest position.

resultPos += 1

while resultPos < len(nails):

# Not quanlified anymore.

if nails[resultPos][1] > plankEnd: break

result = min(result, nails[resultPos][0])

resultPos += 1

# If we find a position before the preResult. We could

# terminate our search and return.

# With a position before the preResult, the result for

# this round must <= preResult. And globally, the final

# result is the maximum of ALL the results in each rounds.

# So the result of this round actually does not affect

# the final result.

if preResult >= result: return preResult

return max(result, preResult)

def solution(A, B, C):

# Sort the nails according to their positions

nails = sorted(enumerate(C), key = lambda x: x[1])

result = -1

for plankIndex in xrange(len(A)):

# Find a nail for the current plank

result = _findFirstNail(A[plankIndex], B[plankIndex], nails, result)

if result == -1: return -1 # Cannot find such a nail

return result + 1

In addition, there is an alternative solution without binary algorithm. This solution has a different but similar time complexity and space complexity (O(M+N)). And it does pass all the tests. Actually, for all binary search algorithms, they have a common issue: they access the items in different and non-consecutive places, that makes the modern data cache system valueless and helpless. That is the battle between heap sort and merge sort. That is also the battle among binary algorithms and their non-binary competitors. At lease in this war, non-binary wins. In the test result, the non-binary algorithm costs noticeable less time.

def solution(A, B, C):

result = -1 # Global result

# Sort the planks according to firstly their begin position,

# and then their end position

planks = zip(A, B)

planks.sort()

# Sort the nails according to their position

nails = sorted(enumerate(C), key = lambda x: x[1])

nailsIndex = 0

# Travel for each plank

for plankIndex in xrange(len(planks)):

plank = planks[plankIndex]

# Find the first quanified nail in linear manner. Beware

# that the planks are sorted. For any two adjacent planks,

# the begin position of the latter one will be:

# either the same as the former's begin position

# or after the former's

# In both cases, the nails, which before the nailsIndex

# of the former plank's round, would never be candidates

# in the latter plank's round. Thus we only need to search

# nails from the previous nailsIndex position.

while nailsIndex < len(nails):

if nails[nailsIndex][1] < plank[0]:

nailsIndex += 1

elif nails[nailsIndex][1] > plank[1]:

# And all the remaining nails > plank[1]

# Impossible to find a quanlified nail

return -1

else:

# plank[0] <= nails[nailsIndex][1] <= plank[1]

break

else:

# Cannot find one

return -1

if plankIndex != 0 and plank[0] == planks[plankIndex-1][0]:

# This plank and previous plank have the same begin

# position. And the planks are sorted. So the end

# position of this plank is after that of previous

# plank. We continue the previous search.

pass

else:

# This plank and previous plank have the different

# begin position. We have to re-search from the

# nailsIndex.

tempRes = len(nails) # Local result for this round

tempIndex = nailsIndex

# Find the first one in all the quanlified nails

while tempIndex < len(nails) and

plank[0] <= nails[tempIndex][1] <= plank[1]:

tempRes = min(tempRes, nails[tempIndex][0])

tempIndex += 1

# If we find a tempRes <= result, the final result

# of current round will <= result. This tempRes

# would never change the global result. Thus we

# could ignore it, and continue the next round.

if tempRes <= result: break

result = max(result, tempRes)

return result+1

Finally, thanks to @Guillermo (StackOverflow Profile) again, here is the C++ solution.

#include <algorithm>

#include <iostream>

#include <climits>

int binsearch(vector< pair<int,int> > &CP,int PlankB,int PlankE,int jmin)

{

int b,mid,e,value,resultpos,sjmin,j,CPsize;

CPsize=CP.size();

b=0;

e=CP.size()-1;

resultpos=-1;

// BinSearch for nail>=LeftPlankSide

while (b<=e)

{

mid = ( b + e) / 2;

value = CP[mid].first;

if ( value >= PlankB )

{

e=mid-1;

resultpos=mid;

}

else

{

b=mid+1;

}

if (-1 == resultpos) return -1;

value = CP[resultpos].first;

if (value > PlankE) return -1;

// Linear Search for nail <= RightPlankSide

// with j<jmin or smaller j

sjmin=INT_MAX;

while ( (value <= PlankE) && (resultpos < CPsize) )

{

j=CP[resultpos].second;

if (j <= jmin ) return jmin;

if (j < sjmin ) sjmin=j;

resultpos++;

if ( resultpos < CPsize ) value = CP[resultpos].first;

}

return sjmin;

}

int solution(vector<int> &A, vector<int> &B, vector<int> &C)

{

int i,j,n,m,jmin;

n = A.size();

m = C.size();

pair<int,int> p(0,0);

vector< pair<int,int> > CP(m,p);

for (j=0;j<m;j++)

{

CP[j].first =C[j];

CP[j].second=j;

}

sort( CP.begin(), CP.end() );

jmin=-1;

for (i=0;i<n;i++)

{

jmin = binsearch(CP,A[i],B[i],jmin);

if (-1==jmin) return -1;

}

return jmin+1;

}

UPDATE (May 2nd, 2016): Many thanks to Dragan@ (blog): he proposed a wonderful solution with linear time complexity. His blog includes a Java solution. And here is my Python.

100

101

102

103

104

105

106

107

108

from collections import deque

class MinQueue():

''' Implement a queue with min() function.

'''

def __init__(self):

# all_data is used to store all the raw data for this queue.

self.all_data = deque()

# min_data is used to store the data for min() function. The values

# in min_data is in non-decreasing order.

self.min_data = deque()

return

def enqueue(self, val):

self.all_data.append(val)

while self.min_data and self.min_data[-1] > val:

self.min_data.pop()

self.min_data.append(val)

return

def dequeue(self):

# Check if the queue is empty.

if not self.all_data: return None

# The to-dequeue value is the minimum in current queue.

if self.all_data[0] == self.min_data[0]:

self.min_data.popleft()

return self.all_data.popleft()

def dequeue_all_if(self, cond):

''' Remove all heading values, if they satisfy the condition "cond".

'''

while self.all_data and cond(self.all_data[0]):

self.dequeue()

return

def min(self):

''' Return the minimal item in current queue. min() is O(1).

'''

if self.min_data: return self.min_data[0]

else: return None

def solution(A, B, C):

# Step 1: Clear all wrapper planks. If there are two planks A and B:

# A.start <= B.start <= B.end <= A.end

# A is a wrapper plank to B.

# Step 1.1: all these planks having the same start point, remove the

# longer wrapper planks. The time complexity is O(N).

# There are at most 2 * len(C) planks.

# If plank_end_points[i] is not zero, there is a plank, starting at i,

# and ending at plank_end_points[i].

plank_end_points = [0] * (len(C) * 2 + 1)

for index in xrange(len(A)):

if plank_end_points[A[index]] == 0:

plank_end_points[A[index]] = B[index]

elif plank_end_points[A[index]] > B[index]:

# Replace with the new and shorter one.

plank_end_points[A[index]] = B[index]

else:

# Keep the old and shorter one.

pass

# Step 1.2: Remove all the other planks, who do not share the same start

# points. The time complexity is O(N), because every plank

# after step 1.1 will enter the stack "planks" once and may or

# may not exit the queue (once or never).

# All position values are in range [1..2*M]. Therefore 0 is never used.

planks = [] # Pairs of (begin, end), sorting with begin position.

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

if plank_end_points[index] != 0:

# Here is a plank.

while planks and planks[-1][1] >= plank_end_points[index]:

# Remove all the wrapper planks to current one.

planks.pop()

planks.append((index, plank_end_points[index]))

del plank_end_points

# Step 2: counting sort the nails, while removing the duplicate nails.

# The time complexity is O(M).

# If nails[i] is zero, there is not any nail in this place. Otherwise, if

# nails[i] = j, the j(th) nail in C is placed in the i position of the

# board.

nails = [-1] * (len(C) * 2 + 1)

for index in xrange(len(C)):

if nails[C[index]] == -1:

# If multiple nails hold the same position, we only keep the

# earliest one.

nails[C[index]] = index

# Step 3: find the minimum number of nails that must be used until all the

# planks are nailed. The time complexity is O(N+M), because:

# a) Every plank after step 1 is checked once and only once; O(N)

# b) After step 2, the nails, who are on top of any plank from a),

# will be enqueued once and only once; otherwise, the remaining

# nails are never touched; O(M)

# c) The enqueued nails will dequeue once OR never dequeue. O(M)

previous_plank = (0, 0)

# The content in nails_queue is (nail order in C, nail position in board)

# Nail order in C is used to compute min() function.

# Nail position in board is determining when to enter and exit queue.

nails_queue = MinQueue()

result = (-1, -1) # An impossible result as the initial value.

for plank in planks:

# Remove all nails before this planks.

nails_queue.dequeue_all_if(lambda x: x[1] < plank[0])

# Add all nails on this plank, if they are not in the queue.

# When this plank is overlapping with the previous one, the nails

# between plank[0] and previous_plank[1]] are already included in

# queue.

for index in xrange(max(plank[0], previous_plank[1]), plank[1] + 1):

if nails[index] != -1:

# Enqueue value: (nail order, nail position)

nails_queue.enqueue((nails[index], index))

# Maybe there is no nail on this plank.

if nails_queue.min() == None: return -1

# Find the earliest nail, which can fix this plank.

result = max(result, nails_queue.min())

return result[0] + 1

15 Replies to “Solution to Nailing-Planks by codility”

While codility will give you 100% for these solutions, they exceed specified time complexity. Worst case – they are O(m*n). Below is a test sample to demonstrate this. It has the same number of planks and nails (n) and clearly shows that if you double the input, the total runtime time is quadrupled.

from time import time

prev = None

for n in [500, 1000, 2000, 4000]:

A = [i for i in range(n)]

B = [n] * n

C = [i for i in range(n)]

start = time()

solution(A, B, C)

end = time()

current = end-start

print("{} took {}s".format(n, current))

if prev is not None:

print("Ratio with previous is {:.2f}".format(current/prev))

prev = current

Sheng says:
November 4, 2014 at 10:17 am
Yes, in the first solution:
Linear search all the quanlified nails.
So in the worst-case, it is N*M.
Reply

# This solution in python, takes O((N+M)*log(M) * log(log(M))), but passes the test suite on codility

def check(A, B, C, K):

# sort the nails if the positions are random

C.sort()

C_len = len(C)

A_len = len(A)

i = 0

j = 0

while K > 0 and i < C_len:

while j < A_len:

if A[j] <= C[i] <= B[j]:

j += 1

else:

break

K -= 1

i += 1

if K < 0 or j < A_len:

return False

else:

return True

def solution(A, B, C):

# sort the lists if random

A, B = (list(x) for x in zip(*sorted(zip(A, B), key=lambda pair: pair[0])))

# use binary search to findout the minimum number of nails needed

minPlanks = 1

maxPlanks = len(C)

result = -1

while minPlanks <= maxPlanks:

currMax = (minPlanks + maxPlanks) / 2

# pass in only the first currMax num of nails to check

if check(A, B, C[:currMax], currMax):

maxPlanks = currMax - 1

result = currMax

else:

minPlanks = currMax + 1

return result

Sheng says:
January 24, 2015 at 1:44 am
Thanks for sharing!
Reply

I used different approach:

bool nailed(vector &A, vector &B, vector &C, int maxNails) {

int n = A.size();

int m = C.size();

vector nailsCounter(m * 2 + 1, 0);

for (int i = 0; i < maxNails; ++i) {

nailsCounter[C[i]] = 1;

}

int counter = 0;

for (auto &v: nailsCounter) {

counter += v;

v = counter;

}

for (int i = 0; i < n; ++i) {

if (nailsCounter[A[i] - 1] == nailsCounter[B[i]]) return false;

}

return true;

}

int solution(vector &A, vector &B, vector &C) {

int lower = 1, upper = C.size();

if (!nailed(A, B, C, upper)) return -1;

while (lower < upper) {

int nails = (lower + upper) / 2;

if (nailed(A, B, C, nails)) upper = nails;

else lower = nails + 1;

}

return lower;

}

Sheng says:
February 27, 2015 at 12:29 am
Thanks for sharing!
Reply
Shashi says:
September 13, 2016 at 11:26 pm
Can you please explain the logic of your code? What is the purpose of nailsCounter?
Reply
- Sam says:
  January 15, 2019 at 4:53 am
  It’s like a prefix sum, with this you can tell if there is a nail between any two position.
  Reply

Zheng Xu says:
March 20, 2015 at 7:12 pm
My solution has an optimal time complexity. Instead of doing a linear scan to find the earliest position, I used Segment Tree, which is O(logM). Thus, the overall time complexity of my solution is O((N + M) * log(M)).
A link to a blog post about my solution:
https://zhengxucoding.wordpress.com/2015/03/21/solution-to-codility-nailingplanks/
Reply
- Sheng says:
  March 23, 2015 at 11:11 pm
  Thanks for sharing a different solution!
  Reply
Dragan Bozanovic says:
April 20, 2016 at 7:59 am
I managed to find a solution with linear complexity. In my solution I first discard all planks that completely wrap other planks, because a nail used for a wrapped plank can be used for all planks that wrap it.
More details at: http://draganbozanovic.blogspot.rs/2016/04/codility-nailingplanks-linear-complexity.html
Reply
- Sheng says:
  May 2, 2016 at 8:15 pm
  Great idea!!! Many thanks!
  Reply

Hello I implemented a similar javascript version of your python binary solution but only get 75% ( 100% correct results but 2 timeouts at the performance tests ).
Could anyone help me to figure out what is wrong with the performance of my code ?
Thank you very much
Cheers
Jack

function solution(A, B, C) {

// write your code in JavaScript (Node.js 8.9.4)

var planksAmount = A.length;

var nailsAmount = C.length;

var sortedNails = C.map((c, i) => {

return [c, i];

}).sort((a, b) => a[0] - b[0]);

var plankIndex = 0;

var firstInitialNailIndex = -1;

while (plankIndex < planksAmount) {

var plankPositionStart = A[plankIndex];

var plankPositionEnd = B[plankIndex];

// binary search to find the first nail able to nail the current plank

var lowNailIndex = 0;

var highNailIndex = nailsAmount - 1;

var firstNailIndex = -1;

while (lowNailIndex <= highNailIndex) {

var middleNailIndex = Math.floor((lowNailIndex + highNailIndex) / 2);

if (sortedNails[middleNailIndex][0] < plankPositionStart) {

lowNailIndex = middleNailIndex + 1;

} else if (sortedNails[middleNailIndex][0] > plankPositionEnd) {

highNailIndex = middleNailIndex - 1;

} else {

// found a matching nail

firstNailIndex = middleNailIndex;

// keep looking for a earlier nail

highNailIndex = middleNailIndex - 1;

}

if (firstNailIndex === -1) {

// no matching nail => one plank won't be nailed

return -1;

}

// find out the first matching nail able to nail the plank in the initial nail array

var currentFirstInitialNailIndex = sortedNails[firstNailIndex][1];

var candidateNailIndex = firstNailIndex;

// linear check all the candidates able to nail the plank

while (candidateNailIndex < nailsAmount && sortedNails[candidateNailIndex][0] <= plankPositionEnd) {

// keep checking the nails while they are able to nail the plank

if (currentFirstInitialNailIndex > sortedNails[candidateNailIndex][1]) {

currentFirstInitialNailIndex = sortedNails[candidateNailIndex][1];

}

candidateNailIndex++;

}

// if the first nail index in the initial array is greater than the one stored in memory then replace the old one by this one

if (currentFirstInitialNailIndex > firstInitialNailIndex) {

firstInitialNailIndex = currentFirstInitialNailIndex;

}

plankIndex++;

}

// the amount of nails is equal to the first nail index plus one

return firstInitialNailIndex + 1;

}

The below solution makes use of a hash lookup & not use binary search.
Passes all codility test cases. Complexity is linear. Instead of binary search it does a hash lookup. The hash contains entry for all points. The value is the first nail (position and point) from that point.

function solution(A, B, C) {

let lookUp = {};

let i = 1;

C.map((n, index) => [n, index]).sort(([nA, indexA], [nB, indexB]) => {

if (nA === nB) {

return indexA - indexB;

}

return nA - nB;

}).forEach(([n, index]) => {

while (i <= n) {

lookUp[i] = [n, index];

i++;

}

});

let ret = -1;

for (let i = 0; i < A.length; i++) {

let start = A[i];

let end = B[i];

let small = Infinity;

let flag = true;

do {

let [n, index] = lookUp[start] || [Infinity];

if (n > end) {

break;

}

flag = false;

small = Math.min(small, index);

if (small <= ret) {

break;

}

start = n + 1;

} while (start <= end);

if (flag) {

return -1;

}

if (ret < small) {

ret = small;

}

return ret + 1;

}

My 100% C++ version:
https://app.codility.com/demo/results/trainingYES68R-VHZ/

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

#include <algorithm>

// Let's define a convenient structure to hold both index position and

// the index of the nail in original nails lists

struct Nail {

int nail_pos;

int nail_index;

};

// an auxiliary function to help us in sorting nails

int compare(Nail &a, Nail &b);

// finding the earliest nail to fix the plank. The implementation can be found after the solution function

int find_first_nail(int plank_begin, int plank_end, std::vector<Nail> &nails, int previous_plank_nail_index);

int solution(const std::vector<int> &A, const std::vector<int> &B, const std::vector<int> &C) {

const int M = C.size();

// let's fill our ordered nail list

std::vector<Nail> nails;

nails.reserve(M);

for (int i = 0; i < M; ++i) {

Nail nail;

nail.nail_index = i;

nail.nail_pos = C[i];

nails.push_back(nail);

}

// Usually, the C++ implementations of sort takes O(M log M)

std::sort(nails.begin(), nails.end(), compare);

int target_nail_index = -1;

const int N = A.size();

int previous_plank_nail_index = -1;

// O(N log M)

for (int i = 0; i < N; ++i) {

// using binary search to find the earliest nail given a plank.

int nail_index = find_first_nail(A[i], B[i], nails, previous_plank_nail_index);

if (nail_index == -1) {

return -1;

}

// only update target_nail_index if the new nail index is after it

if (nail_index > target_nail_index) {

target_nail_index = nail_index;

previous_plank_nail_index = target_nail_index;

}

// The resulting time complexity O(N log M + M log M) = O((N + M) log M)

return target_nail_index + 1;

}

int find_first_nail(int plank_begin, int plank_end, std::vector<Nail> &nails, int previous_plank_nail_index) {

int lower = 0;

int upper = nails.size() - 1;

int lowest_nail_index = -1;

// first, we perform binary search to find the lowest nail position

while (lower <= upper) {

int mid = (lower + upper) / 2;

Nail &nail = nails[mid];

if (nail.nail_pos > plank_end) {

upper = mid - 1;

} else if (nail.nail_pos < plank_begin) {

lower = mid + 1;

} else {

// keeping looking for a suitable nail before mid

upper = mid - 1;

lowest_nail_index = mid;

}

int result = -1;

if (lowest_nail_index > -1) {

// okay. We found the index of the lowest nail inside the plank limits

// but now, we must to find the earlier nail inside the plank limits

// this is done using linear search over the ordered nails starting from lowest_nail_index + 1

// the search finishes when:

// - we find a nail after plank end or

// - we reach the end of nails list

// - we find a nail index which is before the previous plank nail

result = nails[lowest_nail_index].nail_index;

for (int i = lowest_nail_index + 1; result > previous_plank_nail_index && i < nails.size(); i++) {

auto & nail = nails[i];

int nail_pos = nail.nail_pos;

if (nail_pos > plank_end) {

break;

} else if (nail.nail_index < result) {

result = nail.nail_index;

}

return result;

}

int compare(Nail &a, Nail &b) {

if (a.nail_pos < b.nail_pos)

return true;

else if (a.nail_pos > b.nail_pos)

return false;

else if (a.nail_index < b.nail_index)

return true;

else if (a.nail_index > b.nail_index)

return false;

else return true;

}

int main() {

std::cout << solution({1, 4, 5, 8}, {4, 5, 9, 10}, {4, 6, 7, 10, 2}) << " should be " << 4 << "\n";

std::cout << solution({1, 4, 5, 8}, {4, 5, 9, 10}, {4, 6, 7, 10, 2, 4, 6, 7, 10, 2}) << " should be " << 4 << "\n";

std::cout << solution({1}, {2}, {2}) << " should be " << 1 << "\n";

std::cout << solution({1}, {2}, {3}) << " should be " << -1 << "\n";

std::cout << solution({1}, {2}, {2, 2, 2, 3}) << " should be " << 1 << "\n";

std::cout << solution({1}, {2}, {2, 2, 3, 2}) << " should be " << 1 << "\n";

std::cout << solution({1}, {2}, {2, 3, 2, 2}) << " should be " << 1 << "\n";

std::cout << solution({1}, {2}, {3, 2, 2, 2}) << " should be " << 2 << "\n";

std::cout << solution({4}, {1000}, {3, 2, 2, 2}) << " should be " << -1 << "\n";

return 0;

}

15 Replies to “Solution to Nailing-Planks by codility”

Leave a Reply Cancel reply