lazy.rb

# Processes are running, they run forever, never die, and no new
# processes get spawned. Each process eats memory at a constant,
# individual rate - process p_i (with 0 <= i < n) consumes 1 byte
# after every d(p_i) seconds. The total amount of available disk space
# is denoted by X.
#
# For each given input configuration (read from stdin), calculate the
# ETA in seconds. HINT - it is not the average A configuration is
# encoded as a single line like this:
#
# X d(p_1) d(p_2) ... d(p_n)
# Example:
#
#  $ echo -e "4 3 7\n15 2 4 3 6\n16 2 4 3 6" | ruby your_solution.rb
#
# > 9
# > 12
# > 14


#
# One interesting way to solve this is to use lazy evaluation, using
# enumerators in Ruby or list comprehensions in Python.
#
# Our lazy evaluation will have two parts. One part will generate an
# indefinitely long sequence of values to represent the behaviour of a
# single process for every second. The second part will keep taking
# values from the process (i.e., running for another second) until
# we're done.
#

#
# Generating an indefinitely long sequence is easier than you might
# think. We create an Enumerator and pass it a block with an infinite
# loop to generate values. Here is a simple Enumerator that produces a
# series of multiples of two.
#

multiples_of_two = Enumerator.new do |y|
  x = 2 # we have to start somewhere
  loop do
    y << x # return the next value
    x = x * 2 # modify the value for the next iteration
  end
end

#
# If we called .to_a on this then bad things would happen, eventually.
# But we don't need to turn it into an array to use it - we can use
# the 'take' or 'take_while' methods from enumerable.
#

multiples_of_two.take(4) # => [2, 4, 8, 16]
multiples_of_two.take_while { |x| x < 1000 }
# => [2, 4, 8, 16, 32, 64, 128, 256, 512]

#
# We can write processes using a Enumerator that generate 0s to
# represent seconds where they're not taking a byte, and 1s to
# represent seconds where they do.
#
def new_process(freq)
  Enumerator.new do |y|
    idx = 1
    loop do
      v = idx % freq == 0 ? 1 : 0 # i.e., generate 1 every 'freq' seconds
      y << v
      idx += 1
    end
  end
end

#
# Now we can generate some processes using the rate at which they
# consume bytes, and look at their behaviour by using 'take'
#

p1 = new_process(4)
p1.take(9)
# => [0, 0, 0, 1, 0, 0, 0, 1, 0]

p2 = new_process(2)
p2.take(5)
# => [0, 1, 0, 1, 0]

#
# That's a single process, what about the combined effect of all
# processes? We can create a new uber-enumerator that takes a list of
# processes, and each 'tick' pulls the next value of each process
# and sums them.
#

def uber_enumerator(processes)
  Enumerator.new do |y|
    loop do
      values = processes.map(&:next) # call 'next' on each process, get an array of the results
      consumed = values.inject(&:+) # sum the values
      y << consumed # yield the number of bytes consumed this second
    end
  end
end

control = uber_enumerator([p1, p2])
control.take(6) # => [0, 1, 0, 2, 0, 1]

#
# Now we can write something to take from control until we reach some
# limit, and count how long it takes to get there.
#
limit = 4
seconds = 0
total = 0
control.take_while do |consumed|
  seconds = seconds + 1
  total = total + consumed
  total < limit # return true until we hit the limit
end

total # => 5
seconds # => 6

#
# A quick demonstration that this matches the test data from the doc.
#

class Machine
  attr_reader :limit, :control

  def initialize(limit, rates)
    @limit = limit

    processes = rates.map do |rate|
      new_process(rate)
    end
    @control = uber_enumerator(processes)
  end

  def run
    seconds = 0
    total = 0
    control.take_while do |consumed|
      seconds = seconds + 1
      total = total + consumed
      total < limit
    end
    seconds
  end
end

# Example:
#
#  $ echo -e "4 3 7\n15 2 4 3 6\n16 2 4 3 6" | ruby your_solution.rb
#
# > 9
# > 12
# > 14

Machine.new(4, [3, 7]).run # => 9
Machine.new(15, [2, 4, 3, 6]).run # => 12
Machine.new(16, [2, 4, 3, 6]).run # => 14