back to code @codinggame

main.py

import sys
import math

opponent_count = int(input())  # Opponent count

claimed_by_me = set()
claimed_by_opponent = {}
for opp in range(opponent_count):
    claimed_by_opponent[opp] = set()

class Point:
    """A point identified by (x,y) coordinates.
    
    supports: +, -, *, /, str, repr
    
    length  -- calculate length of vector to point from origin
    distance_to  -- calculate distance between two points
    as_tuple  -- construct tuple (x,y)
    clone  -- construct a duplicate
    integerize  -- convert x & y to integers
    floatize  -- convert x & y to floats
    move_to  -- reset x & y
    slide  -- move (in place) +dx, +dy, as spec'd by point
    slide_xy  -- move (in place) +dx, +dy
    rotate  -- rotate around the origin
    rotate_about  -- rotate around another point
    """

    def __init__(self, x=0.0, y=0.0):
        self.x = x
        self.y = y

    def __add__(self, p):
        """Point(x1+x2, y1+y2)"""
        return Point(self.x+p.x, self.y+p.y)

    def __sub__(self, p):
        """Point(x1-x2, y1-y2)"""
        return Point(self.x-p.x, self.y-p.y)

    def __mul__( self, scalar ):
        """Point(x1*x2, y1*y2)"""
        return Point(self.x*scalar, self.y*scalar)

    def __div__(self, scalar):
        """Point(x1/x2, y1/y2)"""
        return Point(self.x/scalar, self.y/scalar)

    def __eq__(self, other):
        if isinstance(other, Point):
            return self.x == other.x and self.y == other.y
        return NotImplemented

    def __ne__(self, other):
        result = self.__eq__(other)
        if result is NotImplemented:
            return result
        return not result

    def __str__(self):
        return "(%s, %s)" % (self.x, self.y)

    def __repr__(self):
        return "%s(%r, %r)" % (self.__class__.__name__, self.x, self.y)

    def __attrs(self):
        return (self.x, self.y)

    def __hash__(self):
        return hash(self.__attrs())

    def length(self):
        return math.sqrt(self.x**2 + self.y**2)

    def distance_to(self, p):
        """Calculate the distance between two points."""
        return (self - p).length()

    def as_tuple(self):
        """(x, y)"""
        return (self.x, self.y)

    def clone(self):
        """Return a full copy of this point."""
        return Point(self.x, self.y)

    def integerize(self):
        """Convert co-ordinate values to integers."""
        self.x = int(self.x)
        self.y = int(self.y)

    def floatize(self):
        """Convert co-ordinate values to floats."""
        self.x = float(self.x)
        self.y = float(self.y)

    def move_to(self, x, y):
        """Reset x & y coordinates."""
        self.x = x
        self.y = y

    def slide(self, p):
        '''Move to new (x+dx,y+dy).
        
        Can anyone think up a better name for this function?
        slide? shift? delta? move_by?
        '''
        self.x = self.x + p.x
        self.y = self.y + p.y

    def slide_xy(self, dx, dy):
        '''Move to new (x+dx,y+dy).
        
        Can anyone think up a better name for this function?
        slide? shift? delta? move_by?
        '''
        self.x = self.x + dx
        self.y = self.y + dy

    def rotate(self, rad):
        """Rotate counter-clockwise by rad radians.
        
        Positive y goes *up,* as in traditional mathematics.
        
        Interestingly, you can use this in y-down computer graphics, if
        you just remember that it turns clockwise, rather than
        counter-clockwise.
        
        The new position is returned as a new Point.
        """
        s, c = [f(rad) for f in (math.sin, math.cos)]
        x, y = (c*self.x - s*self.y, s*self.x + c*self.y)
        return Point(x,y)

    def rotate_about(self, p, theta):
        """Rotate counter-clockwise around a point, by theta degrees.
        
        Positive y goes *up,* as in traditional mathematics.
        
        The new position is returned as a new Point.
        """
        result = self.clone()
        result.slide(-p.x, -p.y)
        result.rotate(theta)
        result.slide(p.x, p.y)
        return result


