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

https://www.hackerrank.com/challenges/new-year-chaos/problem

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

לדוגמא אם אנחנו מתחילים עם הרשימה:

[2, 1, 5, 3, 4]

נצטרך לפחות 3 פעולות החלפה כדי למיין אותה:

1. קודם נחליף את ה-1 וה-2

2. אחרי זה נחליף את ה-3 וה-5

3. אחרי זה נחליף את ה-4 וה-5 (ליד ה-4 היה פעם 3, אבל אחרי ההחלפה הקודמת יש שם עכשיו 5).

ובשביל לסבך קצת את החיים יש גם תוספת קטנה - כל פעם שמחליפים שני מספרים אנחנו רושמים את המספר השמאלי ביניהם בצד ברשימת ה"עוקפים" (כי בשביל להגיע למצב המבולגן הוא היה צריך לעקוף את המספר שמימינו). אם אחד המספרים "עקף" יותר מפעמיים עלינו להפסיק ולהדפיס את הפלט "Too chaotic".

1. פיתרון ראשון - מיון בועות

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

def minimumBribes_slow(start):
    keepgoing = True

    swaps = defaultdict(int)

    while keepgoing:
        keepgoing = False
        for i in range(len(start)-1):
            if start[i] > start[i+1]:
                swaps[start[i]] += 1
                if swaps[start[i]] > 2:
                    print("Too chaotic")
                    return

                tmp = start[i]
                start[i] = start[i+1]
                start[i+1] = tmp
                keepgoing = True

    print(sum(swaps.values()))

בתור בונוס אפשר גם להדפיס את רשימת המספרים וכמה פעמים החלפנו כל אחד מהם מתוך המשתנה swaps.

2. שיפור ביצועים

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

אז אם יש לנו את המערך:

[2, 1, 5, 3, 4]

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

הנה עוד אחד, קחו את המערך:

[1, 2, 5, 3, 7, 8, 6, 4]

ובואו נשאל כמה מספרים עקפו את 4? אז 4 היה צריך להתחיל באינדקס 3 אבל מצאנו אותו באינדקס 7. בין אינדקס 2 ל-7 אנחנו מוצאים את 5, 6, 7 ו-8 הגדולים מ-4 ולכן את 4 היו צריכים לעקוף 4 מספרים. נמשיך את הבדיקה לכל אחד מהמספרים במערך ונסכום את התוצאות וכך נגיע לפיתרון.

בקוד פייתון זה נראה ככה:

def minimumBribes(Q):
    moves = 0 
    Q = [P-1 for P in Q]

    for i,P in enumerate(Q):
        if P - i > 2:
            print("Too chaotic")
            return

        for j in range(max(P-1,0),i):
            if Q[j] > P:
                moves += 1
    print(moves)

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