Monday, March 31, 2008

Finger Exercises

Wow. Three months, no update. Hm.

I've been working on a bunch of little projects recently that individually don't amount to much, yet. I should have something to post about that soon.

In the mean time, here is a cute little problem (via Uri to the fun with Perl list):

What is an easy way to get all possible combinations of Y/N of length 5? (i.e., "YYYYY", "YYYYN", etc.)

Coming up with a solution to this exact problem seemed to cry out for a list comprehension:

[[a,b,c,d,e] | let l <- "YN", 
a <- l, b <- l, c <- l, d <- l, e <- l]

but as soon as I wrote that, I saw how unsatisfactory it was. A better solution would produce all possible combinations of Y and N for a list of any integer n > 0:

yn i = (iterate f [""]) !! i
where f l = map ('Y':) l ++ map ('N':) l

This problem itself isn't very interesting, but it's good to have little diversions like this when you want to take a break while the coffee is steeping, waiting for the Guinness to settle, or whatnot. (Something that's more than a function from the Prelude, but less involved than something from Project Euler.)

Do you have any cute little "finger exercise" problems like these? I'd love to hear about them!

19 comments:

Anonymous said...

Hi,

"What is an easy way to get all possible combinations of Y/N of length 5?"

A shorter solution:

> sequence $ replicate 5 "YN"

Peter

Anonymous said...

ghci> :m +Control.Monad
ghci> replicateM 5 "YN"

I like writing little lambda-calculus interpreters. It's not too difficult but lets you stretch your mind, and there's always a hook for whatever new technique you are trying to understand.

Christophe Poucet said...

Here's a somewhat cleaner solution"

yn 0 = [""]
yn n = return (:) `ap` "YN" `ap` yn (n-1)

Anonymous said...

r 0 = [[]]
r k = [a:x | a<-"yn", x<-r (k-1)]

main = print $ r 5

Anonymous said...

It's almost a prelude function: either Control.Monad.replicateM 5 "YN" or sequence (replicate 5 "YN")

Luke Palmer said...

Here's another implementation of yn:

yn i = sequence (replicate i "YN")

Which is about as good as I can see in "Haskell golf" (which is like Perl golf except you're going for the least inelegance). That's a bad solution though, because the tails vary faster than the heads, and thus there is no sharing (watch "length (yn 500)" eat up all your memory!). This is better:

sequence' [] = return []
sequence' (m:ms) = do {
xs <- sequence' ms;
x <- m;
return x;
}
yn i = sequence' (replicate i "YN")

It's really interesting to me that the "head-recursive" version has better performance after we've all learned to prefer tail recursion.

My favorite finger exercises recently have been dynamic programming exercises, such as:

http://projecteuler.net/index.php?section=problems&id=15
http://projecteuler.net/index.php?section=problems&id=67

Unknown said...

Even easier:

yn = flip replicateM $ "YN"

Neil Mitchell said...

The answer: sequence $ replicate 5 "YN"

bd_ said...

Somewhat of a more clever way to do it (IMO):

Prelude Control.Monad Data.List> replicateM 5 "YN"
["YYYYY","YYYYN","YYYNY","YYYNN","YYNYY","YYNYN","YYNNY","YYNNN","YNYYY","YNYYN","YNYNY","YNYNN","YNNYY","YNNYN","YNNNY","YNNNN","NYYYY","NYYYN","NYYNY","NYYNN","NYNYY","NYNYN","NYNNY","NYNNN","NNYYY","NNYYN","NNYNY","NNYNN","NNNYY","NNNYN","NNNNY","NNNNN"]

Unknown said...

Here is a fun relatively simple problem that actually appeared in a real program for me a few years ago:
Generate all unique lists of N positive integers whose sum is equal to M or equivalently Generate all unique ways to place M identical balls in N different buckets as I like to think about it.
For example with M = 3 and N = 3 it should give (in any order): [[0,0,3], [0,1,2], [0,2,1], [0,3,0], [1,0,2], [1,1,1], [1,2,0], [2,0,1], [2,1,0], [3,0,0]]
Writing a recursive function that solved this was pretty easy, but I suspect it can be written as a oneliner by someone with better Haskell-Fu than me. :)
Happy hacking.

Anonymous said...

replicateM 5 "YN"

tromp said...

a simpler way to do this in Haskell is:

mapM (const "FT") [1..5]

-John

tromp said...

shorter yet is

replicateM 5 "FT"

-John

Anonymous said...

Any time you need combinations, think sequence in the List monad:

yn i = sequence (replicate i "YN")

Cheers,
Tom

Anonymous said...

You mean

sequence $ replicate 5 "YN"

Kevin Reid said...

On that particular problem: any "all possible x" problem leads me to the list monad; in this case, a 'dynamic' version of your list comprehension:

sequence (replicate 5 "YN")

Spencer Janssen said...

I have a favorite solution to this problem:

yn i = replicateM "YN" i

Understanding this solution is a worthy exercise on its own.

Brent said...

What's wrong with 'replicateM 5 "YN"' ? =)

bd_ said...

@Tirpen, it's not the most efficient way to do it, but here's a oneliner anyway:

ways n m = filter ((== m).sum) $ replicateM n [0..m]