Skip to content

Instantly share code, notes, and snippets.

@Muzietto
Created December 31, 2016 08:58
Show Gist options
  • Save Muzietto/22ae80258e0fd19689df8386b6c1761a to your computer and use it in GitHub Desktop.
Save Muzietto/22ae80258e0fd19689df8386b6c1761a to your computer and use it in GitHub Desktop.
Human-readable solution for the NailingPlanks puzzle at Codility (https://codility.com/programmers/lessons/14-binary_search_algorithm/nailing_planks/)
function solution(A,B,C) {
return nailsBinarySearch(A,B,C);
}
function nailsBinarySearch(boardStarts, boardEnds, nailPositions) {
var boards = boardStarts.map((cur, curIndex) => [cur, boardEnds[curIndex]],[]);
var lowerBorderNailsNumber = 1;
var upperBorderNailsNumber = nailPositions.length;
var minimalNailsNumber = -1;
while (lowerBorderNailsNumber <= upperBorderNailsNumber) {
var tentativeNailsNumber = Math.floor((lowerBorderNailsNumber+upperBorderNailsNumber)/2);
if (allBoardsNailed(boards, nailPositions.slice(0, tentativeNailsNumber))) {
// good result
minimalNailsNumber = tentativeNailsNumber;
// maybe tentativeNailsNumber is too large...
upperBorderNailsNumber = tentativeNailsNumber -1;
} else {
// gotta try with a larger tentative
lowerBorderNailsNumber = tentativeNailsNumber + 1;
}
}
return minimalNailsNumber;
}
function allBoardsNailed(boards, nailPositions) {
return boards.every(board => nailPositions.some(nailPos => board[0]<=nailPos && board[1]>=nailPos));
}
@Muzietto
Copy link
Author

Muzietto commented Dec 31, 2016

This one appears to be 100% correct, but still too slow and, as a total, it gets only 62% of the votes. Problems are most likely inside row 27 (which is in any case far too elegant). Every improvement suggestion is welcome.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment