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]]
=> [[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