Platzi - Reto 8

platzi_boxes.rb

# Platzi - Reto 8 Diciembre 23
# @author: @israellias
# ruby_version: 2.5.3
#regalaconocimiento

module Model
  class Box < Struct.new(:name, :money, :weight)
  end

  class Combination < Struct.new(:boxes)
    def initialize(boxes = nil)
      self.boxes = boxes || []
    end

    def +(combination)
      Combination.new(self.boxes + combination.boxes)
    end

    def weight
      boxes.sum(&:weight)
    end

    def money
      boxes.sum(&:money)
    end

    def valid?(limit)
      weight <= limit
    end
  end
end

module App

  # @return [Array[Model::Box]]
  def self.setup
    box_a = Model::Box.new('Caja A', 100, 40)
    box_b = Model::Box.new('Caja B', 20, 10)
    box_c = Model::Box.new('Caja C', 40, 120)
    box_d = Model::Box.new('Caja D', 20, 20)
    box_e = Model::Box.new('Caja E', 10, 10)

    [box_a, box_b, box_c, box_d, box_e]
  end


  # @param [Array[Model::Box]] boxes
  # @return [Array[Model::Combination]]
  def self.combinations(boxes)
    [Model::Combination.new] + combine(boxes)                       # empty case + combinations
  end


  # @param [Array[Model::Box]] boxes
  # @return [Array[Model::Combination]]
  def self.combine(boxes)
    return [] unless boxes.any?                                     # no one combination here e.g. []

    single = Model::Combination.new([boxes.first])                  # get combination with the first box e.g. [1]
    combinations = combine(boxes[1..-1])                            # get combinations with the rest of boxes e.g. [[2],[3],[2,3]] # recursive
    joined = combinations.map {|combination| single + combination}  # join the single and combinations into third group of combinations e.g.[[1,2],[1,3],[1,2,3]]
    [single] + combinations + joined                                # get all combinations for boxes e.g. [[1],[2],[3],[2,3],[1,2],[1,3],[1,2,3]]
  end


  # @param [Array[Model::Box]] boxes
  # @param [Integer] limit
  # @return [Model::Combination]
  def self.choose(boxes, limit)
    @combinations = combinations(boxes)
    @combinations.select {|c| c.valid?(limit)}.max_by(&:money)
  end

  def self.run(boxes = nil, limit = 150)
    boxes ||= setup
    solution = choose(boxes, limit)

    puts "El Grinch encontró la solución óptima con #{solution.boxes.size} cajas:"
    solution.boxes.each {|b| puts b.name}
    puts "Con un peso total de:    #{solution.weight} Kg"
    puts "Y el total de dinero de: #{solution.money} USD"

    puts 'Desear ver todas las combinaciones posibles(y/n)'
    if gets.chomp === 'y'
      @combinations.each do |combination|
        puts "[#{combination.boxes.map(&:name).join(',')}] => {money: #{combination.money}, weight: #{combination.weight}}"
      end
    end
    puts 'Goodbye!'
  end
end

App.run

El resultado en la terminal es el siguiente

El Grinch encontró la solución óptima con 4 cajas:
Caja A
Caja B
Caja D
Caja E
Con un peso total de:    80 Kg
Y el total de dinero de: 150 USD
Desear ver todas las combinaciones posibles(y/n)
y
[] => {money: 0, weight: 0}
[Caja A] => {money: 100, weight: 40}
[Caja B] => {money: 20, weight: 10}
[Caja C] => {money: 40, weight: 120}
[Caja D] => {money: 20, weight: 20}
[Caja E] => {money: 10, weight: 10}
[Caja D,Caja E] => {money: 30, weight: 30}
[Caja C,Caja D] => {money: 60, weight: 140}
[Caja C,Caja E] => {money: 50, weight: 130}
[Caja C,Caja D,Caja E] => {money: 70, weight: 150}
[Caja B,Caja C] => {money: 60, weight: 130}
[Caja B,Caja D] => {money: 40, weight: 30}
[Caja B,Caja E] => {money: 30, weight: 20}
[Caja B,Caja D,Caja E] => {money: 50, weight: 40}
[Caja B,Caja C,Caja D] => {money: 80, weight: 150}
[Caja B,Caja C,Caja E] => {money: 70, weight: 140}
[Caja B,Caja C,Caja D,Caja E] => {money: 90, weight: 160}
[Caja A,Caja B] => {money: 120, weight: 50}
[Caja A,Caja C] => {money: 140, weight: 160}
[Caja A,Caja D] => {money: 120, weight: 60}
[Caja A,Caja E] => {money: 110, weight: 50}
[Caja A,Caja D,Caja E] => {money: 130, weight: 70}
[Caja A,Caja C,Caja D] => {money: 160, weight: 180}
[Caja A,Caja C,Caja E] => {money: 150, weight: 170}
[Caja A,Caja C,Caja D,Caja E] => {money: 170, weight: 190}
[Caja A,Caja B,Caja C] => {money: 160, weight: 170}
[Caja A,Caja B,Caja D] => {money: 140, weight: 70}
[Caja A,Caja B,Caja E] => {money: 130, weight: 60}
[Caja A,Caja B,Caja D,Caja E] => {money: 150, weight: 80}
[Caja A,Caja B,Caja C,Caja D] => {money: 180, weight: 190}
[Caja A,Caja B,Caja C,Caja E] => {money: 170, weight: 180}
[Caja A,Caja B,Caja C,Caja D,Caja E] => {money: 190, weight: 200}
Goodbye!

Process finished with exit code 0

Lo importante está en el método App.combine, que se encarga de preparar todas las posibles combinaciones de cajas que pueden entrar en la bolsa (incluida la opcion de ninguna caja)
Este numero de combinaciones es igual a 2^n donde n es el numero de cajas. En este caso las combinaciones posibles fueron de 2^5 = 32 combinaciones que se deben evaluar para determinar la optima.

Ruby permite escribir codigo legible y corto como se puede ver en la linea 71

71:     @combinations.select {|c| c.valid?(limit)}.max_by(&:money)

y tambien permite modificar los operadores como se hizo en la linea 15

15:    def +(combination)
16:      Combination.new(self.boxes + combination.boxes)
17:    end

y se utilizo en la linea 61

61:    joined = combinations.map {|combination| single + combination}