60 lines
1.4 KiB
Ruby
60 lines
1.4 KiB
Ruby
module Dutch
|
|
# Could use a class for the balls, but that's a little heavy.
|
|
# We'll just use symbols.
|
|
|
|
# List of colors, in order
|
|
Symbols = [:red, :white, :blue]
|
|
|
|
# Reverse map from symbol to numeric value
|
|
Values = Hash[Symbols.each_with_index.to_a]
|
|
|
|
# Pick a color at random
|
|
def self.random_ball
|
|
Symbols[rand 3]
|
|
end
|
|
|
|
# But we will use a custom subclass of Array for the list of balls
|
|
class Balls < Array
|
|
|
|
# Generate a given-sized list of random balls
|
|
def self.random(n)
|
|
self.new(n.times.map { Dutch.random_ball })
|
|
end
|
|
|
|
# Test to see if the list is already in order
|
|
def dutch?
|
|
return true if length < 2
|
|
Values[self[0]] < Values[self[1]] && slice(1..-1).dutch?
|
|
end
|
|
|
|
# Traditional in-place sort
|
|
def dutch!
|
|
lo = -1
|
|
hi = length
|
|
i = 0
|
|
while i < hi do
|
|
case self[i]
|
|
when :red
|
|
lo += 1
|
|
self[lo], self[i] = self[i], self[lo]
|
|
i += 1
|
|
when :white
|
|
i += 1
|
|
when :blue
|
|
hi -= 1
|
|
self[hi], self[i] = self[i], self[hi]
|
|
end
|
|
end
|
|
self
|
|
end
|
|
|
|
# Recursive, non-self-modifying version
|
|
def dutch(acc = { :red => 0, :white => 0, :blue => 0})
|
|
return self.class.new(
|
|
Symbols.map { |c| [c] * acc[c] }.inject(&:+)
|
|
) if length == 0
|
|
acc[first]+=1
|
|
return slice(1..-1).dutch( acc )
|
|
end
|
|
end
|
|
end
|