Finish 2006-12-06 09:00:00 UTC

General Tastic

by Jonathan Hogg

Status: Passed
Results: 12364.3
CPU Time: 12.6708
Score: 123.648
Submitted at: 2006-12-06 13:15:10 UTC
Scored at: 2006-12-06 13:30:29 UTC

Current Rank: 238th
Based on: rotsolver++ 3.0 (diff)
Basis for: General ity (diff)

Comments
Jonathan Hogg
06 Dec 2006
Resubmission for general competition
Please login or create a profile.
Code
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function solution = solver(n)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   solution=-ones(n);
   B=-ones(4*n,1);
   V=B;
   for desp = 0:2
      for rot = [1 6 4 2 7 5 0]
         solution = rotsolver(rot);
         if(done || all(all(solution>=0)))
            solution = max(0,solution);
            return
         end
      end
   end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   function sol = rotsolver(rot)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      solution = ira(solution,rot);
      done = false;
      dj = 130;
      [r,c,s] = mb(1,0,0,rot);
      if solution(1,1)<0 && r==0 && c==0 % If absorbed
         [r1,c1,s1] = mb(0,1,0,rot);
         if (r1==0 && c1==0) % If absorbed
            [r2,c2,s2] = mb(2,0,0,rot);
            if (r2==2 || (r2==0 && c2==0)) % If absorbed, or reflected
               [r3,c3,s3] = mb(0,2,0,rot);
               if (c3==2 || (r3==0 && c3==0)) % If absorbed, or reflected
                  if(desp>=1 && r2==2 && c3==2 && s2==s3)
                     solution(1,1) = s2;
                     mb(1,0,1,rot);
                  elseif (desp>=2 && (r2 == 2 || c3 == 2))
                     mb(1,0,1,rot);
                     if r2 == 2 && c3==2
                        solution(1,1) = min(s2,s3);
                     else
                        solution(1,1) = max(s2,s3);
                     end
                  elseif(desp>=2)
                     % I'm not convinced that beaming actually helps here -jhogg
                     mb(1,0,1,rot,n);
                     [r4,c4,s4] = mb(2,0,0,rot);
                     [r5,c5,s5] = mb(0,2,0,rot);
                     solution(1,1) = max(1,max(s2-s4,s3-s5));
                  else
                     sol = ra(solution,rot);
                     return;
                  end
               end
            end
         end
      end
      solution(1,1) = max(0,solution(1,1));
      [r,c,s] = mb(1,0,0,rot);
      while(~(r==-1 && c==0)) % While we've not appeared out the other side
         if(r==0 && c==0) % If we've been absorbed
            if(desp>=1)
               fnd = 0;
               for tc=1:n-1;
                  if(solution(1,tc+1)>=0)
                     continue;
                  end
                  [r,c,s] = mb(0,tc,0,rot);
                  if(~(r==0 && c==0)) % If not absorbed
                     solution(1,tc) = max(0,solution(1,tc));
                  end
                  if(r==0 && c==tc && (desp>=2 || s<= dj))
                     [r1,c1,s1] = mb(0,c+1,0,rot);
                     if(c+2<=n)
                        [r2,c2,s2] = mb(0,c+2,0,rot);
                     else
                        r2=0;c2=0;s2=0;
                     end
                     if((r1==0 && c1==0) && ...
                           ((c+2<=n && c2==c+2 && s2==s) || ...
                           (desp>=2 && (c+2>n || c2==c+2 || ...
                           (r2==0 && c2==0 && solution(1,c+2)~=0)))));
                        fnd=1;
                        solution(1,c+1) = s;
                        mb(0,c+1,1,rot);
                        break
                     end
                  end
               end
               if(~fnd)
                  sol = ra(solution,rot);
                  return
               end
            else
               sol = ra(solution,rot);
               return
            end
         else
            solution(2,c+1) = s;
            if(c+1<n)
               [r1,c1,s1] = mb(0,c+1,0,rot);
               if(r1 == 0 && c1 == c+1)
                  solution(1,c+2) = s1;
                  mb(0,c+2,1,rot);
               end
            end
            mb(0,c+1,1,rot);
            solution(1,1:min(n,c+2)) = max(0,solution(1,1:min(n,c+2)));
         end
         [r,c,s] = mb(1,0,0,rot);
      end
      nn = n;
      [r,c,s] = mb(nn,0,0,rot);
      while(r==-nn && c==0 && s==0 && nn>1)
         nn = nn-1;
         [r,c,s] = mb(nn,0,0,rot);
      end
      nn = nn-1;
      if(nn==n-1)
         nn=n+1;
      end
      j = 2;
      couo = -1;
      couu = -1;
      while j < nn-2
         if nn<n
            if couo == -1
               couo = 0;
               ro = zeros(n,1);
               [rn,cn,sn] = mb(j,0,0,rot);
               while rn >= 0 % ie while not getting thorugh
                  couo = couo + sn;
                  ro(cn+1) = sn;
                  if cn+2 > n
                     break
                  end
                  [rn,cn2,sn] = mb(0,cn+2,0,rot);
                  if (rn+cn2) == 0 % ie absorbed
                     cn = cn + 1;
                     sn = -1;
                  else
                     cn = cn2;
                  end
               end
            end
            if couu == -1
               couu = 0;
               ru = zeros(n,1);
               [rn,cn,sn] = mb(nn+1,0,0,rot); % nn+1 wtf?
               while rn >= 0
                  couu = couu + sn;
                  ru(-cn+1) = sn;
                  if cn-2 < -n
                     break
                  end
                  [rn,cn2,sn] = mb(0,cn-2,0,rot);
                  if (rn+cn2) == 0
                     cn = cn - 1;
                     sn = -1;
                  else
                     cn = cn2;
                  end
               end
            end
            if couo <= couu % more entries in bottom row than top
               prev = 0;
               for c = 1:n
                  if ro(c)
                     if ro(c) == -1
                        [tmp1,tmp2,s] = mb(j,0,0,rot);
                        solution(j+1,c) = s;
                        prev = s;
                     else
                        solution(j+1,c) = ro(c)-prev;
                        prev = ro(c)-prev;
                     end
                     mb(0,c,1,rot);
                  end
               end
               couo = -1;
               j = j+1;
            else % more entries in top row than bottom
               prev = 0;
               for c = 1:n
                  if ru(c)
                     if ru(c) == -1
                        [tmp1,tmp2,s] = mb(nn+1,0,0,rot);
                        solution(nn,c) = s;
                        prev = s;
                     else
                        solution(nn,c) = ru(c)-prev;
                        prev = ru(c)-prev;
                     end
                     mb(0,-c,1,rot);
                  end
               end
               couu = -1;
               nn = nn-1;
            end
         else % nn >= n
            [r,c,s] = mb(j,0,0,rot);
            while(~(r==-j && c==0))
               solution(j+1,c+1) = s;
               mb(0,c+1,1,rot);
               [r,c,s] = mb(j,0,0,rot);
            end
            j = j+1;
         end
      end
      sl= lrow(nn-1,ra(solution,rot),rot);
      solution = ira(sl,rot);
      if(nn<n)
         sl = lrow(n-nn+1,ra(solution,rot),mod(rot+2,4)+4*(rot>=4));
         solution = ira(sl,rot);
      end
      sol = ra(solution,rot);
      done = true;
   end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   function sol = lrow(nn,start,rot)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      solution = ira(start,rot);
      sc2 = n + 2;
      %nn
      %solution
      [r,c,s] = mb(nn-1,0,0,rot);
      %disp(sprintf('[%d, %d, %d] = (%d, %d, low)\n',r,c,s,nn-1,0));
      if(s) % If not going straight through nor absorbed
         solution(nn,c+1) = s; % Must be deflected
         while(c+2<=n && r~=-(nn-1))
            sc = c+2;
            [r,c,s] = mb(0,sc,0,rot);
            %disp(sprintf('[%d, %d, %d] = (%d, %d, low)\n',r,c,s,0,sc));
            if(~s) % If its been absorbed
               if sc==n % special case if we're at the end
                  [r1, c1, s1]=mb(1-nn,0,0,rot);
                  %disp(sprintf('[%d, %d, %d] = (%d, %d, low)\n',r1,c1,s1,1-nn,0));
                  solution(nn,n)=s1;
                  break;
               end
               % Scan from the right
               if sc2 > n
                  [r2,c2,s2] = mb(1-nn,0,0,rot);
                  %disp(sprintf('[%d, %d, %d] = (%d, %d, low)\n',r2,c2,s2,1-nn,0));
                  if(r2) % reflected
                     solution(nn,n)=s2;
                     prev = s2;
                     sc2 = n-1;
                     [r2,c2,s2] = mb(0, sc2,0, rot);
                     %disp(sprintf('[%d, %d, %d] = (%d, %d, low)\n',r2,c2,s2,0,sc2));
                  else
                     prev = 0;
                  end
                  while(s2) % Note: we always get absorbed at some stage
                     solution(nn, c2-1) = s2 - prev;
                     prev = solution(nn, c2-1);
                     sc2 = c2 - 2;
                     [r2,c2,s2] = mb(0,sc2,0,rot);
                     %disp(sprintf('[%d, %d, %d] = (%d, %d, low)\n',r2,c2,s2,0,sc2));
                  end
               end
               if(sc-sc2 == 1)
                  break; % done
               end

               mb(0,sc-1,1,rot);
               %disp(sprintf('Zorch (%d,%d)\n', 0, sc-1));
               [r,c,s] = mb(0,sc-1,0,rot);
               %disp(sprintf('[%d, %d, %d] = (%d, %d, low)\n',r,c,s,0,sc-1));
               if(~r)
                  solution(nn,sc) = s-solution(nn,c-1);
               else
                  solution(nn,sc) = s;
               end
               c = sc-1;
            elseif(~r)
               solution(nn,c+1) = s-solution(nn,sc-1);
            end
         end
      end
      sol = ra(solution,rot);
   end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   function a=ra(ai,r)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      if(r>=4)
         a=rot90(fliplr(ai),r);
      else
              a = rot90(ai,r);
                end
   end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   function a=ira(ai,r)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      if(r>=4)
         a=fliplr(rot90(ai,-r));
      else
         a = rot90(ai,-r);
      end
   end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   function [rr,cc,ss]=mb(r,c,i,rot,dum)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      if nargin<5
         dum=0;
      end
      if(rot<=0)
         if i > 0
            [rr,cc,ss] = beamkeeper(r,c,2);
         else
            [rr,cc,ss] = beamkeeper(r,c,1);
         end
      elseif(rot>=4)
         if(r==0)
            [ri,ci,ss] = mb(0,sign(c)*(n-abs(c)+1),i,rot-4,dum);
         else
            [ri,ci,ss] = mb(-r,0,i,rot-4,dum);
         end
         if(ri==0 && ci==0)
            rr = 0;
            cc = 0;
         elseif(ri==0)
            rr = 0;
            cc = sign(ci)*(n-abs(ci)+1);
         else
            rr = -ri;
            cc = 0;
         end
      else
         if(r==0)
            [ri,ci,ss] = mb(sign(c)*(n-abs(c)+1),0,i,rot-1,dum);
         else
            [ri,ci,ss] = mb(0,-r,i,rot-1,dum);
         end
         if(ri==0 && ci==0)
            rr = 0;
            cc = 0;
         elseif(ri==0)
            rr = -ci;
            cc = 0;
         else
            rr = 0;
            cc = sign(ri)*(n-abs(ri)+1);
         end
      end
      if i > 1 || nargin>4,
         return;
      end
      if ~r && -c==cc && ~ss
         c=abs(c);
         solution(:,min(n,max(1,c-1:c+1)))=max(0,solution(:,min(n,max(1,c-1:c+1))));
      elseif ~c && ~ss && (-r)==rr
         r=abs(r);
         solution(min(n,max(1,r-1:r+1)),:)=max(0,solution(min(n,max(1,r-1:r+1)),:));
      elseif r==rr && c==cc && ss
         if ~r
            r=(c>0)+(c<0)*n;
            solution(r,abs(c))=max(0,solution(r,abs(c)));
         elseif ~c
            c=(r>0)+(r<0)*n;
            solution(abs(r),c)=max(0,solution(abs(r),c));
         end
      elseif ss
         if ~r
            r=(c>0)+(c<0)*n;
            solution(r,max(1,min(n,abs(c)+(-1:1))))=max(0,solution(r,max(1,min(n,abs(c)+(-1:1)))));
            solution(r+sign(c),abs(c))=max(0,solution(r+sign(c),abs(c)));
         elseif ~c
            c=(r>0)+(r<0)*n;
            solution(max(1,min(n,abs(r)+(-1:1))),c)=max(0,solution(max(1,min(n,abs(r)+(-1:1))),c));
            solution(abs(r),c+sign(r))=max(0,solution(abs(r),c+sign(r)));
         end
         if ~rr
            r=(cc>0)+(cc<0)*n;
            solution(r,max(1,min(n,abs(cc)+(-1:1))))=max(0,solution(r,max(1,min(n,abs(cc)+(-1:1)))));
            solution(r+sign(cc),abs(cc))=max(0,solution(r+sign(cc),abs(cc)));
         elseif ~cc
            c=(rr>0)+(rr<0)*n;
            solution(max(1,min(n,abs(rr)+(-1:1))),c)=max(0,solution(max(1,min(n,abs(rr)+(-1:1))),c));
            solution(abs(rr),c+sign(rr))=max(0,solution(abs(rr),c+sign(rr)));
         end
      end
   end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   function [ri,ci,vi]=beamkeeper(r,c,s)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      idx=rc2idx(r,c);
      if B(idx)>=0 && s == 1
         [ri,ci]=idx2rc(B(idx));
         vi=V(idx);
         return
      end
      if s == 2
         [ri,ci,vi]=beam(r,c,'high');
         L = V|B<=0;
         B(L)=-1;
         V(L)=-1;
         %B = -1;
         %V = -1;
         return
      else
         [ri,ci,vi]=beam(r,c,'low');
      end
      idxi=rc2idx(ri,ci);
      B(idx)=idxi;
      V(idx)=vi;
      if idxi>0
         B(idxi)=idx;
         V(idxi)=vi;
      end
   end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   function idx=rc2idx(r,c)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      rc=r+c;
      idx=(~~rc)*((~r)*2*n+(rc<0)*n+abs(rc));
   end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   function [r,c]=idx2rc(idx)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      if ~idx
         r=0;
         c=0;
         return
      end
      d=floor((idx-1)/n);
      sc=floor(d/2);
      rc=idx-d*n;
      s=1-(d-sc*2)*2;
      r=~sc*s*rc;
      c=sc*s*rc;
   end
end