[seqfan] Re: Sequence from buggy polyomino counter

[Allan Wechsler]

Thinking about this whole mess a little harder, I am having some confusion
about A007846. There must be at least one error in the description, or the
data, or both. Perhaps other Fanatics can help figure this out.

The sequence has three descriptions, claimed to produce the same data. The
first two descriptions are transparently equivalent. The comments section
presents the equivalence, but confusingly labels it, "Mapping between
Descriptions 1 and 3". I am pretty sure the commenter meant "... 1 and 2".

Description 3 is the problematical one. It says, "Number of connected
n-step paths on a rectangular lattice, diagonals or repeated steps not
allowed.". Presumably by "step" the authors meant that the path visits n
lattice sites; there is an indexing issue here. But regardless, I cannot
get any numbers other than (1?,1,4,12 ...) from this description. The first
move can go in any of four directions; the second is constrained to 3
(because it is not permitted to backtrack); and 4*3 is 12. I calculated
another couple of terms and found A001411 (Number of n-step self-avoiding
walks on square lattice). So: what is the purported difference between
description 3 and A001411?

In addition, the comments make it clear that description 3 was the
*original* description. I cannot find a mapping between the path
description (3) and the accretion descriptions (1,2).

Hand calculation confirms the data (1,4,24,176) for the accretion
description. I corrected my original program two ways, one to produce
A048664 (this correction worked) and one to produce the accretion
description of A007846. This second "correction" still has a bug, which I
haven't found yet, and insists that a(4) = 192. Perhaps Alex is right about
my multiply-counting the O's. I'll have to check more carefully.

On Sat, Dec 22, 2018 at 10:21 AM Allan Wechsler <acwacw at gmail.com> wrote:

> 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/
>>
>