Five golden rings

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

% the cyclist solver

% Copyright 2011 the cyclist, Not Inc.

% Sort the words in order of descending weight
[weights indexToWeightSorting] = sort(weights,2,'descend');
words = words(indexToWeightSorting);


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

% 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)
        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

% 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

% 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)
        topVal = board(row,  col);
        midVal = board(row+2,col);
        botVal = board(row+4,col);
        indexToWordToUse = find(word5(1,:)==topVal & word5(3,:)==midVal & word5(5,:)==botVal,1,'first');
        if any(indexToWordToUse)
            board([row+1 row+3],col) = word5([2 4],indexToWordToUse);
            word5(:,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)
           topTwoValue = board(row,nt);
           indexToLengthTwoWordThatFits = find(word2(1,:)==topTwoValue,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