Finding the minimum unfilled index in grid

Question

For sake of this question I will refer to all grid indices, vertexes, or others as points. So (1, 1) is a point on the grid, as an example.

I am looking to find the least largest total-sized index in a grid. In this case (1, 1) would total out to 2, (2, 1) would total out to be 3 and the same goes for (1, 2).

Expected Results:

{ X = 1, Y = 1 }
{ X = 2, Y = 1 }
{ X = 1, Y = 2 }
{ X = 2, Y = 2 }
{ X = 3, Y = 1 }
{ X = 3, Y = 2 }
{ X = 1, Y = 3 }
{ X = 2, Y = 3 }
{ X = 3, Y = 3 }

Actual Results:

{ X = 1, Y = 1 }
{ X = 2, Y = 1 }
{ X = 1, Y = 2 }
{ X = 2, Y = 2 }
{ X = 3, Y = 2 }
{ X = 2, Y = 3 }
{ X = 3, Y = 3 }
{ X = 4, Y = 3 }
{ X = 3, Y = 4 }

Code:

local chunks = {}
local previous = {
    X = 0,
    Y = 0
}

local largest = {
    X = 0,
    Y = 0
}

local function addScene()
    local new = {
        X = (previous.X > previous.Y and previous.Y) or previous.X + 1,
        Y = (previous.X > previous.Y and previous.X) or previous.Y
    }
    
    if new.X == 0 then
        new.X = 1
    end
    
    if new.Y == 0 then
        new.Y = 1
    end
    
    largest.X = math.max(largest.X, new.X)
    largest.Y = math.max(largest.Y, new.Y)
    
    previous.X = new.X
    previous.Y = new.Y
    
    table.insert(chunks, new)
    return new
end

for i = 1, 3*3, 1 do
    local scene = addScene()
    print(i, "(" .. tostring(scene.X) .. ", " .. tostring(scene.Y) .. ")" .. "\n")
end

Test For Yourself

This code, as shown above, gets pretty close to what I'd like it to do but only up to a point and this must be scalable across larger, and larger, grids.

Answer 1

Although, most likely, inefficient this does end up giving close to desired result. You could simply reorganize the table to get it exactly like I showed in the question anyways.

local MAX_SIZE = {
    X = 3,
    Y = 3
}

local chunks = {}
local previous = {
    X = 0,
    Y = 0
}

local function addScene()
    local least = MAX_SIZE.X + MAX_SIZE.Y
    local new = {
        X = 0,
        Y = 0
    }
    
    for x = MAX_SIZE.X, 1, -1 do
        for y = MAX_SIZE.Y, 1, -1 do
            if chunks[tostring(x) .. '-' .. tostring(y)] then
                break
            end
            
            if x ~= 0 and y ~= 0 and x + y <= least then
                least = x + y
                new.X = x
                new.Y = y
            end
        end
    end
    
    if new.X == 0 then
        new.X = 1
    end
    
    if new.Y == 0 then
        new.Y = 1
    end
    
    previous.X = new.X
    previous.Y = new.Y
    chunks[tostring(new.X) .. '-' .. tostring(new.Y)] = new
    return new
end

for i = 1, 3*3, 1 do
    local scene = addScene()
    print(i, "(" .. tostring(scene.X) .. ", " .. tostring(scene.Y) .. ")" .. "\n")
end

Try it out

Results:

1 (1, 1)
2 (1, 2)
3 (2, 1)
4 (1, 3)
5 (2, 2)
6 (3, 1)
7 (2, 3)
8 (3, 2)
9 (3, 3)