-- Turtle Maze Program v2.0

-- GLOBAL VARIABLES

local maze =  {}
local visited = {}

local stackTrace = {}
local stackTraceCount = 0

local mazeSize = 50
local posX = 25
local posY = 0

local currentDirection = 1 -- {"N", "E", "S", "W"}


-- FUNCTIONS

function init()

    for x = 1, mazeSize do
        maze[x] = {}

        for y = 1, mazeSize do
            maze[x][y] = nil
        end
    end

    for x = 1, mazeSize do
        visited[x] = {}

        for y = 1, mazeSize do
            visited[x][y] = 0
        end
    end

end


function forward()

    if currentDirection == 1 then
        posY = posY + 1
    end
    if currentDirection == 2 then
        posX = posX + 1
    end
    if currentDirection == 3 then
        posY = posY - 1
    end
    if currentDirection == 4 then
        posX = posX - 1
    end

    turtle.forward()

    visited[posX][posY] = 1

    saveToStackTrace()
end


function win()

    local success, data = turtle.inspect()

    if success then
        if data.name == "minecraft:cobblestone" then
            return true
        end
    end

    return false
end


function mapPosition()

    if currentDirection == 1 then
        if maze[posX][posY + 1] == nil then -- front
            maze[posX][posY + 1] = (turtle.detect() and 1 or 0)
        end
        if maze[posX - 1][posY] == nil then -- left
            turtle.turnLeft()
            maze[posX - 1][posY] = (turtle.detect() and 1 or 0)
            turtle.turnRight()
        end
        if maze[posX + 1][posY] == nil then -- right
            turtle.turnRight()
            maze[posX + 1][posY] = (turtle.detect() and 1 or 0)
            turtle.turnLeft()
        end
        return
    end

    if currentDirection == 2 then
        if maze[posX + 1][posY] == nil then -- front
            maze[posX + 1][posY] = (turtle.detect() and 1 or 0)
        end
        if maze[posX][posY + 1] == nil then -- left
            turtle.turnLeft()
            maze[posX][posY + 1] = (turtle.detect() and 1 or 0)
            turtle.turnRight()
        end
        if maze[posX][posY - 1] == nil then -- right
            turtle.turnRight()
            maze[posX][posY - 1] = (turtle.detect() and 1 or 0)
            turtle.turnLeft()
        end
        return
    end

    if currentDirection == 3 then
        if maze[posX][posY - 1] == nil then -- front
            maze[posX][posY - 1] = (turtle.detect() and 1 or 0)
        end
        if maze[posX + 1][posY] == nil then -- left
            turtle.turnLeft()
            maze[posX + 1][posY] = (turtle.detect() and 1 or 0)
            turtle.turnRight()
        end
        if maze[posX - 1][posY] == nil then -- right
            turtle.turnRight()
            maze[posX - 1][posY] = (turtle.detect() and 1 or 0)
            turtle.turnLeft()
        end
        return
    end

    if currentDirection == 4 then
        if maze[posX - 1][posY] == nil then -- front
            maze[posX - 1][posY] = (turtle.detect() and 1 or 0)
        end
        if maze[posX][posY - 1] == nil then -- left
            turtle.turnLeft()
            maze[posX][posY - 1] = (turtle.detect() and 1 or 0)
            turtle.turnRight()
        end
        if maze[posX][posY + 1] == nil then -- right
            turtle.turnRight()
            maze[posX][posY + 1] = (turtle.detect() and 1 or 0)
            turtle.turnLeft()
        end
        return
    end
end


