markus4a

function board = solver(wordCell, weights, boardSize, bogusPenalty)

board = zeros(boardSize);

weights = weights(:);
nrOfWords = length(wordCell);
wordLengths = zeros(nrOfWords, 1);

maxWeight = max(weights);
for w = 1 : nrOfWords
  currWord = wordCell{w};
  wordLengths(w) = length(currWord);
end
minWordLength = min(wordLengths);

wordScoreA = weights ./ (wordLengths + 1);
wordScoreB = weights;
wordScoreC = (max(wordLengths) - wordLengths) + 0.9 * weights / maxWeight;

if minWordLength == boardSize
  [ignore, wordScoreASortIndex] = sort(wordScoreA, 1, 'descend');
  [ignore, wordScoreBSortIndex] = sort(wordScoreB, 1, 'descend');

  scoreRedRowStep1 = sum(weights(wordScoreBSortIndex(1:boardSize))) - boardSize * bogusPenalty;
  scoreRedRowStep2 = sum(weights(wordScoreASortIndex(1:(ceil(boardSize/2)))));

  placeWordsNextToEachOther = 0;
  
  if scoreRedRowStep1 > scoreRedRowStep2
    rowStep = 1;
    wordScoreSortIndex = wordScoreBSortIndex;
  else
    rowStep = 2;
    wordScoreSortIndex = wordScoreASortIndex;
  end
else

  placeWordsNextToEachOther = 2;
  [ignore, wordScoreSortIndex] = sort(wordScoreA, 1, 'descend');
  rowStep = 2;

end

  startRow = 1;
  startCol = 1;
  endRow = boardSize;
  endCol = boardSize;
  
if rowStep == 1 && minWordLength == boardSize

  % simply fill the board and return
  for row = 1 : boardSize
    w = wordScoreSortIndex(row);
    board(row, :) = wordCell{w};
  end
  return
 
else

  if placeWordsNextToEachOther == 2
    [ignore, wordScoreSortIndex] = sort(wordScoreC, 1, 'descend');
    nWord = 1;
    dirLeftRight = 0;
    runWhileLoop = 1;
    topRow = 1;
    wordUsed = false(nrOfWords,1);
    while runWhileLoop
      dirLeftRight = ~dirLeftRight;

      putWordIndex = 0;
      putWordNr  = zeros(boardSize,1);
      putWordCol = zeros(boardSize,1);

      if dirLeftRight
        lastRowEndVector = zeros(boardSize, 1);
        for col = 1 : boardSize
          if nWord <= nrOfWords
            w = wordScoreSortIndex(nWord);
            wordUsed(nWord) = true;
            nWord = nWord + 1;
            currWordLength = wordLengths(w);

            lastRowEndVector(col) = topRow + currWordLength - 1;

            if lastRowEndVector(col) <= boardSize
              putWordIndex = putWordIndex + 1;
              putWordNr (putWordIndex) = w;
              putWordCol(putWordIndex) = col;
            else
              startRow = topRow;
              startCol = col + 1;
              runWhileLoop = 0;
              break
            end
          else
            startRow = boardSize + 1;
            runWhileLoop = 0;
            break
          end
        end

      else
        bottomRow = -10;
        for col = boardSize : -1 : 1
          if nWord <= nrOfWords
            w = wordScoreSortIndex(nWord);
            wordUsed(nWord) = true;
            nWord = nWord + 1;
            currWordLength = wordLengths(w);

            currBottomRow = lastRowEndVector(col) + currWordLength + 1;
            if currBottomRow <= boardSize
              bottomRow = max(bottomRow, currBottomRow);
              putWordIndex = putWordIndex + 1;
              putWordNr (putWordIndex) = w;
              putWordCol(putWordIndex) = col;
            else
              endCol   = col - 1;
              if bottomRow > 0
                startRow = bottomRow;
              else
                startRow = max(lastRowEndVector) + 2;
              end
              runWhileLoop = 0;
              break
            end
          else
            startRow = boardSize + 1;
            runWhileLoop = 0;
            break
          end
        end
      end

      for k = 1:putWordIndex
        w = putWordNr(k);
        if dirLeftRight
          putRow1 = topRow;
          putRow2 = topRow + wordLengths(w) - 1;
        else
          putRow2 = bottomRow;
          putRow1 = bottomRow - wordLengths(w) + 1;
        end
        board(putRow1 : putRow2, putWordCol(k)) = wordCell{w};
      end

      if ~dirLeftRight
        topRow = bottomRow + 2;
      end
    end
    
    wordScoreSortIndex(wordUsed) = [];
  end
end

  for n = 1:length(startRow)

    if endRow(n) - startRow(n) < endCol(n) - startCol(n)
      for row = startRow(n) : rowStep : endRow(n)
        col = startCol(n);
        k = 1;
        while (k <= length(wordScoreSortIndex)) && (col <= endCol(n))
          w = wordScoreSortIndex(k);
          if wordLengths(w) <= (endCol(n) - col + 1)
            index = col : col + wordLengths(w) - 1;
            board(row, index) = wordCell{w};
            col = index(end) + 2;
            wordScoreSortIndex(k) = [];
            if endCol(n) - col + 1 < minWordLength
              break;
            end
          else
            k = k + 1;
          end
        end
      end

    else
      colStep = 2;
      for col = startCol(n) : colStep : endCol(n)
        row = startRow(n);
        k = 1;
        while (k <= length(wordScoreSortIndex)) && (row <= endRow(n))
          w = wordScoreSortIndex(k);
          if wordLengths(w) <= (endRow(n) - row + 1)
            index = row : row + wordLengths(w) - 1;
            board(index, col) = wordCell{w};
            row = index(end) + 2;
            wordScoreSortIndex(k) = [];
            if endRow(n) - row + 1 < minWordLength
              break;
            end
          else
            k = k + 1;
          end
        end
      end
    end
  end