[Haskell-cafe] What algorithm to use ?

[Derek Elkins]

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.