Finish 2011-04-20 12:00:00 UTC

meat_packer8_check_the_baloney

by Seth Kosowsky

Status: Passed
Results: 7305724 (cyc: 26, node: 2581)
CPU Time: 28.399
Score: 18283.1
Submitted at: 2011-04-14 15:10:25 UTC
Scored at: 2011-04-14 15:26:01 UTC

Current Rank: 1230th (Highest: 4th )

Comments
Please login or create a profile.
Code
function board = solver(words, weights, n, penalty)
    
    %meat_packer v.8
    %  weight by weight per letter (one for the end too)
    % with scoring metric
    % with/ without dupl dict entries
    
    %make hash
    wordhash = zeros(length(words), 1);
    for jj = 1:length(words),
        wordhash(jj) = applyHash(words{jj});
    end
    
    ii = 0;
    
    dupl_ok = 0;   %y=1/n=0 for dupls
%     ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack2(words, weights, n, penalty, wordhash, dupl_ok);  %every other fill
%     ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack3(words, weights, n, penalty, wordhash, dupl_ok);  % 2 interleaved every other fills
%     ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack4(words, weights, n, penalty, wordhash, dupl_ok);  % all lines filled (squeeze & pack)
%     ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack4order(words, weights, n, penalty, wordhash, dupl_ok);  % all lines filled (squeeze & pack)
    
    dupl_ok = 1;   %y=1/n=0 for dupls
    ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack2(words, weights, n, penalty, wordhash, dupl_ok);  %every other fill
    ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack3(words, weights, n, penalty, wordhash, dupl_ok);  % 2 interleaved every other fills
    ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack4(words, weights, n, penalty, wordhash, dupl_ok);  % all lines filled (squeeze & pack)
    ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack4order(words, weights, n, penalty, wordhash, dupl_ok);  % all lines filled (squeeze & pack)
    
    
    [m, mi] = min(score);
    m = m(1);
    mi = mi(1);
    
    fprintf('Winner %1d   scores:  ', mi);
    fprintf('%7d   ', score);
    fprintf('\n');
    
    board = boardout{mi};
%         board = boardout{4};
end


% *********************************

function [board, estim_score] = meat_pack2(words, weights, n, penalty, wordhash, dupl_ok)
    %meat_packer v.2
    %  weight by weight per letter (one for the end too)
    
    board = zeros(n, n+1);
    
    %just pack in, every other line
    wordavail = ones(size(weights));
    wordnoignore = ones(size(weights));
    %form length indexing
    for ii = 1:length(words),
        tmpl = length(words{ii});
        %         wordsoflen(tmpl) = [words_len(tmpl) ii];
        wordlen(ii) = tmpl;
    end
    %rank the word list
    realweights = weights ./ (wordlen + 1);
    
    %sort by realweights
    [w_sort, w_sorti] = sort(realweights, 1, 'descend');
    
    done = 0;
    row = 1;
    while done == 0,
        %form a row
        tmprow = zeros(1,n+1);
        col = 1;
        donerow = 0;
        colleft = n;
        while donerow == 0
            %next word
            oksize = double(wordlen <= colleft);
            [m0, ii0] = max(realweights .* wordavail .* wordnoignore .*oksize);
            
            if isempty(m0)
                %row is done
                donerow = 1;
            elseif m0(1) == 0,
                donerow = 1;
            else
                m = m0(1); ii = ii0(1);
                if dupl_ok == 1,
                    dupl = 0;   %fake out dupl flagging
                else
                    dupl = 0;
                    thishash = applyHash(words{ii});
                    simi = find(wordhash == thishash);
                    for jj = 1:length(simi),
                        if ~(simi(jj) == ii) & (words{simi(jj)} == words{ii}),
                            dupl = 1;
                            break;
                        end
                    end
                end
                
                if dupl == 1,
                    % dupl found, ignore
                    wordnoignore(ii) = 0;
                    wordnoignore(simi(jj)) = 0;
                else
                    tmprow(col:col+wordlen(ii)) = [words{ii} 0];
                    col = col+wordlen(ii)+1;
                    colleft = n - col + 1;
                    wordavail(ii) = 0;
                    if colleft <= 1,
                        donerow = 1;
                    end
                end
            end
        end
        board(row,:) = tmprow;
        row = row + 2;
        if row > n,
            done = 1;
        end
    end
    
    board = board(:, 1:n);
    
    estim_score = my_estim_score(words, wordhash, weights, wordavail, board, penalty);
    
end


% *********************************

