module Mendel::Combiner

Constants

COMBO

To keep from allocating so many strings

COORDINATES
EmptyList
INPUT
InvalidCoordinates
QUEUED
SCORE
SEEN

Attributes

lists[RW]
priority_queue[RW]

Public Class Methods

included(target) click to toggle source
# File lib/mendel/combiner.rb, line 13
def self.included(target)
  target.extend(ClassMethods)
end
new(*lists) click to toggle source
# File lib/mendel/combiner.rb, line 17
def initialize(*lists)
  raise EmptyList if lists.any?(&:empty?)
  self.lists          = lists
  self.priority_queue = MinPriorityQueue.new
  queue_combo_at(lists.map {0} )
end

Public Instance Methods

dump() click to toggle source
# File lib/mendel/combiner.rb, line 33
def dump
  {INPUT => lists, SEEN => seen_set.to_a, QUEUED => priority_queue.dump }
end
dump_json() click to toggle source
# File lib/mendel/combiner.rb, line 37
def dump_json
  JSON.dump(dump)
end
each() { |combo| ... } click to toggle source
# File lib/mendel/combiner.rb, line 24
def each
  return self.to_enum unless block_given?
  loop do
    combo = next_combination
    break if combo == :none
    yield combo
  end
end
queue_length() click to toggle source
# File lib/mendel/combiner.rb, line 41
def queue_length
  priority_queue.length
end
score_combination(items) click to toggle source
# File lib/mendel/combiner.rb, line 45
    def score_combination(items)
      raise NotImplementedError,
        <<-MESSAGE
        Including class must define. Must take a combination and produce a score.
          - If you have not defined `build_combination`, `score combination` will receive
            an array of N items (one from each list)
          - If you have defined `build_combination`, `score_combination` will receive
            whatever `build_combination` returns
        MESSAGE
    end

Private Instance Methods

build_combination(items) click to toggle source
# File lib/mendel/combiner.rb, line 105
def build_combination(items)
  items
end
combo_at(coordinates) click to toggle source
# File lib/mendel/combiner.rb, line 100
def combo_at(coordinates)
  items = lists.each_with_index.map {|list, i| list[coordinates[i]] }
  build_combination(items)
end
increments_from(coordinates) click to toggle source

All possible coordinates which are one greater than the given coords in a single direction. Eg: increments_from()

#=> [[0,1], [1, 0]]

increments_from()

=> [[11, 5, 7], [10, 6, 7], [10, 5, 8]]
# File lib/mendel/combiner.rb, line 121
def increments_from(coordinates)
  coordinates.length.times.map { |i| coordinates.dup.tap { |c| c[i] += 1} }
end
next_combination() click to toggle source
# File lib/mendel/combiner.rb, line 66
def next_combination
  pair = pop_queue
  return :none if pair.nil?
  data, score = pair
  coordinates = data.fetch(COORDINATES)
  combo       = data.fetch(COMBO)
  queue_children_of(coordinates)
  [combo, score]
end
next_steps_from(coordinates) click to toggle source

Increments which are valid for instance’s lists

# File lib/mendel/combiner.rb, line 110
def next_steps_from(coordinates)
  increments_from(coordinates).select { |coords| valid_for_lists?(coords, lists) }
end
pop_queue() click to toggle source
# File lib/mendel/combiner.rb, line 76
def pop_queue
  priority_queue.pop
end
queue_children_of(coordinates) click to toggle source
# File lib/mendel/combiner.rb, line 80
def queue_children_of(coordinates)
  children_coordinates = next_steps_from(coordinates)
  children_coordinates.each {|cc| queue_combo_at(cc) }
end
queue_combo_at(coordinates) click to toggle source
# File lib/mendel/combiner.rb, line 85
def queue_combo_at(coordinates)
  return if seen_set.include?(coordinates)
  seen_set << coordinates
  queue_item = queueable_item_for(coordinates)
  score = queue_item.delete(SCORE)
  priority_queue.push(queue_item, score)
end
queueable_item_for(coordinates) click to toggle source
# File lib/mendel/combiner.rb, line 93
def queueable_item_for(coordinates)
  raise InvalidCoordinates, coordinates unless valid_for_lists?(coordinates, lists)
  combo = combo_at(coordinates)
  score = score_combination(combo)
  {COMBO => combo, COORDINATES => coordinates, SCORE => score}
end
seen_set() click to toggle source
# File lib/mendel/combiner.rb, line 58
def seen_set
  @seen ||= Set.new
end
seen_set=(set) click to toggle source
# File lib/mendel/combiner.rb, line 62
def seen_set=(set)
  @seen = set
end
valid_for_lists?(coords, lists) click to toggle source

Do the coordinates represent a valid location given these lists? Eg:

valid_for_lists?([0,1], [['thundercats', 'voltron'], ['hi', 'ho']])
  #=> true - represents ['thundercats', 'ho']
valid_for_lists?([0,2], [['thundercats', 'voltron'], ['hi', 'ho']])
  #=> false - first list has an index 0, but second list has no index 2
valid_for_lists?([0,2,0], [['thundercats', 'voltron'], ['hi', 'ho']])
  #=> false - there are only two lists
# File lib/mendel/combiner.rb, line 133
def valid_for_lists?(coords, lists)
  # Must give exactly one index per list
  return false unless coords.length == lists.length
  coords.each_with_index.all? { |value, index| valid_index_in?(lists[index], value) }
end
valid_index_in?(array, index) click to toggle source

Eg:

valid_index_in?(['hi', 'ho'],  1) #=> true
valid_index_in?(['hi', 'ho'],  2) #=> false
valid_index_in?(['hi', 'ho'], -2) #=> true
valid_index_in?(['hi', 'ho'], -3) #=> true
# File lib/mendel/combiner.rb, line 144
def valid_index_in?(array, index)
  index <= (array.length - 1) && index >= (0 - array.length)
end