star-method.py

import pprint

import math

pp = pprint.PrettyPrinter(indent=2, width=120)

pp.pprint("my god it's full of stars")

def turbine_layout(rows, cols, startx=25000, starty=2000, rowgap=500, colgap=750, skewx=lambda _: 0):
  turbines = []

  for m in range(rows):
    turbines.append([])
    for n in range(cols):
      turbines[m].append((skewx(m) + startx + n*rowgap, starty + m*colgap, m, n))

  return turbines

def print_turbines(t):
  for row in reversed(t):
    print(row)

def turbine_count(t):
  size = 0
  for row in t:
    size = size + len(row)
  return size

def turbines_equal(expected, actual):
  rows = len(expected)
  assert(rows is len(actual))
  for i in range(rows):
    assert(len(expected[i]) is len(actual[i]))

  eq = True
  for i in range(rows):
    for j in range(len(expected[i])):
      x1, y1, _, _ = actual[i][j]
      x2, y2 = expected[i][j]
      eq &= x1 == x2 and y1 == y2
  return eq

def odd(x):
  return x & 1

layout_1 = turbine_layout(4,  7, skewx=lambda x: 250 if odd(x) else 0)
layout_2 = turbine_layout(6, 10, skewx=lambda x: 250 if odd(x) else 0)

expected_layout_1 = [
  [(25000, 2000), (25500, 2000), (26000, 2000),
   (26500, 2000), (27000, 2000), (27500, 2000), (28000, 2000)],
  [(25250, 2750), (25750, 2750), (26250, 2750),
   (26750, 2750), (27250, 2750), (27750, 2750), (28250, 2750)],
  [(25000, 3500), (25500, 3500), (26000, 3500),
   (26500, 3500), (27000, 3500), (27500, 3500), (28000, 3500)],
  [(25250, 4250), (25750, 4250), (26250, 4250),
   (26750, 4250), (27250, 4250), (27750, 4250), (28250, 4250)]
]

if not turbines_equal(expected_layout_1, layout_1):
  print("failed to generate turbine layout 1 correctly")

expected_layout_2 = [
  [(25000, 2000), (25750, 2000), (26500, 2000),
   (27250, 2000), (28000, 2000), (28750, 2000),
   (29500, 2000), (30250, 2000), (31000, 2000), (31750, 2000)],
  [(25250, 2500), (26000, 2500), (26750, 2500),
   (27500, 2500), (28250, 2500), (29000, 2500),
   (29750, 2500), (30500, 2500), (31250, 2500), (32000, 2500)],
  [(25000, 3000), (25750, 3000), (26500, 3000),
   (27250, 3000), (28000, 3000), (28750, 3000),
   (29500, 3000), (30250, 3000), (31000, 3000), (31750, 3000)],
  [(25250, 3500), (26000, 3500), (26750, 3500),
   (27500, 3500), (28250, 3500), (29000, 3500),
   (29750, 3500), (30500, 3500), (31250, 3500), (32000, 3500)],
  [(25000, 4000), (25750, 4000), (26500, 4000),
   (27250, 4000), (28000, 4000), (28750, 4000),
   (29500, 4000), (30250, 4000), (31000, 4000), (31750, 4000)],
  [(25250, 4500), (26000, 4500), (26750, 4500),
   (27500, 4500), (28250, 4500), (29000, 4500),
   (29750, 4500), (30500, 4500), (31250, 4500), (32000, 4500)]
]

# if not turbines_equal(expected_layout_2, layout_2):
#   print("failed to generate turbine layout 2 correctly")

if turbine_count(layout_1) is not 7*4:
  print("failed to count turbines in layout 1 correctly")

if turbine_count(layout_2) is not 6*10:
  print("failed to count turbines in layout 2 correctly")

def add_attachment_if_valid(row, col, turbines, connected, attachments):
  if row >= 0 and col >= 0 and row < len(turbines) and col < len(turbines[row]):
    next_turbine = turbines[row][col]
    if next_turbine not in connected:
      attachments.append(next_turbine)
    return next_turbine

