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

HUGO102

by Kristoffer Lindstrom

Status: Failed
Results: []

Comments
Kristoffer Lindstrom
24 Mar 2000
I hope this doesn't time out...
Please login or create a profile.
Code
function Gene=HUGO102(Segments)
%Done, at last...
%I know that this can not compete with the top entries, but the idea
%has kept me occupied the last few days (and nights...)
%There is still a lot of tweaking to be done here, but there is
%unfortunatelly no time left in the contest.
%I specifically opted for a very clear and readable programming style
%in expense of speed, because the idea behind this algorithm is
%pretty involved...
%Try to read it and see what you make of it.
%
%Perfomance is not so good, but acceptable given the time limits...
%The main weakness I think lies in the fact that there is an exponential
%number of trees to choose from (see the function MatchSegments) and
%because of time considerations you are forced to pick only one.
%The other possibility is of course a bug of some kind....
%
%
%Kristoffer Lindstrom
%konst@math.chalmers.se


rand('state',100000);
Segments=unique(Segments,'rows');
Segments=uint8(Segments);

AggregateCell={};
SegLength=size(Segments,2);
RemainingSegments=[];
for MatchLength=SegLength-1:-1:1
   if ~isempty(Segments)
      %Match the segments 
      [AggregateSubCell,RemainingSegments]=MatchSegments(Segments,MatchLength);
      %Concatenate the old and new cell arrays
      AggregateCell={AggregateCell{:} AggregateSubCell{:}};
   end
   if ~isempty(AggregateCell)
      %Now match the aggregates
      AggregateCell=MatchAggregates(AggregateCell,MatchLength);
   end
   Segments=RemainingSegments;
end


Gene=[AggregateCell{:}];







%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [AggregateCell,RemainingSegments]=MatchSegments(Segments,MatchLength)
%This function takes as input a list of segments and a matching length
%and returns a cell array consisting of segment matchings that have maximal
%length + a list of unmatched segments. 

AggregateCell={};
NumberOfSegs=size(Segments,1);
DeleteNodes=zeros(NumberOfSegs,1);
SegTails=Segments(:,(end-MatchLength+1):end);
SegHeads=Segments(:,1:MatchLength);
Tree=zeros(1,NumberOfSegs);
%Find which pairs of segments match and build a tree
for EachSegment=1:NumberOfSegs
   Hit=all(repmat(SegTails(EachSegment,:),NumberOfSegs,1)==SegHeads,2);
   %Don't find yourself
   Hit(EachSegment)=0;
   Match=find(Hit);
   %The number of trees is too big. Pick a tree at random
   r=randperm(length(Match));
   if r
      Tree(Match(r(1)))=EachSegment;
   end
end
MaxComponents=MaxTreeComps(Tree);

for EachLeaf=find(MaxComponents)
   Node=EachLeaf;
   Aggregate=Segments(EachLeaf,:);
   DeleteNodes(EachLeaf)=1;
   %Trace the leaf back to the root
   for i=1:MaxComponents(EachLeaf)
      Node=Tree(Node);
      %Put together all the segments in the tree
      Aggregate=[Segments(Node,1:end-MatchLength) Aggregate];
      %Delete node from the list of segments
      DeleteNodes(Node)=1;
   end
   if ~isempty(Aggregate)
      AggregateCell={AggregateCell{:} Aggregate};
   end
end
RemainingSegments=Segments(~DeleteNodes,:);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function AggregateCellOut=MatchAggregates(AggregateCellIn,MatchLength)
%This function takes as input a cell array of aggregates and a matching length
%and returns a cell array consisting of aggregate matchings that have maximal
%length.
%This is actually just a copy of the function MatchSegments, with the
%nessesary modifications to make work for cell arrays


AggregateCellOut=AggregateCellIn;
AggregateCell={};
NumberOfSegs=length(AggregateCellIn);
DeleteNodes=zeros(NumberOfSegs,1);
for EachCell=1:NumberOfSegs
   SegTails(EachCell,:)=AggregateCellIn{EachCell}(:,end-MatchLength+1:end);
   SegHeads(EachCell,:)=AggregateCellIn{EachCell}(:,1:MatchLength);
end
Tree=zeros(1,NumberOfSegs);
%Find which pairs of segments match and build a tree
for EachSegment=1:NumberOfSegs
   Hit=all(repmat(SegTails(EachSegment,:),NumberOfSegs,1)==SegHeads,2);
   %Don't find yourself
   Hit(EachSegment)=0;
   Match=find(Hit);
   %The number of trees is too big. Pick a tree at random
   r=randperm(length(Match));
   if r
      Tree(Match(r(1)))=EachSegment;
   end
end
MaxComponents=MaxTreeComps(Tree);

for EachLeaf=find(MaxComponents)
   Node=EachLeaf;
   Aggregate=AggregateCellIn{EachLeaf};
   DeleteNodes(EachLeaf)=1;
   %Trace the leaf back to the root
   for i=1:MaxComponents(EachLeaf)
      Node=Tree(Node);
      %Put together all the segments in the tree
      %Aggregate=[Segments(Node,1:end-MatchLength) Aggregate];
      Aggregate=[AggregateCellIn{Node}(1:end-MatchLength) Aggregate];
      %Delete node from the list of segments
      DeleteNodes(Node)=1;
   end
   if ~isempty(Aggregate)
      AggregateCell={AggregateCell{:} Aggregate};
   end
end
RemainingAggregates=AggregateCellIn(~DeleteNodes);
AggregateCellOut={AggregateCell{:} RemainingAggregates{:}};
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [MaxComponents,IsARoot]=MaxTreeComps(Tree)
%Calculates MaxComponents which is a vector of tree nodes s.t. node i
%is a leaf and MaxComponents(i) is the height of the tree with leaf i.
%The leafs are guaranteed not to belong to the same connected component.

TreeLength=length(Tree);

IsARoot=~Tree;
Parents=Tree;
Parents(~Parents)=TreeLength+1;
IsALeaf=ones(1,TreeLength+1);
IsALeaf(Parents)=zeros(1,TreeLength);
IsALeaf(end)=[];
LeafHeights=zeros(1,TreeLength);
Leaf2Root=zeros(1,TreeLength);
%For each leaf, find its root and height
for EachLeaf=find(IsALeaf)
   NodeIndex=EachLeaf;
   Height=0;
   TempTree=Tree;
   TempIndex=[];
   %Backpropagate from a leaf until you reach a root or a cycle
   while TempTree(NodeIndex)
      Height=Height+1;
      TempIndex=NodeIndex;
      NodeIndex=TempTree(NodeIndex);
      %Delete every visited node to avoid cycles
      TempTree(TempIndex)=0;
   end
   LeafHeights(EachLeaf)=Height;
   if IsARoot(NodeIndex)
   else
      IsARoot(TempIndex)=1;
   end
   Leaf2Root(EachLeaf)=NodeIndex;
end

MaxComponents=zeros(1,TreeLength);
for EachRoot=find(IsARoot)
   %Find the leafs that have the same root
   ConnectedComponent=find(Leaf2Root==EachRoot);
   %Among these, find the leaf with the maximum height
   ComponentHeights=zeros(1,TreeLength);
   ComponentHeights(ConnectedComponent)=LeafHeights(ConnectedComponent);
   [MaxHeight,MaxLeaf]=max(ComponentHeights);
   %These are the leafs with the maximum height that belong to different components
   MaxComponents(MaxLeaf)=MaxHeight;
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%