From: Ross Bamford <rossrt@...>
Date: 2006-03-30T16:37:47+09:00
Subject: Re: [QUIZ] B & E (#72)

On Thu, 2006-03-30 at 16:17 +0900, Timothy Bennett wrote:
> Hi, I wanted to discuss this problem from a more mathematical  
> perspective. Anyone that's interested, please comment on this, I'm  
> curious what others' thoughts are.
> 

(I'm not a mathematician (by any stretch of the word) so I may be
utterly wrong in all of this).

I think this problem is basically the shortest common superstring
problem:

http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK5/NODE209.HTM

Which is basically how my solution (and I think yours too) approached
it. The upshot is that it's easy to find a common superstring, and even
a reasonably short common superstring, but very difficult to find the
_shortest_ or determine how long it would be (it's NP complete I
think). 

That said, while working on it my limited mathematical knowledge kept
taunting me that there was a much easier way given that we were dealing
with numbers only, but I couldn't find it and gave up after a bit - I'd
love to see something like that done.

-- 
Ross Bamford - rosco@roscopeco.REMOVE.co.uk