def attach_to_center(center, radius, turbines, connected=[]):
  east   = []
  west   = []
  northe = []
  northw = []
  southe = []
  southw = []

  attachments = []

  x, y, row, col = center

  for dim in (1, 2): # northeast+west/southeast+west, north/south
    for diff in range(-radius, radius + 1):
      if diff is 0:
        continue

      # Look ne+w/se+w
      if dim is 1:
        next_row = row + diff
        next_turbine = add_attachment_if_valid(next_row, col, turbines, connected, attachments)

        if next_turbine:
          nx, ny, nr, nc = next_turbine

          go_north = ny > y
          go_east  = nx > x

          if next_turbine in attachments:
            if go_north:
              if go_east:
                northe.append(next_turbine)
              else:
                northw.append(next_turbine)
            else:
              if go_east:
                southe.append(next_turbine)
              else:
                southw.append(next_turbine)

          # We've looked east; now look (north|south)west
          if go_east:
            next_col = col - 1
            next = add_attachment_if_valid(next_row, next_col, turbines, connected, attachments)
            if next in attachments:
              if go_north:
                northw.append(next)
              else:
                southw.append(next)
          # We've looked west; now look (north|south)east
          else:
            next_col = col + 1
            next = add_attachment_if_valid(next_row, next_col, turbines, connected, attachments)
            if next in attachments:
              if go_north:
                northe.append(next)
              else:
                southe.append(next)
      # Look e/w
      elif dim is 2:
        next_col = col + diff
        next_turbine = add_attachment_if_valid(row, next_col, turbines, connected, attachments)

        if next_turbine:
          nx, ny, nr, nc = next_turbine
          go_east = nx > x

          if next_turbine in attachments:
            if go_east:
              east.append(next_turbine)
            else:
              west.append(next_turbine)

  directed = {
    "east": east,
    "west": west,
    "northeast": northe,
    "northwest": northw,
    "southeast": southe,
    "southwest": southw
  }

  return (attachments, directed)

test_turbines = [[(100, 100, 0, 0), (150, 100, 0, 1), (200, 100, 0, 2)],
                [(125,  50, 1, 0), (175,  50, 1, 1), (225,  50, 1, 2)],
                [(100,   0, 2, 0), (150,   0, 2, 1), (200,   0, 2, 2)]]

actual_attached_1, actual_directed_1 = attach_to_center(
  # center
  test_turbines[1][1],
  # radius
  1,
  # turbines
  test_turbines,
  # do not touch (already used)
  []
)

expected_attached_1 = [
  (150, 100, 0, 1),
  (200, 100, 0, 2),
  (150, 0, 2, 1),
  (200, 0, 2, 2),
  (125, 50, 1, 0),
  (225, 50, 1, 2)
]

expected_directed_1 = {
  "northwest": [(150, 100, 0, 1)],
  "northeast": [(200, 100, 0, 2)],
  "southwest": [(150, 0, 2, 1)],
  "southeast": [(200, 0, 2, 2)],
  "west": [(125, 50, 1, 0)],
  "east": [(225, 50, 1, 2)]
}

if actual_attached_1 != expected_attached_1:
  print("attach_to_center test 1 list failed")
  print(expected_attached_1)
  print(actual_attached_1)

if actual_directed_1 != expected_directed_1:
  print("attach_to_center test 1 directed failed")
  print(expected_directed_1)
  print(actual_directed_1)

###################
###################
## Real Business ##
###################
###################

turbine_output = 4 # MW
medium_voltage_lines = [
  # area mm^2, power MW, cost/meter $
  (120, 19.43, 370),
  (300, 30.29, 505)
]
high_voltage_lines = [
  # area mm^2, power MW, cost/meter $
  (400, 134.89, 642),
  (630, 163.47, 825)
]
transformers = [
  # power MW, cost $
  ( 60, 1.03E6),
  (120, 1.72E6)
]
shore_connection = (0, 0) # (x, y)

