For example, given a set of points where each line is of the form: ID x-coordinate y-coordinate

1 0.0 0.0

2 10.1 -10.1

3 -12.2 12.2

4 38.3 38.3

5 79.99 179.99

Your program should output:

1 2,3,4

2 1,3,4

3 1,2,4

4 1,2,3

5 4,3,1

This is facebook's smallword puzzle, but I am only asking for a O(n

^{2}) solution.

Below is a program that will solve the smallworld puzzle in n-squared time. Notice that this

**will not be accepted**by the facebook robot as it is too slow so don't even bother submitting it (I already tried). If you don't believe me try running it with 10,000 input coordinates.

There is a way to do this in close to linear time, can you figure out how?

#!/usr/bin/env python

import sys

from math import sqrt

class Node:

def __init__(self,name,x,y):

self.name = name

self.x = x

self.y = y

e = Edge(self,self)

e.distance = 1e1000

#3 smallest edges, sorted by distance

self.closest = [e,e,e]

def __str__(self):

return str(self.name) + " " + self.closest[0].b.name + "," + self.closest[1].b.name + "," + self.closest[2].b.name

#O(1) since we keep self.closest limited to 3

def addNeighbor(self,other):

"""Add other to the closest list, but only if it is

closer than the farthest one in the list."""

e = Edge(self,other) # I am always first

if (e.distance < self.closest[2].distance):

self.closest.append(e)

self.closest.sort()

self.closest = self.closest[:3]

if (e.distance < other.closest[2].distance):

e = Edge(other,self) # I am always first

other.closest.append(e)

other.closest.sort()

other.closest = other.closest[:3]

class Edge:

def __init__(self, a, b):

self.a = a

self.b = b

dx = (a.x - b.x)

dy = (a.y - b.y)

self.distance = sqrt(dx*dx + dy*dy)

def __cmp__(self,other):

return cmp(self.distance, other.distance)

def __str__(self):

return self.a.name + "-" + self.b.name

filename = sys.argv[1]

f=open(filename)

nodes = []

# O(n), where n is the number of nodes (friends)

for l in f:

items = l.split()

n = Node(items[0], float(items[1]), float(items[2]))

nodes.append(n)

# O(n^2)

for i in xrange(0,len(nodes)-1):

for j in xrange(i+1,len(nodes)):

nodes[i].addNeighbor(nodes[j])

# O(n)

for n in nodes:

print n

## 3 comments:

Hi ,

This seems like a hard one, esp considering that an O(n^2) solution is pretty straightforward. We can do it in O(nlogn) but the book keeping involved makes it impractical for small test cases. What i tried was creating a binary tree where each point divides the plane into various regions( on the basis of co-ordinates) by finding in which region each point lies and the closest regions we can find out nearest neighbor.

I am not sure about the algo and will be thankful if you can point out the linear running time algo.

ciao

You should go check out the Puzzlemaster discussion page http://www.facebook.com/PuzzleMaster for more tips.

It doesn't feel right for me to be giving tips on solving their puzzle.

Alright a typical nearest neighbor question... x\ The problem is would someone expect us to just program this on-the-fly? ;(

-ray

Post a Comment