Finish 2000-03-27 00:00:00 UTC

SaltySearch

by Roger Stuckey

Status: Passed
Results: 99.9961
CPU Time: 13.659
Score: 51684.7
Submitted at: 2000-03-23 21:37:09 UTC
Scored at: 2000-03-23 21:38:57 UTC

Current Rank: 65th
Based on: Salt12 (diff)
Basis for: SaltySearch S2C3 (diff)
Basis for: SaltySearch S3C2 (diff)
Basis for: SaltySearch S3C3 (diff)
...and 7 others.

Comments
Roger Stuckey
23 Mar 2000
Okay, so my SearchNDestroy times out ... I'll try combining it with Salt12 (current top-runner), since it performs worst (slowest) for a large number of samples.
Please login or create a profile.
Code
function Sequence = saltysearch(Segments)

[nSegs,lSegs] = size(Segments);

if nSegs>2
   Sequence = salt12(Segments,nSegs,lSegs);
else
   Sequence = snd2(Segments,nSegs,lSegs);
end


function Sequence = salt12(Segments,nSegs,lSegs)

[sums,is] = sort(Segments*rand(lSegs,1));
sums(nSegs+1) = 0;
Segments = Segments(is(diff(sums)~=0),:);
[nSegs, lSegs] = size(Segments);

theSegments = cell(nSegs, 1);

theSegs = 1:nSegs;
for index = theSegs,
   theSegments{index} = Segments(index,:);
end
copySegments = theSegments;

EndPart = 2-lSegs:0;
for matchLength = lSegs-1:-1:1
   Segments(:,1) = [];
   for leftSeg = theSegs
      Match = find(strncmp(Segments(leftSeg,:),copySegments,matchLength));
      if Match
         Select = Match(1);
         rightSeg = theSegs(Select);
         if rightSeg == leftSeg 
            if length(Match) > 1 % Rare case
               temp = Match(Match ~= Select);
               Select = temp(1);
               rightSeg = theSegs(Select); 
               
               theSegments{rightSeg} = [theSegments{leftSeg} theSegments{rightSeg}(1+matchLength:end)];
               i = find(theSegs == leftSeg);
               theSegs(i) = [];
               if length(theSegs) == 1 
                  Sequence = [theSegments{theSegs}];
                  return;
               end
               copySegments(Select) = copySegments(i);
               copySegments(i) = [];
            end
         else
            theSegments{rightSeg} = [theSegments{leftSeg} theSegments{rightSeg}(1+matchLength:end)];
            i = find(theSegs == leftSeg);
            theSegs(i) = [];
            if length(theSegs) == 1 
               Sequence = [theSegments{theSegs}];
               return;
            end
            copySegments(Select) = copySegments(i);
            copySegments(i) = [];
         end
      end
   end
   EndPart(1) = [];   
end
Sequence = [theSegments{theSegs}];


function sequence = snd2(Segments,nSegs,lSegs)

ncmp = 2;

for i = 1:nSegs
   subSegs{i} = Segments(i,:);
end

SubSegs = searchsegs(subSegs,ncmp);

SubSegsLen = size(SubSegs,2);

segLen = zeros(1,SubSegsLen);
for k = 1:SubSegsLen
   segLen(k) = size(SubSegs{k},2);
%   fprintf('%3d\n',segLen(k))
end

[tmp,mini] = min(segLen);

sequence = SubSegs{mini};


function SubSegs = searchsegs(subSegs,ncmp)

nsegs = size(subSegs,2);

if nsegs == 2
   SubSegs = seqcmp(subSegs{1},subSegs{2},ncmp);
   return
end

SubSegs = {};

k = 0; z = ones(1,nsegs);
for j = 1:nsegs-1
   for i = j+1:nsegs
      ztmp = z; ztmp([i,j]) = 0;
      subSegs2 = seqcmp(subSegs{i},subSegs{j},ncmp);

      for k = 1:size(subSegs2,2)
         SubSegs = [ SubSegs,searchsegs([subSegs2(k),subSegs(find(ztmp))],ncmp) ];
      end
   end
end


function subSeg = seqcmp(seq,seg,ncmp)

nseq = size(seq,2); nseg = size(seg,2);

nss = [nseq,nseg]; [mins,mini] = min(nss,[],2);

s = 0;
if ~isempty(findstr(seq,seg))
   s = 1;
   if mini == 1
      subSeg{s} = seg; subSegLen(s) = nseg;
   else
      subSeg{s} = seq; subSegLen(s) = nseq;
   end

   if ncmp == s, return, end
end

for i = mins-1:-1:1 % assume mins > 1
   omi = 1-i;
   if strncmp(seq(end+[omi:0]),seg,i)
      s = s+1;
      subSeg{s} = [seq(1:end+omi-1),seg];
      subSegLen(s) = nseq+omi-1+nseg;

      if ncmp == s, [tmp,subSegn] = sort(subSegLen); subSeg = subSeg(subSegn); return, end
   end
end

for i = nseq+nseg-mins+[1:mins-1]
   omi = 1-(nseq+nseg-i);
   if strncmp(seq,seg(end+[omi:0]),nseq+nseg-i)
      s = s+1; 
      subSeg{s} = [seg(1:end+omi-1),seq];
      subSegLen(s) = nseg+omi-1+nseq;

      if ncmp == s, [tmp,subSegn] = sort(subSegLen); subSeg = subSeg(subSegn); return, end
   end
end

s = s+1; subSeg{s} = [seq,seg]; subSegLen(s) = nseq+nseg;
if ncmp == s, [tmp,subSegn] = sort(subSegLen); subSeg = subSeg(subSegn); return, end

s = s+1; subSeg{s} = [seg,seq]; subSegLen(s) = nseg+nseq;

[tmp,subSegn] = sort(subSegLen); subSeg = subSeg(subSegn);