Skip to content

Instantly share code, notes, and snippets.

@jimweirich
Last active January 3, 2016 05:59
Show Gist options
  • Save jimweirich/8419952 to your computer and use it in GitHub Desktop.
Save jimweirich/8419952 to your computer and use it in GitHub Desktop.
This is a refactoring of the Allocation Elimination code. The original code (by Mike Doel and Adam McRae) was originally refactored by a large group at the Neo pairing booth at CodeMash. I then took the final version there and continued to refactor over the course of an evening and this is the result of that. I hope to blog about the refactoring…
Allocation = Struct.new(:project, :person, :start, :finish) do
include Comparable
def mergable_with?(other)
if start > other.start
other.mergable_with?(self)
else
same_assignment?(other) &&
finish >= other.start - 1
end
end
def same_assignment?(other)
person == other.person && project == other.project
end
def merge(other)
fail unless mergable_with?(other)
Allocation.new(
project, person,
[start, other.start ].min,
[finish, other.finish].max)
end
def <=>(other)
(person <=> other.person).nonzero? ||
(project <=> other.project).nonzero? ||
(start <=> other.start)
end
def inspect
"<#{project}/#{person} #{start}..#{finish}>"
end
end
module AllocationEliminator
module_function
def merge_duplicates(allocations)
return [] if allocations.empty?
merge_sorted_duplicates(allocations.sort)
end
def merge_sorted_duplicates(sorted_allocations)
result = []
candidate = sorted_allocations.first
sorted_allocations.drop(1).each do |next_allocation|
if candidate.mergable_with?(next_allocation)
candidate = candidate.merge(next_allocation)
else
result << candidate
candidate = next_allocation
end
end
result << candidate
result
end
end
require 'rspec-given'
require 'allocation_eliminator'
describe AllocationEliminator do
Given(:base_date) { Date.parse("2013-01-01") }
def day(n)
base_date + n - 1
end
When(:result) { AllocationEliminator.merge_duplicates(raw_allocations) }
context "handles empty allocations" do
Given(:raw_allocations) { [ ] }
Then { result == [] }
end
context "handles a single allocation" do
Given(:raw_allocations) {
[
Allocation.new('proj', 'Bob', day(1), day(30))
]
}
Then {
result == [
Allocation.new('proj', 'Bob', day(1), day(30))
]
}
end
context "eliminates overlaps in range" do
Given(:raw_allocations) {
[
Allocation.new('proj1', 'Bob', day(1), day(20)),
Allocation.new('proj1', 'Bob', day(11), day(30)),
]
}
Then { result == [Allocation.new('proj1', 'Bob', day(1), day(30))] }
end
context "does not eliminate disjoints in range" do
Given(:raw_allocations) {
[
Allocation.new('proj1', 'Bob', day(1), day(20)),
Allocation.new('proj1', 'Bob', day(28), day(30)),
]
}
Then { result == raw_allocations.sort }
end
context "multiple people with one overlap" do
Given(:raw_allocations) {
[
Allocation.new('proj1', 'Bob', day(1), day(20)),
Allocation.new('proj1', 'Bob', day(11), day(30)),
Allocation.new('proj1', 'Ada', day(11), day(30)),
]
}
Then {
result == [
Allocation.new('proj1','Bob', day(1), day(30)),
Allocation.new('proj1','Ada', day(11), day(30)),
].sort
}
end
context "multiple projects with one overlap" do
Given(:raw_allocations) {
[
Allocation.new('proj1', 'Bob', day(1), day(20)),
Allocation.new('proj1', 'Bob', day(11), day(30)),
Allocation.new('proj2', 'Bob', day(11), day(30)),
].sort
}
Then {
result == [
Allocation.new('proj1', 'Bob', day(1), day(30)),
Allocation.new('proj2', 'Bob', day(11), day(30))
].sort
}
end
context "one range completely within another" do
Given(:raw_allocations) {
[
Allocation.new('proj1', 'Bob', day(1), day(20)),
Allocation.new('proj1', 'Bob', day(11), day(15)),
]
}
Then { result == [
Allocation.new('proj1', 'Bob', day(1), day(20))
].sort
}
end
context "more than two ranges overlapping" do
Given(:raw_allocations) {
[
Allocation.new('proj1', 'Bob', day(1), day(10)),
Allocation.new('proj1', 'Bob', day(8), day(15)),
Allocation.new('proj1', 'Bob', day(11), day(20))
]
}
Then { result == [
Allocation.new('proj1', 'Bob', day(1), day(20))
]
}
end
context "more than two ranges overlapping moar" do
Given(:raw_allocations) { [
Allocation.new('proj1', 'Bob', day(1), day(10)),
Allocation.new('proj1', 'Bob', day(11), day(15)),
Allocation.new('proj1', 'Bob', day(8), day(20)),
]
}
Then { result == [
Allocation.new('proj1', 'Bob', day(1), day(20))
]
}
end
end
require 'allocation'
describe Allocation do
Given(:mon) { Date.parse("2014-01-13") }
Given(:tue) { mon + 1 }
Given(:wed) { mon + 2 }
Given(:thu) { mon + 3 }
Given(:fri) { mon + 4 }
Given(:sat) { mon + 5 }
describe "merging" do
Given(:first_start) { mon }
Given(:first_finish) { fri }
Given(:second_person) { "Bob" }
Given(:second_project) { "Proj" }
Given(:first) { Allocation.new("Proj", "Bob", first_start, first_finish) }
Given(:second) { Allocation.new(second_project, second_person, second_start, second_finish) }
When(:result) { first.merge(second) }
context "when ummergable" do
Invariant { ! first.mergable_with?(second) }
Invariant { result.should have_failed }
context "when disjoint" do
Given(:second_start) { first_finish + 2 }
Given(:second_finish) { first_finish + 4 }
Then { }
end
context "when disjoint in reverse" do
Given(:second_start) { first_start - 4 }
Given(:second_finish) { first_start - 2 }
Then { }
end
context "when different people" do
Given(:second_start) { first_start }
Given(:second_finish) { first_finish }
Given(:second_person) { "Ada" }
Then { }
end
context "when different project" do
Given(:second_start) { first_start }
Given(:second_finish) { first_finish }
Given(:second_project) { "bench" }
Then { }
end
end
context "when merge-able" do
Invariant { result.start == [first_start, second_start].min }
Invariant { result.finish == [first_finish, second_finish].max }
Invariant { first.mergable_with?(second) }
context "when overlapping" do
Given(:second_start) { first_finish - 2 }
Given(:second_finish) { first_finish + 2 }
Then { result == Allocation.new("Proj", "Bob", first_start, second_finish) }
end
context "when overlapping in reverse" do
Given(:second_start) { first_start - 2 }
Given(:second_finish) { first_start + 2 }
Then { result == Allocation.new("Proj", "Bob", second_start, first_finish) }
end
context "when adjacent" do
Given(:second_start) { first_finish + 1 }
Given(:second_finish) { first_finish + 3 }
Then { result == Allocation.new("Proj", "Bob", first_start, second_finish) }
end
context "when adjacent in reverse" do
Given(:second_start) { first_start - 3 }
Given(:second_finish) { first_start - 1 }
Then { result == Allocation.new("Proj", "Bob", second_start, first_finish) }
end
context "when first contains second" do
Given(:second_start) { first_start + 2 }
Given(:second_finish) { first_finish - 2 }
Then { result == Allocation.new("Proj", "Bob", first_start, first_finish) }
end
context "when second contains first" do
Given(:second_start) { first_start - 2 }
Given(:second_finish) { first_finish + 2 }
Then { result == Allocation.new("Proj", "Bob", second_start, second_finish) }
end
end
end
end
@coreyhaines
Copy link

