TwilightEnd1

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


totalweight=sum(weights);
for x=1:size(words,2)
    origlen(x)=size(words{x},2);
end


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

%construct length array, in sorted order

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

while row <= n
    % 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;
        weightsum=weightsum+weights(locs(item));
        len(item)=[];
        locs(item)=[];
        item=1;
    else
        item=item+1;
    end
    if item > numel(len)
        item=1;
        col=1;
        row=row+2;
    end
    if col >=n
        col=1;
        row=row+2;
    end
    
end

if weightsum == totalweight
    return
end

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

% pre populate board
board2=zeros(n);

%construct length array, in sorted order
len=origlen;

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

while row <= n
    % 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
        alt=~alt;
        weightsum2=weightsum2+weights(locs(item));
        len(item)=[];
        locs(item)=[];
        item=1;
    else
        item=item+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
    if item > numel(len)
        item=1;
        col=1;
        row=row+2+skipnextrow;
        skipnextrow=0;
        alt=0;
    end
    
    
end

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

if weightsum == totalweight
    return
end


%% solver 5, weight per char, every row, full rows if penalty is small
% setup vars
col = 1;
row = 1;
item=1;
weightsum2=0;
% pre populate board
board2=zeros(n);

%construct length array, in sorted order
len=origlen;
minlen = min(len);
avglen=mean(len);
avgweight=mean(weights);
avgperline=round(n/(avglen+1));

if (avgperline*avgweight/2) > (penalty*1)
    linestep=1;
else
    linestep=2;
end

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

while row <= n
    % insert word into board at current location
    if len(item) <= maxlen
        newmaxlen = maxlen - len(item) - 1;
        newlen = len;
        newlen(item) =[];
        newminlen = min(newlen);
        if (newmaxlen == -1) || (newminlen < newmaxlen)|| insertany
            board2(row,col:(col+len(item)-1))=words{locs(item)};
            col = col+len(item)+1;
            weightsum2=weightsum2+weights(locs(item));
            len=newlen;
            locs(item)=[];
            item=1;
            maxlen = newmaxlen;
            minlen=newminlen;
            insertany=0;
            
        else
            item=item+1;
            
        end
        if col >=n
            col=1;
            row=row+linestep;
            maxlen=n;
        end
        if item > numel(len)
            item=1;
            insertany=1;
        end
    else
        item=item+1;     
    end
    if item > numel(len)
        item=1;
        col=1;
        row=row+linestep;
    end
end

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


end