# Flagstone problem

5 messages
Open this post in threaded view
|

## Flagstone problem

 Hi,I've been looking at a "flagstone problem," where no two adjacentn-tuples can be identical. I solved the problem with Icon usingan array of stacks and was going to explore how to do it in Haskellwhen I saw another way to do it explained in the same text. Justcount the ones between the zeros in a(n) to get b(i), a non-repeatingsequence of zeros, ones, and twos. An a(n) is 0 if the number ofone 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             021 = 010101             1                                             222 = 010110             123 = 010111             0                                             024 = 011000             025 = 011001             1                                             226 = 011010             127 = 011011             0                                             128 = 011100             129 = 011101             0                                             030 = 011110             031 = 011111             1                    232 = 100000             133 = 100001             0                                             034 = 100010             0                                             135 = 100011             136 = 100100             0========= Here's my Haskell code ========import Data.Bitsimport Data.Listflagstone n =  foldl (++) "" (take n (map show (f \$ group [if even y then 0 else 1 | y <- [bitcount x  | x <- [20..]]])))bitcount :: (Integral t) => t -> tbitcount 0 = 0bitcount n = let (q,r) = quotRem n 2             in bitcount q + rf [] = []f ([0]:xs) = f xsf ([0,0]:xs) = 0 : f xsf ([1]:xs) = 1 : f xsf ([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 binarydigits in the binary representation of n. Define b(i) asthe number of a's between successive zeros as before.Then T = b(1) b(2) b(3) b(4) ... gives an infinitesequence of *seven* symbols with no repeats. (b) Writea routine to generate a sequence for seven colors ofbeads 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

_______________________________________________
[hidden email]
Open this post in threaded view
|

## Re: 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 [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: 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 <[hidden email]> wrote:From: Brent Yorgey <[hidden email]>Subject: Re: [Haskell-cafe] Flagstone problemTo: [hidden email]Date: Saturday, November 6, 2010, 7:03 AMOn 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 usingInteresting 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 asflagstone n = concat . take n . map show . f . group             . map (fromEnum . odd . bitcount) \$ [20..]You should never use foldl (++) as it is rather inefficient: you getthings like (((a ++ b) ++ c) ++ d) ... which ends up traversing theleft part of the list repeatedly.  And list comprehensions can be niceat 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 binaryrepresentation of n will not be zero very often... -Brent_______________________________________________Haskell-Cafe mailing listHaskell-Cafe@...http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
[hidden email]
Open this post in threaded view
|

## Re: Flagstone problem

 In reply to this post by Brent Yorgey-2 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 [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe