So I know there are folks much smarter than me on this mailing list, so hopefully one of you will be able to answer this question: ( Geeky CS/Math question follows )
What I can't figure out is a smart way to generate a list of array sizes given some maximum word length of x) in descending order of area.
Well, what exactly do you mean by "smart"? You're arrays are bounded by the square of the max size of a word in the dictionary; how big *is* that? If it isn't that big, there's no point in developing a "smart" algorithm; any time saved will be vastly offset by how long it takes to get the algorithm correct in the first place, and if small enough, will not be noticeable anyway. Note that a stupid brute force algorithm *that fits in cache* will very likely beat out a clever algorithm that doesnt fit in cache.
If you really want to do this example, just because this particular mountain is there, I'd point out that you *already know* the sorted order of the array areas; they are just the set of integers from 1 to (max word size)^2.
Step 1: Generate the set of possible factors, from the list of prime numbers <= max_word_size.
Step 2: For each number N, 1 < N < max_word_size^2, list out all of it's
( ... )
It's a very trivial part of the overall problem I'm trying to solve.
I'm applying to work at ITA Software; part of their application process involves having potential employees solve one of these problems.
I *desperately* want to work at a place that wants people who can solve that sort of problem. :) The "Word Rectangle" problem is the one I'm trying to solve. I'm systematically attacking it trying rectangles decreasing area.
My Google searches on some of the problem topics lead me to thisThat gave me enough of an idea for me to hack up a quick and dirty trie-sort-of thing in Perl and start playing with (what I hope) are some clever ideas for solving the problem
( ... )
Comments 3
Well, what exactly do you mean by "smart"? You're arrays are bounded by the square of the max size of a word in the dictionary; how big *is* that? If it isn't that big, there's no point in developing a "smart" algorithm; any time saved will be vastly offset by how long it takes to get the algorithm correct in the first place, and if small enough, will not be noticeable anyway. Note that a stupid brute force algorithm *that fits in cache* will very likely beat out a clever algorithm that doesnt fit in cache.
If you really want to do this example, just because this particular mountain is there, I'd point out that you *already know* the sorted order of the array areas; they are just the set of integers from 1 to (max word size)^2.
Step 1: Generate the set of possible factors, from the list of prime numbers <= max_word_size.
Step 2: For each number N, 1 < N < max_word_size^2, list out all of it's ( ... )
Reply
I'm applying to work at ITA Software; part of their application process involves having potential employees solve one of these problems.
I *desperately* want to work at a place that wants people who can solve that sort of problem. :) The "Word Rectangle" problem is the one I'm trying to solve. I'm systematically attacking it trying rectangles decreasing area.
My Google searches on some of the problem topics lead me to thisThat gave me enough of an idea for me to hack up a quick and dirty trie-sort-of thing in Perl and start playing with (what I hope) are some clever ideas for solving the problem ( ... )
Reply
Reply
Leave a comment