lameSecondTry

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