Weighty matters

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

% the cyclist solver
% Copyright 2011 the cyclist, not Inc.

% Determine word lengths
numberWords = length(words);


lengthWords = nan(numberWords,1);
for ii=1:numberWords
    lengthWords(ii) = length(words{ii});
end

% Sort the words in order of descending weight
[weightsAndLengths indexToWeightSorting] = sortrows([weights'./(n+lengthWords) lengthWords],[-1 2]);
% [weightsAndLengths indexToWeightSorting] = sort(weights,2,'descend');

words = words(indexToWeightSorting);
lengthWords = weightsAndLengths(:,2);

% Preallocate the board with zeros
board = zeros(n,n);

% Fill in every other row, beginning with top row. Iterate the following algorithm:
% -- Find highest-weight word that will fit in the line
% -- Place it, with a blank next to i
% -- Repeat

for row = 1:ceil(n/2)
    currentLength = 0;
    
    while (currentLength <= n)
        indexToWordToUse = find(lengthWords<=(n-currentLength),1,'first');
%         indexToWordsThatFit = find(lengthWords<=(n-currentLength));
%         weightOfWordsThatFit = weights(indexToWordsThatFit);
%         indexToMaxWeightFitWords = find(weightOfWordsThatFit==max(weightOfWordsThatFit));
%         lengthMaxWeightFitWords = lengthWords(indexToWordsThatFit(indexToMaxWeightFitWords));
%         [minLengthMaxWeightFitWords indexToMinLengthMaxWeightFitWords] = min(lengthMaxWeightFitWords);
%         indexToWordToUse = indexToWordsThatFit(indexToMaxWeightFitWords(indexToMinLengthMaxWeightFitWords));
        if not(isempty(indexToWordToUse))
            wordToUse = words{indexToWordToUse};
            lengthWords(indexToWordToUse) = Inf;
            lengthWordToUse = numel(wordToUse);
            board(2*row-1,currentLength+1:currentLength+lengthWordToUse) = wordToUse;
            currentLength = currentLength + lengthWordToUse + 1;
        else
            break
        end
    end
    
end

for kk=1:3
% After the above, there will be a ragged right column. Fill down this column with highest-weight words that fit.
blanksInRightmostColumn = find(board(:,n-1)==0&board(:,n)==0&[nan;board(1:n-1,n)]==0&[board(2:n,n);nan]==0);
numberBlanks = numel(blanksInRightmostColumn);
if numberBlanks>0
    lengthToFit = 0;
    anchor = blanksInRightmostColumn(1);
    for nb = 1:numberBlanks-1
        lengthToFit = lengthToFit+1;
        if blanksInRightmostColumn(nb+1)==blanksInRightmostColumn(nb)+1
            continue
        else
            indexToWordToUse = find(lengthWords<=lengthToFit,1,'first');
            if not(isempty(indexToWordToUse))
                wordToUse = words{indexToWordToUse};
                lengthWords(indexToWordToUse) = Inf;
                lengthWordToUse = numel(wordToUse);
                board(anchor:anchor+lengthWordToUse-1,n) = wordToUse;
            end
            anchor = blanksInRightmostColumn(nb+1);
            lengthToFit = 0;
        end
    end
end
end

% Find 3-letter words that we are going to sneak in.
word3Array = words(find(lengthWords==3))';
numberLength3Words = length(word3Array);
word3 = nan(3,numberLength3Words);
for jj=1:numberLength3Words
    word3(:,jj)=word3Array{jj}';
end

% Anywhere we can fit, place a 3-letter word
for row = 1:n-2
for col = 1:n
    if (row==1  ||board(row-1,col  )==0) ...
    && (col==1  ||board(row+1,col-1)==0) && board(row+1,col)==0  && (col==n||board(row+1,col+1)==0) ...
    && (row==n-2||board(row+3,col  )==0)
        topVal = board(row  ,col);
        botVal = board(row+2,col);
        indexToWordToUse = find(word3(1,:)==topVal&word3(3,:)==botVal,1,'first');
        if any(indexToWordToUse)
            board(row+1,col) = word3(2,indexToWordToUse);
            word3(:,indexToWordToUse) = [];
        end
    end
end
end

% Find 5-letter words that we are going to sneak in.
word5Array = words(find(lengthWords==5))';
numberLength5Words = length(word5Array);
word5 = nan(5,numberLength5Words);
for jj=1:numberLength5Words
    word5(:,jj)=word5Array{jj}';
end

% Anywhere we can fit, place a 5-letter word
for row = 1:n-4
for col = 1:n
    if (row==1  ||board(row-1,col  )==0) ...
    && (col==1  ||board(row+1,col-1)==0) && board(row+1,col)==0  && (col==n||board(row+1,col+1)==0) ...
    && (col==1  ||board(row+3,col-1)==0) && board(row+3,col)==0  && (col==n||board(row+3,col+1)==0) ...
    && (row==n-4||board(row+5,col)==0)
        val1 = board(row,  col);
        val3 = board(row+2,col);
        val5 = board(row+4,col);
        indexToWordToUse = find(word5(1,:)==val1 & word5(3,:)==val3 & word5(5,:)==val5,1,'first');
        if any(indexToWordToUse)
            board([row+1 row+3],col) = word5([2 4],indexToWordToUse);
            word5(:,indexToWordToUse) = [];
        end
    end
end
end

% % Find 7-letter words that we are going to sneak in.
% word7Array = words(find(lengthWords==7))';
% numberLength7Words = length(word7Array);
% word7 = nan(7,numberLength5Words);
% for jj=1:numberLength7Words
%     word7(:,jj)=word7Array{jj}';
% end
% 
% % Anywhere we can fit, place a 5-letter word
% for row = 1:n-6
% for col = 1:n
%     if (row==1||board(row-1,col)==0) ...
%     && (col==1||board(row+1,col-1)==0) && board(row+1,col)==0  && (col==n||board(row+1,col+1)==0) ...
%     && (col==1||board(row+3,col-1)==0) && board(row+3,col)==0  && (col==n||board(row+3,col+1)==0) ...
%     && (col==1||board(row+5,col-1)==0) && board(row+5,col)==0  && (col==n||board(row+5,col+1)==0) ...
%     && (row==n-6||board(row+7,col)==0)
%         val1 = board(row,  col);
%         val3 = board(row+2,col);
%         val5 = board(row+4,col);
%         val7 = board(row+6,col);
%         indexToWordToUse = find(word7(1,:)==val1 & word7(3,:)==val3 & word7(5,:)==val5 & word7(7,:)==val7,1,'first');
%         if any(indexToWordToUse)
%             board([row+1 row+3 row+5],col) = word7([2 4 6],indexToWordToUse);
%             word7(:,indexToWordToUse) = [];
%         end
%     end
% end
% end

% Find 2-letter words that we are going to sneak in.
word2Array = words(find(lengthWords==2))';
numberLength2Words = length(word2Array);
word2 = nan(2,numberLength2Words);
for jj=1:numberLength2Words
    word2(:,jj)=word2Array{jj}';
end

% Anywhere there is room, place a stalagmite down from a main row
for row = 1:2:n-3
   indexToTwoSpots = find(board(row+2,:)==0);
   
   for nt = indexToTwoSpots
       if (nt==1||board(row+1,nt-1)==0) && (nt==n||board(row+1,nt+1)==0) && (row==1||board(row-1,nt)==0)
           val1 = board(row,nt);
           indexToLengthTwoWordThatFits = find(word2(1,:)==val1,1,'first');
           if any(indexToLengthTwoWordThatFits)
               board(row:row+1,nt) = word2(:,indexToLengthTwoWordThatFits);
               word2(:,indexToLengthTwoWordThatFits) = [];
           end
       end
   end
end

% Anywhere there is room, place a stalactite up from a main row
for row = 3:2:n
   indexToTwoSpots = find(board(row-2,:)==0);
   
   for nt = indexToTwoSpots
       if (nt==1||board(row-1,nt-1)==0) && (nt==n||board(row-1,nt+1)==0) && (row==n||board(row+1,nt)==0)
           botTwoValue = board(row,nt);
           indexToLengthTwoWordThatFits = find(word2(2,:)==botTwoValue,1,'first');
           if any(indexToLengthTwoWordThatFits)
               board(row-1:row,nt) = word2(:,indexToLengthTwoWordThatFits);
               word2(:,indexToLengthTwoWordThatFits) = [];
           end
       end
   end
end

end