Ruby on Rails (o Trackety Track)

48

Eres Ruby, un ingeniero ferroviario. Su tarea es establecer un camino en cualquier valle dado de modo que visite cada estación ( M). La cantidad de pista establecida no es importante, pero debe colocarse en un camino continuo que comienza y termina en el punto de entrada / salida del valle ( >) y no se cruza en ningún punto. Hay algunas otras limitaciones: las montañas ( ^) son intransitables, por lo que debe rodearlas, los ríos ( ~) deben cruzarse con un puente ( X) y el borde del valle ( #) también es intransitable.

Las reglas de la pista

Si la pista no se coloca correctamente, habrá descarrilamientos y nadie quiere eso, así que aquí están las reglas sobre la colocación de la pista.

Hay cuatro tipos de vías: - | / \.
Así es como cada uno se puede combinar con los demás:

Combinaciones permitidas de -(en el centro de cada ejemplo):

#####  #####  #####  #####  #####  #####  #####
#   #  #   #  #\  #  #   #  #  /#  #\ /#  #   #
#---#  # --#  # --#  #-- #  #-- #  # - #  # - #
#   #  #/  #  #   #  #  \#  #   #  #   #  #/ \#
#####  #####  #####  #####  #####  #####  #####

-nunca se puede combinar con |. Este es un giro demasiado brusco para que los trenes lo hagan con seguridad.

Combinaciones permitidas de /(en el centro de cada ejemplo):

#####  #####  #####  #####  #####  #####  #####
#  /#  #  -#  #  |#  #  /#  #  /#  #  -#  #  |#
# / #  # / #  # / #  # / #  # / #  # / #  # / #
#/  #  #/  #  #/  #  #|  #  #-  #  #|  #  #-  #
#####  #####  #####  #####  #####  #####  #####

\nunca se puede combinar con /. Este es un giro demasiado brusco para que los trenes lo hagan con seguridad.

Combinaciones permitidas de \(en el centro de cada ejemplo):

#####  #####  #####  #####  #####  #####  #####
#\  #  #-  #  #|  #  #\  #  #\  #  #-  #  #|  #
# \ #  # \ #  # \ #  # \ #  # \ #  # \ #  # \ #
#  \#  #  \#  #  \#  #  |#  #  -#  #  |#  #  -#
#####  #####  #####  #####  #####  #####  #####

Combinaciones permitidas de |(en el centro de cada ejemplo):

#####  #####  #####  #####  #####  #####  #####
# | #  #\  #  #  /#  # | #  # | #  #  /#  #\  #
# | #  # | #  # | #  # | #  # | #  # | #  # | #
# | #  # | #  # | #  #/  #  #  \#  #  \#  #/  #
#####  #####  #####  #####  #####  #####  #####

Las pistas pueden combinarse con las estaciones, puentes y entrada / salida del valle de las siguientes maneras:

#####  #####  #####
#\|/#  #\|/#  #/  #
#-M-#  #-X-#  >-  #
#/|\#  #/|\#  #\  #
#####  #####  #####

Las estaciones tienen mesas giratorias, por lo que es permisible dejar una estación en un ángulo agudo (aunque no en la dirección en la que viniste, ¡no querrás chocar contra el próximo tren programado que viene en la otra dirección!).
Los puentes son para cruzar ríos, por lo que debe salir del puente en el lado opuesto del río en el que ingresó.

Entrada

La entrada será a través de STDIN para programas o un argumento de función para funciones. Si su función necesita un nombre para poder ejecutarlo en mi entrada, entonces esa declaración de nombre debe incluirse en el recuento de bytes.

La entrada será una sola cadena con saltos de línea. Cada línea dentro de su entrada siempre tendrá la misma longitud que las demás, lo que le dará una entrada rectangular. El borde de la entrada siempre será sólido e intransitable ( #) excepto el punto de entrada. Cualquier entrada dada tendrá al menos una respuesta válida.

Salida

Su salida debe devolverse como una sola cadena con saltos de línea desde una función, o imprimirse / repetirse en la pantalla para programas completos.

La salida debe ser la misma que la entrada pero con los caracteres de pista agregados.

Puntuación

El ganador será el código más corto en bytes.

Casos de prueba

###########
#    M    #
#   ^     #
>  ^^  M  #
#    ^    #
#~~~~~~~~~#
# M       #
#     ^^  #
#        M#
###########


#################
#               #
#   M         M #
#       ^       #
#        ^ M    #
#~~~~~~~^       #
#               #
#   ^           #
#   M^          #
#    ^          #
> ^^^          M#
#               #
#        M      #
#################

###############
# M   ~       #
#     ~       #
>     ~    M  #
#     ~       #
#     ~       #
#     ~       #
###############

Posibles soluciones para probar casos

###########
# ---M    #
#/  ^ \   #
>  ^^  M  #
#\   ^ |  #
#~X~~~~X~~#
# M     \ #
#  \  ^^ |#
#   -----M#
###########

#################
#               #
#   M---------M #
#   |   ^    /  #
#  /     ^ M-   #
#~X~~~~~^  |    #
# |         \   #
#  \^        \  #
# --M^        \ #
#/   ^         |#
> ^^^          M#
#\            / #
# -------M----  #
#################

###############
# M   ~       #
#/ \  ~       #
>   --X----M  #
#\    ~    |  #
# \   ~   /   #
#  ---X---    #
###############
Gareth
fuente
8
¡Finalmente! ¡Este desafío ha estado en el Sandbox para siempre!
mbomb007
18
@ mbomb007 No del todo, hubo 4 meses entre el inicio de este sitio y la publicación de la pregunta en el sandbox ;-)
Gareth
1
@Gareth, ¿pueden tener turnos? ¿Pueden ser más anchos que una celda?
Martin Ender
1
espera - ¿Qué pasa si necesitamos mover solo un espacio verticalmente mientras vamos horizontalmente?
SIGSTACKFAULT
1
Me duele la cabeza. He estado trabajando en esto y es muy difícil
Christopher

Respuestas:

26

Python 2 , 3990 3430 4412 4313 bytes

Esto es básicamente un A * con un getChildrenmétodo feo y heurístico feo . Para ejecutar los 3 casos de prueba de forma consecutiva toma 6.5smi máquina. La función fes la solución aquí. Toma el mapa como una cadena y devuelve el mapa resuelto como una cadena.

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]

