אז אתמול היה יום מאוד מיוחד, זה היה יום עם תאריך פלינדרומי – 02.02.2020 (ותודה ללא מדויק שבזכותו שמתי לב.
ואיזו דרך טובה* יותר יש לחגוג יום פלינדרומי מאשר עם אלגוריתם שבודק אם מילה היא פלינדרום?
*אלא אם כן אתן אייבופוביות כמובן. אם כן, אני מתנצלת מראש, ואולי כדאי שתצאו מהפוסט עכשיו 🤷♀️
אוקי, אז איך אני בודקת אם מילה היא פלינדרום?
קודם כל – מהו פלינדרום?
פלינדרום הוא רצף תווים – מילה, מספר או משפט – שנקראים אותו הדבר משמאל לימין ומימין לשמאל.
קודם כל, חשוב לציין שבבדיקה של פלינדרומים אנחנו מתעלמות מסימני פיסוק, רווחים וכו’ אז אני אניח שהקלט שלי מגיע נקי.
מקריאה של ההגדרה יש כבר כמה רעיונות שקופצים לי לראש לבדיקה אם מילה היא פלינדרום, אני אבחר אחד מהם ואממש אותו.
האלגוריתם שאני רוצה לכתוב יתבסס על הרעיון שבעצם פלינדרום מורכב משני חצאים שהם מראה אחד של השני. כל התווים מימין לאמצע המילה וכל התווים משמאל לאמצע המילה זהים והפוכים זה לזה.
למשל בתאריך של אתמול – ה-02022020 יש 8 תווים.
משמאל לאמצע המילה יש את הרצף – 0202
מימין לאמצע המילה יש את הרצף 2020
כדי לנצל את תמונת המראה הזו, האלגוריתם שלי יאתחל שני אינדקסים – אחד לקצה המילה ואחד לתחילת המילה, ויקדם את שניהם עד שהם יפגשו באמצע. בכל שלב האלגוריתם ישווה בין התווים בכל זוג אינדקסים, אם הם שונים הוא יחזיר False. כשהאינדקסים יפגשו באמצע, סימן שכל התווים משני צידי האמצע נבדקו והם זהים, ולכן יש לי פלינדרום.
אני אכתוב את האלגוריתם הזה –
def is_palindrome(word):
i = 0
j = len(word) - 1
while i < j:
if word[i] != word[j]:
return False
i += 1
j -= 1
return True
קצרצר ונחמד.
טוב, כדי לבדוק את האלגוריתם שלי אני אריץ כמה דוגמאות!
בין מקרי הקצה שנראה לי שחשוב להריץ פה יהיו:
- מילה של אות אחת – כי הרי אות אחת נקראת אותו הדבר משני הצדדים ולכן היא פלינדרום.
- פלינדרום עם מספר זוגי של תווים.
- פלינדרום עם מספר אי זוגי של תווים.
- מילה שהיא לא פלינדרום.
word = “a”
is_palindrome(“a”):
i=0
j=0
i=j → skip loop
return True
אחלה!
word = “abba”
is_palindrome(“abba”)
i=0
j=3
word[0] == word[3] = “a”
i = 1
j = 2
word[1] == word[2] “b”
i=2
j=1
i > j → break loop
return True
הידד!
word = “bob”
is_palindrome(“bob”)
i=0
j=2
word[0] == word[2] = “b”
i = 1
j = 1
i = j → break loop
return True
ווהו!
word = “dog”
is_palindrome(“dog”)
i=0
j=2
word[0] != word[2]
return False
מהמם!
כל הדוגמאות שלי עברו, ואני מרגישה מאוד נוח עם האלגוריתם שלי.
עכשיו, הסיבה האמתית שרציתי לכתוב את האלגוריתם הזה, ולא אחד אחר פשוט יותר היא (איך לא?) שהאלגוריתם הזה יראה מצוין ברקורסיה!
אז הנה הגרסה הרקורסיבית של האלגוריתם שלי –
def is_palindrome_recur(word):
if len(word) <= 1:
return True
if word[0] != word[-1]:
return False
return is_palindrome_recur(word[1:-1])
def is_palindrome(word):
return is_palindrome_recur(word)
חמוד, נכון?
גם כאן תנאי העצירה שלי הוא כשהאינדקסים נפגשים, אבל כיוון שבגרסה הרקורסיבית אני כל פעם עובדת על מילה קטנה יותר, כשהאינדקסים נפגשים המילה שלי בעצם מצטמצמת לתו אחד או אפס תווים. כמו כן, כיוון שבכל איטרציה אני מקבלת מילה קטנה יותר, אני תמיד יכולה להשוות את הקצוות של המילה, ולא צריכה לשמור אינדקסים.
זהו, אלו היו האלגוריתמים שלי.
עכשיו אני ממש רוצה לשמוע איך אתן הייתן בודקות אם מילה היא פלינדרום, כמה שיותר יצירתי יותר טוב!
text[::-1]==text
מעולה!
Less readable, more efficient:
`all(a==b for a, b in zip(itertools.islice(text, len(text)//2), reversed(text)))`
באיזה שפת תכנות זה כתוב?
פייתון.
בגדול, אם אני לא מציינת אחרת, כל הקוד כתוב בפייתון
יפה מאוד, יש לך גם בג’אווה סקריפט?
לא כרגע, אולי תנסי/ה?!
function findPlanidrome(word){
return word.split(”).join() === word.split(”).reverse().join();
}
console.log(findPlanidrome(“abba”))
שלום מיה . אני לומד פייתון דרך יודמי . האם אתה עובדת כשכירה בתחום ? האם פייתון לבד זה מספיק לעבודה בתחום ?
כן, אני מפתחת ב-BigPanda.
כרגע אני מפתחת בסקאלה, אבל לפני כן פיתחתי בפייתון במשך חמש שנים.
פייתון מספיקה לעבודה בתחום, אבל זה תלוי כמובן ברמת הידע והניסיון.
היי מאיה, תוכלי להסביר יותר לעומק מה היתרון של האלגוריתם הרקורסיבי?
מצד אחד לא צריך לשמור אינדקסים אבל מצד שני עושים סלייסינג לסטרינג, ובגלל שסטרינג הוא לא mutble אז זה בעצם יצירה של סטרינג חדש (תקני אותי אם אני טועה:). אז נראה לי שאין פה חיסכון במקום, וגם לא בזמן ריצה כי ככה או ככה נעבור על הכל במקרה של פולינדרום.
מה אני מפספסת?
סליחה שלא ראיתי את השאלה קודם!
זה מדויק שאין פה חיסכון במקום ולא בזמן ריצה, מה שיש כאן זה שני דברים –
1. האהבה שלי לרקורסיות.
2. באלגוריתם האיטרטיבי המקורי יש יחסית הרבה מקום לטעויות, החלק מלא לזכור אם זה אמור להיות i<j או i<=j שזה משהו שאנשים תמיד מתבלבלים בו עם שני אינדקסים, דרך להשתמש בטעות ב-len(word) במקום ב-len(word)-1. אז אפשר לטעון שרק מהבחינה של התעסקות באינדקסים זה פתרון יותר פשוט, אבל אני בטוחה שרוב האנשים לא יסכימו איתי 🙂
אפשר בבקשה עזרה בכתיבת תכנית פשוטה של פלינדרום?
שאלה 5: כתבי פעולה המקבלת מחרוזת ומחזירה את המחרוזת ההפוכה.
שאלה 6: כתבי פעולה המקבלת מחרוזת ומחזירה “אמת” אם המחרוזת היא פלינדרום (מחרוזת שניתן לקרוא אותה משני צדיה) ו-“שקר” אחרת. חובה להשתמש בפעולה מסעיף 5.
היי, הודיה!
אני תמיד ממליצה בשאלות תכנות להתחיל מ-stack overflow.
הנה שאלה שעוסקת בהיפוך מחרוזות –
https://stackoverflow.com/questions/3940128/how-do-i-reverse-a-list-or-loop-over-it-backwards/3940137#3940137
פה יש דיון על איך לבדוק פלינדרומים, ובתגובות מדברים גם על היפוך מחרוזות –
https://stackoverflow.com/questions/17331290/how-to-check-for-palindrome-using-python-logic
בהצלחה!