[Haskell-cafe] Flagstone problem
michael rice
nowgate at yahoo.com
Thu Nov 4 13:50:06 EDT 2010
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20101104/72eacf71/attachment.html
More information about the Haskell-Cafe
mailing list