Problem 46618. Kaggle 2020 Drone Delivery Contest

Solution 2996449

Submitted on 27 Sep 2020 by Richard Zapor
  • Size: 3312
  • This is the leading solution.
This solution is locked. To view this solution, you need to provide a solution of the same size or smaller.

This solution is outdated. To rescore this solution, sign in.

Test Suite

Test Status Code Input and Output
1   Pass
tic fname=''; out_fn=''; urlwrite(fname,out_fn); %Load url file to local space 0.74s m=dlmread(out_fn); % 3775, 400 1.1s Read in complete Kaggle Drone Test file nr=m(1,1);nc=m(1,2);ndr=m(1,3);nturns=m(1,4);max_wt=m(1,5); %nr400, nc600, ndr30 drones, nturns112993, max_wt200 %All drones start at first warehouse drones(1:30), warehouses(1:10) nprod=m(2,1); %400 vpwt=m(3,1:nprod); % nw=m(4,1); %10 warehouses wxy=zeros(nw,2); % warehouses x,y wprodq=zeros(nw,nprod); % Quantity of each product in each warehouse Lptr=5; for i=1:nw wxy(i,:)=m(Lptr,1:2)+1; %locations moved off (0,0) to (1,1) wprodq(i,1:nprod)=m(Lptr+1,1:nprod); %qty of items(1:400) at each warehouse Lptr=Lptr+2; end norders=m(Lptr,1); %1250 orders [1:1250] % Delivery dxyq locx,locy,qty_items % Delivery_list dlisth (repeat items possible)[dataset starts at 0, add 1) hist dxyq=zeros(norders,3); dlist=zeros(norders,nprod); % do not know current max of items in an order Lptr=Lptr+1; for i=1:norders %deliveries(1:1250) dxyq(i,1:2)=m(Lptr,1:2)+1; %locations moved off (0,0) to (1,1) dxyq(i,3)=m(Lptr+1,1); %qty of items for a delivery dlist(i,1:dxyq(i,3))=sort(m(Lptr+2,1:dxyq(i,3))+1); % items 0:399 become 1:400 Lptr=Lptr+3; end dlist=dlist(:,1:max(dxyq(:,3))); %dlist width reduces from 400 to 19 %read complete %Create three useful arrays required for scoring % delivery to delivery location and warehouse to delivery location dw2dw=zeros(norders+nw); vx=[dxyq(:,1);wxy(:,1)]; vy=[dxyq(:,2);wxy(:,2)]; for j=1:norders+nw dw2dw(:,j)=ceil(((vx-vx(j)).^2+(vy-vy(j)).^2).^.5); end %warehouse to delivery distance [nw,norders] w2d=dw2dw(norders+1:end,1:norders); %Initialize permutation maps for Brute Force path calculation for i=9:-1:1 pmapc{i}=perms(1:i); end %1.3s Cody setup toc fprintf('%i ',nr,nc,ndr,nturns,max_wt,nprod);fprintf('\n') cmds=drone(nr,nc,ndr,nturns,max_wt,nprod,vpwt,nw,wxy,wprodq,norders,dxyq,dlist,dw2dw,w2d,pmapc); toc %Evaluate cmds provided for accuracy and drone time to deliver packages drIdx=ones(ndr,1)*(norders+1); % drone location index, quantized, range [1:norders norders+wh] drT=zeros(ndr,1); % Drone Time, includes loads and flight legs drW=zeros(ndr,1); % Drone Weight drL=zeros(ndr,nprod); %Histogram of drone loads dt=zeros(norders,1); %delivery time of last item deposited %Reduce cmds for illegal content and give warning csize=size(cmds,1); cmds=abs(cmds); %remove any negatives cmds(prod(cmds,2)==0,:)=[]; % No zeros allowed cmds(cmds(:,2)==1 & cmds(:,3)>nw,:)=[]; %For Load cmds(3)<=1nw cmds(cmds(:,3)>norders,:)=[]; cmds(cmds(:,4)>nprod,:)=[]; cmds(cmds(:,1)<1,:)=[]; cmds(cmds(:,1)>ndr,:)=[]; cmds(cmds(:,2)<1,:)=[]; % invalid cmd type only 1/3 allowed cmds(cmds(:,2)==2,:)=[]; % invalid cmd type only 1/3 allowed cmds(cmds(:,2)>3,:)=[]; % invalid cmd type only 1/3 allowed if size(cmds,1)<csize fprintf('Warning: Invalid cmds purged\n') end flag=0; % No issues 0 for i=1:size(cmds,1) vcmd=cmds(i,:); %[drone 1/3 warehouse/delivery item qty] if vcmd(2)==1 %Load vcmd(3) warehouse (allow warehouse to warehouse,deliv to wh) wptr=vcmd(3); drT(vcmd(1))=drT(vcmd(1))+dw2dw(drIdx(vcmd(1)),norders+wptr)+1; %dist+load drIdx(vcmd(1))=norders+wptr; wprodq(wptr,vcmd(4))=wprodq(wptr,vcmd(4))-vcmd(5); drL(vcmd(1),vcmd(4))=drL(vcmd(1),vcmd(4))+vcmd(5); drW(vcmd(1))=drW(vcmd(1))+vcmd(5)*vpwt(vcmd(4)); %Add item(s) wt if wprodq(wptr,vcmd(4))<0 % Check for excess usage at warehouse flag=1; fprintf('Not enough of item %i at warehouse %i at cmds %i\n',vcmd([4 3]),i); break; end if drW(vcmd(1))>max_wt % check for excess wt loaded flag=1; fprintf('Max wt exceeded: %i drone %i at cmds %i\n',drW(vcmd(1)),vcmd(1),i); break; end else %Deliver: vcmd(3) delivery location (wh2deliv, deliv2deliv) % [drone 3 did item q] dptr=vcmd(3); drT(vcmd(1))=drT(vcmd(1))+dw2dw(drIdx(vcmd(1)),dptr)+1; % dist+drop drIdx(vcmd(1))=dptr; for j=1:vcmd(5) iptr=find(dlist(dptr,:)==vcmd(4),1,'first'); if ~isempty(iptr) dlist(dptr,iptr)=0; else %Excess item being delivered flag=1; fprintf('Excess delivery of item %i at cmds %i\n',vcmd(4),i) break end end if flag==1,break;end %Excess delivery break drL(vcmd(1),vcmd(4))=drL(vcmd(1),vcmd(4))-vcmd(5); drW(vcmd(1))=drW(vcmd(1))-vcmd(5)*vpwt(vcmd(4)); % Unload item(s) wt delivered if drL(vcmd(1),vcmd(4))<0 flag=1; fprintf('Non-existent itme delivery attempt. Item %i cmds %i\n',vcmd(4),i) break; end dt(dptr)=max(dt(dptr),drT(vcmd(1))); end % Load/Delivery end % cmds if flag scr=0; else dt(sum(dlist,2)>0)=nturns; %Non-completed delivery scores Zero scr= sum( ceil(100*(nturns-dt(:))/nturns) ); end fprintf('scr: %i\n',scr) assert(scr>110000)

Elapsed time is 1.118414 seconds. 400 600 30 112993 200 400 Elapsed time is 6.217163 seconds. scr: 111400 Elapsed time is 6.218457 seconds. Elapsed time is 6.219842 seconds. scr: 111400

Suggested Problems

More from this Author246

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!