Last active
January 3, 2016 05:59
-
-
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…
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
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.
@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
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:
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?