- function m=solver(tb,nM)
- [m,b]=l0(tb,nM,1);st=sum(sum(b));if(st > 800)
- [m2,b]=l0(tb,nM,0.9);st2=sum(sum(b));if st2<st
- m=m2;end;end
- function [l1,l2]=l0(tl2,nl1,z)
- l2=zeros(size(tl2,1)+1,size(tl2,2)+2);l2(2:end,2:end-1)=tl2;[l3,l4]=size(l2);l1=ones(nl1,3);l5=0;
- zz=zeros(1,floor(((l3-1)*(l4-2))/2));i=1;for r=l3:-1:2
- for cl=l4-2:-1:1
- if mod(r+cl,2)
- zz(i)=(cl*l3)+r;i=i+1;end;end;end
- l6=zeros(1,900);l7=zeros(1,900);l8=zeros(1,400);l9=zeros(numel(l2),1);
- if (l3*l4)>10.5*nl1
- I0=40;I1=.817;I2=2.93;I3=1.566;elseif (l3*l4)>8.5*nl1
- I0=29;I1=.817;I2=2.93;I3=1.566;elseif l3*l4>=256
- I0=26;I1=.951;I2=2.8;I3=1.4;else
- I0=26;I1=.945;I2=2.97;I3=1.46;end
- I1=I1*z;l2=a37(l2,I3);I4=ceil(I2*nl1/10);I5=floor(0.66*nl1);while 1
- if l5==I5,l2=a37(l2,2/(1+I3));end
- [I6,I7,I8] = I9(l2);if isempty(I6),[O0,l2]=O1(l2);
- if O0(1)
- l5=l5+1;l1(l5,:)=O0;if(l5==nl1)
- break;end
- continue
- end
- break
- end
- if l5<nl1-1
- [I7,O2]=sort(I7,2,'descend');I6=I6(O2);for k=1:min(numel(I6),I0)
- O3=O4(l2,I8,I6(k));[O5,O6]=I9(O3);if (~isempty(O5))
- I4_=max(min(I4,nl1-l5-3),1);if numel(O6)<=I4_
- I7(k)=I7(k)+sum(O6);else
- O6=sort(O6,2,'descend');I7(k)=I7(k)+sum(O6(1:I4_));end
- end
- if (I7(k)<I1*I7(1))
- break;end
- end
- end
- [O7,O2]=max(I7);O8=I6(O2);l5=l5+1;l1(l5,:)=[mod(O8-1,l3),ceil(O8/l3)-1,0];l2=O4(l2,I8,O8);
- if (l5==nl1)
- break;
- end
- end
- l1=l1(1:l5,:);
- function [O5,O6,O9]=I9(l2);
- [l3,l4]=size(l2);L0=0;ii=0;L1=0;L2=0;L3=0;c=0;
- for zi=1:numel(zz)
- i=zz(zi);c=l2(i);if c && (l2(i+1)==c||l2(i+l3)==c||l2(i-1)==c||l2(i-l3)==c)
- L0=L0+1;l8(1)=i;l2(i)=0;L1=i;L2=0;L3=1;while (L3-L2)
- L2=L2+1;ii=l8(L2);l9(ii)=L1;L1=ii;if l2(ii+1)==c
- L3=L3+1;l8(L3)=ii+1;l2(ii+1)=0;end
- if l2(ii-1)==c
- L3=L3+1;l8(L3)=ii-1;l2(ii-1)=0;end
- if l2(ii+l3)==c
- L3=L3+1;l8(L3)=ii+l3;l2(ii+l3)=0;end
- if l2(ii-l3)==c
- L3=L3+1;l8(L3)=ii-l3;l2(ii-l3)=0;end
- end
- l7(L0)=c*L2;l6(L0)=ii;end
- end
- O5=l6(1:L0);O6=l7(1:L0);O9=l9;end
- function B=O4(B,dj,y)
- B(y)=0;L4=ceil(y/l3);L5=L4;L6=L4;while dj(y)~=y
- y=dj(y);B(y)=0;L4=ceil(y/l3);L5=min(L5, L4);L6=max(L6, L4);end;
- for ip=L5:L6,
- kp=B(B(:,ip)>0,ip);B(:,ip)=0;B(l3-numel(kp)+1:l3,ip)=kp;end
- end
- function [O0,L8]=O1(l2)
- [l3 l4]=size(l2);L7=[-1 l3 1 -l3];L9=l3*l4;O0=zeros(1,3);L8=l2;Q0=0;Q1=find(l2~=0)';Q2=numel(Q1);
- for kc=1:Q2
- jj=Q1(kc);for Q3=1:4
- np=jj+L7(Q3);if np>0 && np<=L9 && l2(np)>0 && l2(np)~=l2(jj)
- tl2=Q4(l2,jj,np);[Q5,Q6]=I9(tl2);if (~isempty(Q6))
- if (max(Q6)> Q0)
- Q0=max(Q6);Q7=jj;Q8=Q3;Q9=np;end
- else
- for k2=max(1,kc-20):min(Q2,kc+20)
- W0=Q1(k2);for W1=1:4
- np2=W0+L7(W1);if np2>0 && np2<=L9 && tl2(np2)>0 && tl2(np2)~=tl2(W0)
- W2=Q4(tl2,W0,np2);[W3,W4,W5]=I9(W2);if (~isempty(W4) && max(W4)>Q0)
- W6=false;[W7,W8]=max(W4);Y=W3(W8);
- while (W5(Y)~=Y)
- Y = W5(Y);if (Y==np || Y==jj)
- W6=true;end
- end
- if (Y==np || Y==jj)
- W6=true;
- end
- if (W6)
- Q0=max(W4);Q7=jj;Q8=Q3;Q9=np;
- end
- end
- end
- end
- end
- end
- end
- end
- end
- if (Q0>0)
- O0 = [mod(Q7-1,l3),ceil(Q7/l3)-1,Q8];L8=Q4(l2,Q7,Q9);
- end
- end
- function l2 = Q4(l2,el1,el2)
- l2([el1,el2]) = l2([el2,el1]);
- end
- end
- end
- function y = a37(x, n)
- y =(x.^(1/n));
+ function moves = solver(board,nMoves)
+ %SOLVER Solve the Blockbuster Contest problem
+ %
+ % MOVES = SOLVER(BOARD,NMOVES) BlockBuster solver.
+ %
+ % MOVES -> [row,column,action]
+ % action -> 0 busts, 1 swap up, 2 swap right, 3 swap down, 4 swap left
+
+ %rand('seed',3);
+
+ % N=1, E=2, S=3, W=4
+ I = [-1 0 1 0 ];
+ J = [ 0 1 0 -1 ];
+ N = false(size(board));
+
+ size(board);
+ maxrow = size(board,1);
+ maxcol = size(board,2);
+
+ output = [];
+ %for STEP =1:min(nMoves,3)
+ for STEP =1:nMoves
+ row1 = round(rand*(maxrow-2)+1);
+ col1 = round(rand*(maxcol-1)+1);
+
+ count = 1;
+ while board(row1,col1) == 0 && count<100
+ count = count+1;
+ row1 = round(rand*(maxrow-2)+1);
+ col1 = round(rand*(maxcol-1)+1);
+ end;
+
+ if canPop2(row1,col1,board) == 1
+ if isEmpty(row1,col1,board) == 0
+ output = [output; row1 col1 0];
+ else
+ output = [output; row1 col1 3];
+ end;
+ else
+ output = [output; row1 col1 3];
+ end;
+
+ mv = output(STEP,1:3);
+
+ cp = mv(1,1:2);
+ if board(cp(1),cp(2))>0 %current block must be a non-empty space
+ if mv(1,3) % swap ?
+ np = cp + [I(mv(1,3)) J(mv(1,3))];
+ % swap block must be within the bounds of the board and a non-empty space
+ if all(np>=1) && all(np<=size(board)) && board(np(1),np(2))>0
+ board([cp(1),np(1)],[cp(2),np(2)]) = board([np(1),cp(1)],[np(2),cp(2)]);
+ else
+ % warning('MY ERROR Swap to an empty space or beyond the bounds of the board.')
+ end
+ else % remove block and neighbors
+ N(:) = false;
+ findNeighbors(cp(1),cp(2),board(cp(1),cp(2)));
+ if sum(N(:))>1
+ anyN = any(N);
+ for j = 1:size(board,2)
+ if anyN(j)
+ tmp = board(~N(:,j),j);
+ board(:,j) = 0;
+ board(end-sum(~N(:,j))+1:end,j) = tmp;
+ end
+ end
+ else
+ % warning('MY ERROR You cannot pop single blocks.')
+ end
+ end
+ else
+ % warning('MY ERROR Indices point to an empty space.')
+ end
+
+ end;
+ score = sum(board(:));
+ moves = output;
+
+
+
+
+ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+ function findNeighbors(i,j,c)
+ if ~N(i,j);
+ N(i,j) = true;
+ if i>1 && board(i-1,j)==c; findNeighbors(i-1,j,c); end
+ if j<size(board,2) && board(i,j+1)==c; findNeighbors(i,j+1,c); end
+ if i<size(board,1) && board(i+1,j)==c; findNeighbors(i+1,j,c); end
+ if j>1 && board(i,j-1)==c; findNeighbors(i,j-1,c); end
+ end;
+ end;
+
+
+ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+ function output = isEmpty(row,col,board)
+ tempOutput = 1;
+ if board(row,col) > 0
+ tempOutput = 0;
+ end;
+ output = tempOutput;
+ end;
+ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+ function output = canPop2(row,col,board)
+ tempOutput = 0;
+ neighBors = [];
+
+ %Uppermost row
+ if(row>1)
+ neighBors = [neighBors; row-1 col;];
+ end;
+
+ %Bottom row
+ if(row<size(board,1))
+ neighBors = [neighBors; row+1 col;];
+ end;
+
+ %Left column
+ if(col>1)
+ neighBors = [neighBors; row col-1;];
+ end;
+
+ %Right column
+ if(col<size(board,2))
+ neighBors = [neighBors; row col+1;];
+ end;
+
+ for i=1:size(neighBors,1)
+ if board(neighBors(i,1),neighBors(i,2)) == board(row,col)
+ tempOutput = 1;
+ %fprintf('Can pop: %d %d\n',board(neighBors(i,1),neighBors(i,2)),board(row,col));
+ end;
+ end;
+ output = tempOutput;
+ end;
+
+ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+ function output = canUp(row,col,board)
+ tempOutput = 1;
+ if row==1
+ tempOutput = 0;
+ elseif board(row-1,col)==0
+ tempOutput=0;
+ end;
+ output = tempOutput;
+ end;
+
+ function output = canDown(row,col,board)
+ tempOutput = 1;
+ if row==size(board,1)
+ tempOutput = 0;
+ end;
+ %No need to check down, since blocks slide down. Will always
+ %have a downwards neighbour
+ output = tempOutput;
+ end;
+
+ function output = canRight(row,col,board)
+ tempOutput = 1;
+ if col==size(board,2)
+ tempOutput = 0;
+ elseif board(row,col+1)==0
+ tempOutput = 0;
+ end;
+ output = tempOutput;
+ end;
+
+ function output = canLeft(row,col,board)
+ tempOutput = 1;
+ if col==1
+ tempOutput = 0;
+ elseif board(row,col-1)==0
+ tempOutput = 0;
+ end;
+ output = tempOutput;
+ end;
+
+
end
|