Coding challenge (on Ruby Garden) [long]

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

David Naseby wrote:

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.

Try again:

one_in_each([1,2,3,4],[[1,2,3,4],[2,3,4],[2,3,4],[2,3,4]])

should be true.

This bit looks strange to me, though:

if (arr_of_arr.length - (arr_of_arr - arr).length) > arr.length
^^^^^^^^^^^^^^^^

None of the elements of arr can be in arr_of_arr since they’re of different
types. Thus your use of “arr_of_arr - arr” is the same as
"arr_of_arr.uniq", I think.