Hello I am not sure it is appropriate to post to this mailing list to inquire about a peculiar algorithm, if not let me know... I was looking at one particular puzzle posted on the Facebook site, 'Wiretaps' (http://www.facebook.com/jobs_puzzles/?puzzle_id=11). Briefly, you have 26 programmers (numbers 1 to 26) which need to be assigned a job (a name to decode). Even numbered programmers spend 1.5 hours more per vowel. Odd ones spend 1 hour more per consonant. And finally, each programmer whose number share primes factors with the length of the name to decode, spend 2 hours extra per factor (For example, it takes programmer 12 -- factors of 2 and 3 -- an extra 4 hours to decode 'NORMAN') The point is to come up with the combination of (programmer, name) which minimizes the time taken overall. Now the simplest solution, conceptually, is calculating the time taken by each combination, and pick the fastest... However looking at the number of permutations (26! = 403291461126605635584000000), quickly dampened my enthusiasm... There must be some algorithm (dynamic programming ?), that cuts down the number of calculations involved in order to find the right combination. But I cannot identify the proper algorithm to use... Can someone give me a tip ? Can some of the computations be parallelized ? (it's not an assignment, nor will I send anything to Facebook, I am just trying this out of curiosity) Thank you
On Oct 22, 2007, at 4:09 , manu wrote:
However looking at the number of permutations (26! = 403291461126605635584000000), quickly dampened my enthusiasm...
There must be some algorithm (dynamic programming ?), that cuts down the number of calculations involved in order to find the right combination. But I cannot identify the proper algorithm to use...
Being that I'm lousy at algorithms, I'm sure someone else will come up with something far better... but it occurs to me that you have enough information to reorder the search space such that you're more likely to find a combination which beats most of the search space early in an exhaustive search. For example, combinations of even- length names and even-numbered programmers take a time hit of 2 hours right off the bat due to the common prime factor 2, so you can probably defer those until you've exhausted other possibilities; even more so for names with many vowels. And if you find a combination whose time is less than some combination of delays, you can immediately drop any possibility which incurs those delays. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
On 10/22/07, manu
Hello
I am not sure it is appropriate to post to this mailing list to inquire about a peculiar algorithm, if not let me know...
I was looking at one particular puzzle posted on the Facebook site, 'Wiretaps' (http://www.facebook.com/jobs_puzzles/?puzzle_id=11). Briefly, you have 26 programmers (numbers 1 to 26) which need to be assigned a job (a name to decode). Even numbered programmers spend 1.5 hours more per vowel. Odd ones spend 1 hour more per consonant. And finally, each programmer whose number share primes factors with the length of the name to decode, spend 2 hours extra per factor (For example, it takes programmer 12 -- factors of 2 and 3 -- an extra 4 hours to decode 'NORMAN')
The point is to come up with the combination of (programmer, name) which minimizes the time taken overall.
Now the simplest solution, conceptually, is calculating the time taken by each combination, and pick the fastest... However looking at the number of permutations (26! = 403291461126605635584000000), quickly dampened my enthusiasm...
There must be some algorithm (dynamic programming ?), that cuts down the number of calculations involved in order to find the right combination. But I cannot identify the proper algorithm to use...
Can someone give me a tip ? Can some of the computations be parallelized ?
(it's not an assignment, nor will I send anything to Facebook, I am just trying this out of curiosity)
Thank you
This is an instance of what is known as the assignment problemhttp://en.wikipedia.org/wiki/Assignment_problem-- to find a maximum/minimum weight perfect matching, given a weighted bipartite graph. It can be solved by the Hungarian Algorithmhttp://en.wikipedia.org/wiki/Hungarian_algorithm. You can also read about matchings http://en.wikipedia.org/wiki/Matching in general; there are also other algorithms than the Hungarian which might be somewhat less optimal but still fine for your purposes and perhaps easier to code. -Brent
On Mon, 2007-10-22 at 10:09 +0200, manu wrote:
Hello
I am not sure it is appropriate to post to this mailing list to inquire about a peculiar algorithm, if not let me know...
I was looking at one particular puzzle posted on the Facebook site, 'Wiretaps' (http://www.facebook.com/jobs_puzzles/?puzzle_id=11). Briefly, you have 26 programmers (numbers 1 to 26) which need to be assigned a job (a name to decode). Even numbered programmers spend 1.5 hours more per vowel. Odd ones spend 1 hour more per consonant. And finally, each programmer whose number share primes factors with the length of the name to decode, spend 2 hours extra per factor (For example, it takes programmer 12 -- factors of 2 and 3 -- an extra 4 hours to decode 'NORMAN')
The point is to come up with the combination of (programmer, name) which minimizes the time taken overall.
Now the simplest solution, conceptually, is calculating the time taken by each combination, and pick the fastest... However looking at the number of permutations (26! = 403291461126605635584000000), quickly dampened my enthusiasm...
There must be some algorithm (dynamic programming ?), that cuts down the number of calculations involved in order to find the right combination. But I cannot identify the proper algorithm to use...
Can someone give me a tip ? Can some of the computations be parallelized ?
(it's not an assignment, nor will I send anything to Facebook, I am just trying this out of curiosity)
I'd just write the problem in a constraint programming language and call it a day. One example is (a subset of) the Oz programming language.
participants (4)
-
Brandon S. Allbery KF8NH -
Brent Yorgey -
Derek Elkins -
manu