Python :: Aufgabe #113
3 Lösungen
Wie viele Manhattan-Wege sind bei einem 3 x 3 - Block möglich
Fortgeschrittener - Python
von hollst
- 28.06.2016 um 16:43 Uhr
Gegeben sei ein 3 x 3 - Int-Array, das mit Zahlen im Bereich von 1 ... 9 belegt werden kann, allerdings niemals mit zwei gleichen Zahlen (d. h. alle 1 ... 9 sind irgenwie verteilt und kommen jeweils genau einmal vor). Die Frage lautet: Mit welcher Wahrscheinlichkeit entsteht bei einer zufälligen Belegung des 3 x 3 - Int-Arrays ein Manhatten-Weg? Ein Manhatten-Weg ist folgendes: Beginnend mit dem Feld, das mit 1 belegt ist, muss das mit 2 belegte Feld mit einem einzigen horizontalen oder vertikalen Schritt erreichbar sein (Sprünge sind verboten). Das gilt auch für alle weiteren Schritte 2 -> 3 -> 4-> ... -> 9 bis zum mit 9 belegten Feld, Diagonalschritte sind gleichfalls nicht erlaubt. Im angehängten Bild sind beispielhaft eine Nicht-Manhatten-Weg-Belegung und vier Belegungen mit Manhatten-Weg dargestellt.
Lösungen:
Python-Code
import itertools
def manhattan_way_exists(arr, pos, next = 1):
if next == 9:
return True
else:
if pos % 3 < 2 and arr[pos+1] == next :
return manhattan_way_exists(arr, pos+1, next+1)
elif pos % 3 > 0 and arr[pos-1] == next :
return manhattan_way_exists(arr, pos-1, next+1)
elif pos < 6 and arr[pos+3] == next :
return manhattan_way_exists(arr, pos+3, next+1)
elif pos > 2 and arr[pos-3] == next :
return manhattan_way_exists(arr, pos-3, next+1)
else :
return False
def manhattan_way_prob() :
random_arrays = itertools.permutations(range(9), 9)
manhattan_way_count = 0
total_count = 0
for a in random_arrays:
total_count += 1
if manhattan_way_exists(a, a.index(0)):
manhattan_way_count += 1
return manhattan_way_count / total_count
print(manhattan_way_prob())
So richtig happy bin ich mit der Lösung nicht ;)
Python-Code
Python-Codeimport random
list = [ i+1 for i in range(9)]
def initialize_matrix():
matrix = []
rand = random.sample(list,9)
row = []
for index, elem in enumerate(rand):
row.append(elem)
if (index + 1) % 3 == 0:
matrix.append(row)
row = []
return matrix
def get_index(matrix, number):
for index, row in enumerate(matrix):
try:
return [index,row.index(number)]
except ValueError:
pass
def check_nachbarn(matrix,number):
[row,column] = get_index(matrix, number)
is_nachbar= False
for i in (-1, 1):
try:
if matrix[row+i][column] == number + 1 and row+i >=0 and row + i < 3:
is_nachbar = True
except IndexError:
pass
try:
if matrix[row][column+i] == number + 1 and column+i >= 0 and column+i < 3:
is_nachbar = True
except IndexError:
pass
return is_nachbar
def check_manhattan(matrix):
for number in range(1,8):
if not check_nachbarn(matrix, number):
return False
return True
def run(number_iterations):
erfolge = 0.0
for i in range(number_iterations):
matrix = initialize_matrix()
erfolge += 1 if check_manhattan(matrix) else 0
print('Die Wahrscheinlichkeit, dass eine Matrix mindestens 1 Manhatten Pfad besitzt ist '+ str(erfolge/number_iterations))
run(5000)
matrix = [[1,2,3],[6,5,4],[7,8,9]]
print(check_manhattan(matrix)) Python-Code
import random
startIndex=[]
def getArray():
zahlen= list(range(1,10))
a = [[1,2,3],[4,5,6],[7,8,9]]
for i in range(0,3):
for x in range(0,3):
rnd=random.choice(zahlen)
if rnd == 1:
startIndex.append(i)
startIndex.append(x)
a[i][x]=rnd
zahlen.remove(rnd)
return a
def printErg(b,e):
print("Mannhattan-Weg---------------------------Nach: "+str(e)+" Versuchen")
print(b[0])
print(b[1])
print(b[2])
print("\n")
#Start
for e in range(1,5000):
b=getArray()
index=startIndex
aktZahl=2 #Aktuelle Zahl bei der Index Suche
end=False #Schleifen Ende
steps=[[0,0],[1,0],[0,1],[-1,0],[0,-1]] #Mögliche Schritte die mal laufen kann
reihe=[]
while end==False:
try:
reihe= [0,b[0].index(aktZahl)]
except:
try:
reihe=[1,b[1].index(aktZahl)]
except:
reihe=[2,b[2].index(aktZahl)]
step=[index[0]-reihe[0],index[1]-reihe[1]]
if step not in steps:
end=True
else:
if aktZahl==9:
printErg(b,e)
end=True
aktZahl+=1
index=reihe
startIndex=[]