Browsed by
חודש: אוגוסט 2016

חידת הרכבת

חידת הרכבת

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

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.

יצירת אפליקציית דסקטופ ב- Node.js

יצירת אפליקציית דסקטופ ב- Node.js

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

אבל עדיין יש צורך באפליקציות כאלו. אני רוצה להראות איך אפשר להשתמש ב- Node.js כדי לכתוב אפליקציה בצורה פשוטה – ושתהיה cross platform.

analyze

Read More Read More

בדיקת completionBlocks עם OCMock

בדיקת completionBlocks עם OCMock

יש לנו מתודה ב- Objective C שנראית כך:

- (void)getFileFromServer:(NSString*)url {
    if ([[URLValidator sharedInstance] isValidUrl:url]) {
        [[ServerConnection sharedInstance] getFromUrl:url withTimeout:12.f onCompletion:^(NSData* data) {
            if (data) {
                [[FilesManager sharedApplication] saveFile:data];
            } else {
                NSLog(@"ERROR. Failed to get file.");
            }
        }];
    }
}

קוד פשוט – המתודה מקבלת url, שולחת לבדיקה שזו כתובת תקינה באובייקט URLVAlidator, ואז עם האובייקט ServerConnection הקובץ מתקבל, ונשמר ב- FilesManager.

עד כאן הכל טוב.

השאלה היא איך כותבים לזה טסט. ליצור mock עבור כל אחד מהאובייקטים (במידת הצורך) זה פשוט. partialMock וכו׳. הבעיה זה לבדוק את ה- completionBlock.

הפתרון הוא להוסיף מייד אחרי הקריאה ל- expect, קריאה לביצוע NSInvocation – כלומר אנחנו מפעילים בעצמנו את הבלוק שהולך להגיע כפרמטר (חשוב לשים לב לאינדקס הנכון!). ואז מסיימים את הפקודה עם הפרמטרים של המתודה:

id serverConnection = [OCMockObject partialMockForObject:[ServerConnection sharedInstance]];
id filesManager = [OCMockObject partialMockForObject:[FilesManager sharedInstance]];
[[[serverConnection expect] andDo:^(NSInvocation *invocation) {
        void (^passedBlock)( BOOL );
        [invocation getArgument: &passedBlock atIndex: 4];
        NSData* data = [[NSData alloc] initWith:""];
        passedBlock(data);
    }]  getFromUrl:url withTimeout:12.f onCompletion:OCMOCK_ANY];
[[filesManager expect] saveFile: OCMOCK_ANY];
[filesManager verify];
[serverConnection verify];
 
[filesManager stopMocking];
[serverConnection stopMocking];