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 = 011110 0 31 = 011111 1 2 32 = 100000 1 33 = 100001 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
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
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
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
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.
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
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
participants (3)
-
Alexander Solla -
Brent Yorgey -
michael rice