# Diffing "N1000- sorted2" and "KNodes11"

 Title: N1000- sorted2 KNodes11 Author: Amitabh Verma Alan Chalker Submitted: 2011-04-18 23:03:13 UTC 2011-04-19 00:26:26 UTC Status: Passed Passed Score: 17976.4 17976.4 Result: 7189406 (cyc: 12, node: 895) 7189406 (cyc: 12, node: 893) CPU Time: 6.028 5.883 Code: ```function board = solver(words, weights, n, penalty) words = words(weights>0); weights = weights(weights>0); lengths = cellfun('length',words); [~,idx] = sortrows([weights'./lengths' weights'],[-1 -2]); words = words(idx); weights = weights(idx); sumw = sum(weights); [board, result ] = solver_press(words, weights, n, penalty, sumw); [board1, result1] = solver_columns(words, weights, n, penalty, sumw); [board1, result1] = solver_columns(words, weights, n, sumw); if result1 < result board = board1; end end function [board, result] = solver_press(words, weights, n, penalty, result) board = zeros(n); wordlengths = cellfun('length',words); [B,index] = sortrows([wordlengths' weights'],[1 -2]); % index is wordsFromBIndex last2letterword = find(B(:,1)>2,1)-1; w2l = index(1:last2letterword)'; % should be row vector for for isUnplayed = true(size(words)); hopeless = false(size(words)); [C,alphaix]=sortrows(cell2mat(words(w2l)')); % so char(C) = char(words{w2l(alphaix)}) % alphaix is WfromC c=1; r=1; L = 2; % dim of sq while r+L-1 <= n, [sq, isUnplayed, hopeless] = press2(words, isUnplayed, hopeless, w2l, C, alphaix); if ~sq, break; % no more 2x2s end board(r+(0:L-1),c+(0:L-1)) = sq; c=c+L+1; if c > n-(L-1), r =r+L+1; c=1; end end result = result - sum(weights(~isUnplayed)); % eliminate words that have already been played [B,index] = sortrows([wordlengths(isUnplayed)' weights(isUnplayed)'],[1 -2]); words = words(isUnplayed); nwords=numel(words); %isUnplayed = true(size(nwords)); k=1; % play remaining unused 2 letter words here? % index of last word to play in current row stop_index = min(nwords, n*k-c+1); % check that we haven't run out of words start_index = 1; while (r+B(stop_index,1)-1) <= n, % if the new row fits words_left = stop_index - start_index + 1; % num words to play in this row current_row_points = sum(B(start_index:stop_index,2)) - penalty*B(stop_index-1,1); % use length of next to last word to get number of penalty cols if current_row_points > 0, for cc = c:min(n,words_left+c-1), %fprintf('\n* r=%2i,c=%2i\n',r,c); wi = start_index-c+cc; % word index %board(r:(r+B(wi,1)-1),cc)' %char(words{index(wi)}) board(r:(r+B(wi,1)-1),cc) = words{index(wi)}; end % the row is unplayed I think it will simply be blank end c=1; result = result - current_row_points; r=r+B(stop_index,1)+1; % increment row location wi = start_index-c+cc; % word index board(r:(r+B(wi,1)-1),cc) = words{index(wi)}; end % the row is unplayed I think it will simply be blank end c=1; result = result - current_row_points; r=r+B(stop_index,1)+1; % increment row location k=k+1; % increment row number start_index=stop_index+1; stop_index = min(nwords, stop_index+n); end end % should mark words that didn't work out to avoid retrying them % hopeless marks words that won't work i positions 1 or 2 (1 across and 1 % down). word 1 is equivalent to word 2, and word 3 is equivalent to word 4 % however, words 1 and 2 are not equivalent to words 3 and 4 function [sq, isUnplayed, hopeless] = press2(words, isUnplayed, hopeless, w2l, C, alphaix) sq = zeros(2); % try excluding words with letter frequencies of 1 % ordering words by first and second letter would help for ii = w2l, % w2l must be a row vector here %fprintf('ii = %i\n',ii); if ~isUnplayed(ii) || hopeless(ii), continue; end sq(1,:) = words{ii}; isUnplayed(ii) = false; % fprintf('letter = %s\n',char(sq(1,:))); % char(words{w2l(alphaix(a1:a2))}) % only iterate over reasonable letters a1=find(C(:,1) == sq(1,1),1); a2=find(C(:,1) == sq(1,1),1,'last'); for jj = w2l(sort(alphaix(a1:a2))), %fprintf(' jj = %i\n',ii,jj); %assert(sq(1,1) == words{jj}(1)); if isUnplayed(jj) && ~hopeless(jj), % eval order? also checks could be elim sq(2,1) = words{jj}(2); isUnplayed(jj) = false; b1=find(C(:,1) == sq(1,2),1); b2=find(C(:,1) == sq(1,2),1,'last'); c1=find(C(:,1) == sq(2,1),1); c2=find(C(:,1) == sq(2,1),1,'last'); for kk = w2l(sort(alphaix(b1:b2))), %assert(sq(1,2) == words{kk}(1)); if isUnplayed(kk), sq(2,2) = words{kk}(2); isUnplayed(kk) = false; for ll = w2l(sort(alphaix(c1:c2))), if isUnplayed(ll) && all(sq(2,:) == words{ll}), isUnplayed(ll) = false; %fprintf('1 %s\n2 %s\n3 %s\n4 %s\n\n',char(words{ii}),char(words{jj}),char(words{kk}),char(words{ll})); %disp(char(sq)) return; % press completed! end end isUnplayed(kk) = true; end end isUnplayed(jj) = true; end end isUnplayed(ii) = true; % should mark words that didn't work out to avoid retrying them hopeless(ii) = true; % hopeless in positions 1 or 2 %fprintf('%s (%i) is hopeless\n',char(words{ii}),ii); end sq=zeros(2); % no result end function [board, result] = solver_columns(words, weights, n, penalty, result) function [board, result] = solver_columns(words, weights, n, result) % to do: % use dead space at the bottom of a column more effectively % use better value for wpl % consider penalty board = zeros(n); % for k = 1:length(words), % wordlengths(k)=length(words{k}); % end wordlengths = cellfun('length',words); wordlengths = cellfun('length',words); wpl = weights./(wordlengths); % weight per letter, maybe should also consider blanks; +1 for blank at end of word acutally lowered result? [~,ix] = sort(wpl,'descend'); % so now s_wpl = wpl(ix) % possible sign tricks? w = 1; for col = 1:2:min(n,length(words)), r = 1; while r + wordlengths(ix(w))-1 <= n board(r:(r-1+wordlengths(ix(w))),col) = words{ix(w)}; result = result - weights(ix(w)); r = r + 1 + wordlengths(ix(w)); w = w + 1; end end end```