[Haskell-cafe] What algorithm to use ?
derek.a.elkins at gmail.com
Mon Oct 22 12:48:31 EDT 2007
On Mon, 2007-10-22 at 10:09 +0200, manu wrote:
> 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.
More information about the Haskell-Cafe