Finish 2009-11-11 12:00:00 UTC

A1

by MikeR

Status: Passed
Results: 656122 (cyc: 10, node: 2501)
CPU Time: 92.8966
Score: 6566.02
Submitted at: 2009-11-11 11:49:05 UTC
Scored at: 2009-11-11 13:14:26 UTC

Current Rank: 98th (Highest: 98th )
Based on: Last 35 monkeys (diff)
Basis for: A1t35 (diff)

Comments
Please login or create a profile.
Code
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

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

[R,C]=size(board);

m=max(max(board));


if (m>79||m==35)
colors = switcheroo2(uint8(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);
rightmatches = rightmatches+ones(rows,1)*[0 cumsum(rightmatches(rows,1:columns-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) = 1;

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) = 1; %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));
        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==1) = board_tmp(goal);
        scoreBF = sum(boardBF(:))+sum(colors);
    else
        scoreBF=inf;
    end

    board_tmp(flood==1) = 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) = 1;
blockmatches(lowerrmatches+(uppermatches-1)*numberblocks) = 1;

%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) = 1;
blockmatches(westmatches+(eastmatches-1)*numberblocks) = 1;

[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


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

pointers = rows + k + 1; %preallocate pointer array
pointers(1) = 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(1); % init starting location as the block cost
targettrack = parent; %preallocate target tracking array
targettrack(:,1) = matchingblocks(:,1); %setup first col to equal starting col values
targettrack(1,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) = 1; % 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