Browsed by
חודש: מאי 2017

Look and Say

Look and Say

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

באחת החידות מופיעה הסדרה הבאה:

a = [1, 11, 21, 1211, 111221

והחידה היא:

len(a[30]) = ?

המטרה היא כמובן למצוא את החוקיות של הסדרה, ואז למצוא את אורך האיבר ה- 30.

פתרון

הסדרה נקראת "Look and Say". בכל איבר בסדרה (מלבד הראשון) מקריאים (ורושמים) את מספר הספרות שמתארות את האיבר הקודם. כלומר, אם התחלנו ב- 1, אז האיבר שני יתאר פעם אחת 1 – 11. האיבר השלישי יתאר פעמיים 1 – 21. האיבר הרביעי יתאר פעם אחת 2 ופעם אחת 1 – 1211, וכן הלאה.

כל מה שנשאר זה למצוא את האיבר ה- 30. אפשר למצוא אותו ידנית, אבל זה ייקח הרבה זמן – סדרת "הבט ואמור" (או "סדרת קונווי" אם אתם מתעקשים) גדלה במהירות. חוץ מזה, בשביל זה יש python.

קוד

נתחיל מפתרון נאיבי:

first = '1'
second = ''
for i in range(0, 30):
    j = 0
    k = 0
    while j < len(first):
        while k < len(first) and first[k] == first[j]:
            k += 1
        second += str(k-j) + first[j]
        j = k
    print second
    first = second
    second = ''
print "Final answer:", len(first)

ההתייחסות לכל איבר בסדרה היא כ- string ולא כמספר. בכל איטרציה רצים על התוים משמאל לימין וסופרים את מספר הפעמים בהם תו מסויים מופיע ברצף.

ב- Python יש כלי שיכול לפשט משמעותית את הקוד הנ"ל. נשתמש בספריית re (המשמשת ל- regular expressions) כדי למצוא אורך של תו בכל הופעה שלו. לדוגמא:

re.findall("(\\d)(\\1*)", "111221")

נקבל כתשובה:

[('1', '11'), ('2', '2'), ('1', ")]

קיבלנו מערך של צמדים (tuples) – באיבר הראשון יש את התו של הרצף הנוכחי, ואחריו את שארית הרצף. אם נעבור על המערך ומכל צמד ניקח את אורך האיבר שני (פלוס 1) ונצמיד אותו לאיבר הראשון (שהוא התו הנוכחי של הרצף) נקבל את התוצאה הרצויה – האיבר הבא בסדרה. לדוגמא במערך הנ"ל: האורך של '11' + 1, עם התו '1' => 31. האורך של '2' + 1, עם התו '2' => 22. האורך של " + 1, עם התו '1' => 11. ולסיכום: 312211.

ובקוד:

"".join([str(len(i+j))+i for i,j in re.findall(r"(\d)(\1*)", 111221)])

זה נותן לנו את האפשרות להזין איבר ולקבל את האיבר הבא. עכשיו נעשה את זה עבור האיבר ה- 30:

import re
 
current = "1" #start from '1'
for n in range(30):
    current = "".join([str(len(j) + 1)+i for i, j in re.findall(r"(\d)(\1*)", current)])
 
print "Final answer:", len(current)

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