"""Issue #1: each planet sends just enough ships to take the nearest planet it can win, aiming where an orbiting target will be. Unlike the field's swarm it counts the fleets already flying (its own and the enemy's), keeps what its planets need to hold, never flies through the sun or another planet, and stops buying neutrals that cannot pay back before turn 500.""" import math C, SUN, END, H = 50.0, 10.0, 500, 160 # centre, sun radius, last turn, look-ahead in turns def speed(n): return min(6.0, 1.0 + 5.0 * (math.log(max(n, 1)) / math.log(1000)) ** 1.5) def seg_dist(px, py, ax, ay, bx, by): dx, dy = bx - ax, by - ay l2 = dx * dx + dy * dy t = 0.0 if l2 == 0 else max(0.0, min(1.0, ((px - ax) * dx + (py - ay) * dy) / l2)) return math.hypot(px - ax - t * dx, py - ay - t * dy) def swept_hit(a, b, p0, p1, r): """The engine's test: fleet a->b and planet p0->p1 come within r during the tick.""" d0x, d0y = a[0] - p0[0], a[1] - p0[1] vx, vy = (b[0] - a[0]) - (p1[0] - p0[0]), (b[1] - a[1]) - (p1[1] - p0[1]) qa, qb, qc = vx * vx + vy * vy, 2 * (d0x * vx + d0y * vy), d0x * d0x + d0y * d0y - r * r if qa < 1e-12: return qc <= 0 disc = qb * qb - 4 * qa * qc if disc < 0: return False s = math.sqrt(disc) return (-qb + s) / (2 * qa) >= 0 and (-qb - s) / (2 * qa) <= 1 def paths(obs): """Each planet's centre at t = 0..H turns from now (None once a comet has left).""" w = obs['angular_velocity'] comet = {} for g in obs.get('comets') or []: for i, pid in enumerate(g['planet_ids']): comet[pid] = (g['paths'][i], g['path_index']) out = {} for p in obs['planets']: pid, x, y, r = p[0], p[2], p[3], p[4] if pid in comet: path, k = comet[pid] out[pid] = [tuple(path[k + t]) if 0 <= k + t < len(path) else None for t in range(H + 1)] elif math.hypot(x - C, y - C) + r < 50: rad, a = math.hypot(x - C, y - C), math.atan2(y - C, x - C) out[pid] = [(C + rad * math.cos(a + w * t), C + rad * math.sin(a + w * t)) for t in range(H + 1)] else: out[pid] = [(x, y)] * (H + 1) return out def fly(x, y, ang, n, planets, pos, until=H): """Where a fleet at (x, y) heading ang lands: (planet id, turn), or (None, turn) if the sun or the edge takes it.""" v = speed(n) dx, dy = math.cos(ang) * v, math.sin(ang) * v for t in range(1, until + 1): nx, ny = x + dx, y + dy for p in planets: pp = pos[p[0]] if pp[t] is None or pp[t - 1] is None: continue if abs(pp[t][0] - nx) > v + 9 or abs(pp[t][1] - ny) > v + 9: continue if swept_hit((x, y), (nx, ny), pp[t - 1], pp[t], p[4]): return p[0], t if not (0 <= nx <= 100 and 0 <= ny <= 100) or seg_dist(C, C, x, y, nx, ny) < SUN: return None, t x, y = nx, ny return None, until def owners(p, ships, arrivals, extra=None): """Planet p's owner after each of the next turns, up to the last known fleet, given fleets arriving as {turn: {owner: ships}} and `extra` = (turn, owner, ships) more. Combat as the engine does it.""" arr = arrivals if extra: t, who, n = extra arr = dict(arrivals) arr[t] = dict(arr.get(t, {})) arr[t][who] = arr[t].get(who, 0) + n owner, out = p[1], [p[1]] for t in range(1, max(list(arr) + [1]) + 1): if owner != -1: ships += p[6] a = arr.get(t) if a: top = sorted(a.items(), key=lambda kv: -kv[1]) who, n = top[0] if len(top) > 1: n -= top[1][1] if n > 0: if who == owner: ships += n else: ships -= n if ships < 0: owner, ships = who, -ships out.append(owner) return out def aim(src, tgt, n, pos): """The angle and turn at which a fleet of n from src meets tgt's centre, or None.""" sx, sy, v = src[2], src[3], speed(n) tp = pos[tgt[0]] f = lambda t: math.hypot(tp[t][0] - sx, tp[t][1] - sy) - src[4] - 0.1 - v * t for t in range(1, H + 1): if tp[t] is None: return None if f(t) <= 0: # the meeting is in (t-1, t]: aim at the planet's centre at the nearer whole turn x, y = tp[t] if tp[t - 1] is None or -f(t) < f(t - 1) else tp[t - 1] return math.atan2(y - sy, x - sx), t return None def agent(obs, config=None): me, step = obs['player'], obs.get('step', 0) planets = obs['planets'] pos = paths(obs) arrivals = {p[0]: {} for p in planets} # planet -> turn -> owner -> ships, from the fleets in flight for f in obs['fleets']: pid, t = fly(f[2], f[3], f[4], f[6], planets, pos) if pid is not None: d = arrivals[pid].setdefault(t, {}) d[f[1]] = d.get(f[1], 0) + f[6] ships = {p[0]: p[5] for p in planets} safe = lambda p, n: all(o == me for o in owners(p, ships[p[0]] - n, arrivals[p[0]])) takes = lambda p, t, n: all(o == me for o in owners(p, ships[p[0]], arrivals[p[0]], (t, me, n))[t:]) def least(lo, hi, ok): """The least n in [lo, hi] with ok(n), ok being monotone; None if even hi fails.""" if not ok(hi): return None while lo < hi: mid = (lo + hi) // 2 lo, hi = (lo, mid) if ok(mid) else (mid + 1, hi) return lo moves = [] for src in sorted((p for p in planets if p[1] == me), key=lambda p: -p[5]): if not safe(src, 0): continue keep = least(0, ships[src[0]], lambda k: safe(src, ships[src[0]] - k)) # what it needs to hold have = ships[src[0]] - keep options = [] for tgt in planets: if tgt[0] == src[0] or have <= 0 or owners(tgt, ships[tgt[0]], arrivals[tgt[0]])[-1] == me: continue n, hit = 1, None for _ in range(4): # n sets the speed, the speed the turn, the turn the garrison to beat hit = aim(src, tgt, n, pos) if hit is None: break m = least(n, have, lambda k: takes(tgt, hit[1], k)) if m is None: hit = None break if m == n: break n = m if hit is None or n > have: continue ang, t = hit if tgt[1] == -1 and tgt[6] * (END - step - t) <= tgt[5]: continue # a neutral that would not earn back its garrison before the end options.append((t, tgt[0], tgt, ang, n)) for t, _, tgt, ang, n in sorted(options): # the nearest, in turns, whose path is clear sx, sy = src[2] + math.cos(ang) * (src[4] + 0.1), src[3] + math.sin(ang) * (src[4] + 0.1) pid, t2 = fly(sx, sy, ang, n, planets, pos, t + 3) if pid != tgt[0] or not takes(tgt, t2, n): continue # the sun or another planet is in the way, or it lands later than aimed and too late d = arrivals[tgt[0]].setdefault(t2, {}) d[me] = d.get(me, 0) + n ships[src[0]] -= n moves.append([src[0], ang, n]) break return moves if __name__ == '__main__': # self-check: python3 main.py p = [0, -1, 20, 20, 1, 10, 2] # neutral, 10 ships assert owners(p, 10, {3: {0: 10}}) == [-1, -1, -1, -1] # 10 on 10 does not take it assert owners(p, 10, {3: {0: 11}}) == [-1, -1, -1, 0] assert owners(p, 10, {3: {0: 15, 1: 5}}) == [-1, -1, -1, -1] # 15 - 5 = 10 left over: still not enough assert owners([0, 1, 20, 20, 1, 10, 2], 10, {3: {0: 16}})[-1] == 1 # an owned planet grows 2 a turn: 16 vs 16 assert owners([0, 1, 20, 20, 1, 10, 2], 10, {3: {0: 17}})[-1] == 0 obs = {'angular_velocity': 0.03, 'planets': [[0, 0, 10, 10, 1, 50, 1], [1, -1, 10, 90, 2, 5, 1]], 'fleets': [], 'comets': []} pos = paths(obs) ang, t = aim(obs['planets'][0], obs['planets'][1], 6, pos) sx, sy = 10 + math.cos(ang) * 1.1, 10 + math.sin(ang) * 1.1 assert fly(sx, sy, ang, 6, obs['planets'], pos)[0] == 1 obs = {'angular_velocity': 0.05, 'planets': [[0, 0, 90, 5, 1, 50, 1], [1, -1, 80, 50, 1, 5, 1]], 'fleets': [], 'comets': []} pos, src = paths(obs), obs['planets'][0] # planet 1 orbits the sun at radius 30 for ang, hits in ((aim(src, obs['planets'][1], 200, pos)[0], True), (math.atan2(45, -10), False)): # ahead, at it assert (fly(90 + math.cos(ang) * 1.1, 5 + math.sin(ang) * 1.1, ang, 200, obs['planets'], pos)[0] == 1) == hits print('ok')