text: #
  # Copyright (c) Tobias Pfandzelter. All rights reserved.
  # Licensed under the MIT license. See LICENSE file in the project root for details.
  #
  
  import typing
  import numpy as np
  import itertools
  import tqdm
  
  def weighted_lee(a: typing.Tuple[int, int], b: typing.Tuple[int, int], k1: int, k2: int, d1: float, d2: float) -> float:
          return min((a[0] - b[0]) % k1, (b[0] - a[0]) % k1)*d1 + min((a[1] - b[1]) % k2, (b[1] - a[1]) % k2)*d2
  
  def __placement(k1: int, k2: int, d1: float, d2: float, t: float, debug: bool = False) -> typing.Tuple[typing.List[typing.Tuple[int, int]], float]:
  
      # calculate initial values
  
      # t' is the hops on the modified torus
      t_ = np.floor(t/d1)
  
      if debug:
          print("t':", t_)
  
      # k2' is the vertical size of the modified torus
      # k2'r is k2/k2'
      k2_ = int(np.ceil( (d2 / d1) * k2))
      k2_r = k2 / k2_
  
      if debug:
          print("k2':", k2_)
          print("k2'r:", k2_r)
  
      # now we have a torus of size k1*k2_ and perform a t_-hop placement on that.
      # to convert y coordinates for resource nodes, transform ky_ back into y.
      # build a torus of k*k so that k = 2(t_**2) + 2t_ + 1
      k = int(2*(t_**2) + 2*t_ + 1)
      if debug:
          print("k:", k)
  
      # construct a perfect t_-hop placement on the k*k torus
      p = np.array(
          [y for y in
              [
                  [
                      int(i % k), int((2 * (t_**2) * i ) % k)
                  ]
                  for i in np.arange(0, k)
              ]
          ]
      )
  
      # if debug:
      #     print("p:", p)
  
      # use that to tile the x*ky_ torus
      # we need np.ceil(x/k) times np.ceil(ky_/k) tiles, then we cut off some stuff
      n = []
  
      for i in range(int(np.ceil(k1/k))):
          for j in range(int(np.ceil(k2_/k))):
              for pl in p:
                  # convert ky_ back into y
                  # only if this is still in range, otherwise just discard
                  cx  = (i * k) + pl[0]
                  cy = (j * k) + pl[1]
  
                  if cx < k1 and cy < k2_:
                      #print("add {} {} ({} {}) (i: {} j: {} k: {} pl:{})".format(cx, cy, cx, (j * k) + pl[1], i, j, k, pl))
                      n.append((cx, cy))
  
      if debug:
          print("n:", n)
  
  
      # 6. because we cut off some resource nodes, we have some "uncovered" nodes at the edges.
      # go through all the nodes
      # one by one, add the nodes with the largest nodes until all are covered
      # takes O(n^3) time (?) but should be fine
  
      uncovered = set(itertools.product(range(k1), range(k2_)))
  
      while len(uncovered) > 0:
          max_dist = 0
          max_node = None
  
          for node in tqdm.tqdm(list(uncovered), disable=not debug):
              min_dist = np.inf
  
              for rn in n:
                  dist = weighted_lee(node, rn, k1, k2_, 1.0, 1.0)
  
                  if dist < min_dist:
                      min_dist = dist
  
                  if dist <= t_:
                      uncovered.remove(node)
                      break
  
              if min_dist > t_ and min_dist > max_dist:
                  max_dist = min_dist
                  max_node = node
  
          if max_node == None:
              break
  
          n.append(max_node)
          uncovered.remove(max_node)
  
      # convert the y coordinates back into the old k2
      n = [(x, int(k2_r * y)) for x, y in n]
      if debug:
          print("n:", n)
  
      #cy = int(np.floor(k2_r * ((j * k) + pl[1])))
      # if debug:
      #     print("n:", n)
      # figure out epsilon
      eps = -np.inf
  
      for node in itertools.product(range(k1), range(k2)):
      # for node in itertools.product(range(k1), range(k2)):
          min_dist = np.inf
  
          for rn in n:
              dist = weighted_lee(node, rn, k1, k2, d1, d2)
  
              if dist < min_dist:
                  min_dist = dist
  
          if min_dist-t > eps:
              eps = min_dist-t
  
          if min_dist > t:
              if debug:
                  print("{}".format(min_dist - t))
  
      if debug:
          print("epsilon:", eps)
  
      if debug:
          print("n:", n)
  
      if debug:
          for node in itertools.product(range(k1), range(k2)):
          # for node in itertools.product(range(k1), range(k2)):
              min_dist = np.inf
  
              for rn in n:
                  dist = weighted_lee(node, rn, k1, k2, d1, d2)
  
                  if dist < min_dist:
                      min_dist = dist
  
              if min_dist > t + eps:
                  print("{}".format(min_dist - t))
                  raise ValueError("there is a min_dist > t!")
  
      return n, eps
  
  def placement(k1: int, k2: int, d1: float, d2: float, t: float, debug: bool = False) -> typing.Tuple[typing.List[typing.Tuple[int, int]], float]:
      """
      Calculates a distance-t placement on a k1 x k2 2D torus with horizontal
      weights d1 and vertical weights d2.
  
      Parameters:
      k1, k2: The dimensions of the torus.
      d1, d2: The weights of thee torus.
      t: The target distance limit
  
      Returns:
      A list of tuples, where each tuple contains the x and y coordinates of a
      resource node.
      """
  
      switch = d1 > d2
  
      if switch:
          k1, k2 = k2, k1
          d1, d2 = d2, d1
  
      if debug:
          print("k1: {}, k2: {}, d1: {}, d2: {}, t: {}".format(k1, k2, d1, d2, t))
  
      if d1 <= t and d2 <= t:
          n, eps = __placement(k1, k2, d1, d2, t, debug)
          if switch:
              n = [(y, x) for x, y in n]
  
          return n, eps
  
      elif d1 <= t and d2 > t:
          # tile with the k1 x 1 torus
  
          dist = int(np.floor(t/d1)) * 2 + 1
          n = [(x, 0) for x in range(0, k1, dist)]
          if debug:
              print("n:", n)
  
          n_ = []
          for i in range(k2):
              for rn in n:
                  n_.append((rn[0], i))
          n = n_
  
          if switch:
              n = [(y, x) for x, y in n]
  
          return n, 0
  
      else:
          # every node is a resource node
          n = [(x, y) for x, y in itertools.product(range(k1), range(k2))]
          if switch:
              n = [(y, x) for x, y in n]
  
          return n, 0
  
  if "__main__" == __name__:
      np.random.seed(0)
  
      for i in range(0, 20):
          # make random x, y, dy, dx, t
          x = np.random.randint(1, 50)
          y = np.random.randint(1, 50)
          dx = np.random.random() * 100 + 0.01
          dy = np.random.random() * 100 + 0.01
          t = np.random.random() * 100 + 0.01
  
          # get a placement
          n, eps = placement(x, y, dx, dy, t)
  
          # make sure it is within t + epsilon
          with tqdm.tqdm(total=x*y*len(n), desc="Checking error") as pbar:
              for bx in range(0, x):
                  for by in range(0, y):
                      best_dist = np.inf
                      best_p = (np.inf, np.inf)
                      for i in range(0, len(n)):
                          p = n[i]
                          dist = weighted_lee(p, (bx, by), x, y, dx, dy)
                          if dist < best_dist:
                              best_dist = dist
                              best_p = p
                          pbar.update(1)
  
                      if best_dist > t + eps:
                          print(x, y, dx, dy, t, bx, by, best_p[0], best_p[1], best_dist)
                          exit(1)