Keskustelu: Koodit: Lyhyimmän reitin laskenta (Python)

#!/usr/bin/python
# -*- coding: UTF-8 -*-

# routefuncs.py - reitin laskemisen funktiot

import random

# Palauttaa yhden pisteen perustella sen viereiset pisteet joihin VOIDAAN liikkua
def karsilahimmat(p, maplist, loppu, vapaat, vinottain=1, valmiit=[]):

	if vinottain: # Pisteen kaikki viereiset pisteet
		plist = [(p[0]+1,p[1]),(p[0],p[1]+1),(p[0]+1,p[1]+1),(p[0]-1,p[1]),(p[0],p[1]-1),(p[0]-1,p[1]-1),(p[0]+1,p[1]-1),(p[0]-1,p[1]+1)]
	else: # Pisteen kaikki viereiset pisteet(ei vinosuuntiin)
		plist = [(p[0]+1,p[1]),(p[0],p[1]+1),(p[0]-1,p[1]),(p[0],p[1]-1)]

	nplist = [] # Uusi lista johon lisätään vain kelvolliset pisteet
	y_len = len(maplist)+1 # y:n arvon on AINA oltava pienempi kuin tämä

	for p in plist:
		if p[1] > 0 and p[1] < y_len: # Pitää olla positiivinen luku ja ei saa ylittää karttaa( Y KOORDINAATTI )

			# Pitää olla positiivinen ja ei saa ylittää karttaa(X KOORDINAATTI)
			if p[0] > 0 and p[0] < len(maplist[p[1]-1])+1:

				# Pistettä vastaavan merkin pitää olla kulkukelpoista aluetta
				if p2merkki(p,maplist) in vapaat:
					# Varmistetaan ettei merkata jo merkattuja!
					if p not in valmiit:
						nplist.append(p)

		if p == loppu: nplist.append(p) # Jos piste on päätepiste niin lisätään se varmasti

	return nplist

def p2merkki(p, maplist): # maplist on normaali lista(nmap, jossa ei ole välejä)
	return maplist[p[1]-1][p[0]-1] # Palautetaan kartalta pisteen koordinaatteja vastaavan merkin

def isvino(p1,p2): # Voit käyttää VAIN vierekkäisten pisteiden tapauksessa
	if p1[0] != p2[0] and p1[1] != p2[1]: return 1
	else: return 0

def getstart(maplist,aloitus): # Hakee kartasta aloituspisteen koordinaatit
	o = 0
	for f in maplist:
		if aloitus in f:
			return (f.rfind(aloitus)+1,o+1)
		o += 1
	return -1

def getend(maplist,lopetus): # Hakee kartasta lopetuspisteen koordinaatit
	o = 0
	for f in maplist:
		if lopetus in f:
			return (f.rfind(lopetus)+1,o+1)
		o += 1
	return -1

# Tästä alkaa reitin etsintä!

def lyhyin(kartta,map_aloitus,map_lopetus,vapaat,esteet,vinottain=1):


	# Kartassa ei ole aloitusta tai lopetusta
	if map_aloitus not in ''.join(kartta) or map_lopetus not in ''.join(kartta): return -2
	arvot = {} # Sanakirjaan tulee pisteitä vastaavat arvot
	loppupiste = getend(kartta,map_lopetus)# Haetaan loppupisteen koordinaatit
	# Haetaan alkupisteestä seuraavat mahdolliset reitin jatkopisteet
	edelliset = karsilahimmat(getstart(kartta,map_aloitus),kartta,loppupiste,vapaat,vinottain)

	i = 1
	for p in edelliset: arvot[p] = i # Merkataan niille kaikille arvoksi 1
	if getend(kartta,map_lopetus) in arvot:	return [loppupiste]

	# Lisätään pisteitä ja niiden arvoja sanakirjaan niin kauan kunnes on loppupiste löydetään
	while loppupiste not in arvot:

		i += 1
		uudet = []
		# Käydään viimekerralla löydetyt pisteet läpi ja etsitään jokaiselle niille uudet jatkopisteet
		for p in edelliset:
			for u in karsilahimmat(p,kartta,loppupiste,vapaat,vinottain,arvot.keys()+uudet):
				uudet.append(u)

		if uudet == []: return -1 # Reitti ei ole mahdollinen

		edelliset = uudet[:] # Kopioidaan ne edellisiin, jotta ne jää talteen
		for p in uudet: arvot[p] = i # Merkataan taas uusille pisteille niiden arvot

	reitti = []
	done = 0
	i = 0

	while not done: # Sitten jatketaan pienimpien arvojen etsimistä

		i += 1

		if i != 1: viim_piste = reitti[-1]
		else: viim_piste = loppupiste

		# Karsitaan taas viimeisimmän pisteen perusteella kulkukelpoiset pisteet
		mahd_pisteet = karsilahimmat(viim_piste,kartta,loppupiste,vapaat,vinottain)

		# Selvitetään, mikä on pienin arvo
		pieninarvo = 0
		for p in mahd_pisteet:# Muodostetaan lista pisteitä vastaavista ARVOISTA
			if pieninarvo == 0:
				if p in arvot: pieninarvo = arvot[p]
			else:
				if p in arvot:
					if arvot[p] < pieninarvo: pieninarvo = arvot[p]

		if not vinottain:
			for piste,arvo in arvot.items():
				# Etsitään taas pieniarvoisin piste, jonka täytyy myös olla mahd_pisteet-listassa
				if arvo == pieninarvo and piste in mahd_pisteet:
					reitti.append(piste) # Lisätään se reittiin
					if arvo == 1: # Jos olemme jo yhden päässä aloituspisteestä, lopetetaan.
						done = 1
					break
		else:
			suora = 0
			kelvolliset = []

			for piste,arvo in arvot.items():
				# Jos sanakirjasta löydettiin arvo joka vastaa pienintä
				if arvo == pieninarvo and piste in mahd_pisteet:
					# Lisätään lahimmat listaan piste joka on kelvollinen seuraava askel
					kelvolliset.append(piste)
					if arvo == 1: # Reitti on valmis!
						done = 1

					# Suositaan pisteitä, joihin ei tarvitse liikkua vinottain
					if not isvino(viim_piste,piste):
						reitti.append(piste) # Lisätään piste reittilistaan
						suora = 1 # Löydettiin suorakin siirtymä, joten ei arvota vinottaista
						break

			if not suora: # Jos ei löydetty suoraa siirtymää, niin arvotaan seuraava askel
				reitti.append(random.choice(kelvolliset)) # Erotetaan reitin pisteet x:llä
	return reitti

