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

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

1. האתגר

נתונה מפה בפורמט טקסטואלי שאופייני לאתגרי Advent Of Code:

    ....#.....
    .........#
    ..........
    ..#.......
    .......#..
    ..........
    .#..^.....
    ........#.
    #.........
    ......#...

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

2. חלק 1 - הסימולטור

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

require 'set'

class Guard
  attr_accessor :position, :heading
  def initialize(position)
    self.heading = -1 + 0i
    self.position = position
  end

  def step
    self.position = position + heading
  end

  def turn
    self.heading = Complex(heading.imag, -heading.real)
  end

  def back
    self.position = position - heading
  end

  def coords
    [position.real, position.imag]
  end
end

class Room
  attr_accessor :matrix, :guard, :visited

  def initialize()
    self.visited = Set.new
    self.matrix = File.read('input.txt').lines.each_with_index.flat_map do |line, line_index|
      line.chomp.split('').each_with_index.map do |char, column_index|
        if char == "^"
          self.guard = Guard.new(Complex(line_index, column_index))
          {[line_index, column_index] => '.' }
        else
          {[line_index, column_index] => char }
        end
      end
    end.reduce({}) {|acc, val| acc.merge(val) }
    self.visited << guard.coords
  end

  def step
    guard.step
    if matrix[guard.coords] == "#"
      guard.back
      guard.turn
    end

    visited << guard.coords if matrix.key?(guard.coords)
  end

  def run
    step while matrix.key?(guard.coords)
  end
end

room = Room.new
room.run

pp room.visited.length

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

3. חלק 2 - האתגר

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

    ....#.....
    ....+---+#
    ....|...|.
    ..#.|...|.
    ....|..#|.
    ....|...|.
    .#.O^---+.
    ........#.
    #.........
    ......#...

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

  def initialize()
    self.time_loop = false
    self.visited = Set.new
    self.matrix = File.read('input.txt').lines.each_with_index.flat_map do |line, line_index|
      line.chomp.split('').each_with_index.map do |char, column_index|
        if char == '^'
          self.guard_start = [line_index, column_index]
          self.guard = Guard.new(Complex(line_index, column_index))
          { [line_index, column_index] => '.' }
        else
          { [line_index, column_index] => char }
        end
      end
    end.reduce({}) {|acc, val| acc.merge(val) }
    visited << [guard.coords, guard.heading]
  end

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

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

require 'set'

class Guard
  attr_accessor :position, :heading
  def initialize(position)
    self.heading = -1 + 0i
    self.position = position
  end

  def step
    self.position = position + heading
  end

  def turn
    self.heading = Complex(heading.imag, -heading.real)
  end

  def back
    self.position = position - heading
  end

  def coords
    [position.real, position.imag]
  end
end

class Room
  attr_accessor :matrix, :guard, :visited, :time_loop, :guard_start

  def initialize()
    self.time_loop = false
    self.visited = Set.new
    self.matrix = File.read('input.txt').lines.each_with_index.flat_map do |line, line_index|
      line.chomp.split('').each_with_index.map do |char, column_index|
        if char == '^'
          self.guard_start = [line_index, column_index]
          self.guard = Guard.new(Complex(line_index, column_index))
          { [line_index, column_index] => '.' }
        else
          { [line_index, column_index] => char }
        end
      end
    end.reduce({}) {|acc, val| acc.merge(val) }
    visited << [guard.coords, guard.heading]
  end

  def step
    guard.step
    if matrix[guard.coords] == '#'
      guard.back
      guard.turn
    end

    self.time_loop = true if visited.include?([guard.coords, guard.heading])
    visited << [guard.coords, guard.heading] if matrix.key?(guard.coords)
  end

  def run
    step_count = 0
    turn_count = 0
    while (matrix.key?(guard.coords) && !time_loop) do
      guard_before = guard.coords
      step
      step_count += 1
      if guard.coords == guard_before
        turn_count += 1
      end
    end
  end
end

room = Room.new
start = room.visited.first
room.run

time_loops = (room.visited - Set.new([start])).map(&:first).to_set.filter do |coords|
  room.matrix[coords] = '#'
  room.run
  time_loop = room.time_loop

  room.time_loop = false
  room.matrix[coords] = '.'
  room.visited = Set.new
  room.guard = Guard.new(Complex(room.guard_start[0], room.guard_start[1]))

  time_loop
end

pp time_loops.length

וזה אחרי ש Claude עבר עליו והעביר את לוגיקת האיפוס למתודה בתוך Room (הצעה של קלוד):

require 'set'

class Guard
  attr_accessor :position, :heading

  def initialize(position)
    @heading = -1 + 0i  # Using instance variables consistently
    @position = position
  end

  def step
    @position += @heading  # Using += for cleaner code
  end

  def turn
    @heading = Complex(@heading.imag, -@heading.real)
  end

  def back
    @position -= @heading  # Using -= for cleaner code
  end

  def coords
    [@position.real.to_i, @position.imag.to_i]  # Convert to integers to avoid floating point comparison issues
  end
end

class Room
  attr_accessor :matrix, :guard, :visited, :time_loop, :guard_start

  def initialize
    @time_loop = false
    @visited = Set.new
    parse_input_file
    @visited << [@guard.coords, @guard.heading]
  end

  def parse_input_file
    @matrix = {}
    File.readlines('input.txt', chomp: true).each_with_index do |line, line_index|
      line.chars.each_with_index do |char, column_index|
        coords = [line_index, column_index]
        if char == '^'
          @guard_start = coords
          @guard = Guard.new(Complex(line_index, column_index))
          @matrix[coords] = '.'
        else
          @matrix[coords] = char
        end
      end
    end
  end

  def step
    @guard.step
    if @matrix[@guard.coords] == '#'
      @guard.back
      @guard.turn
    end

    @time_loop = true if @visited.include?([@guard.coords, @guard.heading])
    @visited << [@guard.coords, @guard.heading] if @matrix.key?(@guard.coords)
  end

  def run
    step_count = 0
    turn_count = 0
    while (@matrix.key?(@guard.coords) && !@time_loop) do
      guard_before = @guard.coords
      step
      step_count += 1
      turn_count += 1 if @guard.coords == guard_before
    end

    # Return important values - makes testing easier
    [@time_loop, step_count, turn_count]
  end

  def reset
    @time_loop = false
    @visited = Set.new
    @guard = Guard.new(Complex(@guard_start[0], @guard_start[1]))
    @visited << [@guard.coords, @guard.heading]
  end
end

def find_time_loops(room)
  start = room.visited.first
  room.run

  # Extract the coordinates of visited positions, excluding the start
  visited_positions = (room.visited - Set.new([start])).map(&:first).to_set

  # Find positions that cause time loops
  time_loops = visited_positions.select do |coords|
    original_value = room.matrix[coords]
    room.matrix[coords] = '#'
    room.reset
    result = room.run.first  # Check if a time loop occurred

    # Restore the original value and reset the room
    room.matrix[coords] = original_value
    room.reset

    result
  end

  time_loops.length
end

# Main execution
room = Room.new
puts find_time_loops(room)