I definitely like having the allocation object to put some of things on.

I'm torn on unrolling the recursion into an loop over a mutable list. I've tended to have problems coming back to those to make changes.

@jimweirich
Copy link
Author

Are you referring to the .shift used for walking through the sorted allocations? I'm not too worried about it because the main entry point (merge_duplicates) makes a sorted copy, so only the local copy is modified, not the original. Perhaps this is a point where marking the secondary method (merge_sorted_duplicates) private would emphasize that it is not to be used externally (cf. our conversation about public/private at CodeMash).

Here's a version that doesn't modify the sorted allocations array:

  def merge_sorted_duplicates(sorted_allocations)
    result = []
    candidate = nil
    sorted_allocations.each do |next_allocation|
      if candidate.nil?
        candidate = next_allocation
      elsif candidate.mergable_with?(next_allocation)
        candidate = candidate.merge(next_allocation)
      else
        result << candidate
        candidate = next_allocation
      end
    end
    result << candidate
    result
  end

Although it's flog score is actually less than the original version, the extra if check in the midst of the loop makes the algorithm less clear (IMHO).

Thoughts?

@jimweirich
Copy link
Author

Found a better version of the non-destructive iterative version that I'm kinda liking. I've updated the Gist to reflect the new iterative version.

@adamlogic
Copy link

@jimweirich Very nice! I especially like the simplicity of Allocation#merge. I do hope you blog about this. It was a fun way to end CodeMash, and I loved how into it @coreyhaines and @aeden got. :-)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment