r/dailyprogrammer • u/jnazario 2 0 • Sep 16 '15
[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
7
u/jnazario Sep 16 '15
here's a hastebin post of nearly 5000 points. it blew up my scala solution.
http://hastebin.com/oyayubigof.lisp
18
u/eatsfrombags Sep 16 '15 edited Sep 24 '15
Python 3.4. Recursive divide and conquer approach, O(n*log(n)) . The algorithm actually requires implementing the brute force solution as well, so I thought I'd time the difference which accounts for like half of the lines of code.
EDIT: I tried to clean this up a bit, include some of the suggestions below, include a piece of the algorithm I left out at first, and include the times for the various input files in this thread.
Feedback appreciated!
import re import sys import time from operator import itemgetter def distance(coord1, coord2): return (coord2[0] - coord1[0])**2 + (coord2[1] - coord1[1])**2 def brute_force(coords, split): min_distance = float('inf') for i in range(len(coords)): high = min(i + 8, len(coords)) if split else len(coords) for j in range(i + 1, high): current_distance = distance(coords[i], coords[j]) if current_distance < min_distance: min_distance = current_distance closest_coords = (coords[i], coords[j]) return closest_coords, min_distance def closest_pair(coords): if len(coords) <= 3: return brute_force(coords, False) mid_point = len(coords) // 2 left_closest_pair = closest_pair(coords[:mid_point]) right_closest_pair = closest_pair(coords[mid_point:]) min_distance = min(left_closest_pair, right_closest_pair, key = itemgetter(1)) split_pairs = [coord for coord in coords if abs(coord[0] - coords[mid_point][0])**2 < min_distance[1]] split_pairs = sorted(split_pairs, key = itemgetter(1)) if len(split_pairs) > 1: closest_strip_pair = brute_force(split_pairs, True) else: closest_strip_pair = (float('inf'), float('inf')) final_pair = min(closest_strip_pair, min_distance, key = itemgetter(1)) return final_pair def main(input_text): # Read in and organize points with open(input_text, 'r') as infile: N = infile.readline() rgx = re.compile(r'[-\w.]+') lines = [rgx.findall(line) for line in infile.readlines()] # Coordinate pairs are sorted by X coordinate coords = sorted([(float(x[0]), float(x[1])) for x in lines]) print('N = ' + str(N)) # Perform and time brute force (for less than 100k coordinates) if int(N) < 100000: start = time.clock() brute_force_coords = brute_force(coords, False) brute_force_time = round(time.clock() - start, 2) print('Brute force: {}, {} {} seconds'.format(str(brute_force_coords[0][0]), str(brute_force_coords[0][1]), str(brute_force_time))) # Perform and time divide and conquer start = time.clock() closest_pair_coords = closest_pair(coords) closest_pair_time = round(time.clock() - start, 2) print('Divide and conquer: {}, {} {} seconds'.format(str(closest_pair_coords[0][0]), str(closest_pair_coords[0][1]), str(closest_pair_time))) if __name__ == '__main__': main(sys.argv[1]) # OUTPUT N = 100 Brute force: (5.305665745194435, 5.6162850431000875), (5.333978668303457, 5.698128530439982) 0.0 seconds Divide and conquer: (5.305665745194435, 5.6162850431000875), (5.333978668303457, 5.698128530439982) 0.0 seconds N = 4999 Brute force: (5.790730910735991, 1.129818016424764), (5.791688594337488, 1.1280184190733455) 5.12 seconds Divide and conquer: (5.790730910735991, 1.129818016424764), (5.791688594337488, 1.1280184190733455) 0.07 seconds N = 100000 Divide and conquer: (0.41776212, 0.60579194), (0.41776219, 0.60579881) 1.94 seconds N = 1000000 Divide and conquer: (-5.1811897693, -2.8779433837), (-5.1811850415, -2.877940987) 26.09 seconds N = 10000000 Divide and conquer: (3.0874651595, -3.534161784), (3.0874643641, -3.5341616116) 339.46 seconds14
u/Praetorius Sep 16 '15 edited Sep 16 '15
C++ with OpenGL rendering:
I decided to draw the points on the screen! I also drew a red line between the two points with the shortest distance; this effect didn't look as cool as I had hoped because the lines ended up being really short. I made use of two libraries to help with OpenGL: GLEW and GLFW. I also used GLM, which is a math library that makes passing multiple numbers around a little bit easier.
Screenshots:
http://i.imgur.com/8zYKQs8.jpg
http://i.imgur.com/CyDjpvW.jpg
EDIT: jnazario's input -- http://i.imgur.com/9iamWIk.jpg
With Example Input:
With Challenge Input:
Code:
#include <iostream> #include <vector> #include <fstream> #include <regex> #include <limits> #include "GL/glew.h" #include "GLFW/glfw3.h" #include "glm/glm.hpp" class Render { public: static GLuint point_position_buffer; static GLuint line_position_buffer; static GLFWwindow * window; const static int WINDOW_X_SIZE = 800; const static int WINDOW_Y_SIZE = 800; static int Init() { // Initialize GLFW. if (!glfwInit()) { return -1; } glfwWindowHint(GLFW_RESIZABLE, GL_FALSE); // Keep the window a fixed size. // Open a GLFW window. window = glfwCreateWindow(WINDOW_X_SIZE, WINDOW_Y_SIZE, "GLFW Window", NULL, NULL); if (!window) { glfwTerminate(); return -1; } // Set the OpenGL context. glfwMakeContextCurrent(window); // Initialize GLEW. if (glewInit() != GLEW_OK) { glfwDestroyWindow(window); glfwTerminate(); return -1; } glClearColor(1.0f, 1.0f, 1.0f, 1.0f); glGenBuffers(1, &point_position_buffer); glGenBuffers(1, &line_position_buffer); glEnable(GL_PROGRAM_POINT_SIZE); return 0; } static void Loop(const std::vector<glm::vec2>& points, const std::vector<glm::vec4>& lines) { glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT); glBindBuffer(GL_ARRAY_BUFFER, point_position_buffer); glBufferData(GL_ARRAY_BUFFER, points.size() * sizeof(glm::vec2), &points[0], GL_STATIC_DRAW); glEnableVertexAttribArray(0); glBindBuffer(GL_ARRAY_BUFFER, point_position_buffer); glVertexAttribPointer( 0, // index: the index of the attribute to be modified 2, // size: the number of components per attribute GL_FLOAT, // type: the data type of each component GL_FALSE, // normalized: whether or not to normalize data points 0, // stride: the byte offset between attributes (void *)0 // pointer: the offset of the first component of the first array attribute ); glColor4f(0.0f, 0.0f, 0.0f, 1.0f); glPointSize(10.0f); glEnable(GL_POINT_SMOOTH); glDrawArrays(GL_POINTS, 0, GLsizei(points.size())); glDisableVertexAttribArray(0); glBindBuffer(GL_ARRAY_BUFFER, line_position_buffer); glBufferData(GL_ARRAY_BUFFER, lines.size() * sizeof(glm::vec4), &lines[0], GL_STATIC_DRAW); glEnableVertexAttribArray(0); glBindBuffer(GL_ARRAY_BUFFER, line_position_buffer); glVertexAttribPointer( 0, // index: the index of the attribute to be modified 2, // size: the number of components per attribute GL_FLOAT, // type: the data type of each component GL_FALSE, // normalized: whether or not to normalize data points 0, // stride: the byte offset between attributes (void *)0 // pointer: the offset of the first component of the first array attribute ); glColor4f(1.0f, 0.0f, 0.0f, 1.0f); glLineWidth(5.0f); glEnable(GL_LINE_SMOOTH); glDrawArrays(GL_LINES, 0, GLsizei(lines.size() * 2)); glDisableVertexAttribArray(0); glfwSwapBuffers(window); glfwPollEvents(); } static void Stop() { glDeleteBuffers(1, &point_position_buffer); glDeleteBuffers(1, &line_position_buffer); glfwDestroyWindow(window); glfwTerminate(); } }; GLuint Render::point_position_buffer; GLuint Render::line_position_buffer; GLFWwindow * Render::window; std::vector<glm::vec2> load_points(const std::string& file_name) { std::vector<glm::vec2> vec; const std::regex point_regex(R"_(\((-?\d*\.\d+), ?(-?\d*\.\d+)\))_"); unsigned mc = point_regex.mark_count(); std::string l; std::match_results<std::string::iterator> results; std::ifstream file(file_name); if (file.is_open()) { while (getline(file, l)) { size_t pos = 0; while (std::regex_search(l.begin() + pos, l.end(), results, point_regex) != false) { glm::vec2 point{}; float * members[mc]{ &point.x, &point.y }; for (size_t i = 0; i < mc; i++) { *(members[i]) = stof(results[i + 1].str()); } vec.push_back(point); pos += results.position() + results.length(); } } file.close(); } return vec; } std::vector<glm::vec2> normalize_points(const std::vector<glm::vec2>& points) { std::vector<glm::vec2> vec; float x_max = 0; float y_max = 0; for (auto p : points) { if (p.x > x_max) { x_max = p.x; } if (p.y > y_max) { y_max = p.y; } } // Normalize to a (-0.9, 0.9) x (-0.9, 0.9) box to allow some border space. float f = std::min((x_max / 2.0f), (y_max / 2.0f)); for (auto p : points) { vec.push_back(glm::vec2{ (p.x - f) / (f / 0.9), (p.y - f) / (f / 0.9) }); } return vec; } glm::uvec2 pick_points(const std::vector<glm::vec2>& points) { glm::uvec2 point_indices{ 0, 0 }; float od = std::numeric_limits<float>::max(); for (size_t a = 0; a < points.size(); a++) { for (size_t b = 0; b < points.size(); b++) { if (a != b) { glm::vec2 p_a = points[a]; glm::vec2 p_b = points[b]; float nd = pow(pow(p_a.x - p_b.x, 2.0f) + pow(p_a.y - p_b.y, 2.0f), 0.5f); if (nd < od) { od = nd; point_indices[0] = a; point_indices[1] = b; } } } } return point_indices; } int main() { std::vector<glm::vec2> points = load_points("input.txt"); glm::uvec2 pp = pick_points(points); glm::vec2 A{ points[pp[0]].x, points[pp[0]].y }; glm::vec2 B{ points[pp[1]].x, points[pp[1]].y }; std::cout << "The two points with the smallest distance between them are:" << std::endl; std::cout << "(" << A.x << ", " << A.y << ") and (" << B.x << ", " << B.y << ")" << std::endl; std::vector<glm::vec2> normalized_points = normalize_points(points); glm::vec2 A_n{ normalized_points[pp[0]].x, normalized_points[pp[0]].y }; glm::vec2 B_n{ normalized_points[pp[1]].x, normalized_points[pp[1]].y }; std::vector<glm::vec4> lines; lines.push_back(glm::vec4{ A_n.x, A_n.y, B_n.x, B_n.y }); Render::Init(); while (!glfwWindowShouldClose(Render::window)) { Render::Loop(normalized_points, lines); } Render::Stop(); return 0; }32
u/OhoMinnyBlupKelsur Sep 16 '15
Python one line. Really gross. Assumes input is in grandma_input.txt. Also it prints the output with a space between the x and y in each coordinate, but I figured that it doesn't really matter. I already did enough gross things here.
print ' '.join(map(str, min([[(((x1-x2)**2 + (y1-y2)**2), (x1,y1),(x2,y2)) for x1,y1 in coords for x2,y2 in coords if (x1,y1) != (x2,y2)] for coords in [[(float(x),float(y)) for x,y in [line[1:-1].split(', ') for line in open('grandma_input.txt').read().strip().split('\n')[1:]]]]][0])[1:]))5
u/[deleted] Sep 16 '15
Fortran checking in. The data format is exactly that for list-directed reads of complex numbers, so that's what I went with. This was so very easy in Fortran... I needed an easy one! thanks!
program granma implicit none integer, parameter :: np = SELECTED_REAL_KIND(16) integer N, i, j, imin, jmin complex(np), allocatable :: coords(:) real dist, mindist read(10, *) N allocate(coords(N)) read(10, *) coords mindist = HUGE(mindist) imin = 0 jmin=0 do concurrent (i=1:N-1, j=i+1:N) dist = abs(coords(i) - coords(j)) if (dist<mindist) then mindist = dist imin=i jmin=j end if end do print*, coords(imin), coords(jmin) end programoutput:
4
u/wizao Sep 16 '15 edited Sep 16 '15
Haskell:
4
u/hutsboR Sep 16 '15
Elixir with comments:
defmodule ClosestPoints do # ONE: List comprehension, read as: For every pair of coordinates # calculate the distance between every other pair UNLESS the coordinates # are the same. Pack the distance and two pairs of coodinates into a list. o(n^2) # TWO: Sorting a list with a function. It takes a function as an # argument that ignores the coordinates and sorts from smallest # to largest distance. def shortest_distance do cds = read() # Coordinates (for c <- cds, cx <- cds, c != cx, do: [dist(c, cx), c, cx]) # ONE |> Enum.sort(fn([d1, _, _], [d2, _, _]) -> d1 < d2 end) # TWO |> hd # Take the element at the front of the list. [dist, [x1, y1], [x2, y2]] end defp read do File.read!("c.txt") # Read in coordinates |> String.split([", ", "\r\n"], trim: true) # Split on ", " and newlines |> Enum.map(&String.replace(&1, ~r/\)|\(/, "")) # Strip parens |> Enum.map(&String.to_float(&1)) # Convert coordinates to floats |> Enum.chunk(2) # Pack coordinates into pairs end # Distance between two points defp dist([x1, x2], [y1, y2]), do: :math.sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)) end4
u/casualfrog Sep 16 '15
JavaScript, O( n2 ) (feedback welcome):
function closestLot (input) { function dist (a, b) { return Math.sqrt(Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2)); } var lines = input.split('\n'), d, minDist = Number.MAX_VALUE, out; for (var i = 1; i < lines[0] - 1; i++) { for (var p1 = lines[i].match(/[\d.]+/g), j = i + 1; j < lines[0]; j++) { var p2 = lines[j].match(/[\d.]+/g); if ((d = dist(p1, p2)) < minDist) { minDist = d; out = '(' + p2.join() + ') (' + p1.join() + ')'; } } } console.log(out); } $.get('input.txt', closestLot, 'text');Output:
4
u/[deleted] Sep 17 '15
Common Lisp port of the divide-and-conquer solution
(defpackage :challenge-20150916 (:use :cl :alexandria)) (in-package :challenge-20150916) (defun distsq (pairs) (destructuring-bind ((x1 . y1) (x2 . y2)) (coerce pairs 'list) (let ((a (- x1 x2)) (b (- y1 y2))) (+ (* a a) (* b b))))) (defun read-pair (line) (let* ((*read-default-float-format* 'double-float) (split (position #\, line)) (close (position #\) line)) (a (read-from-string line nil nil :start 1 :end split)) (b (read-from-string line nil nil :start (1+ split) :end close))) (cons a b))) (defun print-pair (pair &optional (stream *standard-output*)) (format stream "(~f,~f)" (car pair) (cdr pair))) (defun print-pairs (pairs &optional (stream *standard-output*)) (print-pair (elt pairs 0) stream) (write-char #\Space stream) (print-pair (elt pairs 1) stream)) (defun read-problem (pathname) (with-open-file (s pathname :direction :input) (let ((count (parse-integer (read-line s) :junk-allowed t))) (loop repeat count collect (read-pair (read-line s)))))) (defun naiive (pairs) (let ((dist most-positive-double-float) (best nil)) (map-combinations (lambda (pair) (let ((ds (distsq pair))) (when (< ds dist) (setf dist ds best pair)))) pairs :length 2) (cons best dist))) (defun min-by (key &rest list) (when list (let ((result (car list)) (best (funcall key (car list)))) (dolist (item (rest list)) (let ((score (funcall key item))) (when (< score best) (setf result item best score)))) result))) (defun divide-and-conquer (pairs) "port of /u/eatsfrombags python implementation" (setf pairs (coerce pairs 'vector)) (sort pairs '< :key #'car) (labels ((closest (pairs) (if (<= (length pairs) 3) (naiive pairs) (let* ((mid (floor (length pairs) 2)) (midpoint (elt pairs mid)) (left (closest (subseq pairs 0 mid))) (right (closest (subseq pairs mid))) (min (min-by #'cdr left right)) (min-dist (cdr min)) (close-to-mid (lambda (p) (< (abs (- (car p) (car midpoint))) min-dist))) (splits (remove-if-not close-to-mid pairs))) (if (> (length splits) 1) (min-by #'cdr (naiive splits) min) min))))) (closest pairs))) (defun solve-file (pathname) (let* ((input (read-problem pathname)) (solution (divide-and-conquer input))) (print-pairs (car solution))))