function [board, estim_score] = meat_pack3(words, weights, n, penalty, wordhash, dupl_ok)
    
    %meat_packer v.3
    %  weight by weight per letter (one for the end too)
    
    board = zeros(n, n+1);
    
    %just pack in, every other line
    wordavail = ones(size(weights));
    wordnoignore = ones(size(weights));
    %form length indexing
    for ii = 1:length(words),
        tmpl = length(words{ii});
        %         wordsoflen(tmpl) = [words_len(tmpl) ii];
        wordlen(ii) = tmpl;
    end
    %rank the word list
    realweights = weights ./ (wordlen + 1);
    
    %sort by realweights
    [w_sort, w_sorti] = sort(realweights, 1, 'descend');
    
    done = 0;
    row = 1;
    while done == 0,
        %form a row
        tmprow = zeros(1,n+1);
        col = 1;
        donerow = 0;
        colleft = n;
        while donerow == 0
            %next word
            oksize = double(wordlen <= colleft);
            [m0, ii0] = max(realweights .* wordavail .* wordnoignore .*oksize);
            
            if isempty(m0)
                %row is done
                donerow = 1;
            elseif m0(1) == 0,
                donerow = 1;
            else
                m = m0(1); ii = ii0(1);
                if dupl_ok == 1,
                    dupl = 0;   %fake out dupl flagging
                else
                    dupl = 0;
                    thishash = applyHash(words{ii});
                    simi = find(wordhash == thishash);
                    for jj = 1:length(simi),
                        if ~(simi(jj) == ii) & (words{simi(jj)} == words{ii}),
                            dupl = 1;
                            break;
                        end
                    end
                end
                
                if dupl == 1,
                    % dupl found, ignore
                    wordnoignore(ii) = 0;
                    wordnoignore(simi(jj)) = 0;
                else
                    tmprow(col:col+wordlen(ii)) = [words{ii} 0];
                    col = col+wordlen(ii)+1;
                    colleft = n - col + 1;
                    wordavail(ii) = 0;
                    if colleft <= 1,
                        donerow = 1;
                    end
                end
            end
        end
        board(row,:) = tmprow;
        row = row + 2;
        if row > n,
            done = 1;
        end
    end
    
    %part 2:
    %
    % estimate: if the remaining weight > 2 penalty per word, then fill in
    % all rows
    
    w_used = sum(1-wordavail);
    wt_used = sum(weights .* (1-wordavail));
    
    if (wt_used / w_used) > 0.9*penalty,
        %         fprintf('fill 2nd half\n');
        
        done = 0;
        row = 2;
        while done == 0,
            %form a row
            tmprow = zeros(1,n+1);
            col = 1;
            donerow = 0;
            colleft = n;
            while donerow == 0
                %next word
                oksize = double(wordlen <= colleft);
                [m0, ii0] = max(realweights .* wordavail .* wordnoignore .*oksize);
                
                if isempty(m0)
                    %row is done
                    donerow = 1;
                elseif m0(1) == 0,
                    donerow = 1;
                else
                    m = m0(1); ii = ii0(1);
                    if dupl_ok == 1,
                        dupl = 0;   %fake out dupl flagging
                    else
                        dupl = 0;
                        thishash = applyHash(words{ii});
                        simi = find(wordhash == thishash);
                        for jj = 1:length(simi),
                            if ~(simi(jj) == ii) & (words{simi(jj)} == words{ii}),
                                dupl = 1;
                                break;
                            end
                        end
                    end
                    
                    if dupl == 1,
                        % dupl found, ignore
                        wordnoignore(ii) = 0;
                        wordnoignore(simi(jj)) = 0;
                    else
                        tmprow(col:col+wordlen(ii)) = [words{ii} 0];
                        col = col+wordlen(ii)+1;
                        colleft = n - col + 1;
                        wordavail(ii) = 0;
                        if colleft <= 1,
                            donerow = 1;
                        end
                    end
                end
            end
            board(row,:) = tmprow;
            row = row + 2;
            if row > n,
                done = 1;
            end
        end
        
        
    end
    board = board(:, 1:n);
    
    estim_score = my_estim_score(words, wordhash, weights, wordavail, board, penalty);
    
end

