daily_programmer_20150515.py

#Answer to https://www.reddit.com/r/dailyprogrammer/comments/3629st/20150515_challenge_214_hard_chester_the_greedy/
#Needs to be further optimized and revisit quadtree implementation (use a bounded quadtree instead or a k-d tree

import heapq
from collections import deque
import random


start = [0.5, 0.5]
food = [(0.9, 0.7), (0.7, 0.7), (0.1, 0.1), (0.4, 0.1), (0.6, 0.6), (0.8, 0.8)]



class QuadTree:
    
    def __init__(self, root_node = None):
        self.root = root_node
        
    def add_node(self, node):
        if self.root:
            self.root.add_node(node)
        else:
            self.root = node
            
        
    def delete_node(self, node):
        if node.parent:
            for quad in ['ne', 'nw', 'se', 'sw']:
                if getattr(node.parent, quad) == node:
                    setattr(node.parent, quad, None)
                    for child in node.get_children():
                        node.parent.add_node(child)
        else:
            #then node is the root_node
            quads = ['ne', 'nw', 'se', 'sw']
            random.shuffle(quads)
            new_root_not_found = True
            self.root = None
            
            for q in quads:
                #run through each child setting the parent to None
                child_node = getattr(node, q)
                
                if child_node:
                    child_node.parent = None
                    
                    #assign the root to the first child
                    if new_root_not_found:
                        self.root = child_node
                        new_root_not_found = False
                    else:
                        self.root.add_node(child_node)
        
    def search_for_nearest(self, starting_point):
        "using djikstra's algorithm to recursively search the tree for the nearest node"
        
        children = self.root.get_children()
        start_x, start_y = starting_point
        
        nearest_node = (euclid_dist(self.root.get_val(), starting_point), self.root)
        
        nodes_visited = 0
    
        d = deque([])
        
        for child in children:
            d.append((euclid_dist(starting_point, child.get_val()), child))
            
        while d:
            nodes_visited += 1
            node = d.popleft()
            node_x, node_y = node[1].get_val()
            if node[0] <= nearest_node[0]:
                nearest_node = node
            
            for child in node[1].get_children():
                child_x, child_y = child.get_val()
                #if a child region has strictly greater distance in both the x and y then all of its children must also have
                #greater distances, and so are disqualified.
            
                #Case 1: Node is NE of Point and Child is NE of Node (necessarily further away
                if (node_x > start_x and node_y > start_y) and (child_x > node_x and child_y > node_y ):
                    continue
                
                #Case 2: Node in SW of Point and Child is SW of Node
                elif (node_x < start_x and node_y < start_y) and (child_x < node_x  and child_y < node_y):
                    continue
                
                #Case 3: Node in NW of Point and Child is NW of Node
                elif (node_x < start_x and node_y > start_y) and (child_x < node_x  and child_y > node_y):
                    continue
                
                #Case 4: Node in SE of Point and Child is SE of Node
                elif (node_x > start_x and node_y < start_y) and (child_x > node_x and child_y < node_y):
                    continue                

                else:
                    d.append((euclid_dist(starting_point, child.get_val()), child))

        #print 'Nodes Visied', nodes_visited
        return nearest_node    
    
    def __repr__(self):
        return str(self.root)
    
    def is_empty(self):
        return not bool(self.root)
    
                    

class QuadTreeNode:
    
    def __init__(self, val):
        self.val = val
        self.nw  = None
        self.ne = None
        self.sw = None
        self.se = None
        self.parent = None


    def add_node(self, node):
        x,y = node.get_val()
        root_x, root_y = self.val
            
        if x <= root_x  and y >=root_y:
            if self.nw == None:
                self.nw = node
                self.nw.parent = self
            else:
                self.nw.add_node(node)
        elif x >= root_x  and y >=root_y:
            if self.ne == None:
                self.ne = node
                self.ne.parent = self
            else:
                self.ne.add_node(node)
        elif x <= root_x  and y <=root_y:
            if self.sw == None:
                self.sw = node
                self.sw.parent = self
            else:
                self.sw.add_node(node)
        elif x >= root_x  and y <=root_y:
            if self.se == None:
                self.se = node
                self.se.parent = self
            else:
                self.se.add_node(node)        

    def get_children(self):
        return [child for child in (self.ne, self.nw, self.se, self.sw) if child]
    
    def get_val(self):
        return self.val
            
        
    def set_parent(self, parent): 
        self.parent = parent
    
    def bfs_get_nodes(self):
        visited = []

        d = deque([self])
        while d:
            parent = d.popleft()
            visited.append(parent)
            for child in parent.get_children():
                #since it's a tree no need to check for cycles
                #implement if-then statement.
                d.append(child)
        return visited
    
    def __repr__(self):
        labeled_children = [(node, label) for node, label in zip([self.ne, self.nw, self.se, self.sw], ["NE", "NW", "SE", "SW"])]
        txt = "Root: %s, Children : %s"%(self.val, ' '.join([child[1]+" "+str(child[0].val) for child in labeled_children if child[0]]) )
        return txt
    

def euclid_dist(point1, point2):
    return (sum([(pt1 - pt2)**2 for pt1, pt2 in zip(point1, point2)]))**0.5
    
    


if __name__ == "__main__":
    tree = QuadTree()
    for f in food:
        tree.add_node(QuadTreeNode(f))
        
    
    current_pos = (0.5, 0.5)
    
    total_dist = 0.0

    while not tree.is_empty():
        
        dist, nearest_node = tree.search_for_nearest(current_pos)
        
        total_dist += dist
        
        print dist, nearest_node
        current_pos = nearest_node.get_val()
        
        tree.delete_node(nearest_node)
    print total_dist
    
    tree100 = QuadTree()
    with open("/Users/mwoods/bonus.txt", "r") as f:
        f.readline()
        for line in f:
            x,y = line.split()
            tree100.add_node(QuadTreeNode((float(x), float(y))))
    
    
    tree = tree100    
    
    nodes = []
    current_pos = (0.5, 0.5)
    total_dist = 0.0
    nodes = [current_pos]
    while not tree.is_empty():
    #for _ in range(8):   
        dist, nearest_node = tree.search_for_nearest(current_pos)
        
        total_dist += dist
        
        print dist, nearest_node
        current_pos = nearest_node.get_val()
        nodes.append(current_pos)
        
        tree.delete_node(nearest_node)
    print total_dist            
    

#optimal9th = tree100.root.ne.sw.ne.ne
#suboptimal9th = tree100.root.ne