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

1. האתגר

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

/a/b/c/1/x.pl
/a/b/c/d/e/2/x.pl
/a/b/c/d/3/x.pl
/a/b/c/4/x.pl
/a/b/c/d/5/x.pl

נצטרך להחזיר את הנתיב /a/b/c כי הוא הנתיב הארוך ביותר שעדיין מכיל את כולם.

2. פיתרון בשפת רובי

הפיתרון לתרגיל הוא הזדמנות לדבר על תחיליות משותפות ומבנה הנתונים Trie. זהו מבנה נתונים מבוסס עץ שמייצג פיצול של אחד הקלטים. אם ניקח לדוגמה את הנתיב הראשון אז הוא ייוצג על ידי העץ:

/a
    /b
        /c
            /1
                /x.pl

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

/a
    /b
        /c
            /1
                /x.pl
            /d
                /e
                    /2
                        /x.pl

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

קוד? בטח. נתחיל במחלקה Node שהיא הבסיס לעץ:

class Node
  attr_accessor :value, :children
  def initialize(value)
    @value = value
    @children = {}
  end

  def <<(path)
    return if path.length == 0

    next_part = path.shift
    @children[next_part] = Node.new(next_part) unless @children[next_part]
    @children[next_part] << path
  end
end

ועכשיו אפשר להכניס את כל הנתיבים שלנו לעץ:

paths = %W[
    /a/b/c/1/x.pl
    /a/b/c/d/e/2/x.pl
    /a/b/c/d/3/x.pl
    /a/b/c/4/x.pl
    /a/b/c/d/5/x.pl
]

root = Node.new("")
paths.each { |path| root << path.split('/') }

ובסוף לרוץ על העץ ולחפש את הנתיב הכי עמוק שמכיל את כולם:

i = root
prefix = ""
loop do
  prefix += '/' + i.value unless i.value.empty?
  break unless i.children.length == 1
  i = i.children[i.children.keys[0]]
end
puts prefix

רוצים לנסות לפתור בעוד שפות? אולי אפילו בפרל? מוזמנים לפתור ולפרסם בתגובות את הגירסאות שלכם.