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

1. השאלה

בהנתן רשימת מילים:

["pool", "loco", "cool", "stain", "satin", "pretty", "nice", "loop"]

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

["pool", "loco", "cool", "stain", "satin", "loop"]

המילים nice ו pretty הן היחידות שמורכבות מהאותיות שלהן, בעוד שעבור כל מילה אחרת יש מילה נוספת המורכבת מאותן האותיות.

אפשר לראות את השאלה והדיון המקורי בפוסט:
http://nafiulis.me/the-deceptive-anagram-question.html

2. האלגוריתם

מטרת השאלה לבדוק כמה אתם יודעים להשתמש ב Hash Maps. ללא שימוש במבנה נתונים זה תצטרכו לרוץ על הרשימה בלולאה כפולה כדי לזהות האם כבר היתה מילה עם אותן האותיות (סיבוכיות n^2). מאחר ושליפה מ Hash מתבצעת ב O(1) , השימוש ב Hash משפר משמעותית את סיבוכיות זמן הריצה. 
אפשר לדעת אם שתי מילים הן אנגרמות אחת של השניה אם נסתכל על אותיות המילה ממוינות. למשל מיון אותיות של המילה loop נותן בדיוק loop, וגם מיון אותיות המילה pool נותן את התוצאה loop. 

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

3. פתרון בפייתון

הפתרון המוצע בפוסט מנצל את העובדה שבשפת פייתון כבר יש מבנה נתונים שנקרא Counter המייצג Hash של מונים. כך נראה הקוד:

from collections import *
from itertools import *

def get_anagrams(words):

    normalized = [''.join(sorted(w)) for w in words]

    d = Counter(normalized)

    return [w for w, n in izip(words, normalized) if d[n] > 1]

print get_anagrams(["pool", "loco", "cool", "stain", "satin", "pretty", "nice", "loop"])

 

4. תרגום לפרל

בפרל אין לנו את האובייקט Counter, ולכן צריך לבנות לבד את מערך המונים, זה הקוד בשורות 11-12. גם את תוכנית הפייתון אפשר היה לכתוב באופן דומה תוך שימוש ב map ו filter, אבל אני לא בטוח שפייתונאים היו מעדיפים זאת. כך נראה הקוד:

use strict;
use warnings;

use v5.18;

sub normalized { join '', sort split //, shift }

sub get_anagrams {
    my (@words) = @_;

    my %counter;
    $counter{normalized($_)}++ for @words;

    grep { $counter{normalized($_)} > 1 } @words;
}

say join(" ", get_anagrams("pool", "loco", "cool", "stain", "satin", "pretty", "nice", "loop"));

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

5. תרגום לרובי

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

def get_anagrams(words)
  normalized = lambda { |w|  w.split(//).sort.join('') }
  anagrams = words.group_by(&normalized)

  words.select { |w| anagrams[normalized.call(w)].count > 1 }
end

puts get_anagrams(["pool", "loco", "cool", "stain", "satin", "pretty", "nice", "loop"])

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