class Rect:

    """A rectangle identified by two points.

    The rectangle stores left, top, right, and bottom values.

    Coordinates are based on screen coordinates.

    origin                               top
       +-----> x increases                |
       |                           left  -+-  right
       v                                  |
    y increases                         bottom

    set_points  -- reset rectangle coordinates
    contains  -- is a point inside?
    overlaps  -- does a rectangle overlap?
    top_left  -- get top-left corner
    bottom_right  -- get bottom-right corner
    expanded_by  -- grow (or shrink)
    """

    def __init__(self, pt1, pt2):
        """Initialize a rectangle from two points."""
        self.set_points(pt1, pt2)

    def set_points(self, pt1, pt2):
        """Reset the rectangle coordinates."""
        (x1, y1) = pt1.as_tuple()
        (x2, y2) = pt2.as_tuple()
        self.left = min(x1, x2)
        self.top = min(y1, y2)
        self.right = max(x1, x2)
        self.bottom = max(y1, y2)

    def contains(self, pt):
        """Return true if a point is inside the rectangle."""
        x,y = pt.as_tuple()
        return (self.left <= x <= self.right and
                self.top <= y <= self.bottom)

    def overlaps(self, other):
        """Return true if a rectangle overlaps this rectangle."""
        return (self.right > other.left and self.left < other.right and
                self.top < other.bottom and self.bottom > other.top)

    def area(self):
        return (self.right - self.left) * (self.bottom - self.top)

    def top_left(self):
        """Return the top-left corner as a Point."""
        return Point(self.left, self.top)

    def top_right(self):
        """Return the top-right corner as a Point."""
        return Point(self.right, self.top)

    def bottom_left(self):
        """Return the bottom-left corner as a Point."""
        return Point(self.left, self.bottom)

    def bottom_right(self):
        """Return the bottom-right corner as a Point."""
        return Point(self.right, self.bottom)

    def lines(self):
        return [self.left_line(), self.top_line(), self.right_line(), self.bottom_line()]

    def right_line(self):
        return Line(self.top_right(), self.bottom_right())

    def top_line(self):
        return Line(self.top_left(), self.top_right())

    def bottom_line(self):
        return Line(self.bottom_left(), self.bottom_right())

    def left_line(self):
        return Line(self.top_left(), self.bottom_left())

    def expanded_by(self, n):
        """Return a rectangle with extended borders.

        Create a new rectangle that is wider and taller than the
        immediate one. All sides are extended by "n" points.
        """
        p1 = Point(self.left-n, self.top-n)
        p2 = Point(self.right+n, self.bottom+n)
        return Rect(p1, p2)

    def expanded_left(self):
        """Expanded rectangle left by n."""
        p1 = Point(self.left-1, self.top)
        p2 = Point(self.right, self.bottom)
        return Rect(p1, p2)

    def expand_left(self):
        """Expand current rectangle left."""
        self.left -= 1

    def expanded_up(self):
        """Expanded rectangle up."""
        p1 = Point(self.left, self.top-1)
        p2 = Point(self.right, self.bottom)
        return Rect(p1, p2)

    def expand_up(self):
        """Expand current rectangle left by n."""
        self.top -= 1

    def expanded_right(self):
        """Expanded rectangle right by n."""
        p1 = Point(self.left, self.top)
        p2 = Point(self.right+1, self.bottom)
        return Rect(p1, p2)

    def expand_right(self):
        """Expand current rectangle right"""
        self.right += 1

    def expanded_down(self):
        """Expanded rectangle down"""
        p1 = Point(self.left, self.top)
        p2 = Point(self.right, self.bottom+1)
        return Rect(p1, p2)

    def expand_down(self):
        """Expand current rectangle left"""
        self.bottom += 1

    def __str__( self ):
        return "<Rect (%s,%s)-(%s,%s)>" % (self.left,self.top,
                                           self.right,self.bottom)

    def __repr__(self):
        return "%s(%r, %r)" % (self.__class__.__name__,
                               Point(self.left, self.top),
                               Point(self.right, self.bottom))

class Line:
    """A line identified by two points."""

    def __init__(self, pt1, pt2):
        """Initialize a rectangle from two points."""
        self.left = pt1
        self.right = pt2

    def set_points(self, pt1, pt2):
        """Reset the rectangle coordinates."""
        self.left = pt1
        self.right = pt2

    def contains(self, pt):
        crossproduct = (pt.y - self.left.y) * (self.right.x - self.left.x) - (pt.x - self.left.x) * (self.right.y - self.left.y)
        if abs(crossproduct) != 0 : return False

        dotproduct = (pt.x - self.left.x) * (self.right.x - self.left.x) + (pt.y - self.left.y)*(self.right.y - self.left.y)
        if dotproduct < 0 : return False

        squaredlengthba = (self.right.x - self.left.x)*(self.right.x - self.left.x) + (self.right.y - self.left.y)*(self.right.y - self.left.y)
        if dotproduct > squaredlengthba: return False

        return True

    def get_nearest_unclaimed_spot(self, x, y):
        if self.left.x == self.right.x:
            # vertical line
            spots = [ Point(self.left.x, y) for y in range(self.left.y, self.right.y, 1) ]
        elif self.left.y == self.right.y:
            # horizontal
            spots = [ Point(x, self.left.y) for x in range(self.left.x, self.right.x, 1) ]
            distances = [(pt, pt.distance_to(Point(x, y))) for pt in spots if pt not in claimed_by_me]
            if not distances:
                return []
            else:
                return min(distances, key = lambda t: t[1])[0]

    def __str__(self):
        return "<Line (%s)-(%s)>" % (self.left, self.right)

    def __repr__(self):
        return "%s(%r, %r)" % (self.__class__.__name__,
                               self.left,
                               self.right)

