Finish 2012-11-07 16:00:00 UTC

LessTangledTrees2

by Greg S

Status: Passed
Results: 21822 (cyc: 22, node: 933)
CPU Time: 1.111
Score: 23055.0
Submitted at: 2012-11-01 19:44:48 UTC
Scored at: 2012-11-01 21:49:01 UTC

Current Rank: 1611th (Highest: 15th )

Comments
Please login or create a profile.
Code
function xyOut = solver(a, xyIn, wts)

dir = [1 0; 1 1; 0 1; -1 1; -1 0; -1 -1; 0 -1; 1 -1];
xyOut = xyIn;
aa = a;
wts=wts';

ZZ =[xyIn(:,1).*wts xyIn(:,2).*wts];
WC = sum(ZZ,1)/sum(wts);


g = zeros(200,200);  %grid of placed points

np = size(xyOut,1); 
d=zeros(np,1); %list of "done" points

sa = sum(a,1);    %sum of a rows, number of cons for each point
[nc,i] = min(sa);

xyOut = xyIn; %REMOVE
%place
cen = [1 50];
xyOut(i,:) = cen;
g(cen(1),cen(2)) = i;
d(i) = 1;
xp = 2;

p2 = find(a(i,:));

aaa = a(p2,p2);
ccnt=sum(aaa,1);
if sum(ccnt>0)
   %rearrange 
    [pp2] = rearrange(aaa,ccnt,a,p2);
    p2=pp2;
end


nn = length(p2);
yp = 50-2*floor(nn/2);
% mbow=ceil(nn/2)-1;
% if mod(nn,2) ==0
%      bow=[0:mbow, mbow:-1:0];
% else
%      bow=[0:mbow, (mbow-1):-1:0];
% end
% if nn>4,
%    bow(1) = bow(1)+1;
%    bow(end) = bow(end) + 1;
% end
mbow=4;

dd= d;
dd(p2) = 1;
cnt=0;
for i=p2
   cnt=cnt+1;
   %place
   q = a(:,i);
   qq = q & dd;
   nq = sum(q) - 2*sum(qq);
   if nq<-1 || (sum(q)==sum(qq));
       bow=0;
   elseif nq==-1
       bow=1;
   elseif nq==0
       bow=2;
   elseif nq==1
       bow=3;
   else
       bow=4;
   end
   
   xyOut(i,:) = [xp+bow yp];
   g(xp,yp) = i;
   d(i) = 1;
   yp=yp+2;
end
xp=xp+1+mbow;

dp = find(d);
aa(dp,dp) = 0;
sa = sum(aa,1);

lp = p2;
while ~isempty(lp)
    lpt=zeros(1,100);
    nn = 0;
    dd= d;
    dd(p2) = 1;
    for i=lp,
        t = sa(i);
        if t>0,  %are there any more points attached to this one, if not move on to next
            p2 = find(aa(i,:));
            aaa = a(p2,p2);
            ccnt=sum(aaa,1);
            if sum(ccnt>0)
                %rearrange
                [pp2] = rearrange(aaa,ccnt,a,p2);
                p2=pp2;
            end

            if ~isempty(find(d(p2)))
                %place these points first
            end
            c = find(triu(a(p2,p2),1));
            if ~isempty(c)
                %rearrange
            end

            for k=p2
                if isempty(find(lpt==k))
                    nn=nn+1;
                    lpt(nn) = k;
                end
            end
        end
    end

    yp = 50-2*round(nn/2);
    lpt=lpt(1:nn);
%    mbow=ceil(nn/2)-1;
%     if mod(nn,2) ==0
%         bow=[0:mbow, mbow:-1:0];
%     else
%         bow=[0:mbow, (mbow-1):-1:0];
%     end
%     if nn>4,
%         bow(1) = bow(1)+1;
%         bow(end) = bow(end) + 1;
%     end
% 
    cnt=0;
    for i=lpt
        cnt=cnt+1;
        %place
        q = a(:,i);
        qq = q & dd;
        nq = sum(q) - 2*sum(qq);
        if nq<-1 || (sum(q)==sum(qq));
            bow=0;
        elseif nq==-1
            bow=1;
        elseif nq==0
            bow=2;
        elseif nq==1
            bow=3;
        else
            bow=4;
        end
        xyOut(i,:) = [xp+bow yp];
        g(xp,yp) = i;
        d(i) = 1;
        yp=yp+2;
    end
    xp=xp+3+max(mbow,1);
    
    lp = lpt;
    dp = find(d);
    aa(dp,dp) = 0;
    sa = sum(aa,1);
    

end


off = [zeros(np,1) 50*ones(np,1)];
xyOut = xyOut-off;

ZZ2 =[xyOut(:,1).*wts xyOut(:,2).*wts];
WC2 = sum(ZZ2,1)/sum(wts);
OFF = round(WC2-WC);
off = [OFF(1)*ones(np,1) OFF(2)*ones(np,1)];

xyOut = xyOut-off;


%xyOut = xyIn;

end

function [pp2] = rearrange(aaa,ccnt,a,p2)
    pp2 = zeros(size(p2));
    nxt =1;
    dp2 = pp2; 
    [cc,ind]=sort(ccnt);
    for ii = 1:length(ind)
      if dp2(ind(ii))==0,  
          pp2(nxt) = p2(ind(ii));
          nxt = nxt+1;
          dp2(ind(ii)) = 1;
          done=0;
          lstpt = ind(ii);
          while~done
              if cc(ii) > 0
                  cpts = find(aaa(lstpt,:) & ~dp2);
                  if ~isempty(cpts)
                      pp2(nxt) = p2(cpts(1));
                      nxt = nxt+1;
                      dp2(cpts(1)) = 1;
                      lstpt = cpts(1);
                  else
                      done=1;
                  end
              else
                  done=1;
              end
          end
      end
    end
end