Skip to content

Instantly share code, notes, and snippets.

@Sh4kE
Created October 1, 2015 15:56
Show Gist options
  • Save Sh4kE/ca67847a18b41f4f3fb1 to your computer and use it in GitHub Desktop.
Save Sh4kE/ca67847a18b41f4f3fb1 to your computer and use it in GitHub Desktop.
back to code @codinggame
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")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment