2011-04-20 12:00:00 UTC

# lameSecondTry

Status: Passed
Results: 8442600 (cyc: 7, node: 506)
CPU Time: 93.977
Score: 21126.0
Submitted at: 2011-04-14 23:15:43 UTC
Scored at: 2011-04-14 23:20:14 UTC

Current Rank: 1546th (Highest: 140th )

Code
function board = solver(words, weights, n, penalty)

% Sample solver

% Copyright 2011 The MathWorks, Inc.

board = zeros(n);
nWords = length(words);

remainInDictionary = struct('words',{words}, 'weights',{weights}, ...
'hash', {cellfun(@applyHash, words)}, ...
'ratio',{[]}, ...
'order',{[]});

%--------------------------------------

fprintf('------------------------------------------\n');
fprintf('%d words, grid %dx%d, penalty is %d\n',nWords,n,n,penalty);

for i = 1:length(words)
remainInDictionary.ratio(i) = weights(i)/length(words{i});
end

% Stores indices of order we will be trying to insert the words
[m,remainInDictionary.order] = sort(remainInDictionary.ratio,'descend');

%--------------------------------------
%
% Basic Structure
%
% For all words
stop = false;
fullcycle = false;
score = 0;
[selectionAlg,positionAlg] = adjustAlgorithm(board, score, penalty);
while( ~fullcycle && ~stop && any(weights) )

ind = remainInDictionary.order;
fullcycle = true;
for i = 1:length(ind)
word = words{ind(i)};
[board,success,stop] = positionAlg(board,word,n);
if (success)
fullcycle = false;
remainInDictionary.order(i) = [];
break;
end
end

end

end

%%
function [selectionAlg,positionAlg] = adjustAlgorithm(board, score, penalty)
selectionAlg = @selectWord;
positionAlg  = @positionWords2;
end

%% Position Algs ---------------------------------------------------------------

function [board,success,stop] = positionWords2(board,word,n)

% Squeezes as many words as it can, no intersections (score: 137177)

success = false;
stop = false;

% Find row index
rIdx = find(board(:,1) > 0);
if (isempty(rIdx))
rIdx = 1;
end

fit = false;
for j = 1:length(rIdx)
row = rIdx(j);
[fit,board] = squeezeWordInRow( board, word, row, n );
if (fit)
success = true;
break;
end
end

if (~fit)
% Try next row
row = rIdx(end)+2;
if (row > n)
return;
else
[fit,board] = squeezeWordInRow( board, word, row, n );
if (~fit)
return;
else
success = true;
end
end
end

end

function [success,board] = squeezeWordInRow( board, word, row, n )

success = false;
colIdx = find(board(row,:) > 0);
if (isempty(colIdx))
col = 1;
else
col = colIdx(end) + 2;
end

if (col > n || (n - col + 1) < length(word))
return;
else
success = true;
board(row,col:(col+(length(word)-1))) = word;
end

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