[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