Pruébalo en línea!

Casos de prueba

Prueba 1

ingrese la descripción de la imagen aquí

###########
# ---M    #
#/  ^ \   #
>  ^^  M  #
#\   ^ |  #
#~X~~~~X~~#
# M    |  #
#  \  ^^\ #
#   -----M#
###########

Prueba 2

ingrese la descripción de la imagen aquí

#################
#               #
#   M---------M #
#  /    ^    /  #
# |      ^ M-   #
#~X~~~~~^   \   #
# |          |  #
#  \^        |  #
# --M^       |  #
#/   ^-       \ #
> ^^^/ \       M#
#\  /   \     / #
# --     M----  #
#################

Prueba 3

ingrese la descripción de la imagen aquí

###############
# M   ~       #
#/ \  ~       #
>   --X----M  #
#\    ~   /   #
# ----X---    #
#     ~       #
###############

Código fuente

A * Estado + A * Clase de solucionador

De hecho, los saqué de mi solución. Pero existen en mi versión 'legible' . La clase de estado es genérica y está destinada a implementarse. La clase Solver toma un estado inicial y luego sigue los estados heurísticos 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

Clase de estado

Esta es la implementación de la clase de estado A *. El método más importante aquí es getDistla heurística para determinar qué tan cerca selfestá de la meta. Básicamente es la distancia mínima para visitar todos los destinos restantes y volver a comenzar.

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)

Clase de mapa

Esta clase almacena y procesa el mapa. El isConnectedmétodo es probablemente la pieza más importante. Prueba para ver si hay 2 piezas de pista conectadas.

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")

Actualizaciones

  • -560 [17-03-31] Un montón de golf regex básico
  • +982 [17-03-31] Se arregló el tendido ilegal de pistas. Gracias @ fəˈnɛtɪk !
  • -99 [17-03-31] Utilizado ;s
Fruta no lineal
fuente
Cambiar algunos nombres de variables para moar golf;)
Matthew Roh
66
Deberías poder jugar más al golf usando una combinación de espacios y pestañas para sangrar
John Dvorak
2
Las dos líneas que comienzan con elif e!=""and e in"MX>"podrían combinarse en una sola línea con un ternario if else. Además, algunos de sus defs podrían ser lambdas. Me gusta def A(s):return str(s)puede ser A=lambda s:str(s), o si cambia de __str__a __repr__, puede usar A=lambda s:`s`, en ese punto, ni siquiera vale la pena tenerlo Acomo su propia función, ya que requiere paréntesis para llamar. Solo usa backticks en su lugar.
mbomb007
El código intenta movimientos ilegales cuando construye puentes. No puedo decir con certeza que este es un problema porque termina los casos de prueba con rutas válidas.
fəˈnɛtɪk
¡Qué! No tenía idea de que esto se hizo. Estaba tratando de hacer esto y nunca terminé, ¡pero buen trabajo!
Christopher