37 lines
983 B
Ruby
37 lines
983 B
Ruby
def best_shuffle(s)
|
|
# Fill _pos_ with positions in the order
|
|
# that we want to fill them.
|
|
pos = []
|
|
# g["a"] = [2, 4] implies that s[2] == s[4] == "a"
|
|
g = s.length.times.group_by { |i| s[i] }
|
|
|
|
# k sorts letters from low to high count
|
|
k = g.sort_by { |k, v| v.length }.map { |k, v| k }
|
|
|
|
until g.empty?
|
|
k.each do |letter|
|
|
g[letter] or next
|
|
pos.push(g[letter].pop)
|
|
g[letter].empty? and g.delete letter
|
|
end
|
|
end
|
|
|
|
# Now fill in _new_ with _letters_ according to each position
|
|
# in _pos_, but skip ahead in _letters_ if we can avoid
|
|
# matching characters that way.
|
|
letters = s.dup
|
|
new = "?" * s.length
|
|
until letters.empty?
|
|
i, p = 0, pos.pop
|
|
i += 1 while letters[i] == s[p] and i < (letters.length - 1)
|
|
new[p] = letters.slice! i
|
|
end
|
|
|
|
score = new.chars.zip(s.chars).count { |c, d| c == d }
|
|
[new, score]
|
|
end
|
|
|
|
%w(abracadabra seesaw elk grrrrrr up a).each do |word|
|
|
puts "%s, %s, (%d)" % [word, *best_shuffle(word)]
|
|
end
|