Browsed by
תגית: python

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.

Character Encoding

Character Encoding

מכירים את זה ש-?????? ואז äîùáø?

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

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

מה זה קידוד

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

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

ASCII

עד תחילת שנות השישים לא היה אף סטנדרט אחיד לקידוד תוים. עד כדי כך, שלעיתים על אותו מחשב רצו מספר תוכנות שכל אחת התייחסה לתווים בצורה שונה – התוכנות לא יכלו לתקשר ביניהן. בשנת 1963 הוסכם על קידוד אחיד: ASCII, שזה: American Standard Code for Information Interchange.

קידוד ASCII מכיל 128 תווים (27). הנה חלק מהטבלה:

  • (במקומות #0-31 – תווי בקרה שכבר לא בשימוש).
  • #32 – תו ריק (רווח).
  • #48-57 – ספרות.
  • #65-90 – אותיות גדולות (A, B, C..).
  • #97-122 – אותיות קטנות (a, b, c..).

החסרון של ASCII שהוא… אמריקאי. הוא עונה על הצרכים של דוברי אנגלית, אבל הוא מוגבל רק ל- 128 תווים – אין לו מקום לתווים בעברית, סינית או פולינזית. בזמן שהוא יצא הוא עשה מהפכה בעולם המחשוב, ולראשונה היתה שפה אחידה שתוכנות יכלו ״לדבר״ ביניהן, אבל היום זה לא ממש מספיק.

ISO-8859

הפיתרון לבעיות של ה- ASCII, היה להוסיף ביט אחד.

[הסבר קצר: המחשב מתרגם כל מספר לבינארי – בסיס 2. כל ספרה נוספת בה משתמשים מצויינת בביט. 8 ביטים = בייט.

הערכים של ASCII הם בין 0 ל- 127, שזה בבינארית 1111111. אם נוסיף ביט, כלומר נשתמש בבייט שלם – נוכל להכפיל את טווח הערכים. 11111111 יהיה הערך המקסימלי – 255.]

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

מי שאחראי על התקינה הוא ISO, שזה International Organization for Standardization. זהו גוף שיוצר תקנים עבור כל דבר – ממידות נעליים, רמזורים ועד לכוסות לטעימת יין. התקן לקידוד לשפות שונות נקרא ISO-8859 באופן כללי, עם מספר נוסף שמציין את השפה הספציפית. ISO-8859-8 הוא התקן לקידוד התווים בעברית.

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

החסרונות של ISO-8859-x:

  • לא ניתן להשתמש באותו מסמך ביותר מקידוד אחד. כל מסמך יתורגם בצורה אחידה לפי קידוד ספציפי. ניתן לכתוב באנגלית + שפה נוספת וזהו.
  • התוכנה צריכה לדעת מראש במה הטקסט מקודד – האם מדובר בלטינית (ISO-8859-1), או ביוונית (ISO-8859-7). ניתן לבצע זיהוי אוטומטי, שמנסה לפענח חלק מהתווים לפי קידוד אחד ובודק אם זה יוצר רצף הגיוני, אבל זה לא תמיד עובד.

תווי כל העולם התאחדו

בגלל הבעיות הנ״ל, בסוף שנות ה- 80 הגיעו למסקנה שחייבים קידוד אחד עבור כל התווים, וכך נולד ה- Unicode.

ה- 256 תווים ראשונים זהים לקידוד ISO-8859-1, מה שאומר 128 תווי ASCII, ו- 128 תווי לטינית.

אחריהם יש… הכל. unicode מכיל כל תו קיים: עברית, יוונית או הירוגליפים מצריים – טבלה ענקית בה ממופים כל התווים. את הטבלה הזו מחלקים למישורים – planes, כל מישור מכיל 65536 תווים (216). במישור הראשון יש את התווים הנפוצים ביותר (הוא נקרא BMP – Basic Multilingual Plane) ואחריו 16 מישורים נוספים. בחשבון פשוט, קידוד unicode יכול להכיל 1,114,112 תווים (17 כפול 216).

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

UTF-8 בא לפתור את הבעיה הזו, Unicode Transformation Format – זהו קידוד מבוסס Unicode. הוא בנוי כך שלפי מספר ביטים בתחילת כל תו ניתן לדעת כמה בייטים לקרוא עבורו. לדוגמא לתווי ה- ASCII שנמצאים בהתחלה (128 הראשונים) – והם גם השימושיים ביותר – נוכל להשתמש בבייט אחד, בצורה הזו: 0xxxxxxx. ככל שמתקדמים בטבלה נצטרך לכל תו יותר בייטים. כאן יש הסבר על איך זה בנוי.

כיום UTF-8 פופולארי ברוב אתרי האינטרנט, ובמערכות הפעלה מבוססות Unix. הוא מאפשר קידוד אחד לכל התווים, בצורה יעילה, והוא מאפשר תאימות אחורה – כל עוד המסמך מכיל רק תווי ASCII הם ייראו אותו דבר.

קוד

כדי לפתור את בעיית פתיחת מסמכים שנשמרו ב- Windows בסביבת Unix – נשתמש בקוד הבא (python):

#!/usr/bin/python
 
import codecs, sys
 
if len(sys.argv) &gt; 1:
    path = sys.argv[1]
else:
    print "arg not found. Run encode.py "
    sys.exit()
# open with Windows format
sourceFile = codecs.open(path, "r", "iso-8859-8")
# save decoded content
contents = sourceFile.read()
# close file so we can re-open it for writing
sourceFile.close()
# open with utf-8 format
targetFile = codecs.open(path, "w", "utf-8")
targetFile.write(contents)
targetFile.close()

זו המקבילה בקוד לפתרון של פתח-בפנקס-רשימות-ושמור-בפורמט-אחר. נפתח את הקובץ כשאנחנו מתייחסים אליו כפורמט iso-8859. נשמור את התוכן, ואז נפתח אותו מחדש בפורמט utf-8 ונכתוב לתוכו את התוכן.

בנוסף, ספריית python שימושית: Chardet. כשמה, היא מזהה את הקידוד בו נכתב הקובץ. בקטע קוד הנ״ל אני מניח שהקידוד של הקובץ הוא ISO-8859-8 (כי זה ידוע לי), אבל אפשר להשתמש ב- Chardet כדי לזהות אוטומטית את הקידוד, וכך הקוד יעבוד גם על עוד קידודים (=שפות).

סיכום

ישנם 3 קידודים בהם ייתכן וניתקל: ASCII, ISO-8859-x, UTF-8. ההבדלים ביניהם יצוצו רק כאשר נשתמש בתווים שהם לא אנגלית/מספרים.

נראה שבעתיד כולם יעברו להשתמש ב- Unicode. גם אם UTF-8 לא נתמך רשמית ב- Windows ברמת מערכת ההפעלה, לא מעט תוכנות כבר משתמשות בו כברירת מחדל.

עד אז, äîùáø.

חידת הרכבת

חידת הרכבת

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

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.