function colors = solver(board,goal)
% Flooding solver
% Commented by Alan Chalker
% Code from a variety of other leading entries
% 11/7/09
% Please leave comments in if you reuse this!!!!!
% board = input game board to flood
% goal = index of target element
% colors = vector of colors change order
rand('seed',17);
randn('seed',17);
board=board*3;
m=(max(max(board));
[R,C]=size(board);
if m==108 || m==111 || m>237
s=inf;
for i=1:(m-102)
[c,score] = switcheroo2(board,goal,R,C));
if score<s
s=score;
colors=c/3;
end
end
else
colors = (glean(board,goal,R,C))/3;
end
end
function [colors,score] = switcheroo2(board,goal,rows,columns)
%finds all the elements with matching pairs next to them and returns
%details on them
% find elements with matching pairs to the right and cumulatively sum
% all the columns to find the number in each. Shift the result 1
% element right and cumulatively sum all the
% column cumsums, then create a new board with each row populated with
% these final cumsums
rightmatches = cumsum([ones(1,columns);board(1:rows-1,:)~=board(2:rows,:)]);
rightmatches = rightmatches+repmat([0 cumsum(rightmatches(rows,1:columns-1))],rows,1);
numberpairs = rightmatches(end); % extract number of pairs found
lowermatches = find([board(:,1:columns-1)==board(:,2:rows),zeros(rows,1)]); % find elements with matching pairs below
% creates a large board for indexing and populates with 1s whereever the
% row / col correspond to a found matching pair index
matchedpairs = logical(speye(numberpairs));
matchedpairs(rightmatches(lowermatches)+numberpairs*rightmatches(lowermatches+rows)-numberpairs) = true;
indexvector = 1:numberpairs; % pair index vector
for count = 1:numberpairs
indexvector(count) = min(indexvector(matchedpairs(:,count))); %set each elemtn of the index vector equal to sum of the corresponding column pairs
end
[uniqueindexvector,uniqueindices,columnindices] = unique(indexvector); %find unique column indexes
paircolumns = columnindices(rightmatches); % return ones that have pairs in them
allColors = nonzeros(unique(board))';
nColors = numel(allColors);
colors = zeros(1,numberpairs); % preallocate colors with max possible pairs
flood = false(rows,columns); %preallocate a new board array
flood(1) = true; %set starting element to true
count = 0; % init counter
while ~flood(goal) % loop until get to target
count = count+1;
xflood = ~flood&([false(1,columns);flood(1:rows-1,:)]|[false(rows,1),flood(:,1:columns-1)]|[flood(2:rows,:);false(1,columns)]|[flood(:,2:columns),false(rows,1)]);
isInXflood = false(nColors,1);
bx = board(xflood);
for i=1:nColors
if any(bx==allColors(i))
isInXflood(i) = 1;
end
end
cval = allColors(isInXflood);
% cval = nonzeros(unique(board(xflood)));
scr = rand(1,numel(cval));
scr(cval > max(max(board))-30) = 2;
[sch,ich] = min(scr);
colors(count) = cval(ich);
if ~xflood(goal) && cval(ich)~=board(goal)
flood = flood|ismember(paircolumns,paircolumns(xflood&(board==cval(ich))));
else
floodBF = flood;
flood = flood|ismember(paircolumns,paircolumns(xflood&(board==cval(ich))));
end
end
insert_colors = unique(cval(cval > max(max(board))-1))';
insert_colors(insert_colors==board(goal))=[];
colors_org = colors(1:count);
colors = [colors(1:count-1) insert_colors colors(count)];
if numel(insert_colors)>0
%board(flood==false) = board(goal);
for ii=1:numel(insert_colors)+1
xflood = ~floodBF&([false(1,columns);floodBF(1:rows-1,:)]...
|[false(rows,1),floodBF(:,1:columns-1)]...
|[floodBF(2:rows,:);false(1,columns)]...
|[floodBF(:,2:columns),false(rows,1)]);
cval = colors(count);
floodBF = floodBF|ismember(paircolumns,paircolumns(xflood&(board==cval)));
count=count+1;
end
boardBF = board;
boardBF(floodBF==true) = board(goal);
scoreBF = sum(boardBF(:))+sum(colors);
else
scoreBF = inf;
end
board(flood==true) = board(goal);score = sum(board(:))+sum(colors_org);
if scoreBF>score
colors=colors_org;
else
score=scoreBF;
end
end
function colors = glean(board,goal,rows,columns)
compactboard = uint8(board);%make a less memory intensive (uint8 type) version of board
maxvalue = max(max(board)); %find the max value
[matchindices matchvalues numberblocks] = group(compactboard); %find all elements with a matching pair next to them
%creates a vector where each element corresponds to the summed relative
%difference between matching pairs and the goal value
newboard = int32(board); %make a int32 version of the board
goalvalue = newboard(goal); % extract the goal value
newboard = goalvalue - newboard(:); %calculate the difference between each element and the goal element
newboard(board==0) = 1e6; % anywhere there is a wall make the value very large
%creates a vector where each element corresponds to the summed relative
%difference between matching pairs and the goal value using the accumarray
%function to accumulatively sum up the elements in newboard, and anywhere
%it is nonzero adds an offset based upon the diff from the goal value
blockcosts = int32(accumarray(matchindices(:), newboard, [numberblocks 1]));
blockcosts(blockcosts>0)=blockcosts(blockcosts>0) + 1.22*(goalvalue-int32(matchvalues(blockcosts>0)'));% finds the locations of matching block pairs that match nearby ones
matchesindex = uint32(matchindices); % make a uint32 version of match indexes
[rows2 columns2] = size(matchindices); % find size of matchindices
blockmatches = false(numberblocks); % preallocate a matrix for the block matches
downmatches = matchindices(1:rows2-1,:) ~= matchindices(2:rows2,:); % find all matching pairs with another matching pair below
uppermatches = matchesindex([downmatches; false(1,columns2)]); % extract the indices of the upper matches
lowerrmatches = matchesindex([false(1,columns2); downmatches]); % extract indices of the lower matches
% set appropriate element of blockmatches to 1 to indicate a block match
blockmatches(uppermatches+(lowerrmatches-1)*numberblocks) = true;
blockmatches(lowerrmatches+(uppermatches-1)*numberblocks) = true;
%repeat the above process with left-right matching blockes
rightmatches = matchindices(:,1:columns2-1) ~= matchindices(:,2:columns2);
eastmatches = matchesindex([rightmatches false(rows2,1)]);
westmatches = matchesindex([false(rows2,1) rightmatches]);
blockmatches(eastmatches+(westmatches-1)*numberblocks) = true;
blockmatches(westmatches+(eastmatches-1)*numberblocks) = true;[rows3 columns3] = find(blockmatches); % find locations of all matching block pairs
matchvalues2 = matchvalues + 3; % create new version of matchvalues with an offset
matchvalues2(matchvalues2==3) = 1;% set anywhere there wasn't a matchvalue to 1, all other locations are greater than 1
matchingblocks = ones(numberblocks, class(matchvalues2)); % preallocate output with ones
matchingblocks(blockmatches) = matchvalues2(rows3); % set the matching blocks equal to the values of them
blockcosts = push_channels(matchingblocks, blockcosts);%update blockcosts to account for large regions
colors = dijkstra(matchingblocks, maxvalue, blockcosts, 1, matchindices(goal));
ecc = double(matchvalues)-board(goal);hcc = hist(matchindices(:),1:numberblocks);
cben = hcc.*ecc; % benefit of each matchindices
flood = matchindices==matchindices(1);%calculate map "flooding" based on provided color vector (except last step)
for c = colors(1:end-1)'
xflood = ~flood&([false(1,columns);flood(1:end-1,:)]|[false(rows,1),flood(:,1:end-1)]|[flood(2:end,:);false(1,columns)]|[flood(:,2:end),false(rows,1)]);
matchvalues = matchindices(xflood&(board==c));
flood = flood|ismember(matchindices,matchvalues);
end
mamax=0;
insert_colors=[];
xflood = ~flood&([false(1,columns);flood(1:end-1,:)]|[false(rows,1),flood(:,1:end-1)]|[flood(2:end,:);false(1,columns)]|[flood(:,2:end),false(rows,1)]);xfloodBF=xflood;
floodBF=flood;
cval = nonzeros(unique(board(xflood)));
cval(cval==colors(end))=[];
cval_org=cval;
ncval_org = numel(cval);
for ii=1:ncval_org
ncval=ncval_org;
extra_score=0;extra_colors=[];
xflood = xfloodBF;
flood=floodBF;
cval=circshift(cval_org,[ii-1,0]);
first=true;
while true
if ~first
xflood = ~flood&([false(1,columns);flood(1:end-1,:)]|[false(rows,1),flood(:,1:end-1)]|[flood(2:end,:);false(1,columns)]|[flood(:,2:end),false(rows,1)]);
cval = nonzeros(unique(board(xflood)));
cval(cval==colors(end))=[];
ncval = numel(cval);
if ncval==0
break
end
end
scr = zeros(1,ncval);
matchvalues = cell(1,ncval);
for i = 1:ncval
matchvalues{i} = matchindices(xflood&(board==cval(i)));
sc(i) = sum(cben((matchvalues{i})))-cval(i);
scr(i) = (sum(cben((matchvalues{i})))-cval(i))/cval(i);
end
if first
ich = 1;
%[sch,ich] = max(scr);
first = false;
else
[sch,ich] = max(scr);
end
if ~isempty(extra_colors) && cval(ich)==extra_colors(end)
break
end
extra_colors=[extra_colors; cval(ich)];extra_score=[extra_score; sc(ich)];
if numel(extra_colors)>9 && extra_score(end)<0
break
end
flood = flood|ismember(matchindices,matchvalues{ich});
end
score_cum_sum=cumsum(extra_score);
[ma, maind]=max(score_cum_sum);
if ma>mamax
insert_colors=extra_colors(1:maind-1);
mamax=ma;
end
end %for ii
colors = [colors(1:end-1);insert_colors;colors(end)];
end
function [matchesindices matchesvalues numberblocks] = group(board)
% Based on Tim Davis' find_components
%this function finds all paired 'groups' of elements on the board and
%returns a list of indices to the elements, a modified board with unique
%values at each element pair, and a total number of pairs
% find dims and total # elements of board
[rows columns] = size(board);totalelements = rows*columns;
numberboard = reshape(1:totalelements, rows, columns); %create board with index #s for elements
rightcheckboard = board(:,1:columns-1) == board(:,2:columns); % create board with 1's anywhere an element matches the color of the element directly right
downcheckboard = board(1:rows-1,:) == board(2:rows,:); % ditto except check elements directly below
% this complicated command does the following: adds a column of 0s to
% rightcheckboard rightmost edge to make it full size again, then uses it to index into
% the numberboard, which returns just the indexes of elements with matching
% elements directly to the right, then reshape this output into a single
% col. Repeat this for the downcheckboard, and the combined
% result is the first term input for the sparse command. Repeat the process
% but add the column to the leftmost / topmost edges to get all the paired element indexes
% This is the second input term for the sparse command. With the other
% input terms, the sparse command produces an output board of dimension
% totalelements x totalelements, where there is a 1 any location with row
% and column coordinates equal to the index values of the elements found in
% right and down checkboards.
matchesboard = sparse([reshape(numberboard([rightcheckboard false(rows,1)]),[],1); ...
reshape(numberboard([downcheckboard; false(1,columns)]),[],1)], ...
[reshape(numberboard([false(rows,1) rightcheckboard]),[],1);...
reshape(numberboard([false(1,columns); downcheckboard]),[],1)],...
1, totalelements, totalelements);
%next, combine the result from above with it's transposed version and an
%identity matrix to produce a 'symmetrical' matrix
matchesboard = matchesboard + matchesboard' + speye(totalelements);
%Perform a Dulmage-Mendelsohn decomposition (there be magic here!;)
% The first 2 output terms are 'permutation vectors', the third term is
% the 'fine block decomposition' indexes.
[permvector1 permvector2 blocks] = dmperm(matchesboard);
numberblocks = numel(blocks) - 1;
matchesvalues = board(permvector1(blocks(1:numberblocks))); % vector with all the matching values
% matches indices is a board with 1s everywhere except for 'matching' pairs
% of elements, which have numerically increasing values to indicate they
% match each other
matchesindices = ones(rows, columns, 'uint16');
for count = 2:numberblocks
matchesindices(permvector1(blocks(count):blocks(count+1)-1)) = uint16(count);
end
end
function [path loss targettrack] = dijkstra(matchingblocks, maxvalue, blockcosts, from, to)
% Similar idea to Dijkstra's shortest path (but not optimal here)
rows = size(matchingblocks, 1); % find number of matching rows
columns = rows; % create a buffer for columns
parent = ones(rows, rows, class(matchingblocks)); %preallocate an tracking array
k = zeros(rows, 1, 'uint16'); % create a zeroed vector of columns
pointers = rows + ones(rows, 1, 'uint16'); %preallocate pointer array
pointers(from) = 1; %set starting point as 1
loss = zeros(rows+1, 1); %setup a zeroed vector to track losses
loss(:) = 1e9; % set everything to a large number
loss(1) = blockcosts(from); % init starting location as the block cost
targettrack = parent; %preallocate target tracking array
targettrack(:,1) = matchingblocks(:,from); %setup first col to equal starting col values
targettrack(from,1) = 2; % init starting location to 2
sizevector = [maxvalue+3 1]; % setup a size vector
indexvector = [0 0 0 1:maxvalue]' * 2; %pad an index vector
changed = false(rows, 1); % preallocate change tracking vector
changed(1) = true; % indicate first element has changed
columncounter = 0; % set column counter to 0
while 1
columncounter = columncounter + 1; %update column counter
%when column counter exceed nuber of columns, if no changes, stop loop,
%otherwise restart counter
if columncounter > rows
if ~any(changed)
break;
end
columncounter = 1;
end
% if the current col hasn't changed, go to next col
if ~changed(columncounter)
continue;
end
changed(columncounter) = false; %set current column to no changes
% if the current target col, row = 2 go to nextcolumn
if targettrack(to,columncounter) == 2
continue;
end
% build a cost vector based upon the track to the target and the
% relevant block costs. Set the starting elements very large, and add
% in the current column losses
ncost = accumarray(targettrack(:,columncounter), blockcosts, sizevector);
ncost(1:3) = 1e14;ncost = loss(columncounter) + (ncost + indexvector) + round(rand(1)*2);% find elements where it cost less to get to than the loss path, if
% there aren't any, go to next column
postivecosts = ncost(targettrack(:,columncounter)) < loss(pointers);
if ~any(postivecosts)
continue;
end
% find the costindices, use to sort the targettrack array, and then
% eliminate any indices to non-net-positive costs
costindices = find(postivecosts)';
[sortedtargets postivecosts] = sort(targettrack(costindices,columncounter));
costindices = costindices(postivecosts);
% find targets that aren't the same and update sortedtargets with them
nondupetargets = [0;find(diff(sortedtargets) ~= 0); numel(sortedtargets)];
sortedtargets = sortedtargets(nondupetargets(2:end));
% update pointers with losses and use to update the postivecosts vector
pointers(costindices) = numel(loss);postivecosts = true(rows+1, 1);postivecosts(pointers) = false;
n = numel(sortedtargets);
C = find(postivecosts(columncounter+1:end-1), n) + columncounter;
n = n - numel(C);
if n
C = [C; find(postivecosts(1:columncounter), n)];
end
ncost = ncost(sortedtargets);
loss(C) = ncost;changed(C) = true;
n = k(columncounter) + 1;
k(C) = n;
K = targettrack(:,columncounter) == 1;
N = (1:n)';
for d = 1:numel(C)
c = C(d);
targettrack(:,c) = targettrack(:,columncounter);
J = targettrack(:,c) == sortedtargets(d);
targettrack(J,c) = 2;targettrack(K,c) = max(matchingblocks(K,J), [], 2);
parent(N,c) = parent(N,columncounter);
parent(n,c) = sortedtargets(d);
pointers(costindices(nondupetargets(d)+1:nondupetargets(d+1))) = c;
end
end
to_ = pointers(to);
path = parent(1:k(to_),to_) - 3;
end
function blockcosts = push_channels(matchingblocks, blockcosts)
% Heuristic to deal with large regions connected by thin channels
%update the blockcosts to account for large connected regions
newmatchings = matchingblocks > 3; % find indices of all matching pairs
matchindices = find(sum(newmatchings, 1) == 1); %sum up the cols and find any with only 1 matching pair
while ~isempty(matchindices)
column = matchindices(1); % extract first element of col sums
row = find(newmatchings(:,column));% find location in col of the matching
if isscalar(row) % check there is only 1 location
blockcosts(row) = blockcosts(row) + blockcosts(column); %accumulate the block costs into that element
blockcosts(column) = 0; % reset the column blockcost
newmatchings(column,row) = false; % reset the matching pair index
matchindices(1) = row; % set the element sum equal to the row
else
matchindices = matchindices(2:end); %remove the first element and repeat with the remainder
end
end
end
|
