P is for Practical | |
PerlMonks |
Egyptian fractionsby jimt (Chaplain) |
on Aug 24, 2006 at 17:51 UTC ( [id://569404]=obfuscated: print w/replies, xml ) | Need Help?? |
Probably not my best obfuscation, but I'm proud of some parts of it. Takes a fraction as an argument and returns the egyptian fraction for that number. For example:
Since I know people like to know how these things work, I'll explain it. First, as always, we'll re-format to pretty it up.
The first function is arbitrarily named 'egypt' to make it blend it. It returns the prime factorization of whatever number is passed into it. I'm fairly proud of this one.
We initialize an arbitrary variable ($f) to 2 (smallest possible divisor), then, as long as the number we've passed in is > 1, check to see if it's divisible by $f. If it is, then return a list starting with $f and appending the recursed prime factorization of the number / $f. Note that we post increment $f to let us jump up to the next number (if the modulus is nonzero), so we pre-decrement it before returning so we actually have the one that was the divisor.
The next block does the algorithm to find egyptian fractions, as defined up in that wikipedia link. It just calls the pharaoh function with the LCD fraction and displays the results. Simple.
The hiero function just reduces a numerator & denominator to lowest terms. It's easy. First, we set up some hashes. Next, we populate the prime factorization of the numerator and denominator into each hash, using the number of appearances of the number as the value. So the prime factorization of 8 is 2,2,2, and we end up with 2 => 3 in our hash. Then simply loop over the keys in the numerator hash. If that key exists in the denominator hash, then delete from the opposite hash the number of times the value occurs for you. For example, if you passed in 4/8, you'd end up with 2 => 2 in the numerator hash and 2 => 3 in the denominator hash. 2 is in both, so we subtract 3 from the numerator hash's value and 2 from the denominator hash's value, ending up with 2 => -1 in the numerator hash and 2 => 0 in the denominator hash. This ensures that any common factors are removed from the numerator and denominator. Next, all we need to do is map out the factors and repeat them the number of times they appear in the hash. So 2 => 3 turns into (2,2,2). We toss on a 1 to this list to avoid errors when there are no factors left. Then we just join those lists with asterisks and eval 'em, yielding the LCD.
pharaoh here is where the magic is. It takes a numerator and denominator as arguments, then recursively builds up the list of unit fractions to return. First of all, if the numerator is 1, then return numerator / denominator (we're done). Otherwise, we apply the algorithm and return a list consisting of int( 1 / (denominator / numerator) ) + 1, and the result of calling pharaoh on the LCD form of the fraction minus the value we just calculated. Further explanation is left as an exercise to the reader, but I'd recommend assigning this (int($_1 / $_[0]) + 1) to a variable and replacing in the function, it'll be clearer.
Back to
Obfuscated Code
|
|