note
jepri
<B>Update:</b> A while ago I saw an absolutely fantastic piece of art on film. It was only a minute or two long. The artist had done some visual thing, but the highlight for me was that he/she had a person reading words that were joined together, similar to what I did to [MeowChow]s post below. It was always just on the edge of understandable. I think it was called 'Mouth Music'. Anyway, it rocked.<P>
Well, here's code that does some of what you want. What I would really like to see is a mathematical proof of the minimum number and length of sequences to get complete reconstruction of the thing you chopped up in the first place.<P>
Plus, when you golf, aren't you meant to post your own code for other people to play with? Maybe I should call homework on this :)<P>
Here are the results:<P>
<code>
logger,gerbil,log,analog,
Constructed sequence is analoggerbil
GATTACA,ATTACA,GATT,AAGAT,CCC,
Constructed sequence is gattacaagatt
Fragment,Reassembly,by,MeowChow,...
Constructed sequence is byoureassemblesuperstringolfednakasubstringsequencing
</code>
<P>
And here is the code that did it:
<P>
<code>
use strict;
sub assemble{
my @sequences = sort {length($b) <=> length($a)} @_;
&text_mangle($_) for @sequences;
my $a=shift @sequences;
my $b=shift @sequences;
while ( @sequences ) {
my $c=overlap($a,$b);
if ( defined($c) ) {
$a=$c;
#push @sequences,$b;
$b=shift @sequences;
}
else
{
push @sequences,$b;
$b=shift @sequences;
}
}
print "Constructed sequence is $a\n";
};
sub overlap{
my ($a,$b)=@_;
my ($i,$l);
if ($a=~/ / || $b=~/ / ) { die "Don't use spaces in your data!\n";}
$l=length($a);
for ($i=0;$i<$l; $i++ ) {
if ( substr($a,$i,$l-$i) eq substr($b,0,$l-$i) ) {
substr($a,$i,($l-$i))= $b;
return $a;
}
}
$l=length($b);
for ($i=0;$i<$l; $i++ ) {
if ( lc(substr($b,$i,$l-$i)) eq lc(substr($a,0,$l-$i)) ) {
substr($b,$i,($l-$i))= $a ;
return $b;
}
return undef;
};
sub text_mangle {
$_[0]=~s/ |\.|\,//g;
my $a=lc($_[0]);
$_[0]=$a;
}
sub swap {
my $a=$_[0];
$_[0]=$_[1];
$_[1]=$a;
}
my @array=qw(logger gerbil log analog);
foreach (@array) {print; print ",";};print "\n";assemble(@array);print "\n";
@array=qw(GATTACA ATTACA GATT AAGAT CCC);
foreach (@array) {print; print ",";};print "\n";assemble(@array);print "\n";
@array=qw(Fragment Reassembly by MeowChow
... aka DNA Sequencing or Shortest Common Superstring. Your mission, should you choose to accept it, is to design a golfed sforeach (@array) {print; print ",";};print "\n";assemble(@array);print "\n";
</code><p>____________________<BR>
Jeremy<BR>
I didn't believe in evil until I dated it.
77183
77183