DarknessEnd2

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



%% solver 1, weight per char, every other row
% setup vars
col = 1;
row = 1;
spaceavail=1;
item=1;
weightsum=0;
% pre populate board
board=zeros(n);

%construct length array, in sorted order
for x=1:size(words,2)
    len(x)=size(words{x},2);
end

% find weight per char
[vals,locs]=sort(weights./len,2,'descend');
len=len(locs);

while spaceavail
    % insert word into board at current location
    if (col+len(item)-1) <= n
        board(row,col:(col+len(item)-1))=words{locs(item)};
        col = col+len(item)+1;
        if col >=n
            col=1;
            row=row+2;
        end
        weightsum=weightsum+weights(locs(item));
        len(item)=[];
        locs(item)=[];
        item=1;
    else
        item=item+1;
        if item > numel(len)
            item=1;
            col=1;
            row=row+2;
        end
    end
    
    if row > n
        spaceavail=0;
    end
    
end

%% solver 2, weight per char, stagger step rows
% setup vars
col = 1;
row = 1;
spaceavail=1;
item=1;
weightsum2=0;
alt=0;
skipnextrow=0;

% pre populate board
board2=zeros(n);

%construct length array, in sorted order
for x=1:size(words,2)
    len(x)=size(words{x},2);
end

% find weight per char
[vals,locs]=sort(weights./len,2,'descend');
len=len(locs);
curlen=len(1);

while spaceavail
    % insert word into board at current location
    if (col+len(item)-1) <= n
        board2(row+alt,col:(col+len(item)-1))=words{locs(item)};
        col = col+len(item);
        if (curlen ~= len(item)) && (row > 1) && (row < n)
            if nnz(board2(row-1,(col-len(item)):end)) > 0
            board2(row+1:row+2,:)=board2(row:row+1,:);
            board2(row,:)=zeros(1,n);
            row=row+1;
            end
            curlen = len(item);
            skipnextrow=1;
        end
        if alt
            alt=0;
        else
            alt=1;
        end
        if row == n
            alt=0;
            col=col+len(item);
        end
        if col >=n
            col=1;
            row=row+2+skipnextrow;
            skipnextrow=0;
            alt=0;
        end
        weightsum2=weightsum2+weights(locs(item));
        len(item)=[];
        locs(item)=[];
        item=1;
    else
        item=item+1;
        if item > numel(len)
            item=1;
            col=1;
            row=row+2+skipnextrow;
            skipnextrow=0;
            alt=0;
        end
    end
    
    if row > n
        spaceavail=0;
    end
    
end

if weightsum2>weightsum
    board=board2;
    weightsum=weightsum2;
end


%% solver 3, length per char, stagger step rows
% setup vars
col = 1;
row = 1;
spaceavail=1;
item=1;
weightsum2=0;
alt=0;
skipnextrow=0;

% pre populate board
board2=zeros(n);

%construct length array, in sorted order
for x=1:size(words,2)
    len(x)=size(words{x},2);
end

% find weight per char
[vals,locs]=sort(len,2,'ascend');
len=len(locs);
curlen=len(1);

while spaceavail
    % insert word into board at current location
    if (col+len(item)-1) <= n
        board2(row+alt,col:(col+len(item)-1))=words{locs(item)};
        col = col+len(item);
        if (curlen ~= len(item)) && (row > 1) && (row < n)
            board2(row+1:row+2,:)=board2(row:row+1,:);
            board2(row,:)=zeros(1,n);
            row=row+1;
            curlen = len(item);
            skipnextrow=1;
        end
        if alt
            alt=0;
        else
            alt=1;
        end
        if row == n
            alt=0;
            col=col+len(item);
        end
        if col >=n
            col=1;
            row=row+2+skipnextrow;
            skipnextrow=0;
            alt=0;
        end
        weightsum2=weightsum2+weights(locs(item));
        len(item)=[];
        locs(item)=[];
        item=1;
    else
        item=item+1;
        if item > numel(len)
            item=1;
            col=1;
            row=row+2+skipnextrow;
            skipnextrow=0;
            alt=0;
        end
    end
    
    if row > n
        spaceavail=0;
    end
    
end

if weightsum2>weightsum
    board=board2;
    weightsum=weightsum2;
end

end