Cody

Problem 1241. PACMAT - Ghosts maximize unique locations; 3 Lives

Solution 1535116

Submitted on 21 May 2018 by Binbin Qi
• Size: 185
• 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.

Test Suite

Test Status Code Input and Output
1   Pass
feval(@assignin,'caller','score',2000);

2   Pass
max_moves=2000; % Fixed path expect to succeed by 600 moves map=[... repmat('a',1,28); 'accccccccccccaacccccccccccca'; 'acaaaacaaaaacaacaaaaacaaaaca'; 'acaaaacaaaaacaacaaaaacaaaaca'; 'acaaaacaaaaacaacaaaaacaaaaca'; 'acccccccccccccccccccccccccca'; 'acaaaacaacaaaaaaaacaacaaaaca'; 'acaaaacaacaaaaaaaacaacaaaaca'; 'accccccaaccccaaccccaacccccca'; 'aaaaaacaaaaabaabaaaaacaaaaaa'; 'aaaaaacaaaaabaabaaaaacaaaaaa'; 'aaaaaacaabbbbbbbbbbaacaaaaaa'; 'aaaaaacaabaaabbaaabaacaaaaaa'; 'aaaaaacaabalbbbblabaacaaaaaa'; 'bbbbbbcbbbabbbbbbabbbcbbbbbb'; 'aaaaaacaabalbbbblabaacaaaaaa'; 'aaaaaacaabaaaaaaaabaacaaaaaa'; 'aaaaaacaabbbbbbbbbbaacaaaaaa'; 'aaaaaacaabaaaaaaaabaacaaaaaa'; 'aaaaaacaabaaaaaaaabaacaaaaaa'; 'accccccccccccaacccccccccccca'; 'acaaaacaaaaacaacaaaaacaaaaca'; 'acaaaacaaaaacaacaaaaacaaaaca'; 'acccaacccccccbdcccccccaaccca'; 'aaacaacaacaaaaaaaacaacaacaaa'; 'aaacaacaacaaaaaaaacaacaacaaa'; 'accccccaaccccaaccccaacccccca'; 'acaaaaaaaaaacaacaaaaaaaaaaca'; 'acaaaaaaaaaacaacaaaaaaaaaaca'; 'acccccccccccccccccccccccccca'; repmat('a',1,28);]; map=map-'b'; [nr, nc]=size(map); gmap=map; % Map used by ghosts to simplify PAC Capture gmap(15,6)=Inf; %No tunnel ghosts gmap(15,26)=Inf; gmap(map==-1)=Inf; % walls to Inf gmap(map>2)=Inf; % Elim start points as viable moves, quicker box exit mapdelta=[-1 nr 1 -nr]; % Valid as long as not on an edge gmovxy=[0 -1;1 0;0 1;-1 0]; tunnel=find(map(:,1)==0); % tunnelptr tunnel=[tunnel tunnel+nr*(nc-1)]; % Entrance/Exit Tunnel [pmr, pmc]=find(map==2); % pi 24 row pj 15 column of map ptrpac=find(map==2); ptrpac=find(map==2); ptrpac_start=ptrpac; ptrg_start=find(map>2); map(ptrg_start)=[10 20 30 40];% use deal? [gstartx, gstarty]=find(map>2); lives=3; % Lives movepac=0; while lives && any(mod(map(:),10)==1) && movepac<max_moves movepac=movepac+1; [curdir]=pacmat(map); % if curdir==0,continue;end % Inf loop error [pmr, pmc]=find(map==2); if curdir>0 if map(ptrpac+mapdelta(curdir))==-1 % Do nothing - Ran into a Wall elseif map(ptrpac+mapdelta(curdir))>2 % ran into ghost map(ptrpac)=0; % remove PAC from the board lives=lives-1; if lives==0,break;end % reset the board [ptrgx, ptrgy]=find(map>2); ptrg=find(map>2); map(ptrg)=mod(map(ptrg),10); map(ptrpac_start)=2; map(ptrg_start)=[10 20 30 40]; ptrpac=find(map==2); continue; else % legal move map(ptrpac)=0; % Eat Dot and clear PAC ptrpac=ptrpac+mapdelta(curdir); if ptrpac==tunnel(1),ptrpac=tunnel(2)-nr;end if ptrpac==tunnel(2),ptrpac=tunnel(1)+nr;end map(ptrpac)=2; end end % curdir >0 % Ghosts for i=1:4 gmapT=gmap; ptrg=find(map>2); % Find all ghosts gmapT(ptrg)=Inf; % Rule out moving onto a ghost dot=false; [gptrx, gptry]=find(map==10*i); gidx=find(map==10*i); if isempty(gidx) [gptrx, gptry]=find(map==10*i+1); % ghost must be on a dot gidx=find(map==10*i+1); dot=true; end % Find valid ghost moves using gmap % mapdelta=[-1 nr 1 -nr]; gmov=find(map(gidx+mapdelta)==2); % adjacent to PACMAT if ~isempty(gmov) % PAC adjacent lives=lives-1; if lives==0,break;end % reset the board [pmr, pmc]=find(map==2); % PACMAT erase coords map(map==2)=0; [ptrgx, ptrgy]=find(map>2); ptrg=find(map>2); map(ptrg)=mod(map(ptrg),10); map(ptrpac_start)=2; map(ptrg_start)=[10 20 30 40]; ptrpac=find(map==2); break; % Ghost move loop else % gmap/gmapT avoids tunnel,other ghosts, Walls gmap(gidx)=gmap(gidx)+1; ghost_adj=gmapT(gidx+mapdelta); if min(ghost_adj)<Inf if rand<0.5 % Push ghosts away from each other gmov=find(ghost_adj==min(ghost_adj),1,'first'); else gmov=find(ghost_adj==min(ghost_adj),1,'last'); end else gmov=[]; end if ~isempty(gmov) % valid g move : ghost may not stand on ghost map(gptrx,gptry)=mod(map(gptrx,gptry),10); map(gidx+mapdelta(gmov))=map(gidx+mapdelta(gmov))+10*i; end % ~isempty(gmov) standard move - no capture end % ~isempty(gmov) PACMAT adjacent end % i ghost moves end % while alive fprintf('moves %i\n',movepac) assert(lives>0,sprintf('Three Captures\n')) assert(~isempty(any(mod(map(:),10)==1)),sprintf('Moves\n',movepac)) % Test Move Timeout feval( @assignin,'caller','score',floor(min( 2000,300-100*lives+movepac )) );

moves 357