r/DailyProgrammer
DailyProgrammer is a subreddit that provide challenge to programmer everyday. Each day i will solve one challenge from it to practice my skill on solving problem.
[2015-09-16] Challenge #232 [Intermediate] Where Should Grandma’s House Go?
Description
My grandmother and I are moving to a new neighborhood. The houses haven’t yet been built, but the map has been drawn. We’d like to live as close together as possible. She makes some outstanding cookies, and I love visiting her house on the weekend for delicious meals - my grandmother is probably my favorite cook! Please help us find the two lots that are closest together so we can build our houses as soon as possible.
Example Input
You’ll be given a single integer, N, on a line, then N lines of Cartesian coordinates of (x,y) pairs. Example:
16
(6.422011725438139, 5.833206713226367)
(3.154480546252892, 4.063265532639129)
(8.894562467908552, 0.3522346393034437)
(6.004788746281089, 7.071213090379764)
(8.104623252768594, 9.194871763484924)
(9.634479418727688, 4.005338324547684)
(6.743779037952768, 0.7913485528735764)
(5.560341970499806, 9.270388445393506)
(4.67281620242621, 8.459931892672067)
(0.30104230919622, 9.406899285442249)
(6.625930036636377, 6.084986606308885)
(9.03069534561186, 2.3737246966612515)
(9.3632392904531, 1.8014711293897012)
(2.6739636897837915, 1.6220708577223641)
(4.766674944433654, 1.9455404764480477)
(7.438388978141802, 6.053689746381798)
Example Output
Your program should emit the two points of (x,y) pairs that are closest together. Example:
(6.625930036636377,6.084986606308885) (6.422011725438139,5.833206713226367)
Challenge Input
100
(5.558305599411531, 4.8600305440370475)
(7.817278884196744, 0.8355602049697197)
(0.9124479406145247, 9.989524754727917)
(8.30121530830896, 5.0088455259181615)
(3.8676289528099304, 2.7265254619302493)
(8.312363982415834, 6.428977658434681)
(2.0716308507467573, 4.39709962385545)
(4.121324567374094, 2.7272406843892005)
(9.545656436023116, 2.874375810978397)
(2.331392166597921, 0.7611494627499826)
(4.241235371900736, 5.54066919094827)
(3.521595862125549, 6.799892867281735)
(7.496600142701988, 9.617336260521792)
(2.5292596863427796, 4.6514954819640035)
(8.9365560770944, 8.089768281770253)
(8.342815293157892, 1.3117716484643926)
(6.358587371849396, 0.7548433481891659)
(1.9085858694489566, 1.2548184477302327)
(4.104650644200331, 5.1772760616934645)
(6.532092345214275, 8.25365480511137)
(1.4484096875115393, 4.389832854018496)
(9.685268864302843, 5.7247619715577915)
(7.277982280818066, 3.268128640986726)
(2.1556558331381104, 7.440500993648994)
(5.594320635675139, 6.636750073337665)
(2.960669091428545, 5.113509430176043)
(4.568135934707252, 8.89014754737183)
(4.911111477474849, 2.1025489963335673)
(8.756483469153423, 1.8018956531996244)
(1.2275680076218365, 4.523940697190396)
(4.290558055568554, 5.400885500781402)
(8.732488819663526, 8.356454134269345)
(6.180496817849347, 6.679672206972223)
(1.0980556346150605, 9.200474664842345)
(6.98003484966205, 8.22081445865494)
(1.3008030292739836, 2.3910813486547466)
(0.8176167873315643, 3.664910265751047)
(4.707575761419376, 8.48393210654012)
(2.574624846075059, 6.638825467263861)
(0.5055608733353167, 8.040212389937379)
(3.905281319431256, 6.158362777150526)
(6.517523776426172, 6.758027776767626)
(6.946135743246488, 2.245153765579998)
(6.797442280386309, 7.70803829544593)
(0.5188505776214936, 0.1909838711203915)
(7.896980640851306, 4.366680008699691)
(1.2404651962738256, 5.963706923183244)
(7.9085889544911945, 3.501907219426883)
(4.829123686370425, 6.116328436853205)
(8.703429477346157, 2.494600359615746)
(6.9851545945688684, 9.241431992924019)
(1.8865556630758573, 0.14671871143506765)
(4.237855680926536, 1.4775578026826663)
(3.8562761635286913, 6.487067768929168)
(5.8278084663109375, 5.98913080157908)
(8.744913811001137, 8.208176389217819)
(1.1945941254992176, 5.832127086137903)
(4.311291521846311, 7.670993787538297)
(4.403231327756983, 6.027425952358197)
(8.496020365319831, 5.059922514308242)
(5.333978668303457, 5.698128530439982)
(9.098629270413424, 6.8347773139334675)
(7.031840521893548, 6.705327830885423)
(9.409904685404713, 6.884659612909266)
(4.750529413428252, 7.393395242301189)
(6.502387440286758, 7.5351527902895965)
(7.511382341946669, 6.768903823121008)
(7.508240643932754, 6.556840482703067)
(6.997352867756065, 0.9269648538573272)
(0.9422251775272161, 5.103590106844054)
(0.5527353428303805, 8.586911807313664)
(9.631339754852618, 2.6552168069445736)
(5.226984134025007, 2.8741061109013555)
(2.9325669592417802, 5.951638270812146)
(9.589378643660075, 3.2262646648108895)
(1.090723228724918, 1.3998921986217283)
(8.364721356909339, 3.2254754023019148)
(0.7334897173512944, 3.8345650175295143)
(9.715154631802577, 2.153901162825511)
(8.737338862432715, 0.9353297864316323)
(3.9069371008200218, 7.486556673108142)
(7.088972421888375, 9.338974320116852)
(0.5043493283135492, 5.676095496775785)
(8.987516578950164, 2.500145166324793)
(2.1882275188267752, 6.703167722044271)
(8.563374867122342, 0.0034374051899066504)
(7.22673935541426, 0.7821487848811326)
(5.305665745194435, 5.6162850431000875)
(3.7993107636948267, 1.3471479136817943)
(2.0126321055951077, 1.6452950898125662)
(7.370179253675236, 3.631316127256432)
(1.9031447730739726, 8.674383934440593)
(8.415067672112773, 1.6727089997072297)
(6.013170692981694, 7.931049747961199)
(0.9207317960126238, 0.17671002743311348)
(3.534715814303925, 5.890641491546489)
(0.611360975385955, 2.9432460366653213)
(3.94890493411447, 6.248368129219131)
(8.358501795899047, 4.655648268959565)
(3.597211873999991, 7.184515265663337)
Challenge Output
(5.305665745194435,5.6162850431000875) (5.333978668303457,5.698128530439982)
Bonus
A nearly 5000 point bonus set to really stress test your approach. http://hastebin.com/oyayubigof.lisp
My solution
I done this pretty simple using bubble sort algorithm. But i think this solution will be really slow when the number of points increase. I will looking into fix this problem this is the output with benchmark.
only-search: 2ms
include-read: 11ms
Point { x: 5.333978668303457, y: 5.698128530439982 } Point { x: 5.305665745194435, y: 5.6162850431000875 }
This is the output with 5000 point:
only-search: 264ms
include-read: 287ms
Point { x: 5.790730910735991, y: 1.129818016424764 } Point { x: 5.791688594337488, y: 1.1280184190733455 }
Javascript
var fs = require('fs');
var rl = require('readline').createInterface({
input: require('fs').createReadStream('./grandma.txt')
});
function Point(x, y){
this.x = x;
this.y = y;
}
var points, i = -1, numPoints, smallestDist = [0, 1];
rl.on('line', function (line) {
if (i == -1){
numPoints = parseInt(line);
points = new Array(numPoints);
} else {
var cordinate = line.slice(1,-1).split(',');
points[i] = new Point(parseFloat(cordinate[0]), parseFloat(cordinate[1]));
}
i++;
}).on('close', function() {
for (var i = 0; i < numPoints; i++){
for (var j = i; j < numPoints; j++){
if (distance(points[smallestDist[0]], points[smallestDist[1]])
> distance(points[i],points[j]) && i != j){
smallestDist[0] = i;
smallestDist[1] = j;
}
}
}
console.log(points[smallestDist[0]], points[smallestDist[1]]);
});
function distance(point1, point2){
return Math.sqrt(Math.pow(point1.x - point2.x, 2) + Math.pow(point1.y - point2.y, 2));
}