- function [moves,score] = submit1(board)
- %
- % Note in the interest of collaboration I'm documenting
- % the leading code as much as possible. Instead of going the
- % obscufation route with this, I invite everyone to
- % document / take credit for their particular changes
- % as the codes get modified.
- %
- % At a minimum, please don't remove the existing comments
- % so someones doesn't have to start from scratch on commenting
- % updated code again
- %
- % Alan Chalker
- %
-
- % Set up the random number generator so it produces a favorable sequence.
+ function [AA,AB] = solver(AD)
rand('state',0);
rand(57,1);
-
- [m,n] = size(board); % find the dims of the board
- pegCount = sum(board(:)>0); % check the number of pegs on the board
- rows = m+4; % expand the height by 4 rows
- rv = 5:rows; % create a new row index starting at 5th row
- cols = n+4; % expand the width by 4 cols
- cv = 5:cols; % create a new col index starting at 5th col
-
-
- i = repmat(rv',[n 1]); % create an index of all the new board row coordinates except for the 1st 4 rows
- j = reshape(repmat(cv,[m 1]),[m*n 1]); % create an index of all the new board col coordinates except for the 1st 4 cols
- % note [i j] would be a list of all original board coordinates in the
- % new board created below
-
- mm = m+8; % expand the original height by 8 rows
- nn = n+8; % expand the original width by 8 cols
- ppBoard = -ones(mm, nn); % create a new board with 4 extra rows / cols of offlimits all the way around the board
- ppBoard(rv,cv) = board; % populate the new board with the original board values
-
- I = [i;i;i;i]; % vector of 4 repeats of row coords
- J = [j;j;j;j]; % vector of 4 repeats of col coords
- K = [i;i;i-2;i+2]; % vector of row cords, row cords, 2 rows above, 2 rows below
- L = [j-2;j+2;j;j]; % vector of 2 cols before, 2 cols past, col cords, col cords
- % [I J K L] would be a matrix of ALL potential moves for this board
-
- K1 = [i;i;i-4;i+4]; % vector of row cords, row cords, 4 rows above, 4 rows below
- L1 = [j-4;j+4;j;j]; % vector of 4 cols before, 4 cols past, col cords, col cords
- % if a move from [I J] to [K L] were done, [K L K1 L1] is the potential next colinear moves
-
- K2 = [i-2;i+2;i-2;i+2]; % vector of 2 rows above, 2 rows below repeated twice
- L2 = [j-2;j+2;j+2;j-2]; % vector of 2 cols before, 2 cols past, 2 cols past, 2 cols before
- % if a move from [I J] to [K L] were done, [K L K2 L2] is the half of the potential next orthogonal moves
-
- K3 = [i+2;i-2;i-2;i+2]; % vector of 2 rows below, 2 rows above, 2 rows above, 2 rows below
- L3 = [j-2;j+2;j-2;j+2]; % vector of 2 cols before, 2 cols past repeated twice
- % if a move from [I J] to [K L] were done, [K L K3 L3] is the other half of the potential next orthogonal moves
-
- F = I+(J-1)*mm; % convert source spot coordinates [I J] into single index value
- T = K+(L-1)*mm; % convert destination spot coordinates [K L] into single index value
- M = (F+T)*0.5; % calculate the index value of the spot that would be jumped if did move [I J K L]
-
- % find indexes of moves that don't involve off limits (-1) areas
- bogusMoves = (ppBoard(F) < 0) | (ppBoard(M) < 0) | (ppBoard(T) < 0);
-
- % remove moves that involve off limits areas
- I(bogusMoves) = [];
- J(bogusMoves) = [];
- K(bogusMoves) = [];
- L(bogusMoves) = [];
- F(bogusMoves) = [];
- T(bogusMoves) = [];
- M(bogusMoves) = [];
- K1(bogusMoves) = [];
- K2(bogusMoves) = [];
- K3(bogusMoves) = [];
- L1(bogusMoves) = [];
- L2(bogusMoves) = [];
- L3(bogusMoves) = [];
-
-
- % convert 2nd jump destination spot coordinates into single index value
- % note invalid jumps are kept in index but not converted
- T1 = K1+(L1-1)*mm; % colinear
- T2 = K2+(L2-1)*mm; % ortho
- T3 = K3+(L3-1)*mm; % ortho
- TT = [T1 T2 T3];
-
- % calculate the index value of the spot that would be jumped if did move
- M1 = (T+T1)*0.5; % [K L K1 L1]
- M2 = (T+T2)*0.5; % [K L K2 L2]
- M3 = (T+T3)*0.5; % [K L K3 L3]
- MM = [M1 M2 M3];
-
- % create first possible move list
- MV = [I J K L];
- MV1 = [K L K1 L1];
- MV2 = [K L K2 L2];
- MV3 = [K L K3 L3];
- MVV = {MV1, MV2, MV3};
- [moveid1,moveid2,moveid3,rMap] = createMoves(M,F,T);
-
- % run the subsolver function
- [moves,score] = subsoltweak( ...
- ppBoard, ...
- F,T,M, ...
- pegCount, ...
- TT,MM,MV,MVV, ...
- moveid1,moveid2,moveid3);
-
- % calculate the max possible score as 81% of the sum of the pegs
- maxsum = sum(board(board>0));
- maxscore = 0.81*maxsum;
- % repeat over the iteration weightings
- for dd = getDdlist(pegCount)
- % if the solver results is more than the maxscore or less than 3 moves long then stop
- if (size(moves,1) <= 3) || (score > maxscore)
- % correct moves due to board padding
- moves = moves - 4;
- return
- end
- % calculate moves and scores of moves with subfunction
- [newMoves,newScore] = subsol( ...
- ppBoard, ...
- dd,0, ...
- F,T,M, ...
- pegCount, ...
- TT,MM,MV,rMap); %, ...
- % moveid1,moveid2,moveid3);
- % if it is better, update the move list.
- if (newScore > score)
- score = newScore;
- moves = newMoves;
- end
- end
- % repeat with randomisation
- k = 1;
- while k <=(min((pegCount/128)+1,3)*(score < maxsum*0.79))
- % calculate moves and scores of moves with nested function
- [newMoves,newScore] = subsol( ...
- ppBoard, ...
- 1.0,1.16, ...
- F,T,M, ...
- pegCount, ...
- TT,MM,MV,rMap); %, ...
- % moveid1,moveid2,moveid3);
- % If it is better, update the move list.
- if (newScore > score)
- score = newScore;
- moves = newMoves;
- end
- k = k+1;
- end
-
- % correct moves due to board padding
- moves = moves - 4;
- % end
- % check if the # pegs or fill ratio is less than set values
- % calculate the peg to off limit areas ratio of board
- fill = (pegCount-nnz(board<0)) / (m*n);
- if (pegCount < 272) && (fill < .96)*(score < maxsum*0.775)
- % run the initial solver routine
- [newMoves,newScore] = solveri(board,rows,cols);
- if (newScore > score)
- score = newScore;
- moves = newMoves;
- end
+ [AL,n] = size(AD);
+ CK = sum(AD(:)>0);
+ rows = AL+4;
+ CP = 5:rows;
+ cols = n+4;
+ cv = 5:cols;
+ fill = (CK-nnz(AD<0)) / (AL*n);
+ i = repmat(CP',[n 1]);
+ j = reshape(repmat(cv,[AL 1]),[AL*n 1]);
+ DK = AL+8;
+ DL = n+8;
+ DM = -ones(DK, DL);
+ DM(CP,cv) = AD;
+ AK = [i;i;i;i];
+ DW = [j;j;j;j];
+ DX = [i;i;i-2;i+2];
+ EA = [j-2;j+2;j;j];
+ EF = [i;i;i-4;i+4];
+ EG = [j-4;j+4;j;j];
+ EM = [i-2;i+2;i-2;i+2];
+ EP = [j-2;j+2;j+2;j-2];
+ ES = [i+2;i-2;i-2;i+2];
+ ET = [j-2;j+2;j-2;j+2];
+ EV = AK+(DW-1)*DK;
+ EZ = DX+(EA-1)*DK;
+ FB = (EV+EZ)*0.5;
+ FI = (DM(EV) < 0) | (DM(FB) < 0) | (DM(EZ) < 0);
+ AK(FI) = [];
+ DW(FI) = [];
+ DX(FI) = [];
+ EA(FI) = [];
+ EV(FI) = [];
+ EZ(FI) = [];
+ FB(FI) = [];
+ EF(FI) = [];
+ EM(FI) = [];
+ ES(FI) = [];
+ EG(FI) = [];
+ EP(FI) = [];
+ ET(FI) = [];
+ [FJ,FK,FL] = FM(FB,EV,EZ);
+ FU = EF+(EG-1)*DK;
+ FV = EM+(EP-1)*DK;
+ FW = ES+(ET-1)*DK;
+ FX = [FU FV FW];
+ FY = (EZ+FU)*0.5;
+ FZ = (EZ+FV)*0.5;
+ GA = (EZ+FW)*0.5;
+ GB = [FY FZ GA];
+ GD = [AK DW DX EA];
+ GE = [DX EA EF EG];
+ GF = [DX EA EM EP];
+ GG = [DX EA ES ET];
+ GH = {GE, GF, GG};
+ [AA,AB] = GJ( ...
+ DM, ...
+ EV,EZ,FB, ...
+ CK, ...
+ FX,GB,GD,GH, ...
+ FJ,FK,FL);
+ GK = sum(AD(AD>0));
+ GL = 0.81*GK;
+ for GQ = GR(CK)
+ if (size(AA,1) <= 3) || (AB > GL)
+ AA = AA - 4;
+ return
end
-
- end % close function solver
-
- %======================================================================
- function ddlist = getDdlist(pegCount)
-
- % create a vector of 4 random values between -1 and 1
- RX = 2*(rand(4,1)-0.5);
-
- switch ceil(pegCount/102.5)
- case 1
- ddlist = [1+0.1*RX(1) 0.05];
- case 2
- ddlist = [6.8 5 2.1 1+0.1*RX(2) 0.6+0.1*RX(2) 0.45];
- % burn 750 random numbers from the sequence
- %rand(750,1);
- case 3
- ddlist = [0.05 2.1 1+0.1*RX(3) 0.6+0.1*RX(3) 0.5+0.1*RX(3) 0.254];
- case 5
- ddlist = [0.05 2.1 0.6+0.1*RX(4) 0.18];
- otherwise
- ddlist = [0.05 2.1 1+0.1*RX(4) 0.6];
+ [HC,HD] = HE( ...
+ DM, ...
+ GQ,0, ...
+ EV,EZ,FB, ...
+ CK, ...
+ FX,GB,GD, ...
+ FJ,FK,FL);
+ if (HD > AB)
+ AB = HD;
+ AA = HC;
end
-
- % if (pegCount > 400 && pegCount < 560)
- % % add an element to the iteration weights list
- % ddlist(end+1) = 0.18;
- % end
end
- %======================================================================
- function [moveid1,moveid2,moveid3,rMap] = createMoves(M,F,T)
-
- ni = max([max(M) max(F) max(T)]); % find the index of the lower right most possible move spots
-
- % create three copies of a vector long enough to contain all possible move
- % position indexes
- nmove1 = zeros(ni,1);
- nmove2 = nmove1;
- nmove3 = nmove1;
-
- % create three copies of a matrix long enough to contain all possible moves
- moveid1 = zeros(ni,4);
- moveid2 = moveid1;
- moveid3 = moveid1;
-
- N=numel(F);
- for k = 1:N % repeat for the number of starting positions
- nmove1(F(k)) = nmove1(F(k))+1; %populate the 1st move position vector with the # of times that source spot is in the possible moves
- moveid1(F(k),nmove1(F(k))) = k; % populate the 1st move list vector with the index value of the corresponding source spots in each col
- % Note: if the 10th position on the board is a peg that could make 3
- % possible moves (i.e. up, down, right), that nmove1(10)=3 and
- % nmoveid1(10,:) = [x y z 0] where x,y,x are the index values in
- % vector F where 10 appears
-
- % Repeat the above for the spots that could be jumped
- nmove2(M(k)) = nmove2(M(k))+1;
- moveid2(M(k),nmove2(M(k))) = k;
-
- % Repeat the above for the destination spots
- nmove3(T(k)) = nmove3(T(k))+1;
- moveid3(T(k),nmove3(T(k))) = k;
+ HH = 1;
+ while HH <=(min((CK*0.0078125)+1,3)*(AB < GK*0.79))
+ [HC,HD] = HE( ...
+ DM, ...
+ 1.0,1.16, ...
+ EV,EZ,FB, ...
+ CK, ...
+ FX,GB,GD, ...
+ FJ,FK,FL);
+ if (HD > AB)
+ AB = HD;
+ AA = HC;
end
- rMap=[moveid1(F,:) moveid2(F,:) moveid3(F,:) moveid1(M,:) moveid2(M,:) moveid3(M,:) moveid1(T,:) moveid2(T,:) moveid3(T,:)];
+ HH = HH+1;
end
-
- %======================================================================
- function [moves,last_score] = solveri(board,rows,cols)
-
- % create a new board with 2 extra rows / cols of offlimits all the way
- % around the board
- pBoard = -ones(rows,cols);
- pBoard(3:end-2,3:end-2) = board;
-
- % allocate buffers
- nNonHoles = nnz(pBoard);
- moves = zeros(nNonHoles,4);
- cellbuf = zeros(nNonHoles*4,1);
- valbuf = cellbuf;
- movebuf = cellbuf;
- hopbuf = cellbuf;
- hop_list = cellbuf;
-
- % initialize various variables
- dead_weight = 0.1 * mean(board(board>0));
- count = 0;
- last_move = 0;
- score = 0;
- last_pos = 0;
- last_score = 0;
+ AA = AA - 4;
+ if (CK < 272) && (fill < .96)*(AB < GK*0.775)
+ [HC,HD] = HJ(AD,rows,cols);
+ if (HD > AB)
+ AB = HD;
+ AA = HC;
+ end
+ end
+ end
+ function HK = GR(CK)
+ HM = 2*(rand(4,1)-0.5);
+ switch ceil(CK/102.5)
+ case 1
+ HK = [1+0.1*HM(1) 0.05];
+ case 2
+ HK = [6.8 5 2.1 1+0.1*HM(2) 0.6+0.1*HM(2) 0.45];
+ case 3
+ HK = [0.05 2.1 1+0.1*HM(3) 0.6+0.1*HM(3) 0.4+0.1*HM(3) 0.254];
+ case 5
+ HK = [0.05 2.1 0.6+0.1*HM(4) 0.18];
+ otherwise
+ HK = [0.05 2.1 1+0.1*HM(4) 0.592];
+ end
+ end
+ function [FJ,FK,FL] = FM(FB,EV,EZ)
+ HR = max([max(FB) max(EV) max(EZ)]);
+ HZ = zeros(HR,1);
+ IA = HZ;
+ IB = HZ;
+ FJ = zeros(HR,4);
+ FK = FJ;
+ FL = FJ;
+ for HH = 1:numel(EV)
+ HZ(EV(HH)) = HZ(EV(HH))+1;
+ FJ(EV(HH),HZ(EV(HH))) = HH;
+ IA(FB(HH)) = IA(FB(HH))+1;
+ FK(FB(HH),IA(FB(HH))) = HH;
+ IB(EZ(HH)) = IB(EZ(HH))+1;
+ FL(EZ(HH),IB(EZ(HH))) = HH;
+ end
+ end
+ function [AA,IP] = HJ(AD,rows,cols)
+ IQ = -ones(rows,cols);
+ IQ(3:end-2,3:end-2) = AD;
+ IT = nnz(IQ);
+ AA = zeros(IT,4);
+ IU = zeros(IT*4,1);
+ IV = IU;
+ IW = IU;
+ IX = IU;
+ IY = IU;
+ JB = 0.1 * mean(AD(AD>0));
+ JC = 0;
+ JD = 0;
+ AB = 0;
+ JE = 0;
+ IP = 0;
depth = 10;
- hop_max = 0;
- hop_cnt = 0;
- liftPenalty=0;
- % calculate all possible moves
- [lJumpers,lValues,lLandings] = CalculateMoves(pBoard);
-
+ JF = 0;
+ JG = 0;
+ [JH,JI,JJ] = JK(IQ);
while true
- % find highest value moves
-
- % if no moves returned, stop
- if isempty(lJumpers)
- break
- end
- preLift=0;
- preRemove=0;
- % calculate the max consecutive hops
- FindHops(pBoard,lJumpers,lLandings,lValues);
-
- % check if any moves have multiple hops
- if (hop_max ~= 0) && (hop_cnt > 2)
- for zh = 1:hop_cnt-1
- lJumpers = [lJumpers;hop_list(zh)]; % update move list with number of hops
- lLandings = [lLandings;hop_list(zh+1)]; % update move list with number of hops
- lValues = [lValues;hop_max]; % update value list with value of hops
- DoMove(numel(lJumpers)); % do the actual hop moves
- end
- else
- % find moves that create hops
- [hop_values,pos] = sort(lValues,'descend'); % find best scoring hops
- lValues = hop_values; % update value list
- lJumpers = lJumpers(pos); % eliminate all nonhop moves from list
- lLandings = lLandings(pos); % eliminate all nonhop moves from list
- ratio_values=[];
- for zh = 1:min(depth,numel(lJumpers))
- [newB,newC,newM,newV] = ...
- ProcessMove(pBoard,zh,lJumpers,lLandings,lValues);
- preRemove=lValues(zh);
- preLift=pBoard(lJumpers(zh));
- FindHops(newB,newC,newM,newV); % find possible hops
- ratio_values(zh) = ratio_max; % update value list with best hop
- end
- [max_val,pos] = max(ratio_values); % find the best hop move
- DoMove(pos) % do the best hop move
- end
+ if isempty(JH)
+ break
end
-
- % truncate the move list to the best moves
- moves(last_pos+1:end,:) = [];
-
- % nested functions follow
- function DoMove(pos)
- max_cell = lJumpers(pos); %extract the move to do from the move list
- max_move = lLandings(pos); %extract the move to do from the move list
- count = count+1; % increment the move count
- moves(count,:) = [mod(max_cell-2,rows),ceil(max_cell/rows)-2,mod(max_move-2,rows),ceil(max_move/rows)-2]; % update the move list with the move
-
- brem = (max_cell+max_move)/2; % calculate the move score
- score = score + pBoard(brem); % update the score total
- if (max_cell ~= last_move) % check if it was a hop
- score = score - pBoard(max_cell); % if it wasn't a hop, subtract the jumping peg
- end
- if (score > last_score) % check if the score improves
- last_pos = count; % update the best move list
- last_score = score; % update the best score
- end;
-
- [pBoard,lJumpers,lLandings,lValues] = ProcessMove(pBoard,pos,lJumpers,lLandings,lValues); % check the move
- last_move = max_move; % find the position of the best move
- end
-
- function FindHops(pBoard,lJumpers,lLandings,lValues)
- hop_max = 0;
- ratio_max=0;
-
- if ~isempty(lJumpers)
- dst=lLandings(1:numel(lJumpers));
-
- tmp=(~pBoard(dst+2)&pBoard(dst+1));
- tmp=(~pBoard(dst-2)&pBoard(dst-1))|tmp;
- tmp=(~pBoard(dst-2*rows)&pBoard(dst-rows))|tmp;
- tmp=(~pBoard(dst+2*rows)&pBoard(dst+rows))|tmp;
-
- idx=find(~tmp);
- if ~isempty(idx)
- tmp2=(preRemove+lValues(idx))./(pBoard(lJumpers(idx))+preLift)+1;
- [ratio_max,tmp2]=max(tmp2);
- tmp2=idx(tmp2);
- hop_max=lValues(tmp2);
- hop_cnt=2; hop_list(1)=lJumpers(tmp2); hop_list(2)=lLandings(tmp2);
- end;
-
- idx=find(tmp)';
- for ii=idx
- hopbuf(1)=lJumpers(ii);
- liftPenalty=preLift+pBoard(lJumpers(ii));
- FindHopTree(pBoard,lJumpers(ii),lLandings(ii),lValues(ii)+preRemove,2);
- end;
- end;
- end
-
- function FindHopTree(pBoard,src,dst,hop_value,count)
-
- % Update the board position
-
- pBoard(dst) = pBoard(src);
- pBoard((src+dst)/2) = 0;
- pBoard(src) = 0;
-
- % save hop
- hopbuf(count) = dst;
-
- % jump down
- if ~pBoard(dst+2) && pBoard(dst+1)>0
- FindHopTree(pBoard,dst,dst+2,hop_value+pBoard(dst+1),count+1);
- end
-
- % jump up
- if ~pBoard(dst-2) && pBoard(dst-1)>0
- FindHopTree(pBoard,dst,dst-2,hop_value+pBoard(dst-1),count+1);
- end
-
- % jump right
- if ~pBoard(dst+2*rows) && pBoard(dst+rows)>0
- FindHopTree(pBoard,dst,dst+2*rows,hop_value+pBoard(dst+rows),count+1);
- end
-
- % jump left
- if ~pBoard(dst-2*rows) && pBoard(dst-rows)>0
- FindHopTree(pBoard,dst,dst-2*rows,hop_value+pBoard(dst-rows),count+1);
- end
-
- % end of hop chain -- check for max and save route
- ratio=hop_value/liftPenalty+1;
- if ratio > ratio_max
- ratio_max=ratio;
- hop_max = hop_value;
- hop_cnt = count;
- hop_list(1:count) = hopbuf(1:count);
- end
-
- end
-
- function n = CalculateBall(pBoard,src,dst,n)
- POP = pBoard((src+dst)*0.5); % extract the jumped position peg
- if POP>0 && ~pBoard(dst) && pBoard(src)>0 % check if source is peg, dest is hole, and jumped is peg
- n = n+1; % update index
- if sum(pBoard([dst+1 dst-1 dst+rows dst-rows])>0) == 1 % check to see if there is only 1 more peg to jump next
- valbuf(n) = POP-pBoard(src)-dead_weight; % if so, add weighted score to buffer
- else
- valbuf(n) = POP-pBoard(src); % if not, add full score
- end
- cellbuf(n) = src; % update move buffers
- movebuf(n) = dst;
- end
- end
-
- function n = CalculateHole(pBoard,dst,src,n)
- pop = (src+dst)/2; % extract the jumped position index
- if pBoard(pop)>0 && pBoard(src)>0 %check to make sure source and jumped position are pegs
- n = n+1; % update index
- if sum(pBoard([dst+1 dst-1 dst+rows dst-rows])>0) == 1 % check to see if there is only 1 more peg to jump next
- valbuf(n) = pBoard(pop)-pBoard(src)-dead_weight; % if so, add weighted score to buffer
- else
- valbuf(n) = pBoard(pop)-pBoard(src); % if not, add full score
- end
- cellbuf(n) = src; % update move buffers
- movebuf(n) = dst;
- end
- end
-
- function [new_cell_list,new_value_list,new_move_list] = CalculateMoves(pBoard)
- zb = find(pBoard>0); %find indexes of all pegs on pBoard
- zz = find(~pBoard); % find indexes of all holes on pBoard
- n = 0;
- if numel(zz)<numel(zb) % if more holes than pegs
- for zi = 1:numel(zz) % repeat for each hole position
- i = zz(zi);
- %check for holes in all 4 possible destination spots
- %away from current hole
- n = CalculateHole(pBoard,i,i-2,n);
- n = CalculateHole(pBoard,i,i+2,n);
- n = CalculateHole(pBoard,i,i-rows*2,n);
- n = CalculateHole(pBoard,i,i+rows*2,n);
- end
- else
- for zi = 1:numel(zb) % repeat for each peg position
- i = zb(zi);
- %check for pegs in all 4 possible destination spots
- %away from current peg
- n = CalculateBall(pBoard,i,i-2,n);
- n = CalculateBall(pBoard,i,i+2,n);
- n = CalculateBall(pBoard,i,i-rows*2,n);
- n = CalculateBall(pBoard,i,i+rows*2,n);
- end
- end
-
- %update buffers
- new_cell_list = cellbuf(1:n);
- new_value_list = valbuf(1:n);
- new_move_list = movebuf(1:n);
- end
-
- function [pBoard,lJumpers,lLandings,lValues] = ProcessMove(pBoard,pos,lJumpers,lLandings,lValues)
- src = lJumpers(pos); %extract the source position
- dst = lLandings(pos); % extract the destination position
- pop = (src+dst)/2; % calculate the jumped position
-
- % update the pBoard
- pBoard(dst) = pBoard(src); % copy the source peg to destination spot
- pBoard(pop) = 0; % zero out the jumped spot
- pBoard(src) = 0; % zero out the source spot
-
- % check if a horizontal or vertical jump
- u = src-pop;
- if (abs(u) == 1)
- v = rows;
- else
- v = 1;
- end
-
- % eliminate the moves from move list that involve these
- % coordinates
- lLandings(logical(lLandings == dst)) = 0;
- lLandings(logical(lJumpers == src)) = 0;
- lLandings(logical(lJumpers == pop)) = 0;
-
- % eliminate moves that are 1 peg away from source
- rem_src = find(lJumpers == src-v);
- lLandings(rem_src(lLandings(rem_src) == src+v)) = 0;
- rem_src = find(lJumpers == src+v);
- lLandings(rem_src(lLandings(rem_src) == src-v)) = 0;
- rem_src = find(lJumpers == src-v-u);
- lLandings(rem_src(lLandings(rem_src) == src+v-u)) = 0;
- rem_src = find(lJumpers == src+v-u);
- lLandings(rem_src(lLandings(rem_src) == src-v-u)) = 0;
-
- % sort remaining moves and update other lists with the indexes
- [lLandings,rem_dst] = sort(lLandings,'descend');
- lJumpers = lJumpers(rem_dst);
- lValues = lValues(rem_dst);
- ncnt = find(~lLandings,1,'first');
-
- % truncate lists at point where moves involve off limits areas
- lJumpers = lJumpers(1:ncnt-1);
- lValues = lValues(1:ncnt-1);
- lLandings = lLandings(1:ncnt-1);
-
- % check all the new possible moves based upon updated pBoard
- n = 0;
- twou=2*u;twov=2*v;
- n = CalculateBall(pBoard,src-3*u,src-u,n);
- n = CalculateBall(pBoard,src+twov-u,src-u,n);
- n = CalculateBall(pBoard,src+twov,src,n);
- n = CalculateBall(pBoard,src+twou,src,n);
- n = CalculateBall(pBoard,src-twov,src,n);
- n = CalculateBall(pBoard,src-twov-u,src-u,n);
- n = CalculateBall(pBoard,dst,dst-twou,n);
- n = CalculateBall(pBoard,dst,dst-twov,n);
- n = CalculateBall(pBoard,dst,dst+twov,n);
- clf = src-v-twou;
- crt = src+v-twou;
- if ~pBoard(clf)
- n = CalculateBall(pBoard,crt,clf,n);
- end
- if ~pBoard(crt)
- n = CalculateBall(pBoard,clf,crt,n);
- end
-
- % if updated moves exist than update moves list
- if (n > 0)
- if (ncnt > 1)
- lJumpers = [lJumpers; cellbuf(1:n)];
- lLandings = [lLandings; movebuf(1:n)];
- lValues = [lValues; valbuf(1:n)];
- else
- lJumpers = cellbuf(1:n);
- lValues = valbuf(1:n);
- lLandings = movebuf(1:n);
- end
- end
- end
-
+ JQ(IQ,JH,JJ,JI);
+ if (JF ~= 0) && (JG > 2)
+ for JS = 1:JG-1
+ JH = [JH;IY(JS)];
+ JJ = [JJ;IY(JS+1)];
+ JI = [JI;JF];
+ DoMove(numel(JH));
end
-
- %======================================================================
- function [moves,v] = subsol( ...
- board, ...
- d, ...
- rfac, ...
- F,T,M, ...
- pegCount, ...
- TT,MM,MV,rMap) %, ...
- % moveid1,moveid2,moveid3)
-
- rrr = rfac*rand(5000,1); % create a vector of 5000 random values
- moves = zeros(pegCount-1,4); % preallocate maximum possible move list based on number of pegs
- v0 = zeros(pegCount-1,1); % preallocate maximum size of score list
- Bzero = ~board; % create inverse board where 1 is a hole and every else is a zero, including offlimits
- Bpos = board>0; % create board with pegs all as 1 and everything else 0
- Bmax = max(board, 0); % create board with offlimits as holes
-
- % search for moves where source is peg, destination is hole and jumped spot is peg
- validMoves = (Bpos(F) & Bzero(T) & Bpos(M));
- % extract indexes of valid moves
- h = find(validMoves);
-
- C0 = board(M(h))-board(F(h)); % calculate score for all valid 1st moves
- if d
- CV = max(Bmax(MM(h,:)).*Bzero(TT(h,:)),[],2); % check to see if next colinear move is best
else
- CV = 0;
+ [JW,JX] = sort(JI,'descend');
+ JI = JW;
+ JH = JH(JX);
+ JJ = JJ(JX);
+ for JS = 1:min(depth,numel(JH))
+ [KD,newC,KE,KF] = ...
+ KG(IQ,JS,JH,JJ,JI);
+ JQ(KD,newC,KE,KF);
+ JW(JS) = JW(JS) + JF;
end
- % add jumped peg to 2nd jump and find best 2 move jump
- [v,k] = max( (1+rrr(1:length(C0))).*(C0+CV*d) );
- v0(1) = C0(k); % extract score of best 1st jump score
- k = h(k); % extract index of best 2 move jump
- moves(1,:) = MV(k,:); % add best move (1st jump) to movelist
- T0 = T(k); % extract 1st jump destination spot
- F0 = F(k); % extract source spot
- M0 = M(k); % calculate jumped spot
- t = 2; % increment move count
-
- % Update board.
- Bmax(T0) = board(F0); % copy the jumping peg value
- Bmax(F0) = 0; % zero out the jumping spot peg
- Bmax(M0) = 0; % zero out the jumped spot peg
- board(T0) = board(F0); % update destination spot with source spot peg
- Bzero(T0) = false; % set the destination spot peg
- Bpos(T0) = true; % set the destination spot peg
- board(F0) = 0; % zero out source spot peg
- Bzero(F0) = true; % create updated inverse board
- Bpos(F0) = false; % zero out the source spot peg
- board(M0)=0; % zero out jumped spot peg
- Bpos(M0) = false; % zero out the jumped spot peg
- Bzero(M0) = true; % create updated inverse board
-
- % assemble list of moves affected by the current move
- allMoves = rMap(k,:);
- allMoves = allMoves(allMoves>0);
- % FF=[F0 M0 T0];
- % originatingMoves = moveid1(FF,:);
- % originatingMoves = originatingMoves(originatingMoves > 0);
- % jumpedMoves = moveid2(FF,:);
- % jumpedMoves = jumpedMoves(jumpedMoves > 0);
- % terminatingMoves = moveid3(FF,:);
- % terminatingMoves = terminatingMoves(terminatingMoves > 0);
- % allMoves = [originatingMoves; jumpedMoves; terminatingMoves];
- % % search for valid moves in new board (original method)
- validMoves(allMoves) = Bpos(F(allMoves)) & Bzero(T(allMoves)) & Bpos(M(allMoves));
- % extract indexes of valid moves
- h = find(validMoves);
- while ~isempty(h)
- if (numel(h) > 1)
- c = find(F(h) == T0); % find indexes of jumps with source peg that is same as last one moved
- if ~isempty(c) % if any current 2 jump moves contain the last peg
- h = h(c); % extract the jump index
- C0 = board(M(h)); % seed possible 2nd jumps board with jumped peg value for all jumps the match last jump end
- else
- C0 = board(M(h))-board(F(h)); % calculate score for all valid 1st moves
- end
-
- if d
- CV = max(Bmax(MM(h,:)).*Bzero(TT(h,:)),[],2); % check to see if next colinear move is best
- else
- CV = 0;
- end
-
- % add jumped peg to 2nd jump and find best 2 move jump
- [v,k] = max( (1+rrr(1:length(C0))).*(C0+CV*d) );
- v0(t) = C0(k); % extract score of best 1st jump score
- k = h(k); % extract index of best 2 move jump
- else
- k = h(1); % extract the move position
- v0(t) = board(M(k))-board(F(k))*(F(k)~=T0); % calculate the jump score
- end
- moves(t,:) = MV(k,:); % add best move (1st jump) to movelist
- T0 = T(k); % extract 1st jump destination spot
- F0 = F(k); % extract source spot
- M0 = M(k); % calculate jumped spot
- t = t+1; % increment move count
-
- % Update board.
- Bmax(T0) = board(F0); % copy the jumping peg value
- Bmax(F0) = 0; % zero out the jumping spot peg
- Bmax(M0) = 0; % zero out the jumped spot peg
- board(T0) = board(F0); % update destination spot with source spot peg
- Bzero(T0) = false; % set the destination spot peg
- Bpos(T0) = true; % set the destination spot peg
- board(F0) = 0; % zero out source spot peg
- Bzero(F0) = true; % create updated inverse board
- Bpos(F0) = false; % zero out the source spot peg
- board(M0)=0; % zero out jumped spot peg
- Bpos(M0) = false; % zero out the jumped spot peg
- Bzero(M0) = true; % create updated inverse board
-
- % assemble list of moves affected by the current move
- allMoves = rMap(k,:);
- allMoves = allMoves(allMoves>0);
- % FF=[F0 M0 T0];
- % originatingMoves = moveid1(FF,:);
- % originatingMoves = originatingMoves(originatingMoves > 0);
- % jumpedMoves = moveid2(FF,:);
- % jumpedMoves = jumpedMoves(jumpedMoves > 0);
- % terminatingMoves = moveid3(FF,:);
- % terminatingMoves = terminatingMoves(terminatingMoves > 0);
- % allMoves = [originatingMoves; jumpedMoves; terminatingMoves];
- % search for valid moves in new board (original method)
- validMoves(allMoves) = Bpos(F(allMoves)) & Bzero(T(allMoves)) & Bpos(M(allMoves));
-
- % extract indexes of valid moves
- h = find(validMoves);
+ [KH,JX] = max(JW);
+ DoMove(JX)
end
-
- v0 = cumsum(v0); % create cumulative sum of scores in movelist
- [v,t] = max(v0); % extract location of best cumulative score
- moves = moves(1:t,:); % output moves up to best location
-
end
-
- %======================================================================
- function [moves,v] = subsoltweak( ...
- board, ...
- F,T,M, ...
- pegCount, ...
- TT,MM,MV,MVV, ...
- moveid1,moveid2,moveid3)
-
- moves = zeros(pegCount-1,4); % preallocate maximum possible move list based on number of pegs
- v0 = zeros(pegCount-1,1); % preallocate maximum size of score list
- Bzero = ~board; % create inverse board where 1 is a hole and every else is a zero, including offlimits
- Bpos = board>0; % create board with pegs all as 1 and everything else 0
- Bmax = max(board, 0); % create board with offlimits as holes
-
- hs = (Bpos(F) & Bzero(T) & Bpos(M)); % search for moves where source is peg, destination is hole and jumped spot is peg
- h = find(hs); % extract indexes of valid moves
- C0 = board(M(h))-board(F(h)); % calculate score for all valid 1st moves
- [CV,kc] = max(Bmax(MM(h,:)).*Bzero(TT(h,:)),[],2); % check to see if next colinear move is best
- [v,k] = max(C0+CV); % add jumped peg to 2nd jump and find best 2 move jump
- v0(1) = C0(k); % extract score of best 1st jump score
- k = h(k); % extract index of best 2 move jump
- moves(1,:) = MV(k,:); % add best move (1st jump) to movelist
- F0 = F(k); % extract source spot
- t = 2; % increment move count
- T0=T(k); % extract 1st jump destination spot
- M0=M(k);
- Bmax(T0)=board(F0);Bmax(F0)=0;Bmax(M0)=0;
- board(T0) = board(F0); % update destination spot with source spot peg
- Bzero(T0) = false; % set the destination spot peg
- Bpos(T0) = true; % set the destination spot peg
- board(F0) = 0; % zero out source spot peg
- Bzero(F0) = true; % create updated inverse board
- Bpos(F0) = false; % zero out the source spot peg
- board(M0) = 0; % zero out jumped spot peg
- Bpos(M0) = false; % zero out the jumped spot peg
- Bzero(M0) = true; % create updated inverse board
-
- % allMoves1 = rMap{k};
- % allMoves1 = allMoves1(allMoves1>0);
- FF=[F0 M(k) T0];
- % assemble list of moves affected by the current move
- originatingMoves = moveid1(FF,:);
- originatingMoves = originatingMoves(originatingMoves>0); % moves originating at spots involved in last move
- jumpedMoves = moveid2(FF,:);
- jumpedMoves = jumpedMoves(jumpedMoves>0); % moves jumping over spots involved in last move
- terminatingMoves = moveid3(FF,:);
- terminatingMoves = terminatingMoves(terminatingMoves>0); % moves terminating at spots involved in last move
- allMoves = [originatingMoves; jumpedMoves; terminatingMoves]; % combine the moves into 1 list
- hs(allMoves) = Bpos(F(allMoves)) & Bzero(T(allMoves)) & Bpos(M(allMoves)); % search for valid moves in new board (original method)
-
- % extract indexes of valid moves
- h = find(hs);
- while ~isempty(h)
- c = find(F(h) == T0); % find indexes of jumps with source peg that is same as last one moved
- if ~isempty(c) % if any current 2 jump moves contain the last peg
- h = h(c); % extract the jump index
- C0 = board(M(h)); % seed possible 2nd jumps board with jumped peg value for all jumps the match last jump end
- else
- C0 = board(M(h))-board(F(h)); % calculate score for all valid 1st moves
- end
-
- [CV,kc] = max(Bmax(MM(h,:)).*Bzero(TT(h,:)),[],2); % check to see if next colinear move is best
- [v,k] = max(C0+CV); % add jumped peg to 2nd jump and find best 2 move jump
- v0(t) = C0(k); % extract score of best 1st jump score
- cv=CV(k);kc=kc(k);
- k = h(k); % extract index of best 2 move jump
-
- moves(t,:) = MV(k,:); % add best move (1st jump) to movelist
- F0 = F(k); % extract source spot
- t = t+1; % increment move count
- if ~cv
- % allMoves1 = rMap{k};
- T0=T(k); % extract 1st jump destination spot
- FF=[F0 M(k) T0];
- else
- T0=TT(k,kc);
- % allMoves1 = rMap2{k,kc};
- M0=MM(k,kc);
- moves(t,:)=MVV{kc}(k,:);
- FF=[F0 M(k) M0 T0];
- v0(t)=cv;
- board(M0)=0;Bzero(M0)=true;Bpos(M0)=false;Bmax(M0)=0;
- t=t+1;
- end
- M0=M(k);
- Bmax(T0)=board(F0);Bmax(F0)=0;Bmax(M0)=0;
- board(T0) = board(F0); % update destination spot with source spot peg
- Bzero(T0) = false; % set the destination spot peg
- Bpos(T0) = true; % set the destination spot peg
- board(F0) = 0; % zero out source spot peg
- Bzero(F0) = true; % create updated inverse board
- Bpos(F0) = false; % zero out the source spot peg
- board(M0) = 0; % zero out jumped spot peg
- Bpos(M0) = false; % zero out the jumped spot peg
- Bzero(M0) = true; % create updated inverse board
-
- % assemble list of moves affected by the current move
- % allMoves1 = allMoves1(allMoves1>0);
- originatingMoves = moveid1(FF,:);
- originatingMoves = originatingMoves(originatingMoves>0); % moves originating at spots involved in last move
- jumpedMoves = moveid2(FF,:);
- jumpedMoves = jumpedMoves(jumpedMoves>0); % moves jumping over spots involved in last move
- terminatingMoves = moveid3(FF,:);
- terminatingMoves = terminatingMoves(terminatingMoves>0); % moves terminating at spots involved in last move
- allMoves = [originatingMoves; jumpedMoves; terminatingMoves]; % combine the moves into 1 list
- hs(allMoves) = Bpos(F(allMoves)) & Bzero(T(allMoves)) & Bpos(M(allMoves)); % search for valid moves in new board (original method)
-
- % extract indexes of valid moves
- h = find(hs);
+ AA(JE+1:end,:) = [];
+ function DoMove(JX)
+ KK = JH(JX);
+ KM = JJ(JX);
+ JC = JC+1;
+ AA(JC,:) = [mod(KK-2,rows),ceil(KK/rows)-2,mod(KM-2,rows),ceil(KM/rows)-2];
+ KO = (KK+KM)/2;
+ AB = AB + IQ(KO);
+ if (KK ~= JD)
+ AB = AB - IQ(KK);
end
-
- v0 = cumsum(v0); % create cumulative sum of scores in movelist
- [v,t] = max(v0); % extract location of best cumulative score
- moves = moves(1:t,:); % output moves up to best location
-
+ if (AB > IP)
+ JE = JC;
+ IP = AB;
+ end;
+ [IQ,JH,JJ,JI] = KG(IQ,JX,JH,JJ,JI);
+ JD = KM;
+ end
+ function JQ(IQ,JH,JJ,JI)
+ JF = 0;
+ if ~isempty(JH)
+ KV=JJ(1:numel(JH));
+ KW=(~IQ(KV+2)&IQ(KV+1));
+ KW=(~IQ(KV-2)&IQ(KV-1))|KW;
+ KW=(~IQ(KV-2*rows)&IQ(KV-rows))|KW;
+ KW=(~IQ(KV+2*rows)&IQ(KV+rows))|KW;
+ KX=find(~KW);
+ if ~isempty(KX)
+ KY=JI(KX); [JF,KY]=max(KY); KY=KX(KY);
+ JG=2; IY(1)=JH(KY); IY(2)=JJ(KY);
+ end;
+ KX=find(KW)';
+ for KZ=KX
+ IX(1)=JH(KZ);
+ LA(IQ,JH(KZ),JJ(KZ),JI(KZ),2);
+ end;
+ end;
+ end
+ function LA(IQ,LB,KV,LC,JC)
+ IQ(KV) = IQ(LB);
+ IQ((LB+KV)/2) = 0;
+ IQ(LB) = 0;
+ IX(JC) = KV;
+ if ~IQ(KV+2) && IQ(KV+1)>0
+ LA(IQ,KV,KV+2,LC+IQ(KV+1),JC+1);
+ end
+ if ~IQ(KV-2) && IQ(KV-1)>0
+ LA(IQ,KV,KV-2,LC+IQ(KV-1),JC+1);
+ end
+ if ~IQ(KV+2*rows) && IQ(KV+rows)>0
+ LA(IQ,KV,KV+2*rows,LC+IQ(KV+rows),JC+1);
+ end
+ if ~IQ(KV-2*rows) && IQ(KV-rows)>0
+ LA(IQ,KV,KV-2*rows,LC+IQ(KV-rows),JC+1);
+ end
+ if LC > JF
+ JF = LC;
+ JG = JC;
+ IY(1:JC) = IX(1:JC);
+ end
+ end
+ function n = LE(IQ,LB,KV,n)
+ LF = IQ((LB+KV)*0.5);
+ if LF>0 && ~IQ(KV) && IQ(LB)>0
+ n = n+1;
+ if sum(IQ([KV+1 KV-1 KV+rows KV-rows])>0) == 1
+ IV(n) = LF-IQ(LB)-JB;
+ else
+ IV(n) = LF-IQ(LB);
+ end
+ IU(n) = LB;
+ IW(n) = KV;
+ end
+ end
+ function n = LL(IQ,KV,LB,n)
+ LM = (LB+KV)/2;
+ if IQ(LM)>0 && IQ(LB)>0
+ n = n+1;
+ if sum(IQ([KV+1 KV-1 KV+rows KV-rows])>0) == 1
+ IV(n) = IQ(LM)-IQ(LB)-JB;
+ else
+ IV(n) = IQ(LM)-IQ(LB);
+ end
+ IU(n) = LB;
+ IW(n) = KV;
+ end
+ end
+ function [LO,LP,LQ] = JK(IQ)
+ LR = find(IQ>0);
+ LS = find(~IQ);
+ n = 0;
+ if numel(LS)<numel(LR)
+ for LU = 1:numel(LS)
+ i = LS(LU);
+ n = LL(IQ,i,i-2,n);
+ n = LL(IQ,i,i+2,n);
+ n = LL(IQ,i,i-rows*2,n);
+ n = LL(IQ,i,i+rows*2,n);
+ end
+ else
+ for LU = 1:numel(LR)
+ i = LR(LU);
+ n = LE(IQ,i,i-2,n);
+ n = LE(IQ,i,i+2,n);
+ n = LE(IQ,i,i-rows*2,n);
+ n = LE(IQ,i,i+rows*2,n);
+ end
+ end
+ LO = IU(1:n);
+ LP = IV(1:n);
+ LQ = IW(1:n);
+ end
+ function [IQ,JH,JJ,JI] = KG(IQ,JX,JH,JJ,JI)
+ LB = JH(JX);
+ KV = JJ(JX);
+ LM = (LB+KV)/2;
+ IQ(KV) = IQ(LB);
+ IQ(LM) = 0;
+ IQ(LB) = 0;
+ MA = LB-LM;
+ if (abs(MA) == 1)
+ MB = rows;
+ else
+ MB = 1;
+ end
+ JJ(logical(JJ == KV)) = 0;
+ JJ(logical(JH == LB)) = 0;
+ JJ(logical(JH == LM)) = 0;
+ MD = find(JH == LB-MB);
+ JJ(MD(JJ(MD) == LB+MB)) = 0;
+ MD = find(JH == LB+MB);
+ JJ(MD(JJ(MD) == LB-MB)) = 0;
+ MD = find(JH == LB-MB-MA);
+ JJ(MD(JJ(MD) == LB+MB-MA)) = 0;
+ MD = find(JH == LB+MB-MA);
+ JJ(MD(JJ(MD) == LB-MB-MA)) = 0;
+ [JJ,MF] = sort(JJ,'descend');
+ JH = JH(MF);
+ JI = JI(MF);
+ MG = find(~JJ,1,'first');
+ JH = JH(1:MG-1);
+ JI = JI(1:MG-1);
+ JJ = JJ(1:MG-1);
+ n = 0;
+ n = LE(IQ,LB-3*MA,LB-MA,n);
+ n = LE(IQ,LB+2*MB-MA,LB-MA,n);
+ n = LE(IQ,LB+2*MB,LB,n);
+ n = LE(IQ,LB+2*MA,LB,n);
+ n = LE(IQ,LB-2*MB,LB,n);
+ n = LE(IQ,LB-2*MB-MA,LB-MA,n);
+ n = LE(IQ,KV,KV-2*MA,n);
+ n = LE(IQ,KV,KV-2*MB,n);
+ n = LE(IQ,KV,KV+2*MB,n);
+ clf = LB-MB-2*MA;
+ MK = LB+MB-2*MA;
+ if ~IQ(clf)
+ n = LE(IQ,MK,clf,n);
+ end
+ if ~IQ(MK)
+ n = LE(IQ,clf,MK,n);
+ end
+ if (n > 0)
+ if (MG > 1)
+ JH = [JH; IU(1:n)];
+ JJ = [JJ; IW(1:n)];
+ JI = [JI; IV(1:n)];
+ else
+ JH = IU(1:n);
+ JI = IV(1:n);
+ JJ = IW(1:n);
+ end
+ end
+ end
+ end
+ function [AA,MB] = HE( ...
+ AD, ...
+ ML, ...
+ MM, ...
+ EV,EZ,FB, ...
+ CK, ...
+ FX,GB,GD, ...
+ FJ,FK,FL)
+ MN = MM*rand(5000,1);
+ AA = zeros(CK-1,4);
+ MQ = zeros(CK-1,1);
+ MR = ~AD;
+ MV = AD>0;
+ MX = max(AD, 0);
+ MZ = (MV(EV) & MR(EZ) & MV(FB));
+ NA = find(MZ);
+ NB = AD(FB(NA))-AD(EV(NA));
+ if ML
+ CV = max(MX(GB(NA,:)).*MR(FX(NA,:)),[],2);
+ else
+ CV = 0;
+ end
+ [MB,HH] = max( (1+MN(1:length(NB))).*(NB+CV*ML) );
+ MQ(1) = NB(HH);
+ HH = NA(HH);
+ AA(1,:) = GD(HH,:);
+ ND = EZ(HH);
+ NE = EV(HH);
+ NF = FB(HH);
+ BN = 2;
+ MX(ND) = AD(NE);
+ MX(NE) = 0;
+ MX(NF) = 0;
+ AD(ND) = AD(NE);
+ MR(ND) = false;
+ MV(ND) = true;
+ AD(NE) = 0;
+ MR(NE) = true;
+ MV(NE) = false;
+ AD(NF)=0;
+ MV(NF) = false;
+ MR(NF) = true;
+ NI=[NE NF ND];
+ NJ = FJ(NI,:);
+ NJ = NJ(NJ > 0);
+ NK = FK(NI,:);
+ NK = NK(NK > 0);
+ NL = FL(NI,:);
+ NL = NL(NL > 0);
+ NM = [NJ; NK; NL];
+ MZ(NM) = MV(EV(NM)) & MR(EZ(NM)) & MV(FB(NM));
+ NA = find(MZ);
+ while ~isempty(NA)
+ if (numel(NA) > 1)
+ NO = find(EV(NA) == ND);
+ if ~isempty(NO)
+ NA = NA(NO);
+ NB = AD(FB(NA));
+ else
+ NB = AD(FB(NA))-AD(EV(NA));
+ end
+ if ML
+ CV = max(MX(GB(NA,:)).*MR(FX(NA,:)),[],2);
+ else
+ CV = 0;
+ end
+ [MB,HH] = max( (1+MN(1:length(NB))).*(NB+CV*ML) );
+ MQ(BN) = NB(HH);
+ HH = NA(HH);
+ else
+ HH = NA(1);
+ MQ(BN) = AD(FB(HH))-AD(EV(HH));
+ end
+ AA(BN,:) = GD(HH,:);
+ ND = EZ(HH);
+ NE = EV(HH);
+ NF = FB(HH);
+ BN = BN+1;
+ MX(ND) = AD(NE);
+ MX(NE) = 0;
+ MX(NF) = 0;
+ AD(ND) = AD(NE);
+ MR(ND) = false;
+ MV(ND) = true;
+ AD(NE) = 0;
+ MR(NE) = true;
+ MV(NE) = false;
+ AD(NF)=0;
+ MV(NF) = false;
+ MR(NF) = true;
+ NI=[NE NF ND];
+ NJ = FJ(NI,:);
+ NJ = NJ(NJ > 0);
+ NK = FK(NI,:);
+ NK = NK(NK > 0);
+ NL = FL(NI,:);
+ NL = NL(NL > 0);
+ NM = [NJ; NK; NL];
+ MZ(NM) = MV(EV(NM)) & MR(EZ(NM)) & MV(FB(NM));
+ NA = find(MZ);
+ end
+ MQ = cumsum(MQ);
+ [MB,BN] = max(MQ);
+ AA = AA(1:BN,:);
+ end
+ function [AA,MB] = GJ( ...
+ AD, ...
+ EV,EZ,FB, ...
+ CK, ...
+ FX,GB,GD,GH, ...
+ FJ,FK,FL)
+ AA = zeros(CK-1,4);
+ MQ = zeros(CK-1,1);
+ MR = ~AD;
+ MV = AD>0;
+ MX = max(AD, 0);
+ NX = (MV(EV) & MR(EZ) & MV(FB));
+ NA = find(NX);
+ NB = AD(FB(NA))-AD(EV(NA));
+ [CV,NY] = max(MX(GB(NA,:)).*MR(FX(NA,:)),[],2);
+ [MB,HH] = max(NB+CV);
+ MQ(1) = NB(HH);
+ HH = NA(HH);
+ AA(1,:) = GD(HH,:);
+ NE = EV(HH);
+ BN = 2;
+ ND=EZ(HH);
+ NI=[NE FB(HH) ND];
+ NF=FB(HH);
+ MX(ND)=AD(NE);MX(NE)=0;MX(NF)=0;
+ AD(ND) = AD(NE);
+ MR(ND) = false;
+ MV(ND) = true;
+ AD(NE) = 0;
+ MR(NE) = true;
+ MV(NE) = false;
+ AD(NF) = 0;
+ MV(NF) = false;
+ MR(NF) = true;
+ NJ = FJ(NI,:);
+ NJ = NJ(NJ>0);
+ NK = FK(NI,:);
+ NK = NK(NK>0);
+ NL = FL(NI,:);
+ NL = NL(NL>0);
+ NM = [NJ; NK; NL];
+ NX(NM) = MV(EV(NM)) & MR(EZ(NM)) & MV(FB(NM));
+ NA = find(NX);
+ while ~isempty(NA)
+ NO = find(EV(NA) == ND);
+ if ~isempty(NO)
+ NA = NA(NO);
+ NB = AD(FB(NA));
+ else
+ NB = AD(FB(NA))-AD(EV(NA));
+ end
+ [CV,NY] = max(MX(GB(NA,:)).*MR(FX(NA,:)),[],2);
+ [MB,HH] = max(NB+CV);
+ MQ(BN) = NB(HH);
+ cv=CV(HH);NY=NY(HH);
+ HH = NA(HH);
+ AA(BN,:) = GD(HH,:);
+ NE = EV(HH);
+ BN = BN+1;
+ if ~cv
+ ND=EZ(HH);
+ NI=[NE FB(HH) ND];
+ else
+ ND=FX(HH,NY);
+ NF=GB(HH,NY);
+ AA(BN,:)=GH{NY}(HH,:);
+ NI=[NE FB(HH) NF ND];
+ MQ(BN)=cv;
+ AD(NF)=0;MR(NF)=true;MV(NF)=false;MX(NF)=0;
+ BN=BN+1;
+ end
+ NF=FB(HH);
+ MX(ND)=AD(NE);MX(NE)=0;MX(NF)=0;
+ AD(ND) = AD(NE);
+ MR(ND) = false;
+ MV(ND) = true;
+ AD(NE) = 0;
+ MR(NE) = true;
+ MV(NE) = false;
+ AD(NF) = 0;
+ MV(NF) = false;
+ MR(NF) = true;
+ NJ = FJ(NI,:);
+ NJ = NJ(NJ>0);
+ NK = FK(NI,:);
+ NK = NK(NK>0);
+ NL = FL(NI,:);
+ NL = NL(NL>0);
+ NM = [NJ; NK; NL];
+ NX(NM) = MV(EV(NM)) & MR(EZ(NM)) & MV(FB(NM));
+ NA = find(NX);
+ end
+ OC = cumsum(MQ);
+ [MB,BN] = max(OC);
+ AA = AA(1:BN,:);
end
|