2009-11-11 12:00:00 UTC

# LastCatStanding_99

Status: Passed
Results: 654921 (cyc: 10, node: 2557)
CPU Time: 96.0483
Score: 6554.76
Submitted at: 2009-11-11 11:58:41 UTC
Scored at: 2009-11-11 23:42:29 UTC

Current Rank: 3rd (Highest: 3rd )
Based on: Balloon Tilt 3 (diff)
Basis for: LCS99 (diff)

Code
```function colors = balloontilt3(board,goal)
% Flooding solver
% Commented by Alan Chalker
% Code from a variety of other leading entries
% 11/7/09
%
%
%
% board = input game board to flood
% goal = index of target element
% colors = vector of colors change order

% seed=17;
rand('seed',17);
randn('seed',17);

[R,C]=size(board);

m=max(max(board));

if (m>79||m==35)
colors = switcheroo2(board,goal,R,C,m);
else
colors = glean(board,goal,R,C,m);
end

end

function colors_out = switcheroo2(board,goal,rows,columns,maxB)
%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:columns),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 = indexvector
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

%s=inf; %infinite score for first run
colors_out=switcheroo_loop(maxB,numberpairs,rows,columns,board,goal,paircolumns,inf);

end

function colors_out=switcheroo_loop(maxB,numberpairs,rows,columns,board,goal,paircolumns,s)

allColors  = nonzeros(unique(board))';
nColors = numel(allColors);
maxBtsh=maxB-32;
for i_ext=1:(round(maxB*.283)-1)
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
board_tmp=board;

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_tmp(xflood);
for i=1:nColors
isInXflood(i) = (sum(bx==allColors(i))>0);
end
cval = allColors(isInXflood);

scr = rand(1,numel(cval))+sqrt(cval)/3;
scr(cval > maxBtsh) = 2;
[sch,ich] = min(scr);
colors(count) = cval(ich);

if xflood(goal) || cval(ich)==board(goal)
floodBF = flood;
end
flood = flood|ismember(paircolumns,paircolumns(xflood&(board==cval(ich))));

end;
insert_colors = unique(cval(cval > maxB-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
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+ii-1);

floodBF = floodBF|ismember(paircolumns,paircolumns(xflood&(board==cval)));
end;

boardBF = board_tmp;
boardBF(floodBF==true) = board_tmp(goal);
scoreBF = sum(boardBF(:))+sum(colors);
else
scoreBF=inf;
end

board_tmp(flood==true) = board_tmp(goal);
score = sum(board_tmp(:))+sum(colors_org);

if scoreBF>score
colors=colors_org;
end
if min(scoreBF,score)<s
s=min(scoreBF,score);
colors_out=colors;
end
end

end

function colors = glean(board,goal,rows,columns,maxvalue)

compactboard = uint8(board); %make a less memory intensive (uint8 type) version of board
[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, 'uint8'); % preallocate output with ones
matchingblocks(blockmatches) = matchvalues2(rows3); %  set the matching blocks equal to the values of them
newmatchings = matchingblocks > 3; % find indices of all matching pairs
row_sum = sum(newmatchings, 1); %sum up the cols
col_sum = sum(newmatchings, 2); %sum up the cols

if numel(board)>1500
blockcosts=blockcosts+int32(row_sum'+col_sum)*0.21;
end

blockcosts = push_channels(matchingblocks, blockcosts); %update blockcosts to account for large regions
colors = dijkstra(matchingblocks, maxvalue, blockcosts, 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

insert_colors=gleanloop(flood,columns,rows,board,colors,matchindices,cben);

colors = [colors(1:end-1);insert_colors;colors(end)];

end

function insert_colors=gleanloop(flood,columns,rows,board,colors,matchindices,cben)

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 ncval~=0
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});

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);

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

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, to)
% Similar idea to Dijkstra's shortest path (but not optimal here)
rows = size(matchingblocks, 1); % find number of matching rows
parent = ones(rows, rows, 'uint8'); %preallocate an tracking array
k = zeros(rows, 1, 'uint16'); % create a zeroed vector of columns
from = 1;
pointers = rows + k + 1; %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```