אני רוצה להמשיך בסדרת הפתרונות של Advent Of Code ולדבר על יום 7, יום שלימד אותי שתכנות דינמי זה דווקא די כיף ולא מסובך. כמו אתמול גם פה החלק הראשון פשוט והחלק השני דורש את המאמץ.

1. האתגר

נתון קלט שמתאר סוג של מסלול מלמעלה למטה:

.......S.......
...............
.......^.......
...............
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
...............

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

.......S.......
.......|.......
......|^|......
...............
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
...............

ובסוף נגיע ל:

.......S.......
.......|.......
......|^|......
......|.|......
.....|^|^|.....
.....|.|.|.....
....|^|^|^|....
....|.|.|.|....
...|^|^|||^|...
...|.|.|||.|...
..|^|^|||^|^|..
..|.|.|||.|.|..
.|^|||^||.||^|.
.|.|||.||.||.|.
|^|^|^|^|^|||^|
|.|.|.|.|.|||.|

המשימה היא לחשב כמה פעמים הקרן מתפצלת.

2. הפתרון

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

class String
  def find_all_indexes(ch)
    chars.each_with_index.filter {|c, i| c == ch }.map {|c, i| i }
  end
end

בגלל שזה רובי אני יכול להגדיר את הפונקציה בתור הרחבה ל Stirng ועכשיו אפשר לכתוב:

"abcabcabc".find_all_indexes("a")

כדי להפעיל את הפונקציה על המחרוזת שמשמאל לנקודה. הקוד עצמו בתוספת הערות של AI הוא:

  def part1
    beam_indexes = Set.new
    count = 0

    File.read(@filename).lines.each do |line|
      # Initialize beam positions when we encounter the start marker
      if beam_index = line =~ /S/
        puts "--- START ---"
        beam_indexes = Set.new([beam_index])
      end

      # Find all splitter positions in current line
      splitter_indexes = Set.new(line.find_all_indexes('^'))
      # When a beam hits a splitter, it splits into two beams (left and right)
      splitted_beams = Set.new((splitter_indexes & beam_indexes).flat_map {|i| [i-1, i+1] })
      # Count interactions with splitters
      count += (splitter_indexes & beam_indexes).size
      # Beams that don't hit splitters continue straight
      continuing_beams = beam_indexes - splitter_indexes
      # Update beam positions: continuing beams + newly split beams
      beam_indexes = continuing_beams + splitted_beams
    end

    count
  end

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

count += (splitter_indexes & beam_indexes).size

כששלחתי את הקוד לקלוד עבור Code Review הוא טען שפעולת חיבור של שתי קבוצות ברובי מחזירה מערך אבל בדיקה בקונסול מראה לי שזו טעות וחיבור שתי קבוצות מחזיר קבוצה:

3.3.5 :005 > (Set.new + Set.new).class
 => Set

הוא גם טען ששכחתי לעשות require ל set וזו גם טעות שלו. שני הדברים מלמדים אותי שקלוד כנראה חושב שאני בגרסה ישנה יותר של רובי. סך הכל הקוד עבד בסדר גמור והחזיר תוצאה נכונה.

3. הטוויסט - תכנות דינמי

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

.......S.......
.......|.......
......|^.......
......|........
.....|^.^......
.....|.........
....|^.^.^.....
....|..........
...|^.^...^....
...|...........
..|^.^...^.^...
..|............
.|^...^.....^..
.|.............
|^.^.^.^.^...^.
|..............

וזו דוגמה לעוד עולם אפשרי:

.......S.......
.......|.......
......|^.......
......|........
......^|^......
.......|.......
.....^|^.^.....
......|........
....^.^|..^....
.......|.......
...^.^.|.^.^...
.......|.......
..^...^|....^..
.......|.......
.^.^.^|^.^...^.
......|........

והשאלה היא כמה עולמות אפשריים כאלה קיימים.

אז ברור שאנחנו לא יכולים "לנסות" את כל העולמות כלומר לחשב ולשמור כל מסלול אפשרי. זה פשוט ייקח הרבה יותר מדי פעולות בגלל החישובים הכפולים. וברגע שחשבתם את המילה "חישובים כפולים" מיד אתם יודעים שנכנסתם לארץ התכנות הדינמי.

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

.......S.......
.......|.......
......|^.......
......|........
......^|^......
.......|.......
.....^|^.^.....
......|........
....^.*|..^....
.......|.......
...^.^.|.^.^...
.......|.......
..^...^|....^..
.......|.......
.^.^.^|^.^...^.
......|........

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

.......S.......
.......|.......
......|^.......
......|........
......^|^......
.......|.......
.....@|@.^.....
......|........
....^.*|..^....
.......|.......
...^.^.|.^.^...
.......|.......
..^...^|....^..
.......|.......
.^.^.^|^.^...^.
......|........

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

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

הנה זה ברובי לא מסובך בכלל:

  def part2
    beams_through = []

    File.read(@filename).lines.each do |line|
      if beam_index = line =~ /S/
        puts "--- START ---"
        beams_through = line.chars.map {|c| c == "S" ? 1 : 0 }
      end

      splitter_indexes = Set.new(line.find_all_indexes('^'))
      beams_through = beams_through.each_with_index.map do |previous_count, index|
        if splitter_indexes.include?(index)
          0
        else
          value = beams_through[index]
          value += beams_through[index - 1] if splitter_indexes.include?(index - 1)
          value += beams_through[index + 1] if splitter_indexes.include?(index + 1)

          value
        end
      end

      pp beams_through
    end
    beams_through.sum
  end