Re: [Haskell-cafe] Flagstone problem
On Thu, Nov 04, 2010 at 10:50:06AM -0700, michael rice wrote: Hi, I've been looking at a flagstone problem, where no two adjacent n-tuples can be identical. I solved the problem with Icon using Interesting stuff! = Here's my Haskell code import Data.Bits import Data.List flagstone n = foldl (++) (take n (map show (f $ group [if even y then 0 else 1 | y - [bitcount x | x - [20..]]]))) By the way, I would write this as flagstone n = concat . take n . map show . f . group . map (fromEnum . odd . bitcount) $ [20..] You should never use foldl (++) as it is rather inefficient: you get things like (((a ++ b) ++ c) ++ d) ... which ends up traversing the left part of the list repeatedly. And list comprehensions can be nice at times, but personally using map seems clearer in this case. = My question A further exercise in the text: Exercise 5.-(a) Define a(n) as the sum of the binary digits in the binary representation of n. Define b(i) as the number of a's between successive zeros as before. Then T = b(1) b(2) b(3) b(4) ... gives an infinite sequence of *seven* symbols with no repeats. (b) Write a routine to generate a sequence for seven colors of beads on a string with no repeats. I may be misreading, but does this make any sense? Doesn't make much sense to me. The sum of binary digits in the binary representation of n will not be zero very often... -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Flagstone problem
Hi Brent, Efficiency aside, your code is definitely more readable. I flubbed that step from True/False to 0/1 using fromEnum. Haskell's grab bag has so many tools it's easy to omit one. Thanks, Michael --- On Sat, 11/6/10, Brent Yorgey byor...@seas.upenn.edu wrote: From: Brent Yorgey byor...@seas.upenn.edu Subject: Re: [Haskell-cafe] Flagstone problem To: haskell-cafe@haskell.org Date: Saturday, November 6, 2010, 7:03 AM On Thu, Nov 04, 2010 at 10:50:06AM -0700, michael rice wrote: Hi, I've been looking at a flagstone problem, where no two adjacent n-tuples can be identical. I solved the problem with Icon using Interesting stuff! = Here's my Haskell code import Data.Bits import Data.List flagstone n = foldl (++) (take n (map show (f $ group [if even y then 0 else 1 | y - [bitcount x | x - [20..]]]))) By the way, I would write this as flagstone n = concat . take n . map show . f . group . map (fromEnum . odd . bitcount) $ [20..] You should never use foldl (++) as it is rather inefficient: you get things like (((a ++ b) ++ c) ++ d) ... which ends up traversing the left part of the list repeatedly. And list comprehensions can be nice at times, but personally using map seems clearer in this case. = My question A further exercise in the text: Exercise 5.-(a) Define a(n) as the sum of the binary digits in the binary representation of n. Define b(i) as the number of a's between successive zeros as before. Then T = b(1) b(2) b(3) b(4) ... gives an infinite sequence of *seven* symbols with no repeats. (b) Write a routine to generate a sequence for seven colors of beads on a string with no repeats. I may be misreading, but does this make any sense? Doesn't make much sense to me. The sum of binary digits in the binary representation of n will not be zero very often... -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Flagstone problem
On Nov 6, 2010, at 4:03 AM, Brent Yorgey wrote: Doesn't make much sense to me. The sum of binary digits in the binary representation of n will not be zero very often... I think they mean the sum (mod 2) when they say the sum of binary digits. That should be zero half the time. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Flagstone problem
Hi, Alexander Your change produces the same sequence of 0s, 1s, and 2s. mod n 2 == fromEnum (even n) Michael --- On Sat, 11/6/10, Alexander Solla a...@2piix.com wrote: From: Alexander Solla a...@2piix.com Subject: Re: [Haskell-cafe] Flagstone problem To: Cc: haskell-cafe Cafe haskell-cafe@haskell.org Date: Saturday, November 6, 2010, 1:40 PM On Nov 6, 2010, at 4:03 AM, Brent Yorgey wrote: Doesn't make much sense to me. The sum of binary digits in the binary representation of n will not be zero very often... I think they mean the sum (mod 2) when they say the sum of binary digits. That should be zero half the time. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Flagstone problem
Hi, I've been looking at a flagstone problem, where no two adjacent n-tuples can be identical. I solved the problem with Icon using an array of stacks and was going to explore how to do it in Haskell when I saw another way to do it explained in the same text. Just count the ones between the zeros in a(n) to get b(i), a non-repeating sequence of zeros, ones, and twos. An a(n) is 0 if the number of one bits in the binary representation of n is even, otherwise odd, and the initial a(n) must be even. n a(n) b(i) 20 = 010100 0 21 = 010101 1 2 22 = 010110 1 23 = 010111 0 0 24 = 011000 0 25 = 011001 1 2 26 = 011010 1 27 = 011011 0 1 28 = 011100 1 29 = 011101 0 0 30 = 00 0 31 = 01 1 2 32 = 10 1 33 = 11 0 0 34 = 100010 0 1 35 = 100011 1 36 = 100100 0 = Here's my Haskell code import Data.Bits import Data.List flagstone n = foldl (++) (take n (map show (f $ group [if even y then 0 else 1 | y - [bitcount x | x - [20..]]]))) bitcount :: (Integral t) = t - t bitcount 0 = 0 bitcount n = let (q,r) = quotRem n 2 in bitcount q + r f [] = [] f ([0]:xs) = f xs f ([0,0]:xs) = 0 : f xs f ([1]:xs) = 1 : f xs f ([1,1]:xs) = 2 : f xs = My question A further exercise in the text: Exercise 5.-(a) Define a(n) as the sum of the binary digits in the binary representation of n. Define b(i) as the number of a's between successive zeros as before. Then T = b(1) b(2) b(3) b(4) ... gives an infinite sequence of *seven* symbols with no repeats. (b) Write a routine to generate a sequence for seven colors of beads on a string with no repeats. I may be misreading, but does this make any sense? There's a reference to The American Mathematical Monthly, June-July 1963, p. 675, by C. H. Braunholtz. Michael ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
