PuzzlOR : Moon Rover Puzzle

The Moon Rover Problem¶

http://puzzlor.com/2015-08_MoonRover.html

In [1]:

pylab inline

Populating the interactive namespace from numpy and matplotlib

In [2]:

import matplotlib.pyplot as plt
import numpy as np
import itertools
from scipy.spatial.distance import pdist, squareform
from time import process_time

In [3]:

# Lookup Table for the original alphanumeric coordinates
site_name = ["D6","H1","E2","B3","G3","H4","G6","I7","A8","G8","D10"]
# Lookup Table for the Science Points
site_value = [0,2,4,3,5,1,4,1,3,2,5]
# Lookup Table for the XY coordinates
site_loc = np.array([[4,6],[8,1],[5,2],[2,3],[7,3],[8,4],[7,6],[9,7],[1,8],[7,8],[4,10]])
print(site_loc)

[[ 4  6]
 [ 8  1]
 [ 5  2]
 [ 2  3]
 [ 7  3]
 [ 8  4]
 [ 7  6]
 [ 9  7]
 [ 1  8]
 [ 7  8]
 [ 4 10]]

In [4]:

# Compute the Euclidean distance between all rows of loc.
site2site_distance = squareform(pdist(site_loc, 'euclidean'))
print(site2site_distance)

[[ 0.          6.40312424  4.12310563  3.60555128  4.24264069  4.47213595
   3.          5.09901951  3.60555128  3.60555128  4.        ]
 [ 6.40312424  0.          3.16227766  6.32455532  2.23606798  3.
   5.09901951  6.08276253  9.89949494  7.07106781  9.8488578 ]
 [ 4.12310563  3.16227766  0.          3.16227766  2.23606798  3.60555128
   4.47213595  6.40312424  7.21110255  6.32455532  8.06225775]
 [ 3.60555128  6.32455532  3.16227766  0.          5.          6.08276253
   5.83095189  8.06225775  5.09901951  7.07106781  7.28010989]
 [ 4.24264069  2.23606798  2.23606798  5.          0.          1.41421356
   3.          4.47213595  7.81024968  5.          7.61577311]
 [ 4.47213595  3.          3.60555128  6.08276253  1.41421356  0.
   2.23606798  3.16227766  8.06225775  4.12310563  7.21110255]
 [ 3.          5.09901951  4.47213595  5.83095189  3.          2.23606798
   0.          2.23606798  6.32455532  2.          5.        ]
 [ 5.09901951  6.08276253  6.40312424  8.06225775  4.47213595  3.16227766
   2.23606798  0.          8.06225775  2.23606798  5.83095189]
 [ 3.60555128  9.89949494  7.21110255  5.09901951  7.81024968  8.06225775
   6.32455532  8.06225775  0.          6.          3.60555128]
 [ 3.60555128  7.07106781  6.32455532  7.07106781  5.          4.12310563
   2.          2.23606798  6.          0.          3.60555128]
 [ 4.          9.8488578   8.06225775  7.28010989  7.61577311  7.21110255
   5.          5.83095189  3.60555128  3.60555128  0.        ]]

In [5]:

best_path_value = 0  # Start with zero Science Points

t=process_time()

# BRUTE FORCE SEARCH
# Consider every possible permutation of the 10 target sites
for path in itertools.permutations([1,2,3,4,5,6,7,8,9,10]):
    current_site = 0
    total_path_length = 0.0
    path_value = 0
    for next_site in path:
        distance=site2site_distance[current_site][next_site]
        if (total_path_length+distance>25.0):
            break
        else:
            total_path_length+=distance
            current_site=next_site
            path_value+=site_value[current_site]
    
    # print(path, total_path_length, current_site, path_value)
    if (path_value>best_path_value):
        best_path=path
        best_path_value=path_value
        last_best_site=current_site

elapsed_time=process_time()-t        
print("Best Path: ",best_path, total_path_length, last_best_site, best_path_value)
print("Elapsed Time: ", elapsed_time)

Best Path:  (3, 2, 1, 4, 6, 9, 10, 8, 5, 7) 23.9038770013 8 28
Elapsed Time:  54.529475274

In [6]:

x = []; y = []
x.append(site_loc[0][0])
y.append(site_loc[0][1])

# Display details about the optimal solution
print("Visit these sites: ",end=" ")
for i in best_path:
    x.append(site_loc[i][0])
    y.append(site_loc[i][1])
    if i==last_best_site:
        print(site_name[i])
        break
    print(site_name[i],end=", ")

print("Total Path Length: ", round(total_path_length,1))
print("Total Science Points: ", best_path_value)

Visit these sites:  B3, E2, H1, G3, G6, G8, D10, A8
Total Path Length:  23.9
Total Science Points:  28

In [7]:

# A simple plot of the path taken by the rover
plt.xlim(0, 10.5)
plt.ylim(0, 10.5)
plt.plot(x, y, 'co')

for i in range(0,len(x)-1):
    plt.arrow(x[i], y[i], (x[i+1] - x[i]), (y[i+1] - y[i]), head_width = .3, 
              color = 'r', length_includes_head = True)