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

sausage links may I take your order

by Seth Kosowsky

Status: Passed
Results: 7329493 (cyc: 22, node: 2216)
CPU Time: 15.581
Score: 18338.1
Submitted at: 2011-04-14 05:16:47 UTC
Scored at: 2011-04-14 05:18:32 UTC

Current Rank: 1239th (Highest: 1st )

Comments
Please login or create a profile.
Code
function board = solver(words, weights, n, penalty)
    
    %meat_packer v.5
    %  weight by weight per letter (one for the end too)
    % with scoring metric
    
    ii = 0;
    
    ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack2(words, weights, n, penalty);  %every other fill
    ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack3(words, weights, n, penalty);  % 2 interleaved every other fills
    ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack4(words, weights, n, penalty);  % all lines filled (squeeze & pack)
    ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack4order(words, weights, n, penalty);  % 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)
    %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));
    %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);
            [m, ii] = max(realweights .* wordavail .* oksize);
            if isempty(m)
                %row is done
                donerow = 1;
            elseif m(1) == 0,
                donerow = 1;
            else
                m = m(1); ii = ii(1);
                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
        board(row,:) = tmprow;
        row = row + 2;
        if row > n,
            done = 1;
        end
    end
    
    board = board(:, 1:n);
    
    %estimate score:
    % assume horiz words ok, vert are bogus
    remain_in_dict = sum(weights .* wordavail);
    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

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

function [board, estim_score] = meat_pack3(words, weights, n, penalty)
    
    %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));
    %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);
            [m, ii] = max(realweights .* wordavail .* oksize);
            if isempty(m)
                %row is done
                donerow = 1;
            elseif m(1) == 0,
                donerow = 1;
            else
                m = m(1); ii = ii(1);
                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
        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);
                [m, ii] = max(realweights .* wordavail .* oksize);
                if isempty(m)
                    %row is done
                    donerow = 1;
                elseif m(1) == 0,
                    donerow = 1;
                else
                    m = m(1); ii = ii(1);
                    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
            board(row,:) = tmprow;
            row = row + 2;
            if row > n,
                done = 1;
            end
        end
        
        
    end
    board = board(:, 1:n);
    
    %estimate score:
    % assume horiz words ok, vert are bogus
    remain_in_dict = sum(weights .* wordavail);
    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

% *********************************
function [board, estim_score] = meat_pack4(words, weights, n, penalty)
    board = zeros(n, n+1);
    
    %just pack in, every other line
    wordavail = 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);
            [m, ii] = max(realweights .* wordavail .* oksize);
            if isempty(m)
                %row is done
                donerow = 1;
            elseif m(1) == 0,
                donerow = 1;
            else
                m = m(1); ii = ii(1);
                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
        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);
                [m, ii] = max(realweights .* wordavail .* oksize);
                if isempty(m)
                    %row is done
                    donerow = 1;
                elseif m(1) == 0,
                    donerow = 1;
                else
                    m = m(1); ii = ii(1);
                    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
            board(row,:) = tmprow;
            row = row + 1;
            if row > n,
                done = 1;
            end
        end
        
        
    end
    board = board(:, 1:n);
    
    %estimate score:
    % assume horiz words ok, vert are bogus
    remain_in_dict = sum(weights .* wordavail);
    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

% *********************************
function [board, estim_score] = meat_pack4order(words, weights, n, penalty)
    board = zeros(n, n+1);
    
    %just pack in, every other line
    wordavail = 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);
            [m, ii] = max(realweights .* wordavail .* oksize);
            if isempty(m)
                %row is done
                donerow = 1;
            elseif m(1) == 0,
                donerow = 1;
            else
                m = m(1); ii = ii(1);
                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
        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);
                [m, ii] = max(realweights .* wordavail .* oksize);
                if isempty(m)
                    %row is done
                    donerow = 1;
                elseif m(1) == 0,
                    donerow = 1;
                else
                    m = m(1); ii = ii(1);
                    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
            board(row,:) = tmprow;
            row = row + 1;
            if row > n,
                done = 1;
            end
        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];
            end
            if rr > n,
                %new pile
                cc = cc + pilewid + 1;  %1 for space
                rr = 1;
                pilewid = 0;
            end
            if n - cc < 2,
                done = 1;
            end
        end
        %next length
        currlen = currlen -1;
        if currlen == 0,
            done = 1;
        end
    end
    board = board2(1:n,1:n);    
            
    
    %estimate score:
    % assume horiz words ok, vert are bogus
    remain_in_dict = sum(weights .* wordavail) + sum(weights(noti));
    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