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

1. האתגר

יום 8 מציג לנו בתור קלט רשימה של מיקומים בעולם תלת מימדי:

162,817,812
57,618,57
906,360,560
592,479,940
352,342,300
466,668,158
542,29,236
431,825,988
739,650,466
52,470,668
216,146,977
819,987,18
117,168,530
805,96,715
346,949,466
970,615,88
941,993,340
862,61,35
984,92,344
425,690,689

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

2. הפתרון

נשים בצד את סיפור הרקע ונשים לב לדילמה - מה עולה ומתי משלמים. שתי אפשרויות:

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

2. אנחנו יכולים אחרי כל חיבור להסתכל מה חיברנו ולאחד את הצמתים לגרף. במצב כזה הכתיבה היא יקרה כי כל פעם שאני יוצר חיבור בין p ל q אני צריך לסמן גם ש p מחובר ל q אבל גם שכל הנקודות שמחוברות ל p עכשיו מחוברות לכל הנקודות שמחוברות ל q כלומר לאחד את המעגלים.

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

def line_to_pos(l)
  l.chomp.split(',').map(&:to_i)
end

def distance(p1, p2)
  (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2 + (p1[2] - p2[2]) ** 2
end

class Day8
  def initialize(filename)
    lines = File.read(filename).lines
    @circuits = lines.map do |line|
      pos = line_to_pos(line)
      [pos, Set.new([pos])]
    end.to_h

    distances = Hash.new {|h, k| h[k] = [] }
    lines.each do |from|
      lines.each do |to|
        next if from == to
        p = line_to_pos(from)
        q = line_to_pos(to)
        d = distance(p, q)
        distances[d] << [p, q] unless distances[d].include?([q, p])
      end
    end
    @distances = distances.keys.sort.flat_map {|k| distances[k] }
  end

  def connect(p, q)
    c_p = @circuits[p]
    c_q = @circuits[q]
    return 0 if c_p == c_q

    @circuits[p].merge(c_q)
    @circuits[q].each do |qq|
      @circuits[qq] = @circuits[p]
    end
    return 1
  end

  def part1
    cables = 1_000
    i = 0
    while cables > 0
      next_p, next_q = @distances[i]
      cables_used = connect(next_p, next_q)
      cables -= 1
      i += 1
    end
    @circuits.values.uniq.map {|s| s.size }.sort.reverse[0..2].reduce(1) {|acc, val| acc * val }
  end
end

למרות שהפתרון נכון ועובד קלוד זיהה את ה"באג הקריטי" הבא:

Problem: Only elements in c_q get updated. Elements in c_p that aren't p may still point to the old set.

הזיהוי הזה בדיוק מראה לנו למה עדיין קשה לקבל Code Review מ AI. כשקוראים את הקוד ואת ההערה זה נראה מאוד נכון, באמת אין סימטריה בפונקציה connect בין p ו q. לקבוצה של p אני רק עושה merge אבל בקבוצה של q אני ממש רץ בלולאה ומעדכן את כל ההפניות. למה לא הייתי צריך לעשות את זה גם ב p ?

התשובה ברורה למי שמבין את זרימת המידע במערכת - הנקודות האחרות ב p כבר מצביעות על אותו Set כמו p כי עדכנתי את ההצבעה שלהן בחיבורים קודמים. אין טעם לרוץ ולעדכן מחדש.

הבאג השני שקלוד מזהה בטעות ב Code Review הוא:

Cables are decremented even when connect returns 0 (already connected):

לכאורה אם connect מחזיר 0 לא חיברנו כלום ולכן מספר החוטים לא ירד. זה נכון ותואם את שמות המשתנים אבל לא תואם את הגדרות השאלה. המשימה שלי היתה לבצע אלף איטרציות בלי קשר לכמות החיבורים שבוצעו או לא בוצעו. אני מבין למה קלוד חושב שמשהו פה מוזר וטוב שהוא מפנה את תשומת לבי לבחירת השמות הלא נכונה אבל נשים לב שאנחנו צריכים להיות מאוד זהירים בקריאת הערות Code Review שמגיעות מ AI כי בלי הבנה קשה לתת פידבק מועיל.

3. הטוויסט

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

  def part2
    i = 0
    while @circuits.values.uniq.size > 1
      next_p, next_q = @distances[i]
      connect(next_p, next_q)
      i += 1
      pp "#{@circuits.values.uniq.size} circuits remaining"
    end
    next_p[0] * next_q[0]
  end

4. ניסיון שני

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

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

1. כל נקודה מיוצגת על ידי צומת.

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

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

זה הקוד של המחלקה Circuit שמנהלת את העץ:

class Circuit
  attr_accessor :parent, :name

  def initialize(name)
    self.name = name
    self.parent = self
  end

  def merge(other)
    self.parent = self.parent.parent while self.parent.parent != self.parent
    other.parent = other.parent.parent while other.parent.parent != other.parent

    return 0 if self.parent == other.parent

    c = Circuit.new("#{self.name}<->#{other.name}")
    self.parent.parent = c
    other.parent.parent = c
    return 1
  end
end

וקוד הפתרון בעזרת Circuit הוא עכשיו:

def part2
  @circuits = @circuits.map {|k, v| [k, Circuit.new(k.to_s)] }.to_h
  cables = @circuits.size - 1

  while cables > 0
    next_p, next_q = @distances.shift
    cables -= @circuits[next_p].merge(@circuits[next_q])
    pp "connected #{next_p[0]}, #{next_q[0]}. #{cables} cables remaining"
  end
  next_p[0] * next_q[0]
end

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