function chooseDirection()

    if not hasPossibleDirection() then
        return false
    end

    while true do

        local number = math.random(1,4)

        if currentDirection == 1 then
            if number == 1 then
                if canMove(posX, posY + 1) then
                    return true
                end
            end
            if number == 2 then
                if canMove(posX + 1, posY) then
                    turtle.turnRight()
                    currentDirection = 2
                    return true
                end
            end
            if number == 3 then
                if canMove(posX, posY - 1) then
                    turtle.turnRight()
                    turtle.turnRight()
                    currentDirection = 3
                    return true
                end
            end
            if number == 4 then
                if canMove(posX - 1, posY) then
                    turtle.turnLeft()
                    currentDirection = 4
                    return true
                end
            end
        end

        if currentDirection == 2 then
            if number == 1 then
                if canMove(posX + 1, posY) then
                    return true
                end
            end
            if number == 2 then
                if canMove(posX, posY - 1) then
                    turtle.turnRight()
                    currentDirection = 3
                    return true
                end
            end
            if number == 3 then
                if canMove(posX - 1, posY) then
                    turtle.turnRight()
                    turtle.turnRight()
                    currentDirection = 4
                    return true
                end
            end
            if number == 4 then
                if canMove(posX, posY + 1) then
                    turtle.turnLeft()
                    currentDirection = 1
                    return true
                end
            end
        end

        if currentDirection == 3 then
            if number == 1 then
                if canMove(posX, posY - 1) then
                    return true
                end
            end
            if number == 2 then
                if canMove(posX - 1, posY) then
                    turtle.turnRight()
                    currentDirection = 4
                    return true
                end
            end
            if number == 3 then
                if canMove(posX, posY + 1) then
                    turtle.turnRight()
                    turtle.turnRight()
                    currentDirection = 1
                    return true
                end
            end
            if number == 4 then
                if canMove(posX + 1, posY) then
                    turtle.turnLeft()
                    currentDirection = 2
                    return true
                end
            end
        end

        if currentDirection == 4 then
            if number == 1 then
                if canMove(posX - 1, posY) then
                    return true
                end
            end
            if number == 2 then
                if canMove(posX, posY + 1) then
                    turtle.turnRight()
                    currentDirection = 1
                    return true
                end
            end
            if number == 3 then
                if canMove(posX + 1, posY) then
                    turtle.turnRight()
                    turtle.turnRight()
                    currentDirection = 2
                    return true
                end
            end
            if number == 4 then
                if canMove(posX, posY - 1) then
                    turtle.turnLeft()
                    currentDirection = 3
                    return true
                end
            end
        end

    end
end


function hasPossibleDirection()

    if not (canMove(posX, posY + 1)) and not (canMove(posX, posY - 1)) and not (canMove(posX + 1, posY)) and not (canMove(posX - 1, posY)) then
        return false
    end
    return true
end


function canMove(x, y)

    if x == 0 or x == mazeSize + 1 or y == 0 or y == mazeSize + 1 then
        return false
    end

    if (visited[x][y] == 1) or (maze[x][y] == 1) then
        return false
    end

    return true
end


function goBack()

    if (stackTrace[stackTraceCount] - currentDirection == 1) or (stackTrace[stackTraceCount] - currentDirection == -3) then
        turtle.turnRight()
    elseif stackTrace[stackTraceCount] ~= currentDirection then
        turtle.turnLeft()
    end

    currentDirection = stackTrace[stackTraceCount]

    if currentDirection == 1 then
        posY = posY - 1
    end
    if currentDirection == 2 then
        posX = posX - 1
    end
    if currentDirection == 3 then
        posY = posY + 1
    end
    if currentDirection == 4 then
        posX = posX + 1
    end

    stackTrace[stackTraceCount] = nil
    stackTraceCount = stackTraceCount - 1

    turtle.back()
end


function saveToStackTrace()

    stackTraceCount = stackTraceCount + 1
    stackTrace[stackTraceCount] = currentDirection
end


-- CODE

init()

forward()

while not win() do

    mapPosition()

    if not hasPossibleDirection() then

        goBack()
    else

        chooseDirection()
        forward()
    end

end

turtle.up()
print("FINISHED MODAFAKA")

sleep(2)

turtle.down()

while stackTraceCount > 0 do
    goBack()
end