Created
December 31, 2016 08:58
-
-
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/)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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)); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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.