# Diffing "LastCatStanding_99" and "LCS99"

 Title: LastCatStanding_99 LCS99 Author: Sergey Y. the cyclist Submitted: 2009-11-11 11:58:41 UTC 2009-11-11 11:59:24 UTC Status: Passed Passed Score: 6554.76 6554.89 Result: 654921 (cyc: 10, node: 2557) 654921 (cyc: 10, node: 2558) CPU Time: 96.0483 96.5576 Code: ```function colors = balloontilt3(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(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 colors = zeros(1,numberpairs,'uint8'); % 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)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```