% *********************************
function [board, estim_score] = meat_pack4(words, weights, n, penalty, wordhash, dupl_ok)
    board = zeros(n, n+1);
    
    %just pack in, every other line
    wordavail = ones(size(weights));
    wordnoignore = ones(size(weights));
    %form length indexing
    for ii = 1:length(words),
        tmpl = length(words{ii});
        %         wordsoflen(tmpl) = [words_len(tmpl) ii];
        wordlen(ii) = tmpl;
    end
    %rank the word list
    realweights = weights ./ (wordlen + 1);
    
    %sort by realweights
    [w_sort, w_sorti] = sort(realweights, 1, 'descend');
    
    done = 0;
    row = 1;
    while done == 0,
        %form a row
        tmprow = zeros(1,n+1);
        col = 1;
        donerow = 0;
        colleft = n;
        while donerow == 0
            %next word
            oksize = double(wordlen <= colleft);
            [m0, ii0] = max(realweights .* wordavail .* wordnoignore .*oksize);
            
            if isempty(m0)
                %row is done
                donerow = 1;
            elseif m0(1) == 0,
                donerow = 1;
            else
                m = m0(1); ii = ii0(1);
                if dupl_ok == 1,
                    dupl = 0;   %fake out dupl flagging
                else
                    dupl = 0;
                    thishash = applyHash(words{ii});
                    simi = find(wordhash == thishash);
                    for jj = 1:length(simi),
                        if ~(simi(jj) == ii) & (words{simi(jj)} == words{ii}),
                            dupl = 1;
                            break;
                        end
                    end
                end
                
                if dupl == 1,
                    % dupl found, ignore
                    wordnoignore(ii) = 0;
                    wordnoignore(simi(jj)) = 0;
                else
                    tmprow(col:col+wordlen(ii)) = [words{ii} 0];
                    col = col+wordlen(ii)+1;
                    colleft = n - col + 1;
                    wordavail(ii) = 0;
                    if colleft <= 1,
                        donerow = 1;
                    end
                end
            end
        end
        board(row,:) = tmprow;
        
        %         %%%% debug
        %         tmprow(tmprow == 0) = 32;
        %         fprintf('%s\n',char(tmprow(1:n)));
        row = row + 2;
        if row > n,
            done = 1;
        end
    end
    
    %part 2:
    %
    % estimate: if the remaining weight > 2 penalty per word, then fill in
    % all rows
    
    w_used = sum(1-wordavail);
    wt_used = sum(weights .* (1-wordavail));
    
    if (wt_used / w_used) > 0.9*penalty,
        %         fprintf('fill 2nd half\n');
        
        %first compact 1st half to upper pt of board  %v5 - for visual:
        %reorder after anyway
        for ii = 3:2:n,
            board((ii+1)/2,:) = board(ii,:);
            board(ii,:) = 0;
        end
        done = 0;
        row = ceil(n/2)+1;
        while done == 0,
            %form a row
            tmprow = zeros(1,n+1);
            col = 1;
            donerow = 0;
            colleft = n;
            while donerow == 0
                %next word
                oksize = double(wordlen <= colleft);
                [m0, ii0] = max(realweights .* wordavail .* wordnoignore .*oksize);
                
                if isempty(m0)
                    %row is done
                    donerow = 1;
                elseif m0(1) == 0,
                    donerow = 1;
                else
                    m = m0(1); ii = ii0(1);
                    if dupl_ok == 1,
                        dupl = 0;   %fake out dupl flagging
                    else
                        dupl = 0;
                        thishash = applyHash(words{ii});
                        simi = find(wordhash == thishash);
                        for jj = 1:length(simi),
                            if ~(simi(jj) == ii) & (words{simi(jj)} == words{ii}),
                                dupl = 1;
                                break;
                            end
                        end
                    end
                    
                    if dupl == 1,
                        % dupl found, ignore
                        wordnoignore(ii) = 0;
                        wordnoignore(simi(jj)) = 0;
                    else
                        tmprow(col:col+wordlen(ii)) = [words{ii} 0];
                        col = col+wordlen(ii)+1;
                        colleft = n - col + 1;
                        wordavail(ii) = 0;
                        if colleft <= 1,
                            donerow = 1;
                        end
                    end
                end
            end
            board(row,:) = tmprow;
            row = row + 1;
            if row > n,
                done = 1;
            end
        end
        
        
    end
    board = board(:, 1:n);
    
    estim_score = my_estim_score(words, wordhash, weights, wordavail, board, penalty);
    
end

