It seems that you can get meat or amazon gift vouchers by lottery, so this time I tried it with python3. https://paiza.jp/poh/phantom_thief
Problem summary
N treasure x,Given the y coordinate.
Move in a straight line between each coordinate.
0,Start from position 0.
Output the route to get each treasure with the shortest route possible.
It does not have to be the shortest distance.
Value to be entered
N (N is the total number of treasures)
x_1 y_1 （x_1 is the x-coordinate of the first treasure location, y_1 is the y coordinate of the first treasure location)
x_1 y_1 （x_2 is the x-coordinate of the second treasure location, y_2 is the y coordinate of the second treasure location)
・ ・ ・
x_N y_N （x_N is the x-coordinate of the Nth treasure location, y_N is the y coordinate of the Nth treasure location)
・ All values are integers
・ 1 ≤ N ≤ 100
・ 1 ≤ x_i, y_i ≦ 1000000 (1 ≦ i ≦ N)
Expected output
Please output the route where you can get all the treasure.
At the end, start a new line and do not include extra characters or blank lines.
Example
Input example 1
3
90 100
40 15
30 30
Output example 1
90 100
40 15
30 30
Input example 2
5
1 1
40 120
199 256
10 30
50 5
Output example 2
1 1
40 120
199 256
10 30
50 5
The code I wrote.
import math
def cal_distance(current_point, point):
"""Find the distance between two points"""
x1 = current_point[0]
y1 = current_point[1]
x2 = point[0]
y2 = point[1]
distance = math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
return distance
def make_distance_list(current_point, position_list):
"""Create a list of distances between two points"""
distance_list = [(i, cal_distance(current_point, x)) for (i, x) in enumerate(position_list)]
return distance_list
#Get input value
list_len = int(input())
position_list = []
for i in range(list_len):
position_list.append(list(map(int,input().split())))
#Move closer to the current position
current_point = [0, 0]
while len(position_list) > 0:
distance_list = make_distance_list(current_point, position_list)
sorted_distance_list = [x[0] for x in sorted(distance_list, key=lambda d: d[1])]
print('{0} {1}'.format(position_list[sorted_distance_list[0]][0],
position_list[sorted_distance_list[0]][1]))
current_point = position_list.pop(sorted_distance_list[0])
Execution result (It is a little difficult to understand the boundary between input and output)
$ python PaizaRouteSearch.py
5
1 2
4 2
10 40
3 2
1 1
1 1
1 2
3 2
4 2
10 40
I wrote it with a simple idea that I should follow the treasure closest to me from my current position. According to what I heard, the shortest route is to solve it with an algorithm called the "traveling salesman problem."
I would like to investigate and review it when I have time.
Postscript: There was an article explaining the problem on paiza's blog. [http://paiza.hatenablog.com/entry/2017/09/26/ [Problem explanation] How to solve the mystery from the phantom thief 813 and get the treasure](http://paiza.hatenablog.com/entry/ 2017/09/26 /% E3% 80% 90% E5% 95% 8F% E9% A1% 8C% E8% A7% A3% E8% AA% AC% E3% 80% 91% E6% 80% AA% E7 % 9B% 97913% E3% 81% 8B% E3% 82% 89% E3% 81% AE% E8% AC% 8E% E3% 82% 92% E8% A7% A3% E3% 81% 84% E3% 81 % A6% E3% 80% 81% E3% 81% 8A% E5% AE% 9D% E3% 82% B2% E3% 83% 83% E3% 83% 88)
It seems that my solution is a greedy algorithm, and I introduced the same solution on paiza's blog. In addition, "simulated annealing", "beam search", "2-opt", "genetic algorithm", It seems that there are various algorithms such as "Christofeed algorithm", "spanning tree", and "slime mold algorithm". Looking at Wikipedia, the formula is ... I have a headache because I have been away from math since I was a student.
About gifts It seems that shipping to the winners has already started, and I have not contacted myself so it seems that I missed it. Sorry.
By the way, the following was wrong. There seems to be a problem and there are several algorithms as a solution.
According to what I heard, the shortest route is to solve with an algorithm called the "traveling salesman problem".
Addendum 2: About gifts About a month and a half later, when I forgot, I received an Amazon gift certificate (1000 yen worth)! I'm glad I didn't expect it! It seems to be a hit unexpectedly, so I would like to participate again next time!
Recommended Posts