חידת הרכבת

חידת הרכבת

התפרסמה היום בגיקטיים כחלק מאתגר גדול יותר, החידה הבאה:

train

אפשר להסתכל על זה כבעיה בגרפים. ניצור מחלקה שמייצגת Node:

class Node:
    def __init__(self):
        self.paths = []

כל node מצביע על רשימת nodes אחרת – או על אף node במקרה של האחרון (וזה יהיה תנאי העצירה).

נאתחל שישה nodes שמצביעים אחד על השני, על פי המסלולים שמתוארים בציור:

a = Node()
b = Node()
c = Node()
d = Node()
e = Node()
f = Node()
 
a.paths = [b]
b.paths = [c, c, c, d]
c.paths = [d, e]
d.paths = [e, e, e]
e.paths = [f]

נעבור רקורסיבית על העץ-

def iterate (node):
    counter = 0
    if node.paths == []:
        return 1
    for p in node.paths:
        counter = counter + iterate(p)
    return counter

זו רקורסיית נסיגה, כלומר נגיע לסוף העץ – תנאי העצירה – ואז נחזור חזרה כל פעם צעד עד למסלול הבא, עד שנעבור על כל המסלולים האפשריים.

ways = iterate(a)
 
print "ways: " + str(ways)

לא אגלה את התוצאה, מוזמנים להריץ את הסקריפט 🙂

——————————–

עדכוןמההערות באתר, מסתבר שהחידה יותר מורכבת (ומעניינת). מסלול רכבת יכול להיות בשני הכיוונים – כל עוד לא עוברים על "קשת" פעמיים.

כדי לפתור את זה, נשנה גישה. נתאר את הגרף בעזרת מטריצה-

A B C D E F
A 1
B 1 3 1
C 3 1 1
D 1 1 3
E 1 3 1
F 1

ניצור מערך דו-מימדי עם הנתונים האלו:

a = [0, 1, 0, 0, 0, 0]
b = [1, 0, 3, 1, 0, 0]
c = [0, 3, 0, 1, 1, 0]
d = [0, 1, 1, 0, 3, 0]
e = [0, 0, 1, 3, 0, 1]
f = [0, 0, 0, 0, 1, 0]
 
mat = [a, b, c, d, e, f]

מכיוון שאנחנו רוצים את כל המסלולים האפשריים, לא מספיק לספור את הקשתות אלא צריך גם לתת להם זיהוי בפני עצמן. לדוגמא בין B ל- C יש 3 קשתות – מסלול אחד יכול להתחיל מקשת התחתונה ומסלול אחר מהעליונה.

לכן נתרגם את המטריצה הזו לתת רשימות:

def createLists(m):
    newMat = []
    for line in m:
        newLine = []
        for cell in line:
            newCell = []
            for i in range(cell):
                newCell.append(i)
            newLine.append(newCell)
        newMat.append(newLine)
    return newMat

בצורה כזו נתרגם כל מספר לרשימה, כלומר 0 יהיה [], ו- 3 יהיה [0, 1 ,2].

נפעיל על המטריצה את הפונקציה הזו:

def iterateMat(m, index):
    if index == 5:
        return 1
    counter = 0
    line = m[index]
    for i in range(len(line)):
        if len(line[i]) > 0:
            for cell in line[i]:
                #deep copying
                newMat = copy.deepcopy(m)
 
                newMat[index][i].remove(cell)
                newMat[i][index].remove(cell)
                counter += iterateMat(newMat, i)
 
    return counter

הרקורסיה זהה לזו שבפתרון המקורי. ההבדל הוא שבכל קריאה מחדש לפונקציה ניצור עותק של המטריצה, שבו נפחית את המסלול שבו ״צעדנו״. בצורה כזו נבטיח שלא נחזור על אותה קשת פעמיים באותו המסלול.

חשוב מאד לשים לב ליצור עותק בכל פעם, ולא לעבוד על אותה המטריצה, אחרת נאבד מסלולים. בשביל זה נשתמש בספריית copy.

mat = createLists([a, b, c, d, e, f])
ways = iterateMat(mat, 0)
 
print "ways: " + str(ways)

אגב, התשובה היא 640.

Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedIn

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *