# Diffing "The Third Monkey" and "... caches the worm"

 Title: The Third Monkey ... caches the worm Author: Fel Fel Submitted: 2012-04-06 19:40:20 UTC 2012-04-06 20:56:48 UTC Status: Passed Passed Score: 11889.8 11855.1 Result: 118458 (cyc: 7, node: 1275) 118284 (cyc: 7, node: 1297) CPU Time: 74.353 60.3 Code: ```function [board, orientation] = solver(tiles, boardSize) orientation = ones(size(tiles,1), 1); ntiles = size(tiles,1); board = zeros(boardSize); played = discardUnplayed(ntiles-numel(board), tiles); orientation = ones(size(tiles,1), 1); ntiles = size(tiles,1); board = zeros(boardSize); cs = [1 2 3 4; 2 3 4 1; 3 4 1 2; 4 1 2 3]; played = discardUnplayed(ntiles-numel(board), tiles); if (ntiles-numel(board)<0) height=min([ceil(sqrt(ntiles)) boardSize(1)]); if (ntiles/boardSize(2))>height height=ceil(ntiles/boardSize(2)); end else ntiles=numel(board); height=boardSize(1); end for k=1:ntiles [y,x]=ind2sub([height,boardSize(2)],k); board(y,x)=-1; end last = [y,x]; for i=8:-1:1 b(:,:,i) = board; o(:,i) = orientation; end list = played; [b(:,:,1),o(:,1),list] = place([1 height],1:last(2),b(:,:,1),played,list,o(:,1),ntiles,boardSize, cs); [b(:,:,1),o(:,1),list] = place(height:-1:1,[last(2) 1],b(:,:,1),played,list,o(:,1),ntiles,boardSize, cs); newList(:,:,1) = list; list = played; [b(:,:,5),o(:,5),list] = place([1 height],last(2):-1:1,b(:,:,5),played,list,o(:,5),ntiles,boardSize, cs); [b(:,:,5),o(:,5),list] = place(1:height,[1 last(2)],b(:,:,5),played,list,o(:,5),ntiles,boardSize, cs); newList(:,:,2) = list; for i=[0 4] [b(:,:,i+2),o(:,i+2),list] = place(2:height-1,2:boardSize(2)-1,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles,boardSize, cs); [b(:,:,i+3),o(:,i+3),list] = place(height-1:-1:2,2:boardSize(2)-1,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles,boardSize, cs); [b(:,:,i+4),o(:,i+4),list] = place(2:height-1,boardSize(2)-1:-1:2,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles,boardSize, cs); [b(:,:,i+1),o(:,i+1),list] = place(height-1:-1:2,boardSize(2)-1:-1:2,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles,boardSize, cs); end overall = zeros(8,1); for i=1:8 b(:,:,i) = board; o(:,i) = orientation; overall(i) = overallScore(b(:,:,i),o(:,i),tiles, cs); end list = played; [b(:,:,1),o(:,1),list] = place([1 height],1:last(2),b(:,:,1),played,list,o(:,1),ntiles); [b(:,:,1),o(:,1),list] = place(1:height,[last(2) 1],b(:,:,1),played,list,o(:,1),ntiles); newList(:,:,1) = list; list = played; [b(:,:,5),o(:,5),list] = place([1 height],last(2):-1:1,b(:,:,5),played,list,o(:,5),ntiles); [b(:,:,5),o(:,5),list] = place(1:height,[last(2) 1],b(:,:,5),played,list,o(:,5),ntiles); newList(:,:,2) = list; % list = played; % [b(:,:,9),o(:,9),list] = place([1 height],last(2):-1:1,b(:,:,9),played,list,o(:,9),ntiles); % [b(:,:,9),o(:,9),list] = place(1:height,[last(2) 1],b(:,:,9),played,list,o(:,9),ntiles); % newList(:,:,3) = list; % % list = played; % [b(:,:,13),o(:,13),list] = place([height 1],last(2):-1:1,b(:,:,13),played,list,o(:,13),ntiles); % [b(:,:,13),o(:,13),list] = place(1:height,[last(2) 1],b(:,:,13),played,list,o(:,13),ntiles); % newList(:,:,4) = list; for i=[0 4] [b(:,:,i+2),o(:,i+2),list] = place(2:height-1,2:boardSize(2)-1,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles); [b(:,:,i+3),o(:,i+3),list] = place(height-1:-1:2,2:boardSize(2)-1,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles); [b(:,:,i+4),o(:,i+4),list] = place(2:height-1,boardSize(2)-1:-1:2,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles); [b(:,:,i+1),o(:,i+1),list] = place(height-1:-1:2,boardSize(2)-1:-1:2,b(:,:,i+1),played,newList(:,:,i/4+1),o(:,i+1),ntiles); end for i=1:8 overall(i) = overallScore(b(:,:,i),o(:,i),tiles); end [~,mo] = min(overall); board = b(:,:,mo); orientation = o(:,mo); end function [score] = overallScore(board, orientation, tiles) cs = [1 2 3 4; 2 3 4 1; 3 4 1 2; 4 1 2 3]; boardSize=size(board); tile = zeros(boardSize(1)*4,boardSize(2)); for y = 1:boardSize(1) for x = 1:boardSize(2) if board(y,x) tile((y-1)*4+1:y*4,x)=tiles(board(y,x),cs(orientation(board(y,x)),:))'; end end end internal = sum(sum(abs(tile(5:4:end,1:end)-tile(3:4:end-4,1:end))))+sum(sum(abs(tile(2:4:end,1:end-1)-tile(4:4:end,2:end)))); external = sum(tile(4:4:end,1))+sum(tile(2:4:end,end))+sum(tile(end-1,1:end))+sum(tile(1,1:end)); score = internal + external; end function [score] = overallScore(board, orientation, tiles, cs) function [brd, ort, lst] = place(rowRange, colRange, board, tiles, list, orientation, ntiles) boardSize=size(board); tile = zeros(boardSize(1)*4,boardSize(2)); for y = 1:boardSize(1) for x = 1:boardSize(2) if board(y,x) tile((y-1)*4+1:y*4,x)=tiles(board(y,x),cs(orientation(board(y,x)),:))'; end end end internal = sum(sum(abs(tile(5:4:end,1:end)-tile(3:4:end-4,1:end))))+sum(sum(abs(tile(2:4:end,1:end-1)-tile(4:4:end,2:end)))); external = sum(tile(4:4:end,1))+sum(tile(2:4:end,end))+sum(tile(end-1,1:end))+sum(tile(1,1:end)); score = internal + external; end function [brd, ort, lst] = place(rowRange, colRange, board, tiles, list, orientation, ntiles, boardSize, cs) k = 1; brd = board; ort = orientation; lst = list; L = size(lst,1); for y=rowRange for x=colRange if (brd(y,x)==-1) [n,e,s,w] = findBoundaries(brd, tiles, ort, y, x); [t, o] = findBestTile(lst, n, e, s, w); [n,e,s,w] = findBoundaries(brd, tiles, ort, y, x, boardSize, cs); [t, o] = findBestTile(lst, L, n, e, s, w, cs); ort(t) = o; brd(y,x)=t; lst(t,:)=inf(1,4); k = k + 1; if (k > ntiles) return; end end end end end function played = discardUnplayed(numUnplayed, tiles) played = tiles; if numUnplayed>0 function [played] = discardUnplayed(numUnplayed, tiles) played = tiles; sums = sum(tiles,2); [~,si] = sort(sums); played(si(1:numUnplayed),:) = Inf(numUnplayed,4); for i = 1:numUnplayed [~, m]=min(sums); played(m,:)=inf(1,4); sums(m)=inf; end end end function [tile, orientation] = findBestTile(list, north, east, south, west) score = int32(zeros(size(list,1),4)); cs = [1 2 3 4; 2 3 4 1; 3 4 1 2; 4 1 2 3]; grid = ones(size(list,1),1)*[north east south west]; for i=1:4 temp = int32(abs(list(:,cs(:,i))-grid)); score(:,i) = sum(temp,2); end [ms, t] = min(score); [~, orientation] = min(ms); tile = t(orientation); function [tile, orientation] = findBestTile(list, L, north, east, south, west, cs) % [t, o] = find(score==min(score(:))); % %[~, which] = max(mean(t,2)); % which = 1;%round(length(t)/2);%round(rand*(length(t)-1)+1); % tile = t(which); % orientation = o(which); score = int32(zeros(L,4)); grid = ones(L,1)*[north east south west]; for i=1:4 score(:,i) = sum(int32(abs(list(:,cs(:,i))-grid)),2); end [ms, t ] = min(score); [~ , orientation] = min(ms); tile = t(orientation); end function [north, east, south, west] = findBoundaries(board, tiles, orientation, row, col) north = boundary(board,tiles,orientation,row-1,col,3); south = boundary(board,tiles,orientation,row+1,col,1); west = boundary(board,tiles,orientation,row,col-1,2); east = boundary(board,tiles,orientation,row,col+1,4); function [north, east, south, west] = findBoundaries(board, tiles, orientation, row, col, boardSize, cs) north = boundary(board,tiles,orientation,row-1,col ,3, boardSize, cs); south = boundary(board,tiles,orientation,row+1,col ,1, boardSize, cs); west = boundary(board,tiles,orientation,row ,col-1,2, boardSize, cs); east = boundary(board,tiles,orientation,row ,col+1,4, boardSize, cs); end function [value] = boundary(board,tiles,orientation,row,col,id) cs = [1 2 3 4; 2 3 4 1; 3 4 1 2; 4 1 2 3]; try if (board(row,col)==0) value = 0; elseif (board(row,col)==-1) value = nan; else tile = tiles(board(row,col),cs(orientation(board(row,col)),:)); value = tile(id); end catch function value = boundary(board,tiles,orientation,row,col,id,boardSize,cs) if row<1 || col<1 || row>boardSize(1) || col>boardSize(2) value = 0; else if board(row,col) == -1 value = nan; elseif board(row,col) == 0 value = 0; else tile = tiles(board(row,col),cs(orientation(board(row,col)),:)); value = tile(id); end end end```