islands.csv

pathfinder.py

import csv
import heapq
import math

class Skyland(object):
  def __init__(self, name, location):
    self.name = name
    self.location = location
    self.neighbours = []
  
  def __repr__(self):
    return "Skyland(%r, %r)" % (self.name, self.location)


MAX_EDGE_DISTANCE = 6000

def distance(a, b):
  return math.sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2)

def load_skylands(fh):
  r = csv.reader(fh)
  skylands = {}
  for name, x, y in r:
    skylands[name] = Skyland(name, (int(x), int(y)))
  for src in skylands.values():
    for dest in skylands.values():
      if src == dest: continue
      dist = distance(src.location, dest.location)
      if dist <= MAX_EDGE_DISTANCE:
        src.neighbours.append((dist, dest))
    src.neighbours.sort()
  return skylands

def dijkstras(src, dest, max_dist):
  final = {}  # Maps vertices to (min cost, real cost, previous vertex) tuples
  intermediate = {}  # Maps vertices to (min cost, real cost, previous vertex) tuples
  frontier = []  # Heap of (vertex, min cost, real cost) tuples
  
  crow_distance = distance(src.location, dest.location)
  heapq.heappush(frontier, (src, crow_distance, 0))
  intermediate[src] = (crow_distance, 0, None)
  
  while frontier:
    current, min_cost, real_cost = heapq.heappop(frontier)
    if current in final: continue
    
    final[current] = intermediate[current]
    del intermediate[current]
    if current == dest: break
    
    for edge_dist, edge_dest in current.neighbours:
      if edge_dest in final: continue
      if edge_dist > max_dist: break
      
      new_real_cost = real_cost + edge_dist
      new_min_cost = new_real_cost + distance(edge_dest.location, dest.location)
      if edge_dest not in intermediate or intermediate[edge_dest][0] > new_min_cost:
        intermediate[edge_dest] = (new_min_cost, new_real_cost, current)
        heapq.heappush(frontier, (edge_dest, new_min_cost, new_real_cost))
    
  if dest not in final:
    return None, []
  path = []
  current = dest
  while current:
    path.append(current)
    current = final[current][2]
  path.reverse()
  return final[dest][1], path

def all_points(graph, max_dist):
  paths = dict(((src, dest), (dist, None)) for src in graph
               for dist, dest in src.neighbours if dist <= max_dist)
  for via in graph:
    for src in graph:
      for dest in graph:
        a = paths.get((src, via))
        b = paths.get((via, dest))
        c = paths.get((src, dest))
        if a and b and (not c or a[0] + b[0] < c[0]):
          paths[(src, dest)] = (a[0] + b[0], via)
  return paths

skyio.py

import socket
import struct

class DesyncException(Exception): pass
class UnknownMessageTypeException(Exception): pass
class InvalidStatusException(Exception): pass

def read_element(fmt):
  """Struct element reader factory.
  
  Returns any primitive.
  """
  size = struct.calcsize(fmt)
  def _in(f):
    return struct.unpack(fmt, f.read(size))[0]
  return _in

def read_struct(fmt):
  """Struct reader factory.
  
  Returns a tuple of primitives.
  """
  size = struct.calcsize(fmt)
  def _in(f):
    return struct.unpack(fmt, f.read(size))
  return _in

def read_string(f):
  """String reader.
  
  Returns str.
  """
  data = f.read(1)
  ret = ''
  while data != '\0':
    ret += data
    data = f.read(1)
  return ret

def read_composite(*converters):
  """Composite  reader factory.
  
  Returns tuple of any.
  """
  def _in(f):
    return tuple(converter(f) for converter in converters)
  return _in

def read_array(length_func, data_func):
  """Array reader factory.
  
  Returns array of any.
  """
  def _in(f):
    length = length_func(f)
    return [data_func(f) for x in range(length)]
  return _in

def assert_equal(reader, eq):
  """Equality assertion factory.
  
  Returns the same type as its reader.
  """
  def _in(f):
    data = reader(f)
    if data != eq:
      raise InvalidDataException("Expected %r, got %r" % (eq, data))
    return data
  return _in

# Returns (0x01, status_message)
read_status = read_composite(
    assert_equal(read_element('B'), 0x01),
    read_string
)

# Returns (0x20, response_type)
read_response_header = read_composite(
    assert_equal(read_element('B'), 0x20),
    read_element('B')
)

# Returns (status, _, [(header, status, _, island_id, island_name, _,
#                       [(resource_type, base_price, max_qty, current_price),
#                        ...]), ...])
read_market_data = read_composite(
    read_status,
    read_element('B'),  # Unknown byte
    read_array(read_element('B'), read_composite(
        assert_equal(read_response_header, (0x20, 0x45)),
        read_status,
        read_element('B'),  # Unknown byte
        read_element('B'),  # Island ID
        read_string,  # Island name
        read_struct('9B'),  # Unknown data
        read_array(read_element('B'), read_struct('!BIII')), # Market data
    )),
)

