Enunciado del problema 1 para la code review

code-review-1.markdown

#GENERACIÓN ALEATORIA DE NUBES DE TAGS A PARTIR DE KEYWORDS

##Problema real A partir de un fichero con 2574 keywords, hay que generar un número determinado de nubes de forma que:

• Cada nube se comprondrá de 20 keywords
• Cada keyword aparezca 50 veces, en nubes diferentes
• Una keyword no puede aparecer repetida en una misma nube
• Todas las nubes han de ser diferentes, considerándose como diferentes dos nubes que, al menos, difieran en una keyword y teniendo en cuenta que la posición de cada keyword dentro de la nube de no es relevante.
• Este proceso se ejecutará una sola vez.

##Notas En este problema en concreto hay solución porque 2574 * 50 / 20 da un número entero. En caso de que no hubiera solución, bastaría con que no hubiera un par de nubes cuya diferencia de apariciones en nubes fuera > 1, o lo que es lo mismo, para todos los pares de keywords k1 y k2, se cumple que el número de apariciones de k1 (nk1) - número de apariciones de k2 (nk2) no es mayor de 1:

|nk1 - nk2| <= 1

##Objetivo

Implementar un algoritmo que resuelva este problema.

Equipo Richie - Paco

words = (1..100).to_a
WORDS_NUM = words.size
CLOUD_SIZE = 5
KEYWORD_APPEAR = 7

ARRAY_NUM = ((WORDS_NUM * KEYWORD_APPEAR).to_f / CLOUD_SIZE.to_f).to_i

CLOUDS = []
ARRAY_NUM.times do
  CLOUDS << []
end

words.each do |word|
  before_index = 0
  KEYWORD_APPEAR.times do
    CLOUDS[before_index..-1].each_with_index do |cloud, index|
      next if cloud.size == CLOUD_SIZE
      next if cloud.include?(word)

      cloud_tmp = cloud.dup
      cloud_tmp << word

      next if CLOUDS.include?(cloud_tmp)
      cloud << word
      before_index = index
      break
    end
  end
end

puts CLOUDS[0..10].inspect

Equipo Diego - Javi

class CloudFactory

  def self.generate(keywords, items_per_cloud, repetitions)
    keywords = keywords.to_a.shuffle
    tag_list = []
    init = 0
    (1..repetitions).each do 
      keywords.rotate!(init).in_groups_of(items_per_cloud) do |group|
        tag_list << group
      end
      last_size = tag_list.last.compact.size
      if last_size < items_per_cloud
        remaining = items_per_cloud - last_size
        tag_list.last.concat(keywords[0, remaining]).compact!
        init = remaining 
      end
      if self.repeating? tag_list
        tag_list.delete_at(-1)
        keywords.shuffle!
      end
    end
    tag_list.map!(&:shuffle)

  end

  def self.repeating?(vals)    
    vals.size != vals.map(&:sort).map{|a| a.join('-')}.uniq.size
  end

  def self.test_clouds
    result = self.generate(1..2574, 20, 50)
    h = Hash.new {|h,k| h[k] = 0}
    result.each do |cloud|
      cloud.each {|i| h[i] += 1}
    end
    h.select{|k,v| v < 48 || v > 52}   
    puts self.repeating? result

  end

end

CloudFactory.test_clouds

class LevelQueue

  attr_reader :max_level, :collection

  def initialize(collection, max_level)
    @collection = collection
    @max_level = max_level
    reset
  end

  def top_level
    @aux.keys.sort.last
  end

  def min_level
    @aux.keys.sort.first
  end

  def get_elements(number)
    res = []
    level = @aux.keys.sort.detect{|x| @aux.keys.present?}
    while res.size < number && level <= @max_level
      res += get_elements_by_level(number - res.size, level)
      level += 1
    end
    update_got_elements
    res
  end

  def reset
    @aux = {0 => @collection}
    @recent_got_elements = {}
  end

  private

  def get_elements_by_level(number, level)
    @recent_got_elements[level] ||= []
    @recent_got_elements[level] += @aux[level].present? ? @aux[level].slice!(0..(number - 1)) : []
  end

  def update_got_elements
    @recent_got_elements.each_pair do |k,v|
      unless k + 1 == @max_level
        @aux[k + 1] ||= []
        @aux[k + 1] += v
        @aux[k] = nil if @aux[k].blank?
      end
    end
    @recent_got_elements = {}
  end

end

class CombinationsGenerator

  def initialize(collection, r, max_appearances)
    @level_queue = LevelQueue.new(collection, max_appearances)
    @combination_n = collection.size
    @combination_r = r
    @combination_l = max_appearances
    @needed_elements = @combination_n.div(@combination_r) * @combination_r
  end

  def combinations
    while (elements = @level_queue.get_elements(@needed_elements).sort_by{rand}).present?
      elements.each_slice(@combination_r) do |subset|
        yield subset
      end
    end
  end

  def reset
    @level_queue.reset
  end
end

module CloudsGenerator

  MAX_APPEARANCES     = 50
  KEYWORDS_PER_CLOUD  = 20

  def self.generate
    generator = CombinationsGenerator.new(prepare_collection, KEYWORDS_PER_CLOUD, MAX_APPEARANCES)
    i = 0
    get_combinations(generator).each do |combination|
      cloud = Cloud.new
      cloud.cloud_keywords = combination.sort{rand}
      cloud.save
      print "\r#{i += 1} clouds created"
    end
  end

  private

  def self.get_combinations(generator)
    clouds = []
    generator.combinations do |combination|
      combination.sort!
      if clouds.include?(combination)
        raise CollisionError
      else
        clouds << combination
      end
    end

    clouds
  end

  def self.prepare_collection
    CloudKeyword.all.sort_by{rand}.each do |k|
      class << k
        def <=>(keyword)
          self.id <=> keyword.id
        end
      end
    end
  end

  public

  class CollisionError < StandardError
    def message
      'An existing combination has been built. Please rerun the execution'
    end
  end
end

Equipo Quico - Andres - Florent

clouds = []
num_clouds = (2574 * 50 / 20).to_i

while clouds.uniq.size != num_clouds do
  puts "Restarting #{clouds.uniq.size} #{clouds.size}"

  clouds = []
  keywords_step1 = (1..2574).to_a
  keywords_step2 = []

  num_clouds.times do
    if keywords_step1.size < 20
      cloud1 = keywords_step1.dup
      cloud2 = keywords_step2.shuffle.slice(0, 20 - cloud1.size)
      clouds << (cloud1 + cloud2).sort

      keywords_step1 += (keywords_step2 - cloud2)
      keywords_step2 = cloud2
    else
      cloud = keywords_step1.shuffle.slice(0, 20)
      clouds << cloud.sort
      keywords_step1 -= cloud
      keywords_step2 += cloud

      if keywords_step1.empty?
        keywords_step1, keywords_step2 = keywords_step2, keywords_step1
      end
    end
  end
end

p clouds