old_contents: # Copyright (c) 2015, Bartlomiej Puget <larhard@gmail.com>
  # All rights reserved.
  #
  # Redistribution and use in source and binary forms, with or without
  # modification, are permitted provided that the following conditions are met:
  #
  #   * Redistributions of source code must retain the above copyright notice,
  #     this list of conditions and the following disclaimer.
  #
  #   * Redistributions in binary form must reproduce the above copyright notice,
  #     this list of conditions and the following disclaimer in the documentation
  #     and/or other materials provided with the distribution.
  #
  #   * Neither the name of the Bartlomiej Puget nor the names of its
  #     contributors may be used to endorse or promote products derived from this
  #     software without specific prior written permission.
  #
  # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  # AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  # IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  # DISCLAIMED. IN NO EVENT SHALL BARTLOMIEJ PUGET BE LIABLE FOR ANY DIRECT,
  # INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  # BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  # OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  # NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
  # EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  
  import queue
  
  from copy import copy
  
  import tsp.utils
  
  
  class TSPPath:
      def __init__(self, path, cost, expected_cost):
          self._path = copy(path)
          self._cost = cost
  
      @property
      def visit_order(self):
          return copy(self._path)
  
      @property
      def cost(self):
          return self._cost
  
  
  def solve(vertices, tactic=None):
      tactic = tactic or tsp.utils.euclid_distance
  
      todo = queue.PriorityQueue()
  
      todo.put((0, [vertices[0]], ))
  
      min_cost = None
      min_path = None
  
      while todo.qsize() > 0:
          expected_cost, path = todo.get()
          cost = tsp.utils.path_length(path)
  
          if len(vertices) == len(path):
              total_cost = cost + tsp.utils.euclid_distance(path[-1], path[0])
              if min_cost is None or min_cost > total_cost:
                  min_cost = total_cost
                  min_path = path
          else:
              for v in vertices:
                  if v not in path:
                      new_cost = cost + tactic(path[-1], v, vertices=vertices,
                              path=path)
                      if min_cost is None or new_cost < min_cost:
                          todo.put((new_cost, path + [v]))
  
      return min_path
  
new_contents: # Copyright (c) 2015, Bartlomiej Puget <larhard@gmail.com>
  # All rights reserved.
  #
  # Redistribution and use in source and binary forms, with or without
  # modification, are permitted provided that the following conditions are met:
  #
  #   * Redistributions of source code must retain the above copyright notice,
  #     this list of conditions and the following disclaimer.
  #
  #   * Redistributions in binary form must reproduce the above copyright notice,
  #     this list of conditions and the following disclaimer in the documentation
  #     and/or other materials provided with the distribution.
  #
  #   * Neither the name of the Bartlomiej Puget nor the names of its
  #     contributors may be used to endorse or promote products derived from this
  #     software without specific prior written permission.
  #
  # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  # AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  # IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  # DISCLAIMED. IN NO EVENT SHALL BARTLOMIEJ PUGET BE LIABLE FOR ANY DIRECT,
  # INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  # BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  # OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  # NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
  # EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  
  import queue
  
  import tsp.utils
  
  
  def solve(vertices, tactic=None):
      tactic = tactic or tsp.utils.euclid_distance
  
      todo = queue.PriorityQueue()
  
      todo.put((0, [vertices[0]], ))
  
      min_cost = None
      min_path = None
  
      while todo.qsize() > 0:
          expected_cost, path = todo.get()
          cost = tsp.utils.path_length(path)
  
          if len(vertices) == len(path):
              total_cost = cost + tsp.utils.euclid_distance(path[-1], path[0])
              if min_cost is None or min_cost > total_cost:
                  min_cost = total_cost
                  min_path = path
          else:
              for v in vertices:
                  if v not in path:
                      new_cost = cost + tactic(path[-1], v, vertices=vertices,
                              path=path)
                      if min_cost is None or new_cost < min_cost:
                          todo.put((new_cost, path + [v]))
  
      return min_path
  
subject: remove tsp.solver.TSPPath