אתמול כתבתי על בדיקת cover? של רובי והיום נראה איך היא עוזרת לנו לפתור בעיה אמיתית מתוך Advent Of Code האחרון ואני מתכוון לחלק השני של יום 5. מה שאהבתי בחלק הזה היה שכשניסיתי לקחת את הפתרון של חלק 1 ולהרחיב אותו לחלק 2 זה פשוט לא עבד וכך הבנתי את הטעות שהיתה לי בחלק 1. אבל בואו לא נקדים את המאוחר ונלך לראות את התרגיל.

1. חלק 1 חיפוש דברים שלא בשום טווח

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

def part1
  @to_check.count {|i| @fresh_ids.any? {|r| r.include?(i) } }
end

כאשר @to_check זה רשימת הערכים שצריך לבדוק, @fresh_ids זו רשימת הטווחים ו include? בודק אם טווח מכיל מספר. יש פה לולאה כפולה שרצה על כל אחד מהמספרים לבדוק ובודקת אותו מול כל אחד מהטווחים.

2. חלק 2 חיפוש כל הדברים

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

3-5
10-14
16-20
12-18

התשובה היא 14 כלומר המספרים 3, 4, 5, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 ו 20.

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

3-5
10-20

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

def add_range(r)
  affected, unaffected = ranges.partition do |range|
    range.cover?(r) || r.cover?(range) || range.cover?(r.begin) || range.cover?(r.end)
  end

  self.ranges = unaffected
  new_range = ([*affected, r].map {|r| r.begin }.min)..([*affected, r].map {|r| r.end }.max)
  return add_range(new_range) unless affected.empty?

  self.ranges << r
end

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

סך הכל זה הקוד המלא של הפתרון:

require 'set'

class RangeSet
  attr_accessor :ranges

  def initialize
    @ranges = []
  end

  def add_range(r)
    affected, unaffected = ranges.partition do |range|
      range.cover?(r) || r.cover?(range) || range.cover?(r.begin) || range.cover?(r.end)
    end

    self.ranges = unaffected
    new_range = ([*affected, r].map {|r| r.begin }.min)..([*affected, r].map {|r| r.end }.max)
    return add_range(new_range) unless affected.empty?

    self.ranges << r
  end
end

class Day5
  attr_accessor :fresh_ids, :to_check
  def initialize(fname)
    fresh_ids, to_check = File
      .read(fname)
      .lines
      .map {|l| l.strip }
      .slice_when {|e1, e2| e1.empty? }
      .to_a

    @fresh_ids = fresh_ids.reject(&:empty?).map do |r|
      r.split("-").map(&:to_i).then {|a| Range.new(*a) }
    end
    @to_check = to_check.map(&:to_i)
  end

  def part1
    @to_check.count {|i| @fresh_ids.any? {|r| r.include?(i) } }
  end

  def part2
    stock = RangeSet.new
    @fresh_ids.each {|r| stock.add_range(r) }
    stock
  end
end

if $PROGRAM_NAME == __FILE__
  d = Day5.new("input.txt")
  pp d.part1
  pp d.part2.ranges.map {|r| r.size }.sum
end