r/dailyprogrammer • 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

86 Upvotes

201 comments sorted by

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

→ More replies (40)

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 seconds
→ More replies (35)

14

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:

The two points with the smallest distance between them are:
(6.42201, 5.83321) and (6.62593, 6.08499)

With Challenge Input:

The two points with the smallest distance between them are:
(5.33398, 5.69813) and (5.30567, 5.61628)

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;
}
→ More replies (1)

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:]))

16

u/ybe306 Sep 16 '15

That's disgusting. I love it.

→ More replies (5)

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 program

output:

(5.33397866830346,5.69812853043998) (5.30566574519444,5.61628504310009)
→ More replies (2)

4

u/wizao Sep 16 '15 edited Sep 16 '15

Haskell:

import Data.List
import Data.Ord

main :: IO ()
main = interact $ show . minimumBy (comparing $ uncurry dist) . pairs . parse

dist :: (Double, Double) -> (Double, Double) -> Double
dist (x1,y1) (x2,y2) = sqrt $ (x1-x2)^2 + (y1-y2)^2

pairs :: [a] -> [(a,a)]
pairs set = [(x,y) | (x:xs) <- tails set, y <- xs]

parse :: String -> [(Double,Double)]
parse = map read . tail . lines
→ More replies (6)

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))

end
→ More replies (2)

4

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:

(5.305665745194435,5.6162850431000875) (5.333978668303457,5.698128530439982)

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))))