Changing a 1D random placement code to 2D

I currently have a code that randomly places 2 different size grains/vechicles on a line of 10,000 spaces with no overlaps. I was wondering if there was an easy way to turn this into a 2D design that fills a 10,000x10,000 space with no overlaps. The shapes should be square so the small should be 3x3 and the large 10x10. The shapes also need to fill from bottom up. This should be something similar to tetris but with no rotation or movement.

x = [];
taken_spots = [];
%% Generate Random Numbers
s = 10000; %total number of available parking spots
n = s*5; %n = quantity of random numbers to generate
L = .1; %chance for large grain = L (0-L = Large grain, > L = small grain)
LG = 10; %large grain size
SG = 3; %small grain size
numbers = rand(n,1); %n number of random numbers to be used for vehicle size
spot = round(s*rand(n,1)); %random starting spots for each vehicle between 1 and s spot limit

is_LG = numbers <= L;
Y = SG*ones(1,n);
Y(is_LG) = LG;

nLG = 0;
nSG = 0;
for i = 1:n
    x = spot(i)+(0:Y(i)-1);
    if ~any(ismember(x, taken_spots))
        taken_spots(end+1:end+Y(i)) = x; %add new spots to end of taken spots array
    end
    if is_LG(i)
        nLG = nLG+1; %count number of large grains
    else
        nSG = nSG+1; %count number of small grains 
    end
end

density = length(taken_spots)/s*100

bar([nSG nLG])
xticklabels({'# Small' '# Large'})

[Walter Roberson]

This should be something similar to tetris

So, to confirm, the following should be a legal output

..LLLLLLLLLL.....SSS....

..LLLLLLLLLL.....SSS....

..LLLLLLLLLL.....SSS....

..LLLLLLLLLL..LLLLLLLLLL

..LLLLLLLLLL..LLLLLLLLLL

..LLLLLLLLLL..LLLLLLLLLL

..LLLLLLLLLL..LLLLLLLLLL

..LLLLLLLLLL..LLLLLLLLLL

..LLLLLLLLLL..LLLLLLLLLL

..LLLLLLLLLL..LLLLLLLLLL

SSS...........LLLLLLLLLL

SSS...........LLLLLLLLLL

SSS...........LLLLLLLLLL

... Or not because there is room for another S block between the L and the S at the top? Or is the number of blocks of each type to be balanced, in which case you would not try to repeatedly drop 3 x 3 into spaces too small to fit 10 x 10, taking into account that due to the differences in sizes that up to nine of the 3 x 3 blocks could fit into a 10 x 10 space ?

[Branson]

The bottom 3 layers would be an acceptable output. However the top 3 rows are not acceptable because they could be filled with 3x3s and noting is blocking their path to fill the space. The number of blocks also doesn't need to be balanced as they would be randomly generated to fill the spaces, but if there is nothing blocking the path of a 3x3 it could fill a space a 10x10 could not fit into.

Answer 1

[Walter Roberson]

So, algorithm:

• initialize output matrix board to 0
• define function hasAvailableSlot(board) as testing whether there is any gap in the third (counting from top) row of the board that is at least 3 wide. This is hasAvailableSlot = @(board) ~isempty(strfind(board(3,:), [0 0 0]))
• while hasAvailableSlot(board)
• generate a random width
• generate a random column number between 1 and s-width+1
• hasroom = ~any(board(width:end,column:column+width-1));
• goes_at_row = sum(cumprod(hasroom));
• if goes_at_row == 0; continue; end %object would have to be above the top, retry the generation
• place object at row goes_at_row:goes_at_row+width-1, and column column:column+width-1
• end while

In summary, this object generates size and generates a column and drops the object from the top, with the bottom of the object placed immediately above the level of the first occupied location (no matter how wide the occupation.) If the generated object does not fit at the random column, then no attempt is made to move the object to somewhere else that it does fit; the loop is restarted to generate a new location.

It would certainly be possible to generate a list of starting columns where there was a large enough gap for the current object, and then to use randi() to select one of them.. the code just does not do that.

[Branson]

I tried to write this but ran into so problems with the code. Could you help me try and work these out?

board=zeros(10000,10000);
hasAvailableSlot = @(board)~isempty(strfind(board(3,:),[0 0 0]));
%% Generate Random Numbers
s = 10000; %total number of available parking spots
n = s*5; %n = quantity of random numbers to generate
L = .1; %chance for large grain = L (0-L = Large grain, > L = small grain)
LG = 10; %large vehical size
SG = 3; %small vehical size
while hasAvailableSlot(board)
    numbers = rand(n,1); %n number of random numbers to be used for vehicle size
    column = round(s*rand(n,1)); %random starting spots for each vehicle between 1 and s spot limit
    
    width = numbers <= L;
    Y = SG*ones(1,n);
    Y(width) = LG;

    hasroom= ~any(board(width:end,column:column+width-1));
    if goes_at_row==0; continue;end
  
    goes_at_row:goes_at_row+width-1;
    column:column+width-1;
end


nLG = 0;
nSG = 0;
if is_LG(1i)
        nLG = nLG+1; %count number of large grains
    else
        nSG = nSG+1; %count number of small grains 
end

density = length(taken_spots)/s*100;

[Walter Roberson]

I reduced to 1000 in order to reduce the runtime for demonstration purposes

s = 1000; %total number of available parking spots
board = zeros(s,s);
hasAvailableSlot = @(board)~isempty(strfind(board(3,:),[0 0 0]));
%% Generate Random Numbers

Lp = .1; %chance for large grain = L (0-L = Large grain, > L = small grain)
Sp = 1-Lp;

LG = 10; %large vehical size
SG = 3; %small vehical size

Scopies = repmat(1, 1, floor(100*Sp));
Lcopies = repmat(2, 1, 100-numel(Scopies));
vsizes = [Scopies, Lcopies];
widths = [SG, LG];

graincounts = zeros(1,2);

while hasAvailableSlot(board)
    widthidx = vsizes(randi(numel(vsizes)));
    width = widths(widthidx);
    column = randi([1, s - width + 1]);
    hasroom = all(board(width:end,column:column+width-1) == 0, 2);
    goes_at_row = sum(cumprod(hasroom));
    if goes_at_row==0; continue; end
    board(goes_at_row:goes_at_row+width-1, column:column+width-1) = width;
    graincounts(widthidx) = graincounts(widthidx) + 1;
end
density = mean(board(:) ~= 0)

density = 0.4234

graincounts

graincounts = 1×2

21901 2263

sum(graincounts)

ans = 24164

%visualize
cmap = zeros(11,3);
cmap(4,:) = [1 1 1];
cmap(11,:) = [0 1 0];
img = reshape(cmap(board+1,:), s, s, 3);
image(img);

Notice the "fans" -- a block can have multiple other blocks perched on it, and each of those can have multiple blocks perched on them and because they are arranged not to collide, the blocks above tend to be further spaced apart than the bottom ones