From: George Ogata [mailto:g_ogata@optushome.com.au]
one_in_each([1,2,3,4,5],
[[1,2,3,4,5],[1,2,3,4,5],[1,2,0,0,0],[1,2,0,0,0],[1,2,0,0,0]])To correct this, his worst-case complexity must increase
dramatically, I think.
Not too dramatically, and incidentally, failing cases are sped up a lot in
this version… although it slows down the passing cases more.
def one_in_each(items,rows)
return false if items.length != rows.length
return true if rows.empty?
item_matches =
items.each_with_index do |item, index|
item_matches << find_matches(item, rows)
return false if item_matches[index].empty?
end
taken_indices =
rows.length.times do
return false if more_same_than_length?(item_matches)
item_matches.each_with_index do |matches, index|
if matches.length == 1
return false if taken_indices.include? matches[0]
taken_indices << matches[0]
item_matches.delete_at(index)
else
matches.delete_if {|i| taken_indices.include?(i)}
end
end
return true if taken_indices.length == rows.length
end
return item_matches.flatten.uniq.length + taken_indices.length ==
rows.length
end
def find_matches(item, rows)
indexArr =
rows.each_with_index do |row, index|
indexArr << index if row.detect {|toMatch| toMatch == item }
end
return indexArr
end
def more_same_than_length?(arr_of_arr)
arr_of_arr.each do |arr|
if (arr_of_arr.length - (arr_of_arr - arr).length) > arr.length
return true
end
end
return false
end