% *********************************
function [board, estim_score] = meat_pack4order(words, weights, n, penalty, wordhash, dupl_ok)
    board = zeros(n, n+1);
    
    %just pack in, every other line
    wordavail = ones(size(weights));
    wordnoignore = ones(size(weights));
    %form length indexing
    for ii = 1:length(words),
        tmpl = length(words{ii});
        %         wordsoflen(tmpl) = [words_len(tmpl) ii];
        wordlen(ii) = tmpl;
    end
    %rank the word list
    realweights = weights ./ (wordlen + 1);
    
    %sort by realweights
    [w_sort, w_sorti] = sort(realweights, 1, 'descend');
    
    done = 0;
    row = 1;
    while done == 0,
        %form a row
        tmprow = zeros(1,n+1);
        col = 1;
        donerow = 0;
        colleft = n;
        while donerow == 0
            %next word
            oksize = double(wordlen <= colleft);
            [m0, ii0] = max(realweights .* wordavail .* wordnoignore .*oksize);
            
            if isempty(m0)
                %row is done
                donerow = 1;
            elseif m0(1) == 0,
                donerow = 1;
            else
                m = m0(1); ii = ii0(1);
                if dupl_ok == 1,
                    dupl = 0;   %fake out dupl flagging
                else
                    dupl = 0;
                    thishash = applyHash(words{ii});
                    simi = find(wordhash == thishash);
                    for jj = 1:length(simi),
                        if ~(simi(jj) == ii) & (words{simi(jj)} == words{ii}),
                            dupl = 1;
                            break;
                        end
                    end
                end
                
                if dupl == 1,
                    % dupl found, ignore
                    wordnoignore(ii) = 0;
                    wordnoignore(simi(jj)) = 0;
                else
                    tmprow(col:col+wordlen(ii)) = [words{ii} 0];
                    col = col+wordlen(ii)+1;
                    colleft = n - col + 1;
                    wordavail(ii) = 0;
                    if colleft <= 1,
                        donerow = 1;
                    end
                end
            end
        end
        board(row,:) = tmprow;
        
        %                 %%%% debug
        %                 tmprow(tmprow == 0) = 32;
        %                 fprintf('%s\n',char(tmprow(1:n)));
        row = row + 1;
        if row > n,
            done = 1;
        end
    end
    
    board = board(:, 1:n);
    
    %reorder the board
    wordused = 1-wordavail;
    lenused = wordlen(wordused == 1);
    
    done = 0;
    board2 = zeros(size(board));
    currlen = max(lenused);
    rr = 1;
    cc = 1;
    pilewid = 0;
    noti = [];
    while done == 0,
        wi = find(wordlen .* wordused == currlen);
        while ~isempty(wi),
            thisi = wi(1);
            wi = wi(2:end);
            if currlen <= n - cc + 1,
                board2(rr, cc:cc+currlen) = [words{thisi} 0];
                rr = rr + 1;
                pilewid = max([pilewid currlen]);
            else
                noti = [noti thisi];
                wordavail(thisi) = 1;   %put it back sadly
            end
            if rr > n,
                %new pile
                cc = cc + pilewid + 1;  %1 for space
                rr = 1;
                pilewid = 0;
            end
%             if n - cc < 2,
%                 %put the remaining unshelved items back
%                 shelve_rest = 1;
%             end
        end
        %next length
        currlen = currlen -1;
        if currlen == 0,
            done = 1;
        end
    end
    board = board2(1:n,1:n);
    
    
    estim_score = my_estim_score(words, wordhash, weights, wordavail, board, penalty);
    
end


function val = applyHash(word)
    % applyHash: A rudimentary hashing function to speed up looking for words
    % in the dictionary
    
    n = min(5, ceil(numel(word)/2));
    m1 = [1e10, 1e9, 1e8, 1e7, 1e6];
    m2 = [1e4, 1e3, 1e2, 1e1, 1e0];
    
    val = 1e12*sum(word) + sum(word(1:n).*m1(1:n)) + sum(word(end-n+1:end).*m2(1:n));
end
function estim_score = my_estim_score(words, wordhash, weights, wordavail, board, penalty);
    
    %estimate score:
    % assume horiz words ok, vert are bogus
    
    %find each word, check score used
    wordused = zeros(size(weights));
    wi = find(wordavail == 0);
    for ii = 1:length(wi),
        thishash = applyHash(words{wi(ii)});
        possi = find(wordhash == thishash);
        for jj = 1:length(possi),
            if isequal(words{wi(ii)}, words{possi(jj)}),
                thisi = possi(jj);
                break
            end
        end
        wordused(thisi) = 1;
    end
    
    %     remain_in_dict = sum(weights .* wordavail);
    remain_in_dict = sum(weights .* (1-wordused));
    n = size(board, 2);
    binboard = [zeros(1,n); sign(board)];
    diff1 = diff(binboard, 1, 1);
    diff2 = diff(diff1, 1, 1);
    diff1 = diff1(1:end-1, :);
    bi = find(diff1 == 1 & diff2 == -1);
    nbogus = numel(bi);
    estim_score = remain_in_dict + nbogus * penalty;
    %     fprintf('Est score: %d    remain: %d    nbogus %d  penalty %d\n', estim_score, remain_in_dict, nbogus, penalty);
    
end  %fn