# Diffing "That's what I'm talking about" and "s14"

 Title: That's what I'm talking about s14 Author: Volkan Satoshi Submitted: 2011-04-20 13:41:19 UTC 2011-04-20 14:25:27 UTC Status: Passed Passed Score: 17201.5 17201.6 Result: 6877819 (cyc: 10, node: 5886) 6877819 (cyc: 10, node: 5851) CPU Time: 61.936 63.113 Code: ```function out = solver(words, weights, N, penalty) [out,sux] = solver_volkan(words, weights, N); if sux;return;end nws = numel(words); words = words(end:-1:1); weights = single(weights(end:-1:1)); lengths = single(cellfun('length',words)); [w1,idx] = sortrows([weights'./lengths' weights'],[-1 -2]); words = words(idx); weights = w1(:,2)'; lengths = lengths(idx); board = zeros(N,'uint8'); SCORE = Inf * ones(1,18); BOARD=cell(1,18); if min(lengths) == N [BOARD{1}, SCORE(1)] = solver_nick_1(board, words, weights, N, penalty, lengths, nws,750,750); if SCORE(1)==0, board=BOARD{1}; out=double(board); return; end end rand('state',789); mywords=cell(1,5); myweights=cell(1,5); mylengths=cell(1,5); for j=1:5 idx1=randperm(nws); words1 = words(idx1); weights1 = weights(idx1); lengths1 = lengths(idx1); [w1,idx] = sortrows([weights1'./lengths1' weights1'],[-1 -2]); mywords{j} = words1(idx); myweights{j} = w1(:,2)'; mylengths{j} = lengths1(idx); end if min(lengths) == N [BOARD{2}, SCORE(2)] = solver_nick_1(board, mywords{1}, myweights{1}, N, penalty, mylengths{1}, nws,750,750); else wordsflip = cellfun(@fliplr,words,'Uniform',false); sumw = sum(weights); [BOARD{3}, SCORE(3)] = solver_nick_2 (board, words, weights, N, penalty, lengths, nws, sumw); [BOARD{4}, SCORE(4)] = solver_nick_3 (board, words, weights, N, lengths, nws, sumw); [BOARD{5}, SCORE(5)] = solver_nick_4 (board, words, weights, N, penalty, lengths, nws, sumw); [BOARD{6}, SCORE(6)] = solver_james1 (board, words, weights, N, penalty, lengths, nws, sumw); [BOARD{7}, SCORE(7)] = solver_james2 (board, words, weights, N, penalty, lengths, nws); [BOARD{8}, SCORE(8)] = solver_victoria(board, words, weights, N, penalty, lengths, nws); [BOARD{9}, SCORE(9)] = solver_james1 (board, wordsflip, weights, N, penalty, lengths, nws, sumw); for j=1:5 [BOARD{10+j}, SCORE(10+j)] = solver_james1 (board, mywords{j}, myweights{j}, N, penalty, mylengths{j}, nws, sumw); end end [~, board_idx] = min(SCORE); board = BOARD{board_idx}; if (board_idx==9) board = board(end:-1:1,end:-1:1); end out = double(board); end function [board, result] = solver_james1(board, words, weights, n, penalty, wordlengths, nwords, total) [B,index] = sortrows([wordlengths' weights'],[1 -2]); % index is wordsFromBIndex last2letterword = find(B(:,1)>2,1)-1; %words2 = words(index(1:last2letterword)); w2l = index(1:last2letterword)'; % should be row vector for for last2letterword = find(wordlengths == 2); isUnplayed = true(1,nwords); hopeless = false(1,nwords); [C,alphaix]=sortrows(cell2mat(words(w2l)')); % so char(C) = char(words{w2l(alphaix)}) % alphaix is WfromC [C,alphaix]=sortrows(cell2mat(words(last2letterword)')); % so char(C) = char(words{w2l(alphaix)}) % alphaix is WfromC %wFromC=w2l(alphaix); % gives index in original words points = 0; c=1; r=1; while r+1 <= n, % try excluding words with letter frequencies of 1 % ordering words by first and second letter would help sq = zeros(2); if ~isempty(w2l) if ~isempty(last2letterword) C1 = C(:,1); [sq, isUnplayed, hopeless] = press2(words, isUnplayed, hopeless, w2l, C1, alphaix,sq); [sq, isUnplayed, hopeless] = press2(words, isUnplayed, hopeless, last2letterword, C1, alphaix,sq); end if ~sq, break; % no more 2x2s end board(r+(0:1),c+(0:1)) = sq; c=c+3; if c > n-1, r =r+3; c=1; end end points = points + 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); isUnplayed2 = true(1,nwords); % play remaining unused 2 letter words here? % index of last word to play in current row stop_index = min(nwords, n-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), wi = start_index-c+cc; % word index board(r:(r+B(wi,1)-1),cc) = words{index(wi)}; isUnplayed2(index(wi)) = false; end % the row is unplayed I think it will simply be blank end c=1; points = points + current_row_points; r=r+B(stop_index,1)+1; % increment row location start_index=stop_index+1; stop_index = min(nwords, stop_index+n); end result = total - points; wordlengths2 = wordlengths(isUnplayed); weights2 = weights(isUnplayed); [board,result] = james_sub_solver(board,wordlengths2,weights2,isUnplayed2,words,result,n); end function [sq, isUnplayed, hopeless] = press2(words, isUnplayed, hopeless, w2l, C1, alphaix,sq) ii_valid = w2l(isUnplayed(w2l) & ~hopeless(w2l)); for ii = ii_valid, % w2l must be a row vector here sq(1,:) = words{ii}; isUnplayed(ii) = false; % only iterate over reasonable letters conda = C1 == sq(1,1); a1 = find(conda,1); a2 = find(conda,1,'last'); w21jj = w2l(sort(alphaix(a1:a2))); condb = C1 == sq(1,2); b1=find(condb,1); b2=find(condb,1,'last'); w21kk = w2l(sort(alphaix(b1:b2))); for jj = w21jj % eval order? also checks could be elim if isUnplayed(jj) && ~hopeless(jj) sq(2,1) = words{jj}(2); isUnplayed(jj) = false; condc = C1 == sq(2,1); c1=find(condc,1); c2=find(condc,1,'last'); w21ll = w2l(sort(alphaix(c1:c2))); for kk = w21kk if isUnplayed(kk) sq(2,2) = words{kk}(2); isUnplayed(kk) = false; for ll = w21ll if isUnplayed(ll) && all(sq(2,:) == words{ll}) isUnplayed(ll) = false; 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 end sq = zeros(2); end function [board, result] = solver_james2(board, words, weights, n, penalty, wordlengths, nwords) result=sum(weights); [B,index] = sortrows([wordlengths' weights'],[1 -2]); k=1; c=1; isUnplayed = true(nwords,1); current_stop_index = min(nwords, n); % check that we haven't run out of words while (c+B(current_stop_index,1)-1) <= n, current_col_points = sum(B(((k-1)*n)+1:current_stop_index,2)) - penalty*B(k*n-1,1); % use length of next to last word to get number of penalty cols if current_col_points > 0, words_left = current_stop_index - n*(k-1); for r = 1:min(n,words_left), board(c:(c+B(r+(k-1)*n,1)-1),r) = words{index(r+(k-1)*n)}; isUnplayed(index(r+(k-1)*n)) = false; end end result = result - current_col_points; c=c+B(current_stop_index,1)+1; k=k+1; current_stop_index = min(nwords, n*k); end [board,result] = james_sub_solver(board,wordlengths,weights,isUnplayed,words,result,n); end function [board,result] = james_sub_solver(board, wordlengths,weights,isUnplayed,words,result,n) wordlengths2 = wordlengths(isUnplayed); weights2 = weights(isUnplayed); words = words(isUnplayed); [~,idx_sort] = sort(wordlengths2 - weights2/max(weights2) ); tres_ceros = board(3:end,1)==0 & board(2:end-1,2)==0 & board(1:end-2,1)==0; r_ini = find(tres_ceros) + 1; if board(n,1)==0 && board(n-1,1)==0 r_ini = [r_ini; n]; end k = 1; for p = 1:length(r_ini) r = r_ini(p); if board(r-1,1)==0 c = 1; while c < n && board(r-1,c)==0 word_n = words{idx_sort(k)}; c2 = c + numel(word_n); if c2-1 <= n && board(r-1,c2-1)==0 board(r,c:c2-1) = word_n; k = k + 1; result = result - weights2(idx_sort(k)); end c = c2 + 1; end end end end function [board0, s0] = solver_nick_1(board, words, weights, N, penalty, wlen, nword,maxnwo,maxnwo2) if numel(words)>maxnwo rand(); ridx = randperm(numel(words)); ridx = ridx(1:maxnwo2) ; words=words(ridx); wlen = wlen(ridx); weights = weights(ridx); nword = maxnwo2; end wmat = uint8(cat(1,words{:})); m = cell(N); for n = 1:N m{n,1} = sparse(bsxfun(@eq,wmat(:,n),wmat(:,1)')); m{3,n} = sparse(bsxfun(@eq,wmat(:,3),wmat(:,n)')); end rwords = zeros(1,N); cwords = zeros(1,N); n = 1; ppm = true(nword); seguir = true; while seguir pm = ppm; ppm = pm & double(m{n,1})*double(m{3,n}); n = n + 2; seguir = (n PThresh; L_slots = P*ceil(N/2) + (1-P)*N; % innovation filter :P MaxQ = P*numel(find(SpecLCum <= (N+1).^2/2)) + (1-P)*MaxQ; slots = ones(1, L_slots); LoL = min(L(IndWS(1:MaxQ))); HiL = max(L(IndWS(1:MaxQ))); IndL = zeros(MaxQ,1); l = 1; for n = HiL:-1:LoL idx_long = find(L(IndWS(1:MaxQ))==n); l2 = l + numel(idx_long); IndL(l:l2-1) = idx_long; l = l2; end IndWS(1:MaxQ) = IndWS(IndL); n = 1; seguir = (min(slots) < N)*(n <= QWords); while seguir Space = N - L(IndWS(n)) + 1 - slots; SlotIndex = find(~Space,1); if isempty(SlotIndex) [Espacio,SlotIndex] = max(Space); else Espacio = 1; end if Espacio > 0 idx_f = (1+P)*SlotIndex-P; idx_c = slots(SlotIndex):slots(SlotIndex) + L(IndWS(n)) - 1; board(idx_f,idx_c) = words{IndWS(n)}; slots(SlotIndex) = slots(SlotIndex) + L(IndWS(n)) + 1; score = score + weights(IndWS(n)); WordsInUse(IndWS(n)) = true; end n = n + 1; seguir = (min(slots) < N)*(n <= QWords); end QWords = QWords*(P>0); for n = 1:QWords CurInd = IndWS(n); CurL = L(CurInd); word_c = words{CurInd}; entrar = (~WordsInUse(CurInd))*(CurL/2 ~= round(CurL/2)); if entrar [I,J] = find(board(1:N - CurL + 1,:) == word_c(1)); if ~isempty(I) k = 1; seguir = (~WordsInUse(CurInd))*(k <= numel(I)); while seguir if all(word_c(1:2:end) == board(I(k):2:I(k) + CurL - 1,J(k))') board(I(k):I(k) + CurL - 1,J(k)) = word_c'; score = score + weights(IndWS(n)); WordsInUse(IndWS(n)) = true; end k = k + 1; seguir = (~WordsInUse(CurInd))*(k <= numel(I)); end end end end [board, score] = victoria_sub_solver(board,words,L,weights,WordsInUse,N,score); %-- pboard = [board;zeros(1,N)]; cs = cumsum(pboard(:)~=0); ntrans = sum(diff(cs(pboard==0))>1) + 1; score = sum(weights(:)) - score + penalty*ntrans; end function [board, score] = victoria_sub_solver(board, words,L,weights,WordsInUse,N,score) L2 = L(~WordsInUse); weights2 = weights(~WordsInUse); words = words(~WordsInUse); [~,idx_sort] = sort(weights2./(L2+1),'descend'); tres_ceros = board(1,3:end)==0 & board(1,2:end-1)==0 & board(1,1:end-2)==0; r_ini = find(tres_ceros) + 1; used = false(size(weights2)); if sum(board(:,N)==0 & board(:,N-1)==0)>3 r_ini = [r_ini; N]; end k=1; for p = 1:length(r_ini) r = r_ini(p); if board(1,r-1)==0 || (r==N && any(all(board(:,r-1:r)==0,2))) c = 1; subv end end function subv while c < N && (board(c,r-1)==0 || r==N) if board(c,r-1)~=0 || board(c,r)~=0 || board(max(c-1,1),r)~=0 c = c+1; continue; end word_n = words{idx_sort(k)}; c2 = c + numel(word_n); [c2,word_n] = subv2(c2,word_n); c = c2 + 1; end end function [c2,word_n] = subv2(c2,word_n) if c2-1 <= N && all(board(c:c2-1,r)==0) && board(min(c2,N),r)==0 board(c:c2-1,r) = word_n; k = k + 1; score = score + weights2(idx_sort(k)); used(idx_sort(k)) = true; elseif r==N || r==N-1 k=1; [~,idx_sort] = sort(L2 - weights2/max(weights2)+used*99); c2 = c+3; [c2,word_n] = subv3(c2,word_n); end end function [c2,word_n] = subv3(c2,word_n) while c < N && board(c,r-1)==0 && board(min(c2,N),r)==0 word_n = words{idx_sort(k)}; c2 = c + numel(word_n); if c2-1 <= N && all(board(c:c2-1,r)==0) board(c:c2-1,r) = word_n; k = k + 1; score = score + weights2(idx_sort(k)); end c = c2 + 1; end end end function [board , sumw] = solver_nick_2(board, words, weights, N, penalty, wlen, nws, sumw) open = true(1,nws); for n = [1:2:N,2:2:N] l = 0; k = find(open & (wlen<=N-l),1); while ~isempty(k) open(k) = false; word = words{k}; % L_word = numel(word); board(n,l+1:l+wlen(k)) = word; l = l + wlen(k) + 1; sumw = sumw - weights(k); k = find(open & (wlen <= N-l),1); end end pboard = [board;zeros(1,N)]; cs = cumsum(pboard(:)~=0); ntrans = sum(diff(cs(pboard==0))>1); sumw = sumw + penalty*ntrans; end function [board2, sumw] = solver_nick_3(board2, words, weights, N, wlen, nws,sumw) open = true(1,nws); wlen_m_N = wlen <= N; for n = 1:2:N l = 0; k = find(open & wlen_m_N,1); while ~isempty(k) open(k) = false; word = words{k}; L_word = numel(word); board(n,l+1:l+L_word) = word; l = l + L_word + 1; sumw = sumw - weights(k); k = find(open & (wlen <= N-l),1); end end pboard = [board;zeros(1,N)]; cs = cumsum(pboard(:)~=0); ntrans = sum(diff(cs(pboard==0))>1); sumw = sumw + penalty*ntrans; end function [board2, sumw] = solver_nick_3(board2, words, weights, N, wlen, nws,sumw) open = true(1,nws); wlen_m_N = wlen <= N; for n = 1:2:N l = 0; k = find(open & wlen_m_N,1); while ~isempty(k) open(k) = false; word = words{k}; L_word = numel(word); board2(n,l+1:l+L_word) = word; l = l+L_word+1; sumw = sumw - weights(k); k = find(open & (wlen <= N-l),1); end end end function [board2, s] = solver_nick_4(board2, words, weights, N, penalty, wlen, nword, sumw) w2 = 0; open = true(1,numel(words)); filled = zeros(1,N); filled(2:2:end) = 1; brk = false; while (filled(1)=N),1); if isempty(k) brk = true; break end targ = wlen(k); board2(1,filled(1)+1:filled(1)+targ) = words{k}; open(k) = false; w2 = w2 + weights(k); wlen_eq_targ = wlen==targ; for n = 2:N k = find(open & wlen_eq_targ,1); % DFM SPEED board2(n,filled(n)+1:filled(n)+targ) = words{k}; open(k) = false; w2 = w2 + weights(k); end filled = filled + targ + 1; end if brk % try two half-sets [brk,board2,open,w2,filled] = nick_two_halves(board2,words,weights,wlen,nword,filled,open,N,w2); end if brk % try two half-sets off by 2 [brk,board2,open,w2,filled] = nick_two_halves_off(board2,words,weights,wlen,nword,filled,open,N,w2); end if brk && any(board2(:)) % finish filling board normally for n = 1:N k = find(open & (wlen<=N-filled(n)),1); while ~isempty(k) open(k) = false; word = words{k}; board2(n,filled(n)+1:filled(n)+numel(word)) = word; filled(n) = filled(n) + numel(word) + 1; w2 = w2 + weights(k); k = find(open & (wlen<=N-filled(n)),1); end end end pboard = [board2; zeros(1,N)]; cs = cumsum(pboard(:)~=0); ntrans = sum(diff(cs(pboard==0))>1); w2 = w2 - penalty*ntrans; s = sumw - w2; end function [brk,board2,open,w2,filled] = nick_two_halves(board2,words,weights,wlen,nword,filled,open,N,w2) brk = false; while filled(1) < N wlen2 = wlen.*open; wlen2(~open) = 1; nlen = accumarray(wlen2(:),ones(nword,1)); ldir = 2*(filled(1) > filled(2)) - 1; nlen(1) = 0; k = find(open & (wlen <= N-filled(1) - 1) & (nlen(wlen)'>=ceil(N/2)) & (nlen(wlen+ldir)'>=ceil(N/2)),1); if isempty(k) brk = true; break end targ = wlen(k); board2(1,filled(1)+1:filled(1)+targ) = words{k}; open(k) = false; w2 = w2 + weights(k); for n = 2:N idir = ldir*(mod(n,2)==0); k = find(open&(wlen==targ+idir),1); board2(n,filled(n)+1:filled(n)+targ+idir) = words{k}; open(k) = false; w2 = w2 + weights(k); end; filled = filled + targ + 1; end end function [brk,board2,open,w2,filled] = nick_two_halves_off(board2,words,weights,wlen,nword,filled,open,N,w2) % try two half-sets off by 2 brk = false; while filled(1) < N wlen2 = wlen.*open; wlen2(~open) = 1; nlen_test = accumarray(wlen2(:),ones(nword,1)); nlen_test(1) = 0; [row,clone] =size(nlen_test); nlen =zeros(row+2,clone); nlen(1:end-2) =nlen_test; k0 = find(open&(wlen<=N-filled(1)-2) & (nlen(wlen)'>=ceil(N/2)) & (nlen(wlen+2)'>=ceil(N/2)),1); if isempty(k0) brk = true; break end if filled(1)>filled(2) targ = ones(1,N)*wlen(k0); targ(2:2:end) = wlen(k0)+2; else targ = ones(1,N)*(wlen(k0)+2); targ(2:2:end) = wlen(k0); end for n = 1:N k = find(open&(wlen==targ(n)),1); board2(n,filled(n)+1:filled(n)+targ(n)) = words{k}; open(k) = false; w2 = w2 + weights(k); end filled = filled + targ + 1; end end function [board,success] = solver_volkan(words, weights, n) % BEWARE! This solver only tries to find a complete solution, and is a huge % waste of CPU cycles if none exists % % HERE IS THE MAIN IDEA: Say a word contains five 'A's, it cannot be put on % the first row of the crossword if we do not have five other words that % begin with the letter 'A'. Expand this idea to all rows and the histogram % of each word, you get yourself a reduced search space. board=zeros(n); success = false; % look for completely solveable with enough words solvable = all(cellfun('length',words) == n); % give up while you can if ~solvable;return;end % remove duplicate words (who put them there anyway?) w = cell2mat(words'); nw = length(w); % reduce search space template = sv_reduce(); % get the rows with the least candidates t_pos = sum(template,1); [~,id1] = sort(t_pos); % exit while you can if prod(t_pos(id1(1:2))) > 5000;return;end % get two sets of candidates for two different rows suit1 = find(template(:,id1(1)))'; suit2 = find(template(:,id1(2)))'; % do the work success = sv_fill(); function template = sv_reduce() % returns a logical template which shows which word % can be placed on which row hist_pos = histc(w,65:90,1); template = false(nw,n); for ind = 1:nw hist_word = histc(w(ind,:),65:90,2)'; hist_word = repmat(hist_word,[1,n]); locate = (hist_pos >= hist_word); template(ind,:) = all(locate); end end function done = sv_fill() % Loops through two sets of row candidates, keeps filling as long as % there is a single cross match, recursively finishes off if not. done = false; for line1 = suit1 if done;break;end for line2 = suit2 if line1 == line2;continue;end board(id1(1:2),:) = w([line1 line2],:); boardcpy = board; while (1) [filled,boardcpy] = sv_cross(boardcpy); if filled boardcpy = boardcpy'; if all(boardcpy(:)) %check if valid board = boardcpy; done = true; break end else done = false; break; end end if done;break else continue;end end end function [filled,outboard] = sv_cross(inboard) % Places crossovers if there is a single match, calls recursive % solver if not. outboard = inboard; filled = false; idx = all(outboard,2); idy = ~all(outboard,1); full = outboard(idx,idy); %Xfull = repmat(shiftdim(full,-1),[nw 1 1]); candi = w(:,idx); %Xcandi = repmat(candi,[1 1 sum(idy)]); match = bsxfun(@eq,shiftdim(full,-1),candi); if isempty(match) % nasty situation when the board is filled but we did not check % the last placement Xboard = repmat(shiftdim(outboard,-1),[nw 1 1]); Xword = repmat(w,[1 1 n]); match = Xboard == Xword; m = squeeze(all(match,2)); mm = squeeze(any(m,1)); mmm = all(mm); if mmm filled = true; return; else return; end end m = squeeze(all(match,2)); mm = squeeze(any(m,1)); mmm = all(mm); if mmm %find and anchor unique columns ms = sum(m,1); %unify duplicate words doubles = ms==2; if any(doubles); duin = m(:,doubles); in_doubles = find(doubles); [duinx,~] = find(duin); for in = 1:(numel(duinx)/2) first = w(duinx(2*in-1),:); second = w(duinx(2*in),:); if all(first==second) % remove one from template m(duinx(2*in),in_doubles(in)) = 0; end end ms = sum(m,1); end uin = ms==1; if any(uin) % we have unique columns muin = m(:,uin); [uinx,~] = find(muin); idy(idy) = uin; outboard(:,idy) = w(uinx,:)'; filled = true; else % start diggin % expand m and ms tmp = inf(nw,n); tmp(:,idy) = m; m = tmp; ms = sum(m,1); [outboard,done] = sv_deeper(outboard); %disp('exited sv_deeper'); filled = done; end end function [dboard,done] = sv_deeper(inboard) % Recursive solver used to finish off the crossword done = false; % get one high probability fit from ms [~,idm] = sort(ms); msin = m(:,idm(1)); [usn,~] = find(msin); % loop candidate words % ignore duplicates aw = w(usn,:); aw = unique(aw,'rows'); if size(aw,1) ~= size(usn,1) usn = usn(1:size(aw,1)); end for i = usn' dboard = inboard; dboard(:,idm(1)) = w(i,:)'; dboard = dboard'; % see if any matching words appeared while (1) [filled,dboard] = sv_cross(dboard); if filled dboard = dboard'; if all(dboard(:)) %check if valid boardcpy = dboard; done = true; break end else done = false; break; end end % check and exit if done;break else continue;end end end end end end```