Winner Paulo Uribe (dm1)

Finish 2004-04-28 09:00:00 UTC

lm55

by Paulo Uribe

Status: Passed
Results: 1.683%
CPU Time: 10.5532
Score: 19.2154
Submitted at: 2004-04-22 11:55:21 UTC
Scored at: 2004-04-22 12:22:32 UTC

Current Rank: 1772nd

Comments
Please login or create a profile.
Code
function d = solver(map,n)
[x,y]=size(map);
d = zeros(x,y);
s=sum(map(:))/n;
ovidx=1;
dir=0;
ndir=0;
%Find single districts
[h,l]=find(map>=s);
idx=1;
lh=length(h);
if lh>0,
  for idx=1:lh
    d(h(idx),l(idx))=idx;
  end
  idx=idx+1;
end

%Find high density districts
map1=map;
map1(d>0)=0;
[h,l]=find(map1>=s*.55);
lh=length(h);
if lh>0,
 for idxc=1:min(lh,n-1)
  nn=1;
  hh=h(idxc);
  ll=l(idxc);
 if d(hh,ll)==0
  d(hh,ll)=idx;
  pos=[];
  ss=sum(map(find(d==idx)));
  if (hh > 1) & d(hh-1,ll)==0    %up
      er=ss+map(hh-1,ll)-s;
      pos=[pos [1 0 er]'];
      if (hh > 2) & d(hh-2,ll)==0    %up
         pos=[pos [1 1 er+map(hh-2,ll)]'];
      end
      if (ll < y) & d(hh-1,ll+1)==0    %right
         pos=[pos [1 2 er+map(hh-1,ll+1)]'];   
      end
      if(ll > 1) & d(hh-1,ll-1)==0     %left
         pos=[pos [1 4 er+map(hh-1,ll-1)]'];   
      end         
  end
  if (ll > 1) & d(hh,ll-1)==0    %left
      er=ss+map(hh,ll-1)-s;     
      pos=[pos [4 0 er]'];     
      if (hh > 1) & d(hh-1,ll-1)==0    %up
         pos=[pos [4 1 er+map(hh-1,ll-1)]'];
      end
      if (ll > 2) & d(hh,ll-2)==0    %left
         pos=[pos [4 4 er+map(hh,ll-2)]'];   
      end
      if(hh < x) & d(hh+1,ll-1)==0     %down
         pos=[pos [4 3 er+map(hh+1,ll-1)]'];   
      end   
  end
  if(ll < y) & d(hh,ll+1)==0     %right
      er=ss+map(hh,ll+1)-s;       
      pos=[pos [2 0 er]'];      
      if (hh > 1) & d(hh-1,ll+1)==0    %up
         pos=[pos [2 1 er+map(hh-1,ll+1)]'];
      end
      if (ll < y-1) & d(hh,ll+2)==0    %right
         pos=[pos [2 2 er+map(hh,ll+2)]'];   
      end
      if(hh < x) & d(hh+1,ll+1)==0     %down
         pos=[pos [2 3 er+map(hh+1,ll+1)]'];   
      end        
  end
  if (hh < x) & d(hh+1,ll)==0    %down
      er=ss+map(hh+1,ll)-s;
      pos=[pos [3 0 er]'];
      if (hh < x-1) & d(hh+2,ll)==0    %down
         pos=[pos [3 3 er+map(hh+2,ll)]'];
      end
      if (ll > 1) & d(hh+1,ll-1)==0    %left
         pos=[pos [3 4 er+map(hh+1,ll-1)]'];   
      end
      if(ll < y) & d(hh+1,ll+1)==0     %right
         pos=[pos [3 2 er+map(hh+1,ll+1)]'];   
      end          
  end
  if ~isempty(pos)
      pos=[pos [0 0 ss-s]'];
      [mn,mp]=min(abs(pos(3,:)));
      if pos(1,mp)==1
          hh=hh-1;
      elseif pos(1,mp)==2
          ll=ll+1;
      elseif pos(1,mp)==3
          hh=hh+1;
      elseif pos(1,mp)==4
          ll=ll-1;
      end
      if pos(1,mp)~=0      
        d(hh,ll)=idx;
      end
      if pos(2,mp)==1
          hh=hh-1;
      elseif pos(2,mp)==2
          ll=ll+1;
      elseif pos(2,mp)==3
          hh=hh+1;
      elseif pos(2,mp)==4
          ll=ll-1;
      end
      if pos(2,mp)~=0
          d(hh,ll)=idx;
      end
%      d(pos(1,mp),pos(2,mp))=idx;
  end  
 
  idx=idx+1;
end 
 end

end

while(idx<=n)
  [a,b] =find(~d);
  j=1;
  if isempty(a)
    %Could not allocate all
    %For now just take away from other districts
    n1=n-idx+1;
    for idxc=1:min(n1,ovidx-1)    
      [a,b]=find(d==ov(idxc));
      d(a(1),b(1))=idx;
      idx=idx+1;
    end
    if idx<=n
     [a,b] =find(~d);
      if isempty(a)
        %Could not allocate all
        %For now just take away from other districts
        n1=n-idx+1;
        for idxc=1:n1
          d(idxc) = idx;
          idx=idx+1;
        end  
      end
     end
else    

 while(j~= 0)
   aa = a(j);
   bb = b(j);
   j = j-1;
   d(aa,bb) = idx;
   if dir~=1
   %move right
   if (bb < y) & d(aa,bb+1)==0
      j = j+1;
      a(j) = aa;
      b(j) = bb+1;
   end
   
   %move up
   if (aa > 1) & d(aa-1,bb)==0
      j = j+1;
      a(j) = aa-1;
      b(j) = bb;
   end
   end
   

   %move down
   if (aa < x) & d(aa+1,bb)==0
      j = j+1;
      a(j) = aa+1;
      b(j) = bb;
   end
   %move left
   if (bb > 1) & d(aa,bb-1)==0
      j = j+1;
      a(j) = aa;
      b(j) = bb-1;
      if bb==1
        ndir=1;
      end
   end
   
   if dir==1
   %move right
   if (bb < y) & d(aa,bb+1)==0
      j = j+1;
      a(j) = aa;
      b(j) = bb+1;
   end
   %move up
   if (aa > 1) & d(aa-1,bb)==0
      j = j+1;
      a(j) = aa-1;
      b(j) = bb;
      if aa==1
        ndir=0;
      end    
    end
   end
   dir=ndir;

   if idx<n
     if sum(map(find(d==idx)))>=s
       if sum(map(find(d==idx)))-s>map(aa,bb)/1.95
          d(aa,bb)=0;
       else
          ov(ovidx)=idx;
          ovidx=ovidx+1;
       end
       break
     end
   end
 end
end
if j==0
    ild=find(d==idx);
    if sum(map(ild))<.5*s
        d(ild)=-1;
    else
        idx=idx+1;
    end
else
idx=idx+1;
end
end

d(find(d==-1))=0;

[a,b] =find(~d);
while ~isempty(a)
    %Could not allocate all
    %For now just attach unresolved locations to nearest district
 for j=1:length(a)
   aa = a(j);
   bb = b(j);
   idx=0;   
   if (aa > 1) & d(aa-1,bb)~=0        %get up
      idx=d(aa-1,bb);
   elseif (bb > 1) & d(aa,bb-1)~=0    %get left
      idx=d(aa,bb-1);
   elseif(bb < y) & d(aa,bb+1)~=0     %get right
      idx=d(aa,bb+1);      
   elseif (aa < x) & d(aa+1,bb)~=0    %get down
      idx=d(aa+1,bb);
   end
   d(aa,bb)=idx;
  
 end
 [a,b] =find(~d);
end