[seqfan] Re: Sequence from buggy polyomino counter
Allan Wechsler
acwacw at gmail.com
Sat Dec 22 16:21:42 CET 2018
I'm still working on it! My first guess was the same as Alex Meiburg's, and
I am disappointed that this guess wasn't right. Now I think that the bug is
so goofy that the resulting sequence really isn't interesting. I'll reveal
what the program is actually doing at the end of this message.
Regarding the question of whether a buggy program can produce a worthwhile
sequence: of course it can. If the bug isn't syntactic, or cause the
program to die, and if what it does is at least deterministic, then the
sequence it produces is following *some* rule or other. The rule may not be
interesting, but on the other hand it might be! (In this case, I think my
error fails the interestingness test.)
The program was supposed to generate a list of order-n polyominoes by first
conducting an order-(n-1) census. The recursion bottomed out by producing a
list of the single monomino by fiat.
To produce the n list from the (n-1) list, it took each smaller polyomino
and extended it in every possible way, appending together the resulting
lists of extensions. Of course this new monster list would contain
duplicates, where the same polyomino could be produced by extending two
different smaller ones, so I intended to eliminate the duplicates by
discarding each polyomino that occurred later in the list, thus retaining
only the last representative of each equivalence class.
One bug was that I would only discard the *first* polyomino if it was
duplicated later. Polyominoes deeper in the list than the first element
would be safe from elimination. But this cannot be the whole story, because
this would predict that the first deviation from A007846 would be to be
short by one (because A007846 would not eliminate any). If anybody wants to
research this further, here is the code; the top level function is countp.
countp :: Int -> Int
countp = length . polys
app :: [[a]] -> [a]
app = foldl (++) []
polys :: Int -> [[(Int, Int)]]
polys 1 = [[(0,0)]]
polys n = (rmdups . app . map extensions . polys . pred) n
extensions :: [(Int, Int)] -> [[(Int, Int)]]
extensions poly = map (: poly) (filter (\x -> not (elem x poly)) (app (map
neighbors poly)))
neighbors :: (Int, Int) -> [(Int, Int)]
neighbors (x,y) = [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]
rmdups :: [[(Int, Int)]] -> [[(Int, Int)]]
rmdups [] = []
rmdups l@(p:ps) = if (finddup p ps) then ps else l
-- The problem is on the previous line, which should be
-- rmdups (p:ps) = if (finddup p ps) then (rmdups ps) else p:(rmdups ps)
-- With that change the code matches A048664 as far as it goes (which is to
about order 7)
finddup :: [(Int, Int)] -> [[(Int, Int)]] -> Bool
finddup _ [] = False
finddup p0 (p1:ps) = (duppoly p0 p1) || (finddup p0 ps)
duppoly :: [(Int, Int)] -> [(Int, Int)] -> Bool
duppoly p0 p1 = and (map (\x -> elem x p1) p0)
On Sat, Dec 22, 2018 at 8:45 AM Frank Adams-watters via SeqFan <
seqfan at list.seqfan.eu> wrote:
> There are only two ways a buggy program can *fail* to produce a "valid"
> sequence. The first is if it fails for some inputs, whether getting an
> error,
> returning a result of the wrong type, or failing the halting problem.
>
> The second is if it has portability problem - the only way I know of for
> the
> mathematical programing tools in use here to have such a problem is to
> convert a floating point number to an integer. For example, if one
> implemented A000196 as "floor(sqrt(n))", you might sometimes get
> a(n^2) = n-1. This would vary depending on the tool, the selected
> precision, and in some cases the specific computer.
>
> Otherwise, you will get a valid sequence.Whether that sequence is worthy
> of
> inclusion in the OEIS is another question. You need to determine what it
> actually is doing so that that can be assessed.
>
> Franklin T. Adams-Watters
>
>
> -----Original Message-----
> From: P. Michael Hutchins <pmh232 at gmail.com>
> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> Sent: Fri, Dec 21, 2018 9:50 am
> Subject: [seqfan] Re: Sequence from buggy polyomino counter
>
>
> Can a buggy program produce a valid sequence?
>
> Note that finding a different program to produce the same sequence would be
> hard to come by.
>
> On Fri, Dec 21, 2018 at 7:21 AM Alex Meiburg <timeroot.alex at gmail.com>
> wrote:
>
> > I initially wanted to guess that this was just double-counting based on
> the
> > *order* pieces were placed after the origin. The 1 and 4 terms agree
> either
> > way; when you get to 18, the two tiles are L (4 centered, 8 off) and I (2
> > centered, 4 off). The most likely explanation is that you'd treat the
> > polyomino (0,0) (1,0) (0,1) differently from (0,0) (1,0) (0,1) because of
> > the ordering. If your algorithm was successively laying down pieces to an
> > earlier stage, but not checking for multiple routes that might produce
> the
> > same shape, this would give 24.
> >
> > I checked with the next element though, and I found that this particular
> > mistake would give 176 for n=4. I ran this through the OEIS and this
> turns
> > out to be http://oeis.org/A007846 .
> >
> > I tried to reverse engineer your next term, then, the 192. This has an
> > additional excess of 16. Of the tetrominoes "with ordering" in the sense
> of
> > A007846, there are 16 I pieces, 64 L, 48 T, 32 S, and 16 O. If there was
> > one piece I would be suspicious of it would be O, given its unusual
> > topology. So maybe you're somehow counting O's double with the two ways
> you
> > can go "around" the O?
> >
> > Anyway, I hope the idea that you might be counting (0,0) (1,0) (0,1) and
> > (0,0) (1,0) (0,1) separately would be enough to find a mistake in your
> > program.
> >
> > In any case, trying to find out what your code is actually counting would
> > be a lot of fun -- and I'd bet good odds that it's counting *something*!
> > Maybe post your code? :)
> >
> > -- Alexander Meiburg
> >
> >
> > On Fri, Dec 21, 2018 at 3:39 AM Hugo Pfoertner <yae9911 at gmail.com>
> wrote:
> >
> > > Not very serious: My guess: 8*A279651 <http://oeis.org/A279651>(5) =
> > > 8*2232
> > > = 17856
> > >
> > > Hugo
> > >
> > > On Fri, Dec 21, 2018 at 5:20 AM Allan Wechsler <acwacw at gmail.com>
> wrote:
> > >
> > > > I was trying to sharpen my Haskell skills by writing a program to
> > compute
> > > > A048664, the number of different polyominos including the origin
> cell,
> > > > where rotations, translations, and reflections are considered
> distinct.
> > > >
> > > > I wrote the code, compiled it a couple of times to get the syntax
> > errors
> > > > out, and then tried it out. It has a bug. Instead of 1, 4, 18, 76,
> 315,
> > > it
> > > > produces 1, 4, 24, 192, 1856.
> > > >
> > > > My first impulse was: fix the darned bug! But then I thought: wait a
> > > > second, maybe OEIS can help me find the bug. So I searched for the
> > > programs
> > > > buggy output sequence.
> > > >
> > > > It's not in OEIS. Question: how much effort should I put into
> analyzing
> > > the
> > > > program's actual behavior? It might be doing something interesting
> that
> > > is
> > > > worth including. If anybody wants to try guessing, what's the next
> > > element?
> > > >
> > > > --
> > > > Seqfan Mailing list - http://list.seqfan.eu/
>
> > > >
> > >
> > > --
> > > Seqfan Mailing list - http://list.seqfan.eu/
> > >
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>
More information about the SeqFan
mailing list