class GameRound:
    def __init__(self, round, map):
        self.round = round
        self.map = map
        self.M = 20
        self.N = 35
        self.cache = [0 for _ in range(self.M)]
        self.stack = []

    def is_spot_claimable(self, x, y):
        return self.map[y][x] == '.' or self.map[y][x] == '0'

    def update_cache(self, x):
        for y in range(self.M):
            if self.is_spot_claimable(x, y):
                self.cache[y] += 1
            else:
                self.cache[y] = 0

    def area(self, ll, ur):
        if ll.x > ur.x or ll.y > ur.y:    # If ur is left of or
            return 0                      # below ll: return 0
        else:
            return (ur.x-ll.x+1)*(ur.y-ll.y+1)

    def find_best_rect(self):
        best_ll = Point(0, 0)
        best_ur = Point(-1, -1)

        for x in list(reversed(range(self.N))):
            self.update_cache(x)
            width = 0
            for y in range(self.M):
                if self.cache[y] > width: # Opening new rectangle(s)?
                    self.stack.append((y, width))
                    width = self.cache[y]
                if self.cache[y] < width: # Closing rectangle(s)?
                    while True:
                        (y0, w0)= self.stack.pop()
                        if width * (y-y0) > self.area(best_ll, best_ur):
                            best_ll = Point(x, y0)
                            best_ur = Point(x + width - 1, y - 1)
                        width = w0
                        if self.cache[y] >= width:
                            break
                    width = self.cache[y]
                    if width != 0: # Popped an active "opening"?
                        self.stack.append((y0, width))
        return best_ll, best_ur

def is_claimed_by_opponent(p):
    for i in range(opponent_count):
        if p in claimed_by_opponent[i]:
            return True
    return False

def is_claimed_by_other_opponent_or_me(opponent, p):
    if p in claimed_by_me:
        return True
    for i in range(opponent_count):
        if i != opponent:
            if p in claimed_by_opponent[i]:
                return True
    return False

def is_valid_rectangle(r):
    if r.left < 0 or r.top < 0 or r.right >= 35 or r.bottom >= 20:
        return False
    for i in range(opponent_count):
        for p in claimed_by_opponent[i]:
            if r.contains(p):
                return False
    return True

def nearest_unclaimed_corner(rect, x, y):
    corners = [ rect.top_left(),
                rect.top_right(),
                rect.bottom_left(),
                rect.bottom_right(),
                ]

    distances = [(corner, corner.distance_to(Point(x, y))) for corner in corners if corner not in claimed_by_me]
    try:
        return min(distances, key = lambda t: t[1])[0]
    except ValueError:
        p = Point(x, y)
        for line in rect.lines():
            if line.contains(p):
                nearest_unclaimed_spot = line.get_nearest_unclaimed_spot(x, y)
                if nearest_unclaimed_spot:
                    return nearest_unclaimed_spot


"""
Here starts game logic...
"""

# game loop
while 1:
    game_round = int(input())
    x, y, back_in_time_left = [int(i) for i in input().split()]

    p = Point(x, y)
    if not is_claimed_by_opponent(p):
        claimed_by_me.add(p)

    for i in range(opponent_count):
        opponent_x, opponent_y, opponent_back_in_time_left = [int(j) for j in input().split()]
        opponent_p = Point(opponent_x, opponent_y)
        if not is_claimed_by_other_opponent_or_me(i, opponent_p):
            claimed_by_opponent[i].add(opponent_p)

    map = []
    for _ in range(20):
        line = input()
        map.append(line)

    round = GameRound(game_round, map)
    ll, ur = round.find_best_rect()
    rect = Rect(ll, ur)

    p = nearest_unclaimed_corner(rect, x, y)
    print(rect, file = sys.stderr)
    print("{0} {1}".format(p.x, p.y))
    #print("0 0")