Reply to thread

Message: [QUOTE="Ruby Quiz, post: 4451125"] The general idea behind a lot of the solutions to this week's quiz was pretty basic. Try a big list (probably the whole list, in this problem), if that gets blocked divide it into smaller lists and try again. When one of these chunks of words gets through, we know that every words in that chunk was clean. The higher up in our search that happens, the more work that saves us. Because of that, this solution is ideal when there aren't a lot of banned words, as would probably be the case in the real world example of this quiz. Here's my own solution as the most basic example of this process: def isolate( list, test ) if test.clean? list.join(" ") Array.new elsif list.size == 1 list else left, right = list[0...(list.size / 2)], list[(list.size / 2)..-1] isolate(left, test) + isolate(right, test) end end isolate() is a recursive routine that takes an Array of words and a test filter and returns the banned words. If the entire words list passes a clean?() test, we return an empty Array (no banned words in the given list). If we don't get an okay from clean?() and we only have one word in the list, we've found a banned word and we return the one word Array itself to show that. Finally, if we didn't pass clean?() and we have more than one word, we divide the list in half, call isolate() on each half, and combine the results of both of those calls. Eventually, this drills down to find all the banned words. Of course, that's just the basics. Wayne Vucenic found a very clever optimization. If we check a big list and it gets banned, then we split it up and check the first half, which comes back clean, we know the second have would be banned and can skip the check. That could save a significant amount of messages that we would otherwise need to send. Brian Schroeder made a search for the optimal divisor for the word list, when breaking it into chunks. Brian landed on 3 as the magic number, but there has been some follow up discussion on Ruby Talk about his findings and if they are complete. Regardless, do download Brian's code to see just how much thought and effort he has put into it (and why he wants to sue me). Jannis Harder didn't cut the word list in half at each step either. I'm not sure exactly how Jannis arrived at the progression used, but it's an interesting scale: @steps = [110000,700000,300000,200000,110000, 70000,30000,20000,11000,7000, 3000,2000,1100,700,300,200,110, 70,30,20,11,7,3,2,1] In my own testing, this doesn't seem to best Wayne's optimization though. Jannis Harder did post a test framework that ended up being used by multiple entries. I thought that was very helpful. The final entry was by Michael Ulm, who used knowledge of the dictionary size and banned word probability to optimize the number of messages needed to find the banned words. This is a nice example of what can be done with a little bit of knowledge, though that's probably not too likely in real world scenarios. The main issue brought up in discussion was that my filter class had issues. Several alternatives where proposed, each with their own issues. Matching a word can be surprisingly tricky, when you take into account simple things like plurals, international characters, and apostrophes. In the end, everybody seem to just use what they could live with. My thanks to the submitters and discussers, informative as always. We'll try a classic programming challenge tomorrow from Knuth... [/QUOTE]

Verification