יום 7 - The Sum of Its Parts

קישור לחידה המקורית:
https://adventofcode.com/2018/day/7

פיתרון שלי בשפת Ruby:

require 'tsort'

class Task
  attr_accessor :worktime, :id
  def initialize(id, graph)
    @worktime = id.ord - 'A'.ord + 1 + 60
    @graph = graph
    @id = id
  end

  def to_s
    "#{id} [#{@worktime}]"
  end

  def inspect
    self.to_s
  end

  def finish
    @graph.remove(id)
  end
end

class Worker
  def initialize
    @task = nil
    @work_left = Float::INFINITY
  end

  def free?
    @task.nil?
  end

  def start(task)
    @task = task
    @work_left = task.worktime
  end

  def tick
    @work_left -= 1
    if @work_left == 0
      @task.finish
      @task = nil
    end
  end
end

class Factory
  attr_reader :ticks

  def initialize(workers)
    @workers = []
    @queue = []
    @ticks = 0
    workers.times do
      @workers << Worker.new
    end
  end

  def queue(task)
    @queue << task
  end

  def finished?
    @queue.empty? && @workers.all? {|w| w.free? }
  end

  def tick
    @workers.select {|w| w.free? }.each do |w|
      w.start(@queue.shift) if @queue.length > 0
    end

    @workers.each {|w| w.tick }
    @ticks += 1
  end
end

class TaskGraph
  attr_reader :prereqs

  def initialize(factory)
    @prereqs = {}
    @factory = factory
  end

  def build_next_task    
    task = @prereqs.select {|k, v| v.length == 0}.keys.sort.first    
    return if task.nil?
    @factory.queue(Task.new(task, self))
    @prereqs.delete(task)
  end

  def remove(task)
    @prereqs.transform_values! {|prereqs| prereqs - [task] }
  end

  def add_prereq(prereq, task)
    @prereqs[task] ||= []
    @prereqs[prereq] ||= []
    @prereqs[task] << prereq
  end

  def ready?
    @prereqs.values.any? {|v| v.length == 0 }
  end

  def finished?
    @prereqs.keys.length == 0
  end
end

builder = Factory.new(5)
tg = TaskGraph.new(builder)

ARGF.each_line.sort.each do |line|
  _, prereq, task = *line.match(/Step ([A-Z]) must be finished before step ([A-Z]) can begin/)
  tg.add_prereq(prereq, task)
end

while !(tg.finished? && builder.finished?) do
  tg.build_next_task while tg.ready?
  builder.tick
end

puts builder.ticks

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