def star_method(turbines, first_center, radius=1):
  stars     = {}
  centers   = []
  connected = []

  center = first_center
  _, _, _, first_col = first_center

  # Connect all the stars we can make of high radius
  star_list, star_directed = attach_to_center(center, radius, turbines, connected)
  while len(star_list) != 0:
    centers.append(center)
    stars[center] = star_directed
    connected = connected + [ center ] + star_list

    # Find the next center (Which must be far enough away to make use of radius)
    x, y, row, col = center
    next_col = col + 2*radius + 1
    next_row = row + 2*radius + 1

    # If we can stay in this row, do...
    if next_col < len(turbines[row]):
      center = turbines[row][next_col]
    # Otherwise, go to the next row.
    elif next_row < len(turbines):
      center = turbines[next_row][first_col]

    star_list, star_directed = attach_to_center(center, radius, turbines, connected)

  # Connect all the stragglers
  while len(connected) != turbine_count(turbines):
    for row in turbines:
      for turbine in row:
        if turbine not in connected:
          star_list, star_directed = attach_to_center(turbine, radius, turbines, connected)
          stars[turbine] = star_directed
          connected = connected + [ turbine ] + star_list

  # Start calculating cost
  cost_so_far = 0

  # Choose cabling for each leg of each star
  for center in stars:
    for direction in stars[center]:
      connected = stars[center][direction]
      distances = map(turbine_distance(center), connected)
      # with_distance = map(prepend(turbine_distance(center)), connected)
      # order_of_distance = sorted(with_distance, key=lambda x: x[0])
      total_wattage = (len(connected) + 1) * turbine_output

      # print(order_of_distance)
      total_distance = sum(distances)
      # print("total distance", total_distance)

      line_options = []

      for mv in medium_voltage_lines:
        _, line_wattage, line_cost = mv
        bundle_size = math.ceil(total_wattage/line_wattage)
        line_options.append((line_cost * bundle_size, mv))

      cost, mv = min(line_options, key=lambda option: option[0])
      # print(center, direction, connected, total_distance, mv, cost * total_distance)
      cost_so_far = cost_so_far + cost * total_distance

  # print('%.2E' % cost_so_far)

  # Place the collection_point at the first possible place
  collection_point = turbines[0][0]

  for center in stars:
    directed = stars[center]
    connected = []
    for connections in directed.values():
      connected = connected + connections

    total_wattage = (len(connected) + 1) * turbine_output
    distance = turbine_distance(collection_point)(center)

    line_options = []

    for mv in medium_voltage_lines:
      _, line_wattage, line_cost = mv
      bundle_size = math.ceil(total_wattage/line_wattage)
      line_options.append((line_cost * bundle_size, mv))

    cost, mv = min(line_options, key=lambda option: option[0])
    cost_so_far = cost_so_far + cost * distance

  all_wattage = turbine_output * turbine_count(turbines)
  distance = turbine_distance(collection_point)((0, 0, -1, -1))

  line_options = []

  for hv in high_voltage_lines:
    _, line_wattage, line_cost = hv
    bundle_size = math.ceil(all_wattage/line_wattage)
    for tx in transformers:
      tx_cap, tx_cost = tx
      count = all_wattage / tx_cap
      line_options.append((line_cost * bundle_size * distance + count * tx_cost, hv))

  for mv in medium_voltage_lines:
    _, line_wattage, line_cost = mv
    bundle_size = math.ceil(all_wattage/line_wattage)
    line_options.append((line_cost * bundle_size * distance, mv))

  cost_to_shore, xv = min(line_options, key=lambda option: option[0])

  return cost_so_far + cost_to_shore, stars

  # Attach all turbines that are star_radius away. (Look up, down, left, right, and then again)
  # Repeat until all turbines are either centers, or are connected to one.
  # Attach all the centers to one location; this will be the collection_point.

def prepend(val):
  def inner(t):
    x, y, r, c = t
    return (val(t), x, y, r, c)
  return inner

def turbine_distance(center):
  def inner(other):
    cx, cy, ci, cj = center
    ox, oy, oi, oj = other
    dist = math.sqrt((cy - oy)**2 + (cx - ox)**2)
    #print(dist)
    return dist
  return inner

test_turbines = [[(100, 100, 0, 0), (150, 100, 0, 1), (200, 100, 0, 2)],
                [(125,  50, 1, 0), (175,  50, 1, 1), (225,  50, 1, 2)],
                [(100,   0, 2, 0), (150,   0, 2, 1), (200,   0, 2, 2)]]

layout_1 = turbine_layout(4,  7, skewx=lambda x: 250 if odd(x) else 0)
layout_2 = turbine_layout(6, 10, skewx=lambda x: 250 if odd(x) else 0)
layout_huge = turbine_layout(50, 50, skewx=lambda x: 250 if odd(x) else 0)

# print(attach_to_center(layout_1[3][4], 1, layout_1))

# star_method(test_turbines, test_turbines[0][0])
results = []
for row in layout_1:
  for turbine in row:
    _, _, row, col = turbine
    results.append(star_method(layout_1, layout_1[row][col], radius=1))

best = min(results, key=lambda stars: stars[0])

pp.pprint(best[1])
print('%.2E' % best[0])

# pp.pprint(layout_1)

'''
Okay. Situation:

We have a wind farm described like so:
  turbines=[(x,y)]
  turbine_output=4MW
  shore_connection=(x,y)

With the ability to place features like so:
  transformers
  high_voltage_lines
  medium_voltage_lines

And we need to choose the best position for:
  collection_point

1. Place collection_point
2. Connect turbines to each other and to collection_point
  a. Using combination of medium and high voltage cabling
  b. Potentially installing transformers to up voltage before sending to shore

::: collection_point can be placed anywhere at all
::: All connections can criss-cross
::: Only one type of cable can be placed between 2 nodes, but bundles of same type can be made
::: No high voltage lines can be installed between turbines

'''