response_handlers = {
  0x44: read_market_data,
}

def read_response(f):
  _, response_type = read_response_header(f)
  if response_type not in response_handlers:
    raise UnknownMessageTypeException(response_type)
  return response_type, response_handlers[response_type](f)

class SocketReader(object):
  def __init__(self, sock):
    self.sock = sock
    self.buf = ''

  def read(self, count):
    while len(self.buf) < count:
      data = self.sock.recv(count - len(self.buf))
      if data == '':
        raise EOFError()
      self.buf += data
    ret = self.buf[:count]
    self.buf = self.buf[count:]
    return ret


def write_element(fmt):
  """Struct element writer factory.
  
  data = any primitive
  """
  def _out(f, data):
    f.write(struct.pack(fmt, data))
  return _out

def write_struct(fmt):
  """Struct writer factory.
  
  data = tuple of any primitive
  """
  def _out(f, data):
    f.write(struct.pack(fmt, *data))
  return _out

def write_string(f, data):
  """String writer.
  
  data = str
  """
  f.write(data + '\0')

def write_composite(*converters):
  """Composite writer factory.
  
  data = tuple of any
  """
  def _out(f, data):
    for converter, datum in zip(converters, data):
      converter(f, datum)
  return _out

def write_request(message_type, request_writer):
  """Request writer factory.
  
  data = (session_id, any)
  """
  def _out(f, data):
    f.write(struct.pack('!BBi', 0xa0, message_type, data[0]))
    request_writer(f, data[1])
  return _out

# data = (session_id, (0x00, 0x00))
write_market_data_request = write_request(0x45, write_struct('BB'))

class SocketWriter(object):
  def __init__(self, sock):
    self.sock = sock

  def write(self, data):
    while len(data):
      sent = self.sock.send(data)
      data = data[sent:]

def get_market_data(address, port):
  s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
  s.connect((address, port))
  
  reader = SocketReader(s)
  writer = SocketWriter(s)
  
  write_market_data_request(writer, (0, (0, 0)))
  type, response = read_response(reader)
  s.close()
  
  data = {}
  assert type == 0x44
  for header, status, _, island_id, island_name, _, cols in response[2]:
    data[island_name] = cols
  return data

def market_price(base_price, max_qty, current_qty):
  return base_price + base_price * (1-(float(current_qty)/max_qty))

market_prices = dict((k, [market_price(*x[1:]) for x in v]) for k, v in market.items())

def find_best_trade(src, dest, num_resources):
  best_profit = 0
  best_resource = None
  for i, (src_price, dest_price) in enumerate(zip(src[:num_resources], dest[:num_resources])):
    if dest_price - src_price > best_profit:
      best_profit = dest_price - src_price
      best_resource = i
  return best_resource, best_profit

tradefinder.py

import logging

class Tradefinder(object):
  def __init__(self, skylands, distances, profits):
    """Constructor.
    
    Args:
      skylands: A list of permissible skylands.
      distances: A dict mapping (src, dest) skyland tuples to (distance, via) tuples
      profits: A dict mapping (src, dest) skyland tuples to (resource, profit) tuples
    """
    self.distances = distances
    self.profits = profits
    self.skylands = skylands

  def _get_next_state(self, state, sources):
    next_state = {}
    next_sources = []
    for dest in self.skylands:
      best_route, best_profit_dist = None, None
      for src in sources:
        if src == dest: continue
        src_dist, src_profit, src_path, src_resources = state[src]
        new_dist = src_dist + self.distances[src, dest][0]
        leg_cargo, leg_profit = self.profits[src, dest]
        new_profit = src_profit + leg_profit
        new_profit_dist = new_profit / new_dist
        if not best_profit_dist or new_profit_dist > best_profit_dist:
          best_profit_dist = new_profit_dist
          best_route = (new_dist, new_profit, src_path + [src], src_resources + [leg_cargo])
      if best_route:
        next_state[dest] = best_route
        if dest not in best_route[2]:
          next_sources.append(dest)
      else:
        next_state[dest] = state[dest]
        next_sources.append(dest)
    return next_state, next_sources
        
  def find_best_route(self, start):
    """Finds the best route beginning at start and ending in a cycle.
    
    Args:
      start: The skyland to start at.
    Returns:
      (list of hops, list of resources to trade)
    """
    # State maps skylands to (distance travelled, profit made, hops, resources) tuples
    state = {}
    state[start] = (0.0, 0.0, [], [])
    sources = [start]
    
    while sources:
      state, sources = self._get_next_state(state, sources)
    
    best_profit_dist = None
    best_route = None
    for dest, (dist, profit, hops, resources) in state.iteritems():
      if dist / profit > best_profit_dist:
        best_profit_dist = dist / profit
        best_route = (hops + [dest], resources)
    return best_route