Flagstone problem

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Flagstone problem

michael rice-3
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


 
                        


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Flagstone problem

Brent Yorgey-2
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
Reply | Threaded
Open this post in threaded view
|

Re: Flagstone problem

michael rice-3
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 problem
To: [hidden email]
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@...
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Flagstone problem

Alexander Solla-2
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
Reply | Threaded
Open this post in threaded view
|

Re: Flagstone problem

michael rice-3
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 <[hidden email]> wrote:

From: Alexander Solla <[hidden email]>
Subject: Re: [Haskell-cafe] Flagstone problem
To:
Cc: "haskell-cafe Cafe" <[hidden email]>
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@...
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe