מספרים תיאוריים

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

נתונה סדרת מספרים, שהמספר הראשון בה הוא 1, והחל ממנו כל מספר הוא “תיאור” מספרי של המספר הקודם לו.

הסדרה מתחילה כך –

1, 11, 21, 1211, 111221

המספר הראשון הוא 1

המספר השני הוא תיאור של הראשון -פעם אחת 1 (11)

המספר השלישי הוא תיאור של השני –  פעמיים 1 (21)

המספר הרביעי הוא תיאור של השלישי – פעם אחת 2 פעם אחת 1 (1211)

וכן הלאה…

המשימה – בהינתן n להחזיר את המספר ה-n-י הסדרה.

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

המספר החמישי מתאר את הרביעי – פעם אחת 1, פעם אחת 2, פעמיים 1 (111221)

המספר השישי יהיה – שלוש פעמים 1, פעמיים 2, פעם אחת 1 (312211)

המספר השביעי יהיה – פעם אחת 3 פעם אחת 1 פעמיים 2 פעמיים 1 (13112221)

אוקי, אני אתחיל מלנסות למצוא פתרון נאיבי.

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

אני אכתוב את האלגוריתם הנאיבי הזה.

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

איך אני יוצרת תיאור של מספר? אני רצה עליו משמאל לימין, סופרת את אורך הרצף של ספרה יחידה, ואז רושמת בתוצאה את אורך הרצף ואת הספרה.

def get_number_description(num):
    res = ""
    current_count = 1
    current_digit = num[0]
    for i in range(1, len(num)):
        if num[i] == current_digit:
            current_count += 1
        else:
            res = res + str(current_count) + current_digit
            current_digit = num[i]
            current_count = 1
    return int(res)

אבדוק שהפונקציה שלי עובדת על אחת הדוגמאות למעלה –

num=111221
res=””
current_count=1
current_digit=1
i=1
num[1] = 1
current_count=2
i=2
num[2]=1
current_count=3
i=3
num[3]=2
res=31
current_digit=2
current_count=1
i=4
num[4]=2
current_count=2
i=5
num[5]=1
res=3122
current_digit=1
current_count=1
return 3122

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

אני אוסיף שורה אחרי היציאה מהלולאה שמוסיפה את הרצף האחרון לתוצאה.

def get_number_description(num):
    res = ""
    current_count = 1
    current_digit = num[0]
    for i in range(1, len(num)):
        if num[i] == current_digit:
            current_count += 1
        else:
            res = res + str(current_count) + current_digit
            current_digit = num[i]
            current_count = 1
    res = res + str(current_count) + current_digit
    return int(res)

אחלה, יש לי פונקציה שמחזיר את הערך ה-n בהינתן הערך ה-n-1.

עכשיו רק ארשום לולאה פשוטה שמביאה תמיד את הערך הבא-

def get_nth_descriptive(n):
    if n == 1:
        return 1
    else:
        i = 1
        current_number = 1
        while i < n:
            current_number = get_number_description(str(current_number))
            i += 1
        return current_number

נבדוק את הפונקציה.

n=2
i=1 (i<2)
current_number=1
current_number=11
i=2
return 11

מעולה!

יש לי פתרון נאיבי.

מה הסיבוכיות של הפתרון?

ובכן, הלולאה החיצונית רצה n פעמים והלולאה בפונקציה get_number_decription רצה k פעמים בעבור מספר באורך k.

הסיבוכיות של הפתרון היא O(n*k). זה אולי נשמע כמו פתרון סביר ולינארי, אבל חשוב לשים לב ש-k הולך וגדל ממש מהר, ובקלות עוקף את n. כבר בעבור  n=10 מתקיים k=20. אז זו איננה סיבוכיות טובה.

האם אני יכולה לשפר את הפתרון הזה?

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

1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221, 13211311123113112211

אררג, המספרים נהיים גדולים מדי, מהר מדי, והדוגמאות נהיות יותר מדי עבודה.

אולי אני אנסה להסתכל רק על החלק הראשון של כל מספר מעכשיו –

1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221, 132131112..., 11131211133112…, 311311123123...., 132113311213....,111312212321121113..., 31131122111213...

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

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

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

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

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

אבוי, החיים קשים, הפתרון הנאיבי שלי הוא הפתרון המלא של השאלה באתר.

אז אפשר לסכם שיש לי פתרון מלא בסיבוכיות של O(n*k) כאשר k הוא האורך של הספרה ה-n-ית. ואני נשארת לתהות האם הייתי אמורה להבין לבד שזו הסיבוכיות הכי טובה שאפשר להגיע אליה.

קוד בגיט – https://github.com/mgershovitz/maya_solves/blob/master/descriptive_numbers.py