#!/usr/bin/python
# -*- coding: UTF-8 -*-

# route.py - lyhyimmän reitin laskija

import sys
from routefuncs import *

if len(sys.argv) == 2: # Tiedosto annettiin parametrinä
	map_tiedosto = sys.argv[1]
else:
	map_tiedosto = 'kartta.txt' # Tiedosto, josta luetaan kartta

map_aloitus = 'S' # Karttan merkitty päätepiste
map_lopetus = 'F' # Karttaan merkitty aloituspiste
nmap_vapaat = ['0'] # Kartassa olevat liikkumakelpoiset merkit
nmap_esteet = ['1'] # Kartassa olevat esteet

emap_este = '#' # Kun kartta tulostetaan niin kaikki esteet merkataan selvyyden vuoksi tällä merkillä

# Merkkaa kartan reunat siististi
def reunusta(teksti,u='|',d='-'):
	ulist = [' '*len(u)+d*len(teksti[0])]
	i = 0
	k = 0
	for x in teksti:
		if i == len(teksti)-1:
			ulist.append(u+x+u)

		elif len(x) < len(teksti[i+1]):
			pituus = len(teksti[i+1])-len(x)
			if pituus < 0: pituus *= -1
			ulist.append(u+x+' '+(d*(pituus-1)))

		elif len(x) > len(teksti[i+1]):
			ulist.append(u+x+u)
			pituus = len(x)-len(teksti[i+1])
			if pituus < 0: pituus *= -1
			print pituus
			k = 1
		elif k==1:
			k = 0
			ulist.append(u+teksti[i]+' '+(d*(pituus-1)))
		else:
			ulist.append(u+x+u)
		i += 1

	return ulist+[' '*len(u)+d*len(teksti[-1])]

def map2vmap(nmap): # Muuttaa kartan jossa ei ole joka toinen kirjain väli, sellaiseksi jossa joka toinen on väli(kartta.txt)
	vmap = []
	for f in nmap:
		line = ''
		for k in f:
			line = line+' '+k
		vmap.append(line[1:])
	return vmap

def vmap2map(vmap): # Poistetaan kartasta välilyöntimerkit
	nmap = []
	for f in vmap:
		nmap.append(f[::2]) # Joka toinen kirjain
	return nmap

def nmap2emap(nmap): # Muutetaan normaalimuotoinen kartta sellaiseksi jonka voi tulostaa
	emap = []
	for f in nmap:
		line = ''
		for k in f:
			if k in nmap_esteet: k = emap_este
			line = line+k
		emap.append(line)
	return emap

def muutapiste(p,merkki,maplist): # Palauttaa uuden maplistin jossa on pisteen kohdalle sijoitettu uusi merkki
	line = maplist[p[1]-1] # Kaivetaan kartasta oikea rivi
	maplist[p[1]-1] = line[0:p[0]-1]+merkki+line[p[0]:] # Muutetaan riviä niin, että korvataan koordinaattia vastaava kirjain halutuksi
	return maplist

def luemap(tiedosto):
	f = open(tiedosto,'r')
	textmap = []
	for line in f.readlines():
		if line[-1] == '\n': textmap.append(line[0:-1])
		else: textmap.append(line)
	return textmap



maplist = nmap2emap(vmap2map(luemap(map_tiedosto))) # Luetaan kartta maplist listaan niin että siinä ei ole välejä
if map_aloitus not in ''.join(maplist):
	print 'Kartassa ei ole aloituspistettä!'
	sys.exit()
if map_lopetus not in ''.join(maplist):
	print 'Kartassa ei ole lopetuspistettä!'
	sys.exit()

# Tulostetaan ratkaisematon kartta
print '\nRATKAISEMATON'
for f in reunusta(map2vmap(maplist)): print f.replace(nmap_vapaat[0],' ')

reitti = lyhyin(maplist,map_aloitus,map_lopetus,nmap_vapaat,nmap_esteet,1)
if reitti == -1:
	print 'Reittiä ei ole mahdollista muodostaa'
	sys.exit()

if len(reitti) > 1:
	for piste in reitti: # Käydään reitin pisteet läpi
		maplist = muutapiste(piste,'+',maplist) # Käytetään muutapiste funktiota muuttamaan kartassa reitin pisteet +:ksi

# Tulostetaan ratkaistu kartta
print '\nRATKAISTU'
for f in reunusta(map2vmap(maplist)): print f.replace(nmap_vapaat[0],' ')