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

אבל אז במחשבה שניה נראה לי שלהבין ולדעת להיכנס לראש שלהם זה אולי לא כזה רע (גם אם לא יצירתי במיוחד) כמו שתראו בדוגמא הבאה.

1. השאלה: טיפוס מדרגות

אז השאלה שהתחלתי איתה סיפרה על בית עם גרם מדרגות פנימי וילד שאוהב מאוד לטפס עליהן. הילד יכול לבחור לטפס מדרגה-מדרגה, או לדלג שתי מדרגות או לדלג שלוש מדרגות. אם הילד בוחר כל יום לטפס בדרך אחרת, תוך כמה ימים הוא יצטרך לעבור דירה? (כי לא יישארו לו עוד דרכים חדשות לטפס).

אם לדוגמא יש בבית 3 מדרגות אז האפשרויות של הילד די מוגבלות:

1. הוא יכול לטפס את כל שלושת המדרגות בצעד אחד.
2. הוא יכול לטפס את שתי המדרגות הראשונות בצעד אחד, ואז עוד צעד למדרגה האחרונה.
3. הוא יכול לטפס את המדרגה הראשונה בצעד אחד, ואז את השתיים הנותרות בצעד הבא.
4. הוא יכול לטפס צעד-צעד את כל המדרגות ולעלות את שלושת המדרגות ב-3 צעדים.

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

2. פתרון למקרה הכללי בשפת Python

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

כיוון אחר שלי היה יותר אינטואיטיבי היה פיתרון רקורסיבי:

1. נסה לטפס מדרגה אחת.
2. נסה לטפס שתי מדרגות.
3. נסה לטפס שלוש מדרגות.

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

בדוגמא של שלוש המדרגות זה יראה בערך כך:

1. אם טיפסתי את כל שלושת המדרגות יחד הגעתי. נשארו 0 מדרגות לטפס. לכן ניתן לאפשרות זו את הערך 1.
2. אם טיפסתי שתי מדרגות נשארה מדרגה אחת בלבד: א. אני יכול לטפס מדרגה אחת נוספת ולהגיע (עוד 1). ב. אני יכול לטפס 2 או 3 מדרגות, אבל אז אגיע רחוק מדי לכן אפשר להתעלם מאפשרויות אלו.
3. אם טיפסתי מדרגה אחת נשארו שתי מדרגות לטפס: א. אני יכול לטפס עוד 2 מדרגות ולהגיע (עוד 1). ב. אני יכול לטפס עוד 3 מדרגות, אבל אז הגעתי רחוק מדי (להתעלם). ג. אני יכול לטפס עוד מדרגה אחת. עדיין לא הגעתי לסוף אז מנסים שוב:
   • אני יכול לטפס עוד מדרגה אחת (הגעתי! עוד 1)
   • אני יכול לטפס 2 או 3 מדרגות אבל אז הגעתי רחוק מדי ולכן נתעלם.

סך הכל כשנסכום את כל האפשרויות נגיע ל-4, שזה גם מה שיצא בחישוב ידני. את התהליך קל לקודד בפייתון באמצעות רקורסיה. הפונקציה ways מחזירה את מספר האפשרויות לטפס גרם מדרגות בגובה h:

def ways(h):
    if h < 0: return 0
    if h == 0: return 1

    return ways(h-1) + ways(h-2) + ways(h-3)

print(ways(3))

והתוצאה כצפוי 4, וגם לקלטים אחרים התוצאה נשארת מדויקת.

3. אבל זה לא היה מספיק טוב בשביל האקרראנק

וכנראה אם תגיעו לראיון עבודה זה גם לא יהיה מספיק טוב למראיין שלכם. הסיבה? ננסה את החישוב על 30 מדרגות:

$ time python3 stairs.py 30
53798080

real    0m33.208s
user    0m32.673s
sys 0m0.222s

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

הסיבה לאיטיות היא טיפוסית לפתרונות רקורסיביים מסוג זה. הוספתי הדפסה בכניסה לפונקציה ונראה מה נקבל כשננסה למצוא את מספר האפשרויות ל-4 מדרגות:

$ python3 stairs.py 4
Calculating ways(4)
Calculating ways(3)
Calculating ways(2)
Calculating ways(1)
Calculating ways(0)
Calculating ways(-1)
Calculating ways(-2)
Calculating ways(0)
Calculating ways(-1)
Calculating ways(1)
Calculating ways(0)
Calculating ways(-1)
Calculating ways(-2)
Calculating ways(0)
Calculating ways(2)
Calculating ways(1)
Calculating ways(0)
Calculating ways(-1)
Calculating ways(-2)
Calculating ways(0)
Calculating ways(-1)
Calculating ways(1)
Calculating ways(0)
Calculating ways(-1)
Calculating ways(-2)
7

יש כאן המון חישובים כפולים. בשביל לחשב את ערך הפונקציה עבור 4 יש לחשב את ערך הפונקציה עבור 3, 2 ו-1. אבל בשביל לחשב את ערך הפונקציה עבור 3 צריך לחשב אותה עבור 2, 1 ו-0, ולכן חישוב הערך עבור 2 מבוצע פעמיים.

ככל שהקלט גדול יותר כך יהיו יותר חישובים כפולים והשפעתם על הביצועים תהיה מורגשת יותר.

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

דרך קלה לעשות זאת היא להוסיף dictionary באופן הבא:

import sys

mem = { -2: 0, -1: 0, 0: 1 }

def ways(h):
    try:
        return mem[h]

    except KeyError:
        mem[h] = ways(h-1) + ways(h-2) + ways(h-3)
        return mem[h]

print(ways(int(sys.argv[1])))

התוצאה עכשיו הרבה יותר טובה:

$ time python3 stairs.py 30
53798080

real    0m0.053s
user    0m0.036s
sys 0m0.011s

שיפור דרמטי בזמן הריצה מחצי דקה להרבה פחות משניה.

ואגב לפייתון 3 יש כבר מנגנון מובנה בשפה של מילון שמחובר לפונקציה וזוכר תוצאות ישנות. זה נקרא lru ונראה כך:

import sys
from functools import lru_cache

@lru_cache(maxsize=None)
def ways(n):
    if n < 0:  return 0
    if n == 0: return 1
    return ways(n-1) + ways(n-2) + ways(n-3)

print(ways(int(sys.argv[1])))

הפעם כל מה שהיה צריך זה להוסיף שתי שורות לקוד המקורי: האחת שורת import והשניה הפעלת ה Decorator על הפונקציה. כל הקסם של המילון נמצא בתוך ה Decorator.

4. מסקנות ומחשבות להמשך

שאלות מסוג זה בודקות אינטואיציה ויכולת כתיבת קוד מאוד מסוימת. הרבה אנשים לא אוהבים את זה ועוד יותר לא אוהבים ששאלות כאלה נשאלות בראיונות עבודה טכניים (ועוד יותר מכך לא אוהבים לענות עליהן על לוח במקום על מחשב).

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

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