פורסם ב זה רק קוד, מתכוננות לראיונות

מראה מראה שעל הקיר, מי הכי פלינדרום בעיר?

קוד: palindrome.py
זמן קריאה: 4 דקות

אז אתמול היה יום מאוד מיוחד, זה היה יום עם תאריך פלינדרומי – 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

קצרצר ונחמד.

טוב, כדי לבדוק את האלגוריתם שלי אני אריץ כמה דוגמאות!
בין מקרי הקצה שנראה לי שחשוב להריץ פה יהיו:

  1. מילה של אות אחת – כי הרי אות אחת נקראת אותו הדבר משני הצדדים ולכן היא פלינדרום.
  2. פלינדרום עם מספר זוגי של תווים.
  3. פלינדרום עם מספר אי זוגי של תווים.
  4. מילה שהיא לא פלינדרום.
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)

חמוד, נכון?

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

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

10 תגובות בנושא “מראה מראה שעל הקיר, מי הכי פלינדרום בעיר?

      1. Less readable, more efficient:
        `all(a==b for a, b in zip(itertools.islice(text, len(text)//2), reversed(text)))`

    1. function findPlanidrome(word){
      return word.split(”).join() === word.split(”).reverse().join();

      }

      console.log(findPlanidrome(“abba”))

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

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

השאר תגובה