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 )

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```