Diffing "Gal and Omri TakeFinal33" and "Gal and Omri TakeFinal44"

 Title: Gal and Omri TakeFinal33 Gal and Omri TakeFinal44 Author: Omri and Gal Omri and Gal Submitted: 2009-11-09 16:42:57 UTC 2009-11-09 19:00:35 UTC Status: Passed Passed Score: 6569.89 6569.94 Result: 656720 (cyc: 10, node: 2140) 656720 (cyc: 10, node: 2140) CPU Time: 75.6857 76.8167 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',seed); randn('seed',seed); [R,C]=size(board); if (max(board(:))>34) if (max(max(board))>34) s=inf; for i=1:15 [c,score] = switcheroo2(board,goal,R,C); if score max(board(:))-30) = 2; scr(cval > max(max(board))-30) = 2; [sch,ich] = min(scr); colors(count) = cval(ich); flood = flood|ismember(paircolumns,paircolumns(xflood&(board==cval(ich)))); end; insert_colors = unique(cval(cval > max(board(:))-1))'; insert_colors = unique(cval(cval > max(max(board))-1))'; colors = [colors(1:count-1) insert_colors colors(count)]; if numel(insert_colors)>0 board(flood==false) = board(goal); else board(flood==true) = board(goal); end score = sum(board(:))+sum(colors); 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 extra_score=0; extra_colors=[]; while true 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 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 [sch,ich] = max(scr); 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); insert_colors=[]; if ma>0 insert_colors=extra_colors(1:maind-1); end 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```