voxel

-- Hybrid Optimal Mining Algorithm for ComputerCraft
-- Combines minimal rotations with optimal layer transitions
-- Dynamically selects the best pattern based on room dimensions

-- Define the directions (ComputerCraft orientation)
local DIRECTIONS = {
    NORTH = 0,  -- -Z (toward starting edge)
    EAST = 1,   -- +X
    SOUTH = 2,  -- +Z (deeper into the room)
    WEST = 3    -- -X
}

-- Direction names for debugging
local DIRECTION_NAMES = {
    [0] = "NORTH",
    [1] = "EAST",
    [2] = "SOUTH",
    [3] = "WEST"
}

-- Define the costs
local MOVEMENT_COST = 1
local ROTATION_COST = 8

-- Initialize tracking variables
local currentDir = DIRECTIONS.SOUTH  -- Default turtle starts facing into the room (SOUTH)
local totalCost = 0
local movements = 0
local rotations = 0
local blocksDigged = 0

-- Function to calculate the relative rotation to reach the target direction
local function getRotation(currentDir, targetDir)
    local diff = (targetDir - currentDir) % 4
    if diff == 0 then
        return 0  -- No rotation needed
    elseif diff == 1 then
        return 1  -- Turn right once
    elseif diff == 2 then
        return 2  -- Turn either way twice (we'll choose right twice)
    else -- diff == 3
        return -1 -- Turn left once (quicker than three rights)
    end
end

-- Function to rotate the turtle to face a specific direction
local function rotateTo(targetDir, simulate)
    if currentDir == targetDir then
        return true  -- Already facing the correct direction
    end

    local rotation = getRotation(currentDir, targetDir)

    if not simulate then
        if rotation == 1 then
            -- Turn right once
            if not turtle.turnRight() then
                print("Failed to turn right")
                return false
            end
        elseif rotation == 2 then
            -- Turn right twice
            if not turtle.turnRight() then
                print("Failed to turn right (1/2)")
                return false
            end
            if not turtle.turnRight() then
                print("Failed to turn right (2/2)")
                return false
            end
        elseif rotation == -1 then
            -- Turn left once
            if not turtle.turnLeft() then
                print("Failed to turn left")
                return false
            end
        end
    end

    -- Update tracking variables
    rotations = rotations + math.abs(rotation)
    totalCost = totalCost + ROTATION_COST * math.abs(rotation)

    -- Update current direction
    currentDir = targetDir
    return true
end

-- Function to dig and move in the current direction
local function digAndMoveForward(simulate)
    if not simulate then
        -- Always try to dig first
        if turtle.detect() then
            if not turtle.dig() then
                print("Failed to dig block in front")
                return false
            end
            blocksDigged = blocksDigged + 1
        end

        -- Then try to move
        if not turtle.forward() then
            print("Failed to move forward even after digging")
            return false
        end
    end

    -- Update tracking variables
    movements = movements + 1
    totalCost = totalCost + MOVEMENT_COST
    return true
end

-- Function to dig and move up
local function digAndMoveUp(simulate)
    if not simulate then
        -- Always try to dig first
        if turtle.detectUp() then
            if not turtle.digUp() then
                print("Failed to dig block above")
                return false
            end
            blocksDigged = blocksDigged + 1
        end

        -- Then try to move
        if not turtle.up() then
            print("Failed to move up even after digging")
            return false
        end
    end

    -- Update tracking variables
    movements = movements + 1
    totalCost = totalCost + MOVEMENT_COST
    return true
end

-- Function to dig and move down
local function digAndMoveDown(simulate)
    if not simulate then
        -- Always try to dig first
        if turtle.detectDown() then
            if not turtle.digDown() then
                print("Failed to dig block below")
                return false
            end
            blocksDigged = blocksDigged + 1
        end

        -- Then try to move
        if not turtle.down() then
            print("Failed to move down even after digging")
            return false
        end
    end

    -- Update tracking variables
    movements = movements + 1
    totalCost = totalCost + MOVEMENT_COST
    return true
end

-- Function to deposit items in chest
local function depositItems(simulate)
    if simulate then
        return true
    end

    print("Depositing items in chest...")

    -- Turn around to face the chest (which is behind the starting position)
    rotateTo(DIRECTIONS.NORTH, simulate)

    -- Move out of the room to the chest
    if not turtle.forward() then
        print("Failed to move to chest")
        -- Just continue, we'll try to deposit next time
        rotateTo(DIRECTIONS.SOUTH, simulate)  -- Turn back to face into the room
        return false
    end

    -- Deposit all items except fuel in slot 1
    for i = 2, 16 do
        if turtle.getItemCount(i) > 0 then
            turtle.select(i)
            turtle.drop()
        end
    end
    turtle.select(1)  -- Return to slot 1

    -- Return to the room
    rotateTo(DIRECTIONS.SOUTH, simulate)
    if not turtle.forward() then
        print("Failed to return to room!")
        return false
    end

    return true
end

-- Check if inventory is getting full
local function isInventoryNearlyfull()
    local emptySlots = 0
    for i = 1, 16 do
        if turtle.getItemCount(i) == 0 then
            emptySlots = emptySlots + 1
        end
    end
    return (16 - emptySlots) >= 14  -- If only 2 or fewer slots are empty
end

-- Function to determine the best pattern for a given room size
local function getBestPattern(width, depth)
    -- Special cases for tiny rooms
    if width == 1 or depth == 1 then
        return "line"
    elseif width <= 2 and depth <= 2 then
        return "tiny"
    elseif width <= 3 and depth <= 3 then
        return "small_spiral"
    end

    -- Check if width and depth are odd or even
    local isWidthOdd = width % 2 == 1
    local isDepthOdd = depth % 2 == 1

    -- For larger rooms, always use serpentine patterns
    -- as they're more predictable and efficient
    if isWidthOdd and isDepthOdd then
        return "serpentine_odd_odd"
    elseif not isWidthOdd and not isDepthOdd then
        return "serpentine_even_even"
    else
        return "serpentine_mixed"
    end
end

-- Generate a path that minimizes rotations but ends near the start
function generateOptimizedPath(width, depth, reverse)
    local pattern = getBestPattern(width, depth)
    local path = {}
    reverse = reverse or false

    print("Using pattern: " .. pattern .. (reverse and " (reversed)" or ""))

    -- LINE pattern (1xN or Nx1 room)
    if pattern == "line" then
        if width == 1 then
            -- Single column
            if not reverse then
                -- Forward: top to bottom
                for z = 1, depth do
                    table.insert(path, {x = 1, z = z, dir = DIRECTIONS.SOUTH})
                end
            else
                -- Reverse: bottom to top
                for z = depth, 1, -1 do
                    table.insert(path, {x = 1, z = z, dir = DIRECTIONS.NORTH})
                end
            end
        else
            -- Single row
            if not reverse then
                -- Forward: left to right
                for x = 1, width do
                    table.insert(path, {x = x, z = 1, dir = DIRECTIONS.EAST})
                end
            else
                -- Reverse: right to left
                for x = width, 1, -1 do
                    table.insert(path, {x = x, z = 1, dir = DIRECTIONS.WEST})
                end
            end
        end
        return path
    end

    -- TINY pattern (2x2 or smaller)
    if pattern == "tiny" then
        if not reverse then
            -- Forward: clockwise loop
            return {
                {x = 1, z = 1, dir = DIRECTIONS.EAST},
                {x = 2, z = 1, dir = DIRECTIONS.SOUTH},
                {x = 2, z = 2, dir = DIRECTIONS.WEST},
                {x = 1, z = 2, dir = DIRECTIONS.NORTH}
            }
        else
            -- Reverse: counter-clockwise loop
            return {
                {x = 1, z = 2, dir = DIRECTIONS.EAST},
                {x = 2, z = 2, dir = DIRECTIONS.NORTH},
                {x = 2, z = 1, dir = DIRECTIONS.WEST},
                {x = 1, z = 1, dir = DIRECTIONS.SOUTH}
            }
        end
    end

    -- SMALL SPIRAL pattern (3x3 or smaller)
    if pattern == "small_spiral" then
        if not reverse then
            -- Build clockwise spiral path
            local spiral = {}

            -- First row
            for x = 1, width do
                table.insert(spiral, {x = x, z = 1, dir = DIRECTIONS.EAST})
            end

            -- Right edge down
            for z = 2, depth do
                table.insert(spiral, {x = width, z = z, dir = DIRECTIONS.SOUTH})
            end

            -- Bottom row backwards
            for x = width-1, 1, -1 do
                table.insert(spiral, {x = x, z = depth, dir = DIRECTIONS.WEST})
            end

            -- Left edge up (if room is at least 3 deep)
            if depth >= 3 then
                for z = depth-1, 2, -1 do
                    table.insert(spiral, {x = 1, z = z, dir = DIRECTIONS.NORTH})
                end
            end

            -- Fill in the center if needed (for 3x3 or larger)
            if width >= 3 and depth >= 3 then
                table.insert(spiral, {x = 2, z = 2, dir = DIRECTIONS.EAST})
                if width >= 4 then
                    for x = 3, width-1 do
                        table.insert(spiral, {x = x, z = 2, dir = DIRECTIONS.EAST})
                    end

                    if depth >= 4 then
                        -- Continue filling in larger rooms
                        -- (Pattern continues but rarely needed for ComputerCraft mining)
                    end
                end
            end

            return spiral
        else
            -- Reverse spiral (counter-clockwise)
            local spiral = {}

            -- First column down
            for z = 1, depth do
                table.insert(spiral, {x = 1, z = z, dir = DIRECTIONS.SOUTH})
            end

            -- Bottom row right
            for x = 2, width do
                table.insert(spiral, {x = x, z = depth, dir = DIRECTIONS.EAST})
            end

            -- Right edge up
            for z = depth-1, 1, -1 do
                table.insert(spiral, {x = width, z = z, dir = DIRECTIONS.NORTH})
            end

            -- Top row backwards (if room is at least 3 wide)
            if width >= 3 then
                for x = width-1, 2, -1 do
                    table.insert(spiral, {x = x, z = 1, dir = DIRECTIONS.WEST})
                end
            end

            -- Fill in the center if needed
            if width >= 3 and depth >= 3 then
                table.insert(spiral, {x = 2, z = 2, dir = DIRECTIONS.SOUTH})
                if depth >= 4 then
                    for z = 3, depth-1 do
                        table.insert(spiral, {x = 2, z = z, dir = DIRECTIONS.SOUTH})
                    end

                    if width >= 4 then
                        -- Continue filling in larger rooms as needed
                    end
                end
            end

            return spiral
        end
    end

    -- SERPENTINE patterns for all room types
    if pattern == "serpentine_odd_odd" or pattern == "serpentine_even_even" or pattern == "serpentine_mixed" then
        local serpentine = {}

        if not reverse then
            -- Forward pattern

            -- For odd×odd rooms, we need to handle the last column differently
            -- to ensure we end up near the starting position
            local normalColCount = width
            if pattern == "serpentine_odd_odd" then
                normalColCount = width - 1  -- We'll handle the last column separately
            end

            -- Process the main part of the room using standard serpentine pattern
            for x = 1, normalColCount do
                if x % 2 == 1 then
                    -- Odd columns go south
                    for z = 1, depth do
                        -- When at the end of an odd column, we need to decide if we turn east or go up
                        if z == depth and x < normalColCount then
                            -- Turn east at the end of the column (if not the last column)
                            table.insert(serpentine, {x = x, z = z, dir = DIRECTIONS.EAST})
                        else
                            -- Otherwise, continue south
                            table.insert(serpentine, {x = x, z = z, dir = DIRECTIONS.SOUTH})
                        end
                    end
                else
                    -- Even columns go north
                    for z = depth, 1, -1 do
                        -- At the end of an even column, turn east if not the last column
                        if z == 1 and x < normalColCount then
                            table.insert(serpentine, {x = x, z = z, dir = DIRECTIONS.EAST})
                        else
                            table.insert(serpentine, {x = x, z = z, dir = DIRECTIONS.NORTH})
                        end
                    end
                end
            end

            -- For odd×odd rooms, handle the last column to end near start
            if pattern == "serpentine_odd_odd" and width % 2 == 1 and normalColCount < width then
                local lastCol = width
                -- We're now at the top of the second-to-last column
                -- Turn east to enter the last column
                table.insert(serpentine, {x = normalColCount, z = 1, dir = DIRECTIONS.EAST})

                -- Now we're at the top of the last column, and need to go down
                for z = 1, depth do
                    -- Use SOUTH direction for all positions in this column
                    table.insert(serpentine, {x = lastCol, z = z, dir = DIRECTIONS.SOUTH})
                end
            end
        else
            -- Reverse pattern

            -- For odd×odd rooms in reverse, we start from the bottom of the last column
            local startingCol = 1
            if pattern == "serpentine_odd_odd" and width % 2 == 1 then
                startingCol = width  -- Start at the last column

                -- Process the last column from bottom to top
                for z = depth, 1, -1 do
                    table.insert(serpentine, {x = startingCol, z = z, dir = DIRECTIONS.NORTH})
                end

                -- Move west to second-to-last column
                table.insert(serpentine, {x = startingCol, z = 1, dir = DIRECTIONS.WEST})

                -- Continue with the rest of the serpentine pattern
                startingCol = width - 1
            end

            -- Process the main part of the room
            for x = startingCol, 1, -1 do
                if (width - x) % 2 == 0 then
                    -- Process in the south direction
                    for z = 1, depth do
                        if z == depth and x > 1 then
                            -- Turn west at the end of the column
                            table.insert(serpentine, {x = x, z = z, dir = DIRECTIONS.WEST})
                        else
                            table.insert(serpentine, {x = x, z = z, dir = DIRECTIONS.SOUTH})
                        end
                    end
                else
                    -- Process in the north direction
                    for z = depth, 1, -1 do
                        if z == 1 and x > 1 then
                            -- Turn west at the end of the column
                            table.insert(serpentine, {x = x, z = z, dir = DIRECTIONS.WEST})
                        else
                            table.insert(serpentine, {x = x, z = z, dir = DIRECTIONS.NORTH})
                        end
                    end
                end
            end
        end

        return serpentine
    end

    -- OPTIMIZED ZIGZAG pattern (even×even rooms)
    if pattern == "optimized_zigzag" then
        local zigzag = {}

        if not reverse then
            -- Forward pattern: start at top-left, end at bottom-left
            -- This minimizes rotations while ensuring we end near the start

            -- Process each row
            for z = 1, depth do
                if z % 2 == 1 then
                    -- Odd rows go east
                    for x = 1, width do
                        if x == width and z < depth then
                            -- Last position in row (except for last row)
                            table.insert(zigzag, {x = x, z = z, dir = DIRECTIONS.SOUTH})
                        else
                            table.insert(zigzag, {x = x, z = z, dir = DIRECTIONS.EAST})
                        end
                    end
                else
                    -- Even rows go west
                    for x = width, 1, -1 do
                        if x == 1 and z < depth then
                            -- Last position in row (except for last row)
                            table.insert(zigzag, {x = x, z = z, dir = DIRECTIONS.SOUTH})
                        else
                            table.insert(zigzag, {x = x, z = z, dir = DIRECTIONS.WEST})
                        end
                    end
                end
            end
        else
            -- Reverse pattern: start at bottom-left, end at top-left

            for z = depth, 1, -1 do
                if z % 2 == 0 then
                    -- Even rows (from bottom) go east
                    for x = 1, width do
                        if x == width and z > 1 then
                            -- Last position in row (except for first/top row)
                            table.insert(zigzag, {x = x, z = z, dir = DIRECTIONS.NORTH})
                        else
                            table.insert(zigzag, {x = x, z = z, dir = DIRECTIONS.EAST})
                        end
                    end
                else
                    -- Odd rows (from bottom) go west
                    for x = width, 1, -1 do
                        if x == 1 and z > 1 then
                            -- Last position in row (except for first/top row)
                            table.insert(zigzag, {x = x, z = z, dir = DIRECTIONS.NORTH})
                        else
                            table.insert(zigzag, {x = x, z = z, dir = DIRECTIONS.WEST})
                        end
                    end
                end
            end
        end

        return zigzag
    end

    -- OPTIMIZED STRIPES pattern (for odd×even or even×odd rooms)
    if pattern == "optimized_stripes" then
        local stripes = {}

        -- Choose horizontal or vertical stripes based on which minimizes rotations
        local horizontal = width >= depth

        if horizontal then
            -- Horizontal stripes (minimize rotations by doing longer runs)
            if not reverse then
                -- Forward pattern
                for z = 1, depth do
                    if z % 2 == 1 then
                        -- Odd rows go east
                        for x = 1, width do
                            if x == width and z < depth then
                                -- Turn at the end of row
                                table.insert(stripes, {x = x, z = z, dir = DIRECTIONS.SOUTH})
                            else
                                table.insert(stripes, {x = x, z = z, dir = DIRECTIONS.EAST})
                            end
                        end
                    else
                        -- Even rows go west
                        for x = width, 1, -1 do
                            if x == 1 and z < depth then
                                -- Turn at the end of row
                                table.insert(stripes, {x = x, z = z, dir = DIRECTIONS.SOUTH})
                            else
                                table.insert(stripes, {x = x, z = z, dir = DIRECTIONS.WEST})
                            end
                        end
                    end
                end
            else
                -- Reverse pattern
                for z = depth, 1, -1 do
                    if (depth - z + 1) % 2 == 1 then
                        -- Odd rows from bottom go east
                        for x = 1, width do
                            if x == width and z > 1 then
                                -- Turn at the end of row
                                table.insert(stripes, {x = x, z = z, dir = DIRECTIONS.NORTH})
                            else
                                table.insert(stripes, {x = x, z = z, dir = DIRECTIONS.EAST})
                            end
                        end
                    else
                        -- Even rows from bottom go west
                        for x = width, 1, -1 do
                            if x == 1 and z > 1 then
                                -- Turn at the end of row
                                table.insert(stripes, {x = x, z = z, dir = DIRECTIONS.NORTH})
                            else
                                table.insert(stripes, {x = x, z = z, dir = DIRECTIONS.WEST})
                            end
                        end
                    end
                end
            end
        else
            -- Vertical stripes
            if not reverse then
                -- Forward pattern
                for x = 1, width do
                    if x % 2 == 1 then
                        -- Odd columns go south
                        for z = 1, depth do
                            if z == depth and x < width then
                                -- Turn at the end of column
                                table.insert(stripes, {x = x, z = z, dir = DIRECTIONS.EAST})
                            else
                                table.insert(stripes, {x = x, z = z, dir = DIRECTIONS.SOUTH})
                            end
                        end
                    else
                        -- Even columns go north
                        for z = depth, 1, -1 do
                            if z == 1 and x < width then
                                -- Turn at the end of column
                                table.insert(stripes, {x = x, z = z, dir = DIRECTIONS.EAST})
                            else
                                table.insert(stripes, {x = x, z = z, dir = DIRECTIONS.NORTH})
                            end
                        end
                    end
                end
            else
                -- Reverse pattern
                for x = width, 1, -1 do
                    if (width - x + 1) % 2 == 1 then
                        -- Odd columns from right go south
                        for z = 1, depth do
                            if z == depth and x > 1 then
                                -- Turn at the end of column
                                table.insert(stripes, {x = x, z = z, dir = DIRECTIONS.WEST})
                            else
                                table.insert(stripes, {x = x, z = z, dir = DIRECTIONS.SOUTH})
                            end
                        end
                    else
                        -- Even columns from right go north
                        for z = depth, 1, -1 do
                            if z == 1 and x > 1 then
                                -- Turn at the end of column
                                table.insert(stripes, {x = x, z = z, dir = DIRECTIONS.WEST})
                            else
                                table.insert(stripes, {x = x, z = z, dir = DIRECTIONS.NORTH})
                            end
                        end
                    end
                end
            end
        end

        return stripes
    end

    -- H_STRIPS_OPTIMIZED and V_STRIPS_OPTIMIZED patterns
    -- These are optimized versions of horizontal and vertical strips for larger rooms
    if pattern == "h_strips_optimized" or pattern == "v_strips_optimized" then
        local horizontal = (pattern == "h_strips_optimized")
        local strips = {}

        if horizontal then
            -- Horizontal strips with special handling to end near start
            if not reverse then
                -- Calculate if we need to do special handling for the last row
                local normalRows = depth
                local endsNearStart = true

                if depth % 2 == 0 then
                    -- For even depths, we're already good - ends at bottom left
                    endsNearStart = true
                else
                    -- For odd depths, we need to modify the last row pattern
                    -- to ensure we end near the start
                    normalRows = depth - 1
                    endsNearStart = false
                end

                -- Process normal rows with standard zigzag
                for z = 1, normalRows do
                    if z % 2 == 1 then
                        -- Odd rows go east
                        for x = 1, width do
                            if x == width and z < normalRows then
                                -- Turn at the end of row
                                table.insert(strips, {x = x, z = z, dir = DIRECTIONS.SOUTH})
                            else
                                table.insert(strips, {x = x, z = z, dir = DIRECTIONS.EAST})
                            end
                        end
                    else
                        -- Even rows go west
                        for x = width, 1, -1 do
                            if x == 1 and z < normalRows then
                                -- Turn at the end of row
                                table.insert(strips, {x = x, z = z, dir = DIRECTIONS.SOUTH})
                            else
                                table.insert(strips, {x = x, z = z, dir = DIRECTIONS.WEST})
                            end
                        end
                    end
                end

                -- Handle the special last row for odd depths
                if not endsNearStart then
                    -- Last row needs to end near start (left side)
                    -- For odd depths, the last row starts at top right
                    local lastZ = depth

                    -- Two options:
                    -- 1. Zigzag from right to left (if width > 4)
                    -- 2. Straight line from right to left (if width <= 4)

                    if width > 4 then
                        -- Zigzag approach - minimizes rotation cost
                        -- This creates a zigzag within the last row to end at the left
                        -- Exact pattern will depend on width

                        -- This is a simplified version - a real implementation would
                        -- optimize this path further

                        -- Process the last row in segments
                        local segments = math.ceil(width / 3)
                        for seg = 1, segments do
                            local startX = width - ((seg-1) * 3)
                            local endX = math.max(1, startX - 2)

                            -- Go left within this segment
                            for x = startX, endX, -1 do
                                if x == endX and endX > 1 then
                                    -- At the end of segment, turn south briefly
                                    table.insert(strips, {x = x, z = lastZ, dir = DIRECTIONS.SOUTH})
                                    -- Then back north
                                    table.insert(strips, {x = x, z = lastZ + 1, dir = DIRECTIONS.NORTH})
                                    -- Then continue west
                                    table.insert(strips, {x = x, z = lastZ, dir = DIRECTIONS.WEST})
                                else
                                    table.insert(strips, {x = x, z = lastZ, dir = DIRECTIONS.WEST})
                                end
                            end
                        end
                    else
                        -- For narrow rooms, just go straight from right to left
                        for x = width, 1, -1 do
                            table.insert(strips, {x = x, z = lastZ, dir = DIRECTIONS.WEST})
                        end
                    end
                end
            else
                -- Reverse pattern
                -- Similar logic but reversed direction

                -- Calculate if we need to do special handling for the first row
                local normalRows = depth
                local startsNearEnd = true

                if depth % 2 == 0 then
                    -- For even depths, we start at bottom left
                    startsNearEnd = true
                else
                    -- For odd depths, we need a special first row
                    normalRows = depth - 1
                    startsNearEnd = false
                end

                -- Handle the special first row for odd depths
                if not startsNearEnd then
                    -- First row (from reverse perspective) needs to start near the end of normal pattern
                    local firstZ = depth

                    -- Similar options as in forward pattern
                    if width > 4 then
                        -- Reverse of the zigzag approach
                        local segments = math.ceil(width / 3)
                        for seg = segments, 1, -1 do
                            local startX = width - ((seg-1) * 3)
                            local endX = math.max(1, startX - 2)

                            -- Go right within this segment (reversed from forward)
                            for x = endX, startX do
                                if x == endX and endX > 1 and seg > 1 then
                                    -- Reverse of the special turns
                                    table.insert(strips, {x = x, z = firstZ, dir = DIRECTIONS.EAST})
                                    -- Then down and up
                                    table.insert(strips, {x = x, z = firstZ + 1, dir = DIRECTIONS.SOUTH})
                                    table.insert(strips, {x = x, z = firstZ, dir = DIRECTIONS.NORTH})
                                else
                                    table.insert(strips, {x = x, z = firstZ, dir = DIRECTIONS.EAST})
                                end
                            end
                        end
                    else
                        -- For narrow rooms, just go straight from left to right
                        for x = 1, width do
                            table.insert(strips, {x = x, z = firstZ, dir = DIRECTIONS.EAST})
                        end
                    end
                end

                -- Process normal rows with standard zigzag (reversed)
                for z = normalRows, 1, -1 do
                    if z % 2 == 0 then
                        -- Even rows go east (reversed from forward pattern)
                        for x = 1, width do
                            if x == width and z > 1 then
                                -- Turn at the end of row
                                table.insert(strips, {x = x, z = z, dir = DIRECTIONS.NORTH})
                            else
                                table.insert(strips, {x = x, z = z, dir = DIRECTIONS.EAST})
                            end
                        end
                    else
                        -- Odd rows go west (reversed from forward pattern)
                        for x = width, 1, -1 do
                            if x == 1 and z > 1 then
                                -- Turn at the end of row
                                table.insert(strips, {x = x, z = z, dir = DIRECTIONS.NORTH})
                            else
                                table.insert(strips, {x = x, z = z, dir = DIRECTIONS.WEST})
                            end
                        end
                    end
                end
            end
        else
            -- Vertical strips with special handling to end near start
            -- Similar logic as horizontal strips but with x and z swapped
            if not reverse then
                -- Calculate if we need to do special handling for the last column
                local normalCols = width
                local endsNearStart = true

                if width % 2 == 0 then
                    -- For even widths, we're good - ends at bottom left
                    endsNearStart = true
                else
                    -- For odd widths, need to modify the last column
                    normalCols = width - 1
                    endsNearStart = false
                end

                -- Process normal columns with standard zigzag
                for x = 1, normalCols do
                    if x % 2 == 1 then
                        -- Odd columns go south
                        for z = 1, depth do
                            if z == depth and x < normalCols then
                                -- Turn at the end of column
                                table.insert(strips, {x = x, z = z, dir = DIRECTIONS.EAST})
                            else
                                table.insert(strips, {x = x, z = z, dir = DIRECTIONS.SOUTH})
                            end
                        end
                    else
                        -- Even columns go north
                        for z = depth, 1, -1 do
                            if z == 1 and x < normalCols then
                                -- Turn at the end of column
                                table.insert(strips, {x = x, z = z, dir = DIRECTIONS.EAST})
                            else
                                table.insert(strips, {x = x, z = z, dir = DIRECTIONS.NORTH})
                            end
                        end
                    end
                end

                -- Handle the special last column for odd widths
                if not endsNearStart then
                    -- Last column needs to end near start (top position)
                    local lastX = width

                    -- For odd widths, the last column starts at bottom
                    if depth > 4 then
                        -- Zigzag approach for tall rooms
                        local segments = math.ceil(depth / 3)
                        for seg = 1, segments do
                            local startZ = depth - ((seg-1) * 3)
                            local endZ = math.max(1, startZ - 2)

                            -- Go up within this segment
                            for z = startZ, endZ, -1 do
                                if z == endZ and endZ > 1 then
                                    -- At the end of segment, turn east briefly
                                    table.insert(strips, {x = lastX, z = z, dir = DIRECTIONS.EAST})
                                    -- Then back west
                                    table.insert(strips, {x = lastX + 1, z = z, dir = DIRECTIONS.WEST})
                                    -- Then continue north
                                    table.insert(strips, {x = lastX, z = z, dir = DIRECTIONS.NORTH})
                                else
                                    table.insert(strips, {x = lastX, z = z, dir = DIRECTIONS.NORTH})
                                end
                            end
                        end
                    else
                        -- For short rooms, just go straight from bottom to top
                        for z = depth, 1, -1 do
                            table.insert(strips, {x = lastX, z = z, dir = DIRECTIONS.NORTH})
                        end
                    end
                end
            else
                -- Reverse pattern
                -- Similar logic but reversed direction

                -- Calculate if we need to do special handling for the first column
                local normalCols = width
                local startsNearEnd = true

                if width % 2 == 0 then
                    -- For even widths, we start at top right
                    startsNearEnd = true
                else
                    -- For odd widths, we need a special first column
                    normalCols = width - 1
                    startsNearEnd = false
                end

                -- Handle the special first column for odd widths
                if not startsNearEnd then
                    -- First column (from reverse perspective) needs to start near the end
                    local firstX = width

                    -- Similar options as in forward pattern
                    if depth > 4 then
                        -- Reverse of the zigzag approach
                        local segments = math.ceil(depth / 3)
                        for seg = segments, 1, -1 do
                            local startZ = depth - ((seg-1) * 3)
                            local endZ = math.max(1, startZ - 2)

                            -- Go down within this segment (reversed from forward)
                            for z = endZ, startZ do
                                if z == endZ and endZ > 1 and seg > 1 then
                                    -- Reverse of the special turns
                                    table.insert(strips, {x = firstX, z = z, dir = DIRECTIONS.SOUTH})
                                    -- Then east and west
                                    table.insert(strips, {x = firstX + 1, z = z, dir = DIRECTIONS.EAST})
                                    table.insert(strips, {x = firstX, z = z, dir = DIRECTIONS.WEST})
                                else
                                    table.insert(strips, {x = firstX, z = z, dir = DIRECTIONS.SOUTH})
                                end
                            end
                        end
                    else
                        -- For short rooms, just go straight from top to bottom
                        for z = 1, depth do
                            table.insert(strips, {x = firstX, z = z, dir = DIRECTIONS.SOUTH})
                        end
                    end
                end

                -- Process normal columns with standard zigzag (reversed)
                for x = normalCols, 1, -1 do
                    if x % 2 == 0 then
                        -- Even columns go south (reversed from forward pattern)
                        for z = 1, depth do
                            if z == depth and x > 1 then
                                -- Turn at the end of column
                                table.insert(strips, {x = x, z = z, dir = DIRECTIONS.WEST})
                            else
                                table.insert(strips, {x = x, z = z, dir = DIRECTIONS.SOUTH})
                            end
                        end
                    else
                        -- Odd columns go north (reversed from forward pattern)
                        for z = depth, 1, -1 do
                            if z == 1 and x > 1 then
                                -- Turn at the end of column
                                table.insert(strips, {x = x, z = z, dir = DIRECTIONS.WEST})
                            else
                                table.insert(strips, {x = x, z = z, dir = DIRECTIONS.NORTH})
                            end
                        end
                    end
                end
            end
        end

        return strips
    end

    -- Fallback to simple horizontal stripes pattern
    local fallback = {}

    for z = 1, depth do
        if z % 2 == 1 then
            -- Odd rows go east
            for x = 1, width do
                if x == width and z < depth then
                    table.insert(fallback, {x = x, z = z, dir = DIRECTIONS.SOUTH})
                else
                    table.insert(fallback, {x = x, z = z, dir = DIRECTIONS.EAST})
                end
            end
        else
            -- Even rows go west
            for x = width, 1, -1 do
                if x == 1 and z < depth then
                    table.insert(fallback, {x = x, z = z, dir = DIRECTIONS.SOUTH})
                else
                    table.insert(fallback, {x = x, z = z, dir = DIRECTIONS.WEST})
                end
            end
        end
    end

    return fallback
end

-- Function to excavate a room with optimal pathing
function excavateRoom(width, height, depth, simulate)
    simulate = simulate or false  -- Default to actual mining, not simulation

    -- Validate dimensions
    if width < 1 or width > 200 or height < 1 or height > 200 or depth < 1 or depth > 200 then
        error("Dimensions must be between 1 and 200")
    end

    -- Reset counters for a new excavation
    totalCost = 0
    movements = 0
    rotations = 0
    blocksDigged = 0

    -- Print starting information
    print("Starting excavation of " .. width .. "x" .. height .. "x" .. depth .. " room")
    print("Mode: " .. (simulate and "Simulation" or "Actual mining"))
    print("Starting position: 1,1,1 (front-left corner of the room)")

    -- Calculate total blocks to mine
    local totalBlocks = width * height * depth
    local minedBlocks = 0

    -- Select appropriate pattern and indicate to user
    local patternName = getBestPattern(width, depth)
    print("Using optimal pattern: " .. patternName)

    -- Execute the excavation layer by layer
    for y = 1, height do
        print("--- Mining layer " .. y .. " of " .. height .. " ---")

        -- Determine if we should use forward or reverse pattern for this layer
        local useReverse = (y % 2 == 0)  -- Even layers use reverse pattern

        -- Get the optimized path for this layer
        local layerPath = generateOptimizedPath(width, depth, useReverse)

        -- Current position starts at appropriate corner based on pattern
        local currentPos
        if not useReverse then
            -- Forward pattern starts at front-left
            currentPos = {x = 1, y = y, z = 1}
        else
            -- Reverse pattern starts at the end of the forward pattern
            local lastPos = layerPath[1]
            currentPos = {x = lastPos.x, y = y, z = lastPos.z}
        end

        -- First block is already visited
        minedBlocks = minedBlocks + 1

        -- For each position in the path (skipping the first as we're already there)
        for i = 2, #layerPath do
            local targetPos = layerPath[i]
            local targetDir = targetPos.dir

            -- First rotate if needed
            if currentDir ~= targetDir then
                rotateTo(targetDir, simulate)
            end

            -- Then move forward
            if not digAndMoveForward(simulate) then
                print("Failed to move to next position")
                return false
            end

            -- Update current position
            if targetDir == DIRECTIONS.NORTH then
                currentPos.z = currentPos.z - 1
            elseif targetDir == DIRECTIONS.EAST then
                currentPos.x = currentPos.x + 1
            elseif targetDir == DIRECTIONS.SOUTH then
                currentPos.z = currentPos.z + 1
            elseif targetDir == DIRECTIONS.WEST then
                currentPos.x = currentPos.x - 1
            end

            -- Update progress
            minedBlocks = minedBlocks + 1
            if minedBlocks % 10 == 0 or minedBlocks == totalBlocks then
                print("Mined " .. minedBlocks .. "/" .. totalBlocks .. " blocks")
            end

            -- Check if inventory is getting full
            if not simulate and isInventoryNearlyfull() then
                depositItems(simulate)
            end
        end

        -- After completing a layer, move up if not at the top
        if y < height then
            if not digAndMoveUp(simulate) then
                print("Failed to move to next layer")
                return false
            end

            -- Reset current direction based on the next layer's pattern
            local nextLayerReverse = ((y+1) % 2 == 0)
            local nextLayerPath = generateOptimizedPath(width, depth, nextLayerReverse)
            local nextStartDir = nextLayerPath[1].dir

            -- Rotate to the starting direction for the next layer
            rotateTo(nextStartDir, simulate)
        end
    end

    -- Return to the starting position (1,1,1) and deposit items
    print("Mining complete! Returning to starting position...")

    -- First get back to the bottom layer
    while currentPos.y > 1 do
        if not digAndMoveDown(simulate) then
            print("Failed to return to bottom layer")
            return false
        end
        currentPos.y = currentPos.y - 1
    end

    -- Then navigate back to the starting position
    -- Use a direct path to minimize rotations

    -- Decide which direction to move first (x or z) based on which requires fewer rotations
    local xDiff = currentPos.x - 1
    local zDiff = currentPos.z - 1

    -- Calculate rotation costs for different approaches
    local costXFirst = 0
    local costZFirst = 0

    -- If moving in x direction first
    if xDiff > 0 then
        costXFirst = costXFirst + getRotationCost(currentDir, DIRECTIONS.WEST)
        -- After moving in x, calculate cost to turn for z
        costXFirst = costXFirst + getRotationCost(DIRECTIONS.WEST, (zDiff > 0) and DIRECTIONS.NORTH or DIRECTIONS.SOUTH)
    elseif xDiff < 0 then
        costXFirst = costXFirst + getRotationCost(currentDir, DIRECTIONS.EAST)
        -- After moving in x, calculate cost to turn for z
        costXFirst = costXFirst + getRotationCost(DIRECTIONS.EAST, (zDiff > 0) and DIRECTIONS.NORTH or DIRECTIONS.SOUTH)
    else
        -- No x movement needed
        costXFirst = costXFirst + getRotationCost(currentDir, (zDiff > 0) and DIRECTIONS.NORTH or DIRECTIONS.SOUTH)
    end

    -- If moving in z direction first
    if zDiff > 0 then
        costZFirst = costZFirst + getRotationCost(currentDir, DIRECTIONS.NORTH)
        -- After moving in z, calculate cost to turn for x
        costZFirst = costZFirst + getRotationCost(DIRECTIONS.NORTH, (xDiff > 0) and DIRECTIONS.WEST or DIRECTIONS.EAST)
    elseif zDiff < 0 then
        costZFirst = costZFirst + getRotationCost(currentDir, DIRECTIONS.SOUTH)
        -- After moving in z, calculate cost to turn for x
        costZFirst = costZFirst + getRotationCost(DIRECTIONS.SOUTH, (xDiff > 0) and DIRECTIONS.WEST or DIRECTIONS.EAST)
    else
        -- No z movement needed
        costZFirst = costZFirst + getRotationCost(currentDir, (xDiff > 0) and DIRECTIONS.WEST or DIRECTIONS.EAST)
    end

    -- Choose the path with lower rotation cost
    if costXFirst <= costZFirst then
        -- Move in x direction first
        if xDiff > 0 then
            rotateTo(DIRECTIONS.WEST, simulate)
            for i = 1, xDiff do
                if not digAndMoveForward(simulate) then
                    print("Failed to return to starting x position")
                    return false
                end
            end
        elseif xDiff < 0 then
            rotateTo(DIRECTIONS.EAST, simulate)
            for i = 1, -xDiff do
                if not digAndMoveForward(simulate) then
                    print("Failed to return to starting x position")
                    return false
                end
            end
        end

        -- Then move in z direction
        if zDiff > 0 then
            rotateTo(DIRECTIONS.NORTH, simulate)
            for i = 1, zDiff do
                if not digAndMoveForward(simulate) then
                    print("Failed to return to starting z position")
                    return false
                end
            end
        elseif zDiff < 0 then
            rotateTo(DIRECTIONS.SOUTH, simulate)
            for i = 1, -zDiff do
                if not digAndMoveForward(simulate) then
                    print("Failed to return to starting z position")
                    return false
                end
            end
        end
    else
        -- Move in z direction first
        if zDiff > 0 then
            rotateTo(DIRECTIONS.NORTH, simulate)
            for i = 1, zDiff do
                if not digAndMoveForward(simulate) then
                    print("Failed to return to starting z position")
                    return false
                end
            end
        elseif zDiff < 0 then
            rotateTo(DIRECTIONS.SOUTH, simulate)
            for i = 1, -zDiff do
                if not digAndMoveForward(simulate) then
                    print("Failed to return to starting z position")
                    return false
                end
            end
        end

        -- Then move in x direction
        if xDiff > 0 then
            rotateTo(DIRECTIONS.WEST, simulate)
            for i = 1, xDiff do
                if not digAndMoveForward(simulate) then
                    print("Failed to return to starting x position")
                    return false
                end
            end
        elseif xDiff < 0 then
            rotateTo(DIRECTIONS.EAST, simulate)
            for i = 1, -xDiff do
                if not digAndMoveForward(simulate) then
                    print("Failed to return to starting x position")
                    return false
                end
            end
        end
    end

    -- Deposit final items
    depositItems(simulate)

    -- Print stats
    print("\n--- Excavation Summary ---")
    print("Room dimensions: " .. width .. "x" .. height .. "x" .. depth)
    print("Total blocks mined: " .. minedBlocks .. "/" .. totalBlocks)
    print("Blocks dug: " .. blocksDigged)
    print("Movements: " .. movements)
    print("Rotations: " .. rotations)
    print("Total cost (with rotation = " .. ROTATION_COST .. "x movement): " .. totalCost)
    print("Average cost per block: " .. string.format("%.2f", totalCost / totalBlocks))

    return true
end

-- Calculate rotation cost between two directions
function getRotationCost(fromDir, toDir)
    local rot = getRotation(fromDir, toDir)
    return math.abs(rot) * ROTATION_COST
end

-- Function to check fuel level and refuel if necessary
function ensureFuel(requiredFuel)
    local currentFuel = turtle.getFuelLevel()

    if currentFuel == "unlimited" then
        print("Fuel level: Unlimited")
        return true
    end

    print("Current fuel level: " .. currentFuel)

    if requiredFuel and currentFuel < requiredFuel then
        print("Need more fuel! Attempting to refuel...")

        -- Try to refuel from inventory
        for slot = 1, 16 do
            turtle.select(slot)
            if turtle.refuel(0) then  -- Check if item is valid fuel
                local fuelNeeded = requiredFuel - currentFuel
                if turtle.refuel(fuelNeeded) then
                    local newLevel = turtle.getFuelLevel()
                    print("Refueled to level: " .. newLevel)
                    if newLevel >= requiredFuel then
                        return true
                    end
                end
            end
        end

        print("Warning: Unable to reach required fuel level of " .. requiredFuel)
        return false
    end

    return true
end

-- Calculate approximate fuel needed, accounting for rotation costs
function calculateFuelNeeded(width, height, depth)
    -- Estimate movements (one per block)
    local movements = width * height * depth

    -- Estimate rotations based on room dimensions and pattern
    local pattern = getBestPattern(width, depth)
    local rotationsPerLayer

    -- Estimate rotations per layer based on pattern
    if pattern == "line" then
        rotationsPerLayer = 0
    elseif pattern == "tiny" then
        rotationsPerLayer = 4
    elseif pattern == "small_spiral" then
        rotationsPerLayer = 4
    elseif pattern == "optimized_spiral" then
        rotationsPerLayer = 4
    elseif pattern == "optimized_zigzag" then
        rotationsPerLayer = math.min(depth - 1, 1) * 2
    elseif pattern == "optimized_stripes" then
        if width >= depth then
            -- Horizontal stripes
            rotationsPerLayer = math.min(depth - 1, 1) * 2
        else
            -- Vertical stripes
            rotationsPerLayer = math.min(width - 1, 1) * 2
        end
    elseif pattern == "h_strips_optimized" then
        rotationsPerLayer = depth - 1
    elseif pattern == "v_strips_optimized" then
        rotationsPerLayer = width - 1
    else
        -- Fallback estimate
        rotationsPerLayer = math.max(width, depth)
    end

    -- Total rotations including layer transitions
    local totalRotations = rotationsPerLayer * height + (height - 1) * 2

    -- Add fuel for inventory trips (deposit items when full)
    local inventoryTrips = math.ceil((width * height * depth) / 14) * 4  -- 4 moves per trip

    -- Calculate total cost
    local totalCost = (movements * MOVEMENT_COST) + (totalRotations * ROTATION_COST) + inventoryTrips

    -- Add 20% buffer
    return totalCost * 1.2
end

-- Main function to run the program
function main()
    print("ComputerCraft Hybrid Optimal Mining Algorithm")
    print("--------------------------------------------")
    print("This program uses advanced pathing to mine rooms efficiently.")
    print("It minimizes rotations and ensures optimal layer transitions.")
    print("")

    -- Get dimensions from user input
    print("Enter the dimensions of the room to excavate:")

    io.write("Width (X): ")
    local width = tonumber(io.read()) or 3

    io.write("Height (Y): ")
    local height = tonumber(io.read()) or 3

    io.write("Depth (Z): ")
    local depth = tonumber(io.read()) or 3

    io.write("Simulate only? (y/n): ")
    local simulateStr = io.read():lower()
    local simulate = (simulateStr == "y" or simulateStr == "yes")

    -- Ensure dimensions are valid
    if width < 1 or width > 200 or height < 1 or height > 200 or depth < 1 or depth > 200 then
        print("Error: Dimensions must be between 1 and 200")
        return
    end

    -- Calculate required fuel with rotation costs
    local requiredFuel = calculateFuelNeeded(width, height, depth)
    print("Estimated fuel required: " .. math.ceil(requiredFuel))

    -- Check fuel if not simulating
    if not simulate then
        if not ensureFuel(requiredFuel) then
            print("Warning: Proceeding with insufficient fuel. The turtle may stop before completing the excavation.")
        end
    end

    -- Execute the excavation
    local success = excavateRoom(width, height, depth, simulate)

    if success then
        print("Excavation completed successfully!")
    else
        print("Excavation failed or was interrupted.")
    end
end

-- Run the program
main()