[Haskell-cafe] What algorithm to use ?
manu
emmanuel.delaborde at citycampus.com
Mon Oct 22 04:09:20 EDT 2007
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
More information about the Haskell-Cafe
mailing list