[Question]
  [
You are Ruby, a railway engineer. Your task is to lay track in any given valley such that it visits every station (`M`). The amount of track laid is not important, but it must be laid in one continuous path which starts and ends at the valley entrance/exit point (`>`) and does not, at any point cross itself. There are a few other constraints: mountains(`^`) are impassable so you must go around them, rivers(`~`) must be crossed using a bridge(`X`), and the edge of the valley (`#`) is also impassable.
**The Rules of the Track**
If track is not laid properly there will be derailments and nobody wants that, so here are the rules over track placement.
There are four kinds of track: `-` `|` `/` `\`.  
Here's how each one may be combined with the others:
Allowed combinations from `-` (in the centre of each example):
```
#####  #####  #####  #####  #####  #####  #####
#   #  #   #  #\  #  #   #  #  /#  #\ /#  #   #
#---#  # --#  # --#  #-- #  #-- #  # - #  # - #
#   #  #/  #  #   #  #  \#  #   #  #   #  #/ \#
#####  #####  #####  #####  #####  #####  #####
```
`-` may never be combined with `|`. This is too sharp a turn for the trains to make safely.
Allowed combinations from `/` (in the centre of each example):
```
#####  #####  #####  #####  #####  #####  #####
#  /#  #  -#  #  |#  #  /#  #  /#  #  -#  #  |#
# / #  # / #  # / #  # / #  # / #  # / #  # / #
#/  #  #/  #  #/  #  #|  #  #-  #  #|  #  #-  #
#####  #####  #####  #####  #####  #####  #####
```
`\` may never be combined with `/`. This is too sharp a turn for the trains to make safely.
Allowed combinations from `\` (in the centre of each example):
```
#####  #####  #####  #####  #####  #####  #####
#\  #  #-  #  #|  #  #\  #  #\  #  #-  #  #|  #
# \ #  # \ #  # \ #  # \ #  # \ #  # \ #  # \ #
#  \#  #  \#  #  \#  #  |#  #  -#  #  |#  #  -#
#####  #####  #####  #####  #####  #####  #####
```
Allowed combinations from `|` (in the centre of each example):
```
#####  #####  #####  #####  #####  #####  #####
# | #  #\  #  #  /#  # | #  # | #  #  /#  #\  #
# | #  # | #  # | #  # | #  # | #  # | #  # | #
# | #  # | #  # | #  #/  #  #  \#  #  \#  #/  #
#####  #####  #####  #####  #####  #####  #####
```
Tracks may combine with the stations, bridges and valley entrance/exit in the following ways:
```
#####  #####  #####
#\|/#  #\|/#  #/  #
#-M-#  #-X-#  >-  #
#/|\#  #/|\#  #\  #
#####  #####  #####
```
Stations have turn-tables, so it's permissible to leave a station at a sharp angle (though not back the way you came - you wouldn't want to crash into the next scheduled train coming the other way!).  
Bridges are for crossing rivers so you must exit the bridge on the opposite side of the river that you entered it.
## Input
Input will be via STDIN for programs or a function argument for functions. If your function needs a name in order for me to run it on my input then that name declaration should be included in the byte count.
The input will be a **single** string with line-breaks. Each line within your input will always be the same length as the others, giving you a rectangular input. The edge of the input will always be solid and impassable (`#`) except for the point of entry. Any given input will have at least one valid answer.
## Output
Your output should be returned as a **single** string with line-breaks from a function, or printed/echoed to the screen for full programs.
The output should be the same as the input but with the track characters added.
## Scoring
Winner will be the shortest code in bytes.
## Test cases
```
###########
#    M    #
#   ^     #
>  ^^  M  #
#    ^    #
#~~~~~~~~~#
# M       #
#     ^^  #
#        M#
###########
#################
#               #
#   M         M #
#       ^       #
#        ^ M    #
#~~~~~~~^       #
#               #
#   ^           #
#   M^          #
#    ^          #
> ^^^          M#
#               #
#        M      #
#################
###############
# M   ~       #
#     ~       #
>     ~    M  #
#     ~       #
#     ~       #
#     ~       #
###############
```
## Possible solutions to test cases
```
###########
# ---M    #
#/  ^ \   #
>  ^^  M  #
#\   ^ |  #
#~X~~~~X~~#
# M     \ #
#  \  ^^ |#
#   -----M#
###########
#################
#               #
#   M---------M #
#   |   ^    /  #
#  /     ^ M-   #
#~X~~~~~^  |    #
# |         \   #
#  \^        \  #
# --M^        \ #
#/   ^         |#
> ^^^          M#
#\            / #
# -------M----  #
#################
###############
# M   ~       #
#/ \  ~       #
>   --X----M  #
#\    ~    |  #
# \   ~   /   #
#  ---X---    #
###############
```
  
[Answer]
# [Python 2](https://docs.python.org/2/), ~~3990~~ ~~3430~~ ~~4412~~ 4313 bytes
This is a basically an A\* with a ugly heuristic and an ugly `getChildren` method. To run the 3 test cases consecutively takes `6.5s` on my machine. The function `f` is the solution here. It takes the map as a string and returns the solved map as a string.
```
from itertools import*
import sys
from Queue import*
A,B,C,D,E,F,G=">|\\/-MX";H=range;I=permutations;J=set;K=abs;L=len
class M:
	@staticmethod
	def T(a):return a in">|\\/-MX"
	@staticmethod
	def C(a,b,c,d,x,y,e):
		if not M.T(d)or not M.T(e):return 0
		if e in"MX"and d in"MX"and e!=d:return 1
		if d==A:return x>0 and(e==D and y==-1 or e==E and y==0 or e==C and y==1)
		if d==F:return e==C and K(x+y)==2 or e==D and x+y==0 or e==B and x==0 or e==E and y==0
		if d==G:
			if b!=0!=c and K(b-x)+K(c-y)==1:return 0
			return e==C and K(x+y)==2 or e==D and x+y==0 or e==B and x==0 or e==E and y==0
		if e!=""and e in"MX>"and a!=""and a in"MX>":return M.C("",0,0,a,-b,-c,d)and M.C("",0,0,e,-x,-y,d)
		elif e!=""and e in"MX>"and a!="":return M.C("",0,0,d,b,c,a)and M.C("",0,0,e,-x,-y,d)
		elif e!=""and e in"MX>"and a=="":return M.C("",0,0,e,-x,-y,d)
		elif a!=""and a in"MX>":return M.C("",0,0,a,-b,-c,d)and M.C("",0,0,d,x,y,e)
		f=[[E,-1,0,E,1,0,E],[D,-1,1,E,1,0,E],[C,-1,-1,E,1,0,E],[E,-1,0,E,1,1,C],[E,-1,0,E,1,-1,D],[C,-1,-1,E,1,-1,D],[D,-1,1,E,1,1,C],[D,-1,1,D,1,-1,D],[D,-1,1,D,1,-1,E],[D,-1,1,D,1,-1,B],[B,-1,1,D,1,-1,D],[E,-1,1,D,1,-1,D],[B,-1,1,D,1,-1,E],[E,-1,1,D,1,-1,B],[C,-1,-1,C,1,1,C],[C,-1,-1,C,1,1,E],[C,-1,-1,C,1,1,B],[B,-1,-1,C,1,1,C],[E,-1,-1,C,1,1,C],[B,-1,-1,C,1,1,E],[E,-1,-1,C,1,1,B],[B,0,-1,B,0,1,B],[C,-1,-1,B,0,1,B],[D,1,-1,B,0,1,B],[B,0,-1,B,-1,1,D],[B,0,-1,B,1,1,C],[D,1,-1,B,1,1,C],[C,-1,-1,B,-1,1,D]];g=0;h=[a,b,c,d,x,y,e];j=[0,3][a==""]
		for k in f:
			l=1;m=1;n=[k[6],k[4],k[5],k[3],k[1],k[2],k[0]]
			for i in H(j,L(k)):
				if k[i]!=h[i]:l=0
				if n[i]!=h[i]:m=0
			if l or m:g=1
		return g
	def __init__(s,a):s.m=[list(x)for x in a.split("\n")]
	def __str__(s):return"\n".join(["".join(x)for x in s.m])
	def A(s):return str(s)
	def B(s):return L(s.m[0])
	def D(s):return L(s.m)
	def E(s):
		a=[]
		for y in H(1,s.D()-1):
			for x in H(1,s.B()-1):
				if s.J(x,y)==F and L(s.H(x,y, F))==0:a+=[(x,y)]
		return a
	def F(s):
		for y in H(s.D()):
			for x in H(s.B()):
				if s.J(x,y)==A:return(x,y)
	def G(s):
		a=0
		for y in H(0,s.D()-1):
			for x in H(0,s.B()-1):
				b=s.J(x,y)
				c=L(s.H(x,y,b))
				if b==A:
					if c==0:a=(x,y)
					c=0
				if c==1:return(x,y)
		if a!=0:
			return a
		raise ValueError()
	def J(s,x,y):return s.m[y][x]
	def K(s,x,y,b):
		a=[[i for i in row]for row in s.m];a[y][x]=b
		return"\n".join("".join(x)for x in a)
	def H(s,x,y,c):
		d=[];e=[]
		for a,b in J(I([-1,-1,0,1,1],2)):
			g=s.J(x+a,y+b)
			if M.T(g)and M.C("",0,0,c,a,b,g):e+=[[g,a,b]]
		if L(e)==1:return[e[0][0]]
		if L(e)==0:return[]
		for g,h in I(e,2):
			i,j,k=g;l,m,n=h;o=x + m;p=y + n
			if M.C(i,j,k,c,m,n,l):
				if l==F:
					if L(s.H(o,p,l))>=1:d+=[l]
				else:d+=[l]
		return d
	def I(s,x,y,a,b):
		if a==0 or b==0:return 0
		a=s.J(x+a,y);b=s.J(x,y+b)
		return(M.T(a)or a==F)and(M.T(b)or b==F)
class P:
	@staticmethod
	def A(x0,y0,x1,y1):return K(x0-x1)+4*K(y0-y1)
	def __init__(s,a,p,t=0,g=0):
		s.a=[];s.b=p;s.c=a;s.d=[a];s.e=t;s.f=g
		if p:s.d=p.d[:];s.d+=[a];s.e=p.e;s.f=p.f
		s.g=M(a);s.h=s.B()
	def __str__(s):return s.g.A()
	def B(s):
		a=0;b=1;c=0
		try:c=s.g.G()
		except:a=1
		d=s.g.E();e=s.g.F();g=[]
		if L(d)==0 and not a:g=P.A(c[0],c[1],e[0],e[1])+b
		elif L(d)==0 and a:return 0
		elif c:
			h,i=c
			for j in combinations(d,L(d)):
				k=0
				for x,y in j:k+=P.A(h,i,x,y);h,i=x,y
				g+=[k]
			g=min(g);g+=s.g.B()+s.g.D()+b
		else:return sys.maxint
		if g<1:return 0
		return g
	def C(s):
		try:a=s.g.G()
		except:s.a=[];return
		b=s.g.J(a[0],a[1]);c=("",0,0);e=(0,0)
		for x,y in J(I([-1,-1,0,1,1],2)):
			g,h=a[0]+x,a[1]+y;i=s.g.J(g,h)
			if M.T(i)and M.C("",0,0,i,x,y,b):c=(i,x,y)
			if i=="~":e=(x,y)
		for x,y in J(I([-1,-1,0,1,1],2)):
			g,h=a[0]+x,a[1]+y;i=s.g.J(g,h)
			if not(i in"^#"or M.T(i)):
				for j in"-|\\/":
					if i=="~":
						j=G 
						if c[0]==G:continue
					if c[0]==G and K(e[0])==1 and y==c[1]:continue
					if c[0]==G and K(e[1])==1 and x==c[0]:continue
					k=s.g.H(g,h,j);l=L(k)
					if(l==1 or l==2 and A in k)and M.C(c[0],c[1],c[2],b,x,y,j)and not s.g.I(a[0],a[1],x,y):
						try:s.a+=[P(s.g.K(g,h,j),s)]
						except:pass
def f(x):
	d=[];a=[];b=PriorityQueue();b.put((0,P(x,0)))
	while not d and b.qsize():
		c=b.get()[1];c.C();a+=[c.c]
		for e in c.a:
			if e.c not in a:
				if not e.h:d=e.d
				b.put((e.h,e))
	return d[-1]
```
[Try it online!](https://tio.run/nexus/python2#tVhtb@M2Ev4c/wqt9wtV0zop294HqwwucZyXzRpIgeJwgFYxKImRZcuyT1JQ61DsX9/O8EWSX7YFrq2DlciHM8OZ4cMhtV9fy@3GympR1tttXlnZZrct6@8G6m1VTTWQEj@9iTfRjl7TGzqlt3RG7@g9G179@vnzP8bz/wz9B1byIhX@I9uJcvNW8zrbFpX/kVWi9p8Yjyr/E8tFMYhzXlXWfDK4@FeFUvFG1MttMrhIxKv1M@H2pBT1W1lY3MqKboKz4lPCaURjmtA9baiwwehF9moV29qaOz@TxN6WbUe0hl0lJdA@WOZFYiW9tnjHEiPqKdGEsWsD7a9cC8SIYOwWG1bD2NizYCZAZgZxNTA1gGe3pu6MqXb8iexHjc3YpdZShgHrDN0oqAO6qVrD9xg/tqN3zH3HYm07Gu/t0ROJxziF18/Cxd/hCORvqBKpknolO9yg3KDGkbkzJcMhdeGP03FEx7CeNkr2BgQd7@m4gQGYQ@S/P8sZw4mkCf@/zbLzZk/1/1yYhsdg7ZUFwYyOPUBnVD5DGtwi4PWAKQLjPtLT8ej0EIDG7ZGShnqGlZYGbk9ENDI7QW4AuTnRmp0gNyd2Zid2jIfT1p9DZHaCtLMfaM1OkJsTO7MzdlzpCLwO3ekQ42sLtDoqlD7SpdQ7BDqzWin0U@b6SxYcVLXQX7HApR/CQNIwRHLAzlsDwaxXueNz5vkb@FewYB38M6Tr4Ht8/ICPD/jw8HGJDzdEfWkgQwMPZEU/kbUtS6fcvusgC9@xJTwnudzSqqR26EahAOZYATaTlGGZ1DRPVWVeLLIiqxcLUsGum1TOhgV5VtVkb@PUe5yaO9Uuz2oy/FwM7dCoVXWJWqZY46Cz2mYFCYa60TMBdkNbaV53OhbYgJ7Cb3r4JwIKkAI9dHs8pPEZ4hARZ4FJdqNy5dHKuSX22FPpav1QIzfdCGancj4SWECopneyQuIUD4hQ684G1J3wEQukSNjljysf7rQPvcnl1CcTy2nPTWoOLNlVRu/bwNxD0@4343KP4oqYmUF2Y9ZFFdm28SLC6WUHe7GMlXVaoNYSK@6OJCOgyqg76R1QHBPEs0pY/@b5m5iV5bYkOqqPwDHUbFcf1rgJg72m1JMaBvf0mgaZ1dK/3P4SYgfehk8@V9osahelI@EZDnLtxoOeJ5bzJMAdX3QEgh2Nwh/JIwnUrsfKAfvyUi9eqhI74rQZRbbeYHhvSY8PCTjHoDyk9kQAfYIUe3JTg/wnuOV0@QwEcF3v@HbQNYPGs5Qu0bNHIsAXdYGgK7pmqZ/TDS3Y0t@yvTWyNv6ONfAuWt@mREqCQyBH846EOd5x2uVXDNnSHYjYV@BdAn7nsgzBmVmJrq8XUF/uHnVCuV46pIW@dURdHPIew7vk2X5LUZVHzS1MJcf7INi4w5RKJLKVtTtb30ufz99Lr8nepY1L9x5tvJZpcFtyx3vPHn3/3RNp3HHj2afVD@KumUuhsssoKgfLil85EdvBM2YcnsAWjphgNTxfWarC3U1waOckwQRHMU9abOcIKbhzXqXNlM0hOoCWTO7Xb1RTIHjqXJN@aVTlAJLm@WpX1mUziRkK3hN5rdnHYlfD/vUkrXFgRmzgNrbuoJUqlsuVTpBhstrhtZvD0fAM88VAQhrjKYSMhIcX2qPIXJn6Wry/qnI0lkRa0ozFpjStkK/xdhNlhfrKIAlFI5qAa11c5A6lssKtJuuR9ATsyFrho0FoSMEU8roO1SbcwOZOIaaRDA8yOcI31EbtL9DVpLKBasH3WVGr4NMfD67Wh8fhVKcak8tPk6tJoXQGqsqmQGKO6eKYLlgcvf8x9QTfg4MQf6ey0CVDQ6O9NDVq/Eybh5F@pcmOK01mCidMrvKmpTO4iHwZTkRb0/86R4A3BEvz8OX9EIwqv/TKmsUfjvGrcNiVGO2P6l@s2L2lm0ggmBE/jeJtUWfFmxgcDejvHmQm1k7zMYN0/WMdr9PZo457rLOWET5ghHRl@znDy5YxR3JUhqBy/OJCI9eYwXW7Dt3GifH6Fsn1WNlmf6Hpx44k6hTUkSPTgFZA7WeCck/aBVrZoRbR5NtB3RsgSV/hWAN1eXRJPkbsucy2ZVY38j8BYK9Hzu6tJkC/Z1h518YT/5dllgvpTiJDiJz/Vtn/QBg9iVnkpKImNrjnxxCR7aNLsROb40fIzexw8@kqnFgaw5O1PVAQEM5ykjDhJOoeohwBED6XwAtzdADzwq8Zlr6Cb8RiAcRYLDY8KxYL5EfqwQ16@L77Dd5b8JvjQ7VfLNW@guaLHNEyL1rmi/khLhVbXaVi2mgX2t0PZgYPLo886PvR@ylk3vbnPbsvR7NKaH7o3xmZA@TldK6XY8Q6QK4guh4w/5Zly@ocP4i/n4UPZ7Kg8/nlyNqXngdtf35u/A/7ZzzZlVDBgfopnt1t57Lf@WB//Q0)
## Test Cases
### Test 1
[![enter image description here](https://i.stack.imgur.com/XB2Wx.gif)](https://i.stack.imgur.com/XB2Wx.gif)
```
###########
# ---M    #
#/  ^ \   #
>  ^^  M  #
#\   ^ |  #
#~X~~~~X~~#
# M    |  #
#  \  ^^\ #
#   -----M#
###########
```
---
### Test 2
[![enter image description here](https://i.stack.imgur.com/8tQW9.gif)](https://i.stack.imgur.com/8tQW9.gif)
```
#################
#               #
#   M---------M #
#  /    ^    /  #
# |      ^ M-   #
#~X~~~~~^   \   #
# |          |  #
#  \^        |  #
# --M^       |  #
#/   ^-       \ #
> ^^^/ \       M#
#\  /   \     / #
# --     M----  #
#################
```
---
### Test 3
[![enter image description here](https://i.stack.imgur.com/yA5Rg.gif)](https://i.stack.imgur.com/yA5Rg.gif)
```
###############
# M   ~       #
#/ \  ~       #
>   --X----M  #
#\    ~   /   #
# ----X---    #
#     ~       #
###############
```
---
## Source Code
### A\* State + A\* Solver Class
I actually golfed these out of my solution. But they exist in my *'readable'* version. The State class is generic and meant to be implemented. The Solver class takes a start state and then follows that states heuristic `getDist`.
```
from Queue import PriorityQueue
# A* State
class State(object):
    # The type of value should be a primative
    def __init__(self, value, parent, start=0, goal=0):
        self.children = []
        self.parent = parent
        self.value = value
        self.dist = 0
        if parent:
            self.path = parent.path[:]
            self.path.append(value)
            self.start = parent.start
            self.goal = parent.goal
        else:
            self.path = [value]
            self.start = start
            self.goal = goal
    # Implement a heuristic for calculating the distance from this state to the goal
    def getDist(self):
        pass
    # Implement a way to create children for this state
    def createChildren(self):
        pass
# A* Solver 
# Note: if maxmin = 1: Solver tries to minimize the distance
#       if maxmin = -1: Solver tries to maximize the distance
class AStar_Solver:
    def __init__(self,startState,maxmin=1):
        self.path = []
        self.visitedQueue = []
        self.priorityQueue = PriorityQueue()
        self.priorityQueue.put((0,startState))
        self.startState = startState
        self.maxmin = maxmin
        self.count = 0
    # Create a png of the string 'qPop'
    def imager(self,qPop):
        # Imager(qPop,str(self.count).rjust(5,"0")+".png")
        # print str(qPop)+"\n"
        self.count += 1
    # Solve the puzzle
    def solve(self):
        while(not self.path and self.priorityQueue.qsize()):
            closestChild = self.priorityQueue.get()[1]
            self.imager(str(closestChild))
            closestChild.createChildren()
            self.visitedQueue.append(closestChild.value)
            for child in closestChild.children:
                if child.value not in self.visitedQueue:
                    if not child.dist:
                        self.imager(str(child))
                        self.path = child.path
                        break
                    self.priorityQueue.put((self.maxmin*child.dist,child))
        if not self.path:
            print "Goal was not reachable"
        return self.path
```
### State Class
This is the implementation of the A\* state class. The most important method here is `getDist`, it is the heuristic for determining how close `self` is to the goal. It is basically the minimum distance to visit all the remaining destinations and get back to start.
```
from A_Star import State,AStar_Solver
from Ruby_Map import Map
from itertools import combinations, permutations
import sys
# A state class designed to work with A*
class State_Pathfinder(State):
    # This is deprecated
    @staticmethod
    def toValue(location):
        return str(location[0])+","+str(location[1])
    # Calculate the weighted distance between 2 points.
    # Not sure why the deltaY is more weighted. My theory
    # is that it is because the starting point is always
    # on a side. So vertical space is most precious?
    @staticmethod
    def distance(x0,y0,x1,y1):
        # return (abs(x0-x1)**2+abs(y0-y1)**2)**.5
        return 1*abs(x0-x1)+4*abs(y0-y1)
    def __init__(self, maps, parent, value=0, start=0, goal=0):
        super(State_Pathfinder,self).__init__(maps,parent,start,goal)
        self.map = Map(maps)
        self.dist = self.getDist()
        if not value:
            location = self.map.getLocation()
            self.value = maps
            self.path = [self.value]
    def __str__(self):
        return self.map.getDisplay()
    # The heuristic function that tells us
    # how far we are from the goal
    def getDist(self):
        blownup = False
        WEIGHT = 1
        location = None
        try:
            location = self.map.getLocation()
        except ValueError as e:
            blownup = True
        destinations = self.map.getDestinations()
        goal = self.map.getGoal()
        dist = []
        if len(destinations) == 0 and not blownup:
            dist = State_Pathfinder.distance(location[0],location[1],goal[0],goal[1])+WEIGHT
        elif len(destinations) == 0 and blownup:
            return 0
        elif location:
            oldX,oldY = location
            for path in combinations(destinations,len(destinations)):
                length = 0
                for pair in path:
                    x,y = pair
                    length += State_Pathfinder.distance(oldX,oldY,x,y)
                    oldX,oldY = x,y
                dist.append(length)
            dist = min(dist)
            dist += self.map.getWidth()+self.map.getHeight()+WEIGHT
        else:
            return sys.maxint
        if dist<1:
            return 0
        return dist
    # Creates all possible (legal) child states of this state
    def createChildren(self):
        if not self.children:
            try:
                location = self.map.getLocation()
            except:
                self.children = []
                return
            track = self.map.get(location[0],location[1])
            intrack = ("",0,0)
            river = (0,0)
            for x,y in set(permutations([-1,-1,0,1,1],2)):
                realX,realY = location[0]+x,location[1]+y
                adjacent = self.map.get(realX,realY)
                if Map.isTrack(adjacent) and Map.isConnected("",0,0,adjacent,x,y,track):
                    intrack = (adjacent,x,y)
                if adjacent=="~":
                    river = (x,y)
            for x,y in set(permutations([-1,-1,0,1,1],2)):
                realX,realY = location[0]+x,location[1]+y
                adjacent = self.map.get(realX,realY)
                if not Map.isBlocking(adjacent) and not adjacent in "M":
                    for outtrack in "-|\\/":
                        if adjacent=="~":
                            outtrack="X"
                            if intrack[0]=="X":continue
                        if intrack[0]=="X" and abs(river[0])==1 and y==intrack[1]:continue
                        if intrack[0]=="X" and abs(river[1])==1 and x==intrack[0]:continue
                        connections = self.map.getConnections(realX,realY,outtrack)
                        hoppin = len(connections)
                        connected = Map.isConnected(intrack[0],intrack[1],intrack[2],track,x,y,outtrack)
                        blocked = self.map.isBlocked(location[0],location[1],x,y)
                        if (hoppin==1 or hoppin==2 and ">" in connections) and connected and not blocked:
                            try:
                                maps = self.map.set(realX,realY,outtrack)
                                value = State_Pathfinder.toValue((realX,realY))
                                child = State_Pathfinder(maps,self,value)
                                self.children.append(child)
                            except ValueError as e:
                                print "Bad kid"
                                print e
# The solution function. Takes a map string
# and returns a map string.
def f(mapX):
    a = AStar_Solver(State_Pathfinder(mapX,0))
    a.solve()
    print a.path[-1]
if __name__ == "__main__":
    map1 = """###########
#    M    #
#   ^     #
>  ^^  M  #
#    ^    #
#~~~~~~~~~#
# M       #
#     ^^  #
#        M#
###########"""
    map2 = """#################
#               #
#   M         M #
#       ^       #
#        ^ M    #
#~~~~~~~^       #
#               #
#   ^           #
#   M^          #
#    ^          #
> ^^^          M#
#               #
#        M      #
#################"""
    map3 = """###############
# M   ~       #
#     ~       #
>     ~    M  #
#     ~       #
#     ~       #
#     ~       #
###############"""
    f(map3)
    f(map2)
    f(map1)
```
### Map Class
This class stores and processes the map. The `isConnected` method is probably the most important piece. It tests to see if 2 pieces of track are connected.
```
from itertools import permutations,combinations
# A map class designed to hold string map
# the specification is found here:
# http://codegolf.stackexchange.com/questions/104965/ruby-on-rails-or-trackety-track
class Map(object):
    # Is 'track' part of the railroad?
    @staticmethod
    def isTrack(track):
        return track in ">|\\/-MX"
    # Can I not build on this terrian?
    @staticmethod
    def isBlocking(terrian):
        return terrian in "^#" or (Map.isTrack(terrian) and not terrian=="M")
    # Are these 3 consecuative tracks connected in a legal fashion?
    @staticmethod
    def isConnected(inTerrian,relativeXin,relativeYin,centerTerrian,relativeXout,relativeYout,outTerrian):
        tin = inTerrian
        xin = relativeXin
        yin = relativeYin
        x = relativeXout
        y = relativeYout
        tout = outTerrian
        center = centerTerrian
        if not Map.isTrack(center) or not Map.isTrack(tout):
            return False
        if tout in "MX" and center in "MX" and tout!=center:
            return True
        if center == ">":
            return x>0 and (\
                tout == "/" and y == -1 or \
                tout == "-" and y == 0 or \
                tout == "\\" and y == 1 \
                )
        if center == "M":
            return tout == "\\" and abs(x+y) == 2 or \
                tout == "/" and x+y == 0 or \
                tout == "|" and x == 0 or \
                tout == "-" and y == 0
        if center == "X":
            if xin!=0!=yin and abs(xin-x)+abs(yin-y) == 1:
                return False
            return tout == "\\" and abs(x+y) == 2 or \
                tout == "/" and x+y == 0 or \
                tout == "|" and x == 0 or \
                tout == "-" and y == 0
        if tout!="" and tout in "MX>" and tin!="" and tin in "MX>":
            return Map.isConnected("",0,0,tin,-xin,-yin,center) and Map.isConnected("",0,0,tout,-x,-y,center)
        elif tout!="" and tout in "MX>" and tin!="":
            return Map.isConnected("",0,0,center,xin,yin,tin) and Map.isConnected("",0,0,tout,-x,-y,center)
        elif tout!="" and tout in "MX>" and tin=="":
            return Map.isConnected("",0,0,tout,-x,-y,center)
        elif tin!="" and tin in "MX>":
            return Map.isConnected("",0,0,tin,-xin,-yin,center) and Map.isConnected("",0,0,center,x,y,tout)
        allowed = [ \
            ["-",-1,0,"-",1,0,"-"], \
            ["/",-1,1,"-",1,0,"-"], \
            ["\\",-1,-1,"-",1,0,"-"], \
            ["-",-1,0,"-",1,1,"\\"], \
            ["-",-1,0,"-",1,-1,"/"], \
            ["\\",-1,-1,"-",1,-1,"/"], \
            ["/",-1,1,"-",1,1,"\\"], \
            ["/",-1,1,"/",1,-1,"/"], \
            ["/",-1,1,"/",1,-1,"-"], \
            ["/",-1,1,"/",1,-1,"|"], \
            ["|",-1,1,"/",1,-1,"/"], \
            ["-",-1,1,"/",1,-1,"/"], \
            ["|",-1,1,"/",1,-1,"-"], \
            ["-",-1,1,"/",1,-1,"|"], \
            ["\\",-1,-1,"\\",1,1,"\\"], \
            ["\\",-1,-1,"\\",1,1,"-"], \
            ["\\",-1,-1,"\\",1,1,"|"], \
            ["|",-1,-1,"\\",1,1,"\\"], \
            ["-",-1,-1,"\\",1,1,"\\"], \
            ["|",-1,-1,"\\",1,1,"-"], \
            ["-",-1,-1,"\\",1,1,"|"], \
            ["|",0,-1,"|",0,1,"|"], \
            ["\\",-1,-1,"|",0,1,"|"], \
            ["/",1,-1,"|",0,1,"|"], \
            ["|",0,-1,"|",-1,1,"/"], \
            ["|",0,-1,"|",1,1,"\\"], \
            ["/",1,-1,"|",1,1,"\\"], \
            ["\\",-1,-1,"|",-1,1,"/"] \
        ]
        passing = False
        forward = [tin,xin,yin,center,x,y,tout]
        start = [0,3][tin==""]
        for allow in allowed:
            maybeF = True
            maybeB = True
            backallowed = [allow[6],allow[4],allow[5],allow[3],allow[1],allow[2],allow[0]]
            for i in range(start,len(allow)):
                if allow[i]!=forward[i] and str(forward[i])not in"*":
                    maybeF = False
                if backallowed[i]!=forward[i] and str(forward[i])not in"*":
                    maybeB = False
            if maybeF or maybeB:
                passing = True
        return passing
    def __init__(self,mapString):
        self.indexableMap = [list(x) for x in mapString.split("\n")]
    def __str__(self):
         return "\n".join(["".join(x) for x in self.indexableMap])
    # Get the string representation of this map
    def getDisplay(self):
        return self.__str__()
    # Get map width
    def getWidth(self):
        return len(self.indexableMap[0])
    # Get map height
    def getHeight(self):
        return len(self.indexableMap)
    # Get unvisited destinations
    def getDestinations(self):
        destinations = []
        for y in xrange(1,self.getHeight()-1):
            for x in xrange(1,self.getWidth()-1):
                sigma = 2
                if self.get(x,y)=="M":
                    sigma = len(self.getConnections(x,y,"M"))
                    if sigma==0:
                        destinations.append((x,y))
        return destinations
    # Get the x,y of the goal (endpoint)
    def getGoal(self):
        for y in xrange(self.getHeight()):
            for x in xrange(self.getWidth()):
                if self.get(x,y)==">":
                    return (x,y)
    # Get the x,y of the current location
    def getLocation(self):
        location = None
        for y in xrange(0,self.getHeight()-1):
            for x in xrange(0,self.getWidth()-1):
                track = self.get(x,y)
                sigma = len(self.getConnections(x,y,track))
                if track == ">":
                    if sigma==0:
                        location = (x,y)
                    sigma = 0
                if sigma == 1:
                    return (x,y)
        if location != None:
            return location
        raise ValueError('No location found in map\n'+self.getDisplay())
    # Get the terrian at x,y
    def get(self,x,y):
        return self.indexableMap[y][x]
    # Set the terrain at x,y
    # (non-destructive)
    def set(self,x,y,value):
        newMap = [[i for i in row] for row in self.indexableMap]
        newMap[y][x] = value
        return "\n".join(["".join(x) for x in newMap])
    # Get the track connectioning to a piece of track at x,y
    def getConnections(self,x,y,track):
        connections = []
        tracks = []
        for a,b in set(permutations([-1,-1,0,1,1],2)):
            outtrack = self.get(x+a,y+b)
            if Map.isTrack(outtrack) and Map.isConnected("",0,0,track,a,b,outtrack):
                tracks+=[[outtrack,a,b]]
        if len(tracks)==1:return [tracks[0][0]]
        if len(tracks)==0:return []
        for inner,outer in permutations(tracks,2):
            intrack,relXin,relYin = inner
            other,relX,relY = outer
            ex = x + relX
            ey = y + relY
            if Map.isConnected(intrack,relXin,relYin,track,relX,relY,other):
                if other == "M":
                    if len(self.getConnections(ex,ey,other))>=1:
                        connections.append(other)
                else:
                    connections.append(other)
        return connections
    # Is could a piece of track at x,y build in
    # the direct of relX,relY?
    def isBlocked(self,x,y,relX,relY):
        if relX==0 or relY==0:
            return False
        side1 = self.get(x+relX,y)
        side2 = self.get(x,y+relY)
        return (Map.isTrack(side1) or side1=="M")  and (Map.isTrack(side2) or side2=="M")
```
---
## Updates
* **-560** [17-03-31] A bunch of basic regex golfing
* **+982** [17-03-31] Fixed illegal track laying. Thanks *@fəˈnɛtɪk*!
* **-99** [17-03-31] Utilized `;`s
]