kelpqueue.lua -- queue-based kelp harvester with TLA+-proven per-step NEVER-STRAND fuel guard

kelpqueue.lua

-- kelpqueue.lua -- QUEUE-BASED kelp harvester for a CC: Tweaked turtle (MC 1.21.8).
--
-- DESIGN (the user's algorithm, implemented exactly):
--   A precomputed QUEUE of surface target columns + a dead-simple per-target
--   primitive.  We DO NOT detect kelp to navigate; we navigate over LIVE water on
--   a fixed travel plane (walls/structure are reliably inspectable -- only kelp
--   detection was ever unreliable, and we never rely on it).
--
--   1. Get out of the dock and go to the first target.
--   2. For each target (a QUEUE we POP): rise inside the column to the air above
--      the kelp top, then DESCEND digging kelp until the block BELOW is "not kelp"
--      (the seabed) -- you're now in the base cell -- PLANT a kelp (placeDown ->
--      replant the base), then ascend back to the travel plane and POP the target.
--   3. One extra primitive: move from one target to the next -- a 2D BFS move at
--      the travel plane over live water.
--
-- ---- TRAVEL PLANE (verified in-world) ------------------------------------
--   The dock caps y62 with a DECK, so the turtle CANNOT rise straight from home
--   to the air plane (airDy=+3, y63).  But y60 (waterTravelDy=0) is OPEN WATER
--   across the west field AND reachable from the dock by escaping WEST/EAST.  So
--   we travel at waterTravelDy and rise into each open-air target column to reach
--   the air above its kelp top, then run the descend primitive so the WHOLE column
--   (including kelp ABOVE the travel plane) is harvested.
--
-- ---- RELATIVE FRAME / REQUIRED IN-WORLD PLACEMENT ------------------------
--   No GPS.  Placed spot = HOME origin = relative (0,0,0).
--     * Place the turtle at world (999,60,735) -- ANY facing (we self-calibrate).
--     * Collection chest sits DIRECTLY ABOVE home at (0,1,0): deposit = dropUp().
--     * Home neighbours: N(-z)=hopper, S(+z)=ladder, up=chest, down=turtle.  The
--       ONLY passable horizontal home exits are WEST(-x) and EAST(+x).
--     * heading convention: dir 0=+z(S), 1=-x(W), 2=-z(N), 3=+x(E).
--
-- ---- NEVER STRAND --------------------------------------------------------
--   Before every venture we reserve the REAL BFS path home at the travel plane +
--   a full column climb-back (airDy-baseDy) + margin, and refuel(0)/burn any
--   non-kelp fuel from the inventory (never burn harvested raw kelp).
--
-- ---- PERSISTENCE ---------------------------------------------------------
--   Progress {queue index, pos, dir} is saved to /kelpqueue.state after every
--   move; a restart (re-place the turtle at origin, any facing) resumes at the
--   next un-popped target.

local CFG = {
  margin    = 64,    -- fuel kept in reserve beyond the computed home cost
  tick      = 5,     -- sleep between full-queue sweeps (regrowth wait)
  maxNav    = 4096,  -- BFS node cap (the live water graph is small)
  fullCarry = 15,    -- deposit when this many inventory slots are occupied (of 16)
}

-- ---- BAKED QUEUE (inlined for single-file deploy) ------------------------
-- Mirrors maps/kelp_targets.lua.  Origin = placed spot = relative (0,0,0).
local MAP = {
  meta = {
    origin_world  = { x = 999, y = 60, z = 735 },
    airDy         = 3,    -- y63: air above the TALLEST kelp (rise target ceiling)
    baseDy        = -10,  -- y50: kelp base / replant floor
    seabedDy      = -11,  -- y49: solid seabed
    waterTravelDy = 0,    -- y60: open-water travel plane
    chest         = { dx = 0, dy = 1, dz = 0 },   -- dropUp target (above home)
  },
  -- target columns { dx, dz } (air above each at airDy; base at baseDy).
  targets = {
    {-8,-4},{-8,-2},{-8,1},{-8,4},{-8,5},{-8,6},{-7,-5},{-7,-2},{-7,1},{-7,3},
    {-7,7},{-7,8},{-6,-6},{-6,-3},{-6,3},{-6,4},{-6,5},{-6,6},{-6,7},{-6,9},
    {-5,-7},{-5,1},{-5,4},{-5,8},{-5,9},{-4,-7},{-4,-6},{-4,-5},{-4,1},{-4,3},
    {-4,6},{-4,8},{-4,9},{-3,-7},{-3,-6},{-3,-5},{-3,-4},{-3,2},{-3,6},{-2,7},
  },
}
local META     = MAP.meta
local TRAVELDY  = META.waterTravelDy   -- 0  (y60)
local AIRDY     = META.airDy           -- 3  (y63)
local BASEDY    = META.baseDy          -- -10 (y50)
local TARGETS   = MAP.targets

-- ---- helpers -------------------------------------------------------------
local function isKelp(d)  return d and d.name and d.name:find("kelp") ~= nil end
local function kelpItem(d) return d and d.name == "minecraft:kelp" end
-- Real CC inspect()/inspectUp()/inspectDown() return FALSE for AIR and WATER.

-- heading convention: dir 0=+z(S), 1=-x(W), 2=-z(N), 3=+x(E).
local VEC = { [0]={0,1}, [1]={-1,0}, [2]={0,-1}, [3]={1,0} }

local STATE = "/kelpqueue.state"
local S

local function save()
  local f = fs.open(STATE, "w"); f.write(textutils.serialize(S)); f.close()
end
local function load()
  if fs.exists(STATE) then
    local f = fs.open(STATE, "r"); S = textutils.unserialize(f.readAll()); f.close()
  end
  if not S then
    -- boot: at origin (0,0,0); dir is calibrated below before any move.
    S = { x = 0, y = 0, z = 0, dir = 1, idx = 1 }
  end
end

-- ---- movement (relative-frame position tracking) -------------------------
local function turnR() turtle.turnRight(); S.dir = (S.dir + 1) % 4; save() end
local function turnL() turtle.turnLeft();  S.dir = (S.dir + 3) % 4; save() end
local function faceTo(d)
  while S.dir ~= d do
    if (S.dir + 1) % 4 == d then turnR() else turnL() end
  end
end
local function rawUp()   if turtle.up()   then S.y = S.y + 1; save(); return true end return false end
local function rawDown() if turtle.down() then S.y = S.y - 1; save(); return true end return false end
local function rawForward()
  if turtle.forward() then
    S.x = S.x + VEC[S.dir][1]; S.z = S.z + VEC[S.dir][2]; save(); return true
  end
  return false
end

-- ---- boot facing calibration ---------------------------------------------
-- Do NOT assume placement facing (a real in-world bug).  Determine true facing
-- by matching HOME's unique inspectable neighbours: North(-z, dir 2)=hopper,
-- South(+z, dir 0)=ladder.  Physically rotate, inspect front; on a match SET
-- S.dir to the known relative direction so the frame is aligned.  Must run AT
-- home (the placed origin) before any move.  Returns true on success.
local function calibrate()
  for _ = 0, 3 do
    local ok, d = turtle.inspect()
    if ok and d and d.name then
      if d.name:find("hopper") then S.dir = 2; save(); return true end  -- facing North
      if d.name:find("ladder") then S.dir = 0; save(); return true end  -- facing South
    end
    turtle.turnRight()   -- rotate physically; S.dir is corrected on the match
  end
  return false
end

-- ---- HALT signalling -----------------------------------------------------
-- When the turtle cannot SAFELY continue (out of fuel, inventory jammed) we set
-- HALTED and unwind to main(), which stops cleanly with a clear message instead
-- of churning "could not reach" warnings or stranding in the field.
local HALTED = false
local HALT_MSG = nil
local function halt(msg) HALTED = true; HALT_MSG = msg; printError(msg) end

-- ---- fuel ----------------------------------------------------------------
local function fuel() local f = turtle.getFuelLevel(); if f == "unlimited" then return math.huge end return f end
local function freeSlots() local n = 0 for s = 1, 16 do if turtle.getItemCount(s) == 0 then n = n + 1 end end return n end
local function occupiedSlots() return 16 - freeSlots() end
-- refuel(0)-style: burn any NON-kelp burnable item from the inventory to top up.
-- Tops up until fuel exceeds `want` (default margin*4); never burns raw kelp.
local function ensureFuel(want)
  want = want or CFG.margin * 4
  if fuel() == math.huge or fuel() > want then return end
  for s = 1, 16 do
    local d = turtle.getItemDetail(s)
    if d and not kelpItem(d) then          -- never burn harvested raw kelp
      turtle.select(s)
      if turtle.refuel(0) then             -- ask the turtle: is this fuel?
        while fuel() <= want and turtle.refuel(8) do end
        if fuel() > want then break end
      end
    end
  end
  turtle.select(1)
end

-- ---- LIVE-water BFS over the travel plane --------------------------------
-- Navigate at TRAVELDY only.  Walls/structure are reliably visible to inspect.
-- We assume every in-field cell passable EXCEPT home's blocked N/S exits, walk
-- the BFS path, and if a physical step is blocked by an unforeseen wall we mark
-- that edge blocked and replan.  A kelp top AT the travel plane is dig-through.

local blocked = {}
local function ekey(x, z, nx, nz) return x..","..z..">"..nx..","..nz end

local function edgeAllowed(x, z, nx, nz)
  if blocked[ekey(x, z, nx, nz)] then return false end
  local atHome = (x == 0 and z == 0)
  local toHome = (nx == 0 and nz == 0)
  if atHome or toHome then
    if nz ~= z then return false end   -- N/S move touching home: blocked (hopper/ladder)
  end
  return true
end

local function bfsPath(sx, sz, gx, gz)
  if sx == gx and sz == gz then return { { sx, sz } } end
  -- bounding box: field dx -8..-2, dz -7..+9, plus home at 0,0.  Pad by 1.
  local minX, maxX, minZ, maxZ = -9, 1, -8, 10
  local function inBox(x, z) return x >= minX and x <= maxX and z >= minZ and z <= maxZ end
  local q = { { sx, sz } }
  local seen = { [sx..","..sz] = true }
  local from = {}
  local h = 1
  local cap = 0
  while h <= #q do
    local cur = q[h]; h = h + 1
    cap = cap + 1; if cap > CFG.maxNav then return nil end
    local cx, cz = cur[1], cur[2]
    for d = 0, 3 do
      local nx, nz = cx + VEC[d][1], cz + VEC[d][2]
      local nk = nx..","..nz
      if inBox(nx, nz) and not seen[nk] and edgeAllowed(cx, cz, nx, nz) then
        seen[nk] = true; from[nk] = cur
        if nx == gx and nz == gz then
          local path = { { nx, nz } }; local c = nk
          while c ~= (sx..","..sz) do
            local p = from[c]; path[#path+1] = p; c = p[1]..","..p[2]
          end
          local r = {}; for i = #path, 1, -1 do r[#r+1] = path[i] end
          return r
        end
        q[#q+1] = { nx, nz }
      end
    end
  end
  return nil
end

-- Physically step to an ADJACENT (nx,nz) at TRAVELDY.  Digs a kelp TOP in the
-- way (the only block we expect to dig while travelling).  A non-kelp solid
-- records the edge blocked and returns false.
-- BFS distance home from an ARBITRARY (x,z) at the travel plane (used by the
-- travel-out guard; homeDist() below reuses this from the current cell).
local function distHomeFrom(x, z)
  local p = bfsPath(x, z, 0, 0)
  if p then return #p - 1 end
  return (math.abs(x) + math.abs(z)) * 2     -- unknown route: pessimistic
end

-- physStep(nx, nz [, guard]): step to ADJACENT (nx,nz).  When `guard` is true
-- (travelling OUTWARD to a target) we apply the per-step NEVER-STRAND reserve:
-- only step if, after spending the fuel, we can still BFS home from the RESULT
-- cell + margin.  Return-home navigation passes guard=false (always allowed).
local function physStep(nx, nz, guard)
  if guard and fuel() ~= math.huge
     and fuel() - 1 < distHomeFrom(nx, nz) + CFG.margin then
    return false       -- would strand: refuse this outward step
  end
  local dx, dz = nx - S.x, nz - S.z
  local d = (dx == 1 and 3) or (dx == -1 and 1) or (dz == 1 and 0) or (dz == -1 and 2)
  if not d then return false end
  faceTo(d)
  if rawForward() then return true end
  local ok, data = turtle.inspect()
  if ok and isKelp(data) then
    turtle.dig()
    if rawForward() then return true end
  end
  blocked[ekey(S.x, S.z, nx, nz)] = true
  return false
end

-- Navigate to (gx,gz) at TRAVELDY, replanning around any newly-found wall.
-- `guard` (default false) applies the per-step travel-out NEVER-STRAND reserve.
-- A guard=true call that stops because the next step would strand returns false
-- WITHOUT setting HALTED (the caller routes home and skips the target).  A move
-- that physically fails with fuel()==0 is a real out-of-fuel stall: HALT.
local function navTo(gx, gz, guard)
  while S.y < TRAVELDY do if not rawUp()   then break end end
  while S.y > TRAVELDY do if not rawDown() then break end end
  for _ = 1, 200 do
    if S.x == gx and S.z == gz then return true end
    local path = bfsPath(S.x, S.z, gx, gz)
    if not path then return false end
    local advanced = false
    for i = 2, #path do
      local step = path[i]
      if physStep(step[1], step[2], guard) then advanced = true
      else
        -- A step we DIDN'T take because we're out of fuel (not a wall, not a
        -- refused outward guard step): clean HALT instead of churning.
        if fuel() == 0 then
          halt("OUT OF FUEL -- add burnable fuel and rerun.")
        end
        break
      end
    end
    if not advanced then return false end
  end
  return S.x == gx and S.z == gz
end

-- ---- fuel reserve: real BFS path home + full column climb-back -----------
local function homeDist() return distHomeFrom(S.x, S.z) end
-- A target column can climb from baseDy up to airDy, then back down to travelDy:
-- reserve the full vertical span both ways.
local function columnSpan() return (AIRDY - BASEDY) + (AIRDY - TRAVELDY) end
local function reserveHome() return homeDist() + columnSpan() + CFG.margin end

-- PER-STEP NEVER-STRAND GUARD (the TLA+-proven rule, KelpQueue.tla cost(h,v)).
-- Worst-case cost to get FULLY home from a hypothetical position whose vertical
-- offset from the travel plane is `vOff` (signed: + above, - below): climb back
-- to the travel plane (|vOff|) + BFS path home from the current x,z + margin.
-- We must reserve this BEFORE committing to any move that LANDS at vOff -- not
-- just once before the target.  `canStepTo(vOff)` answers: after spending 1 fuel
-- on the move that lands us there, can we still get home?  (fuel-1 >= cost.)
local function costHomeFromV(vOff)
  local climb = (vOff < 0) and -vOff or vOff
  return climb + homeDist() + CFG.margin
end
local function canStepTo(vOff)
  if fuel() == math.huge then return true end
  return fuel() - 1 >= costHomeFromV(vOff)
end

-- ---- deposit -------------------------------------------------------------
-- Stand at home (0,0) at TRAVELDY and dropUp all harvested kelp into the chest
-- directly above (0,1,0).
local function depositAtHome()
  if not navTo(0, 0) then return false end
  while S.y < TRAVELDY do if not rawUp()   then break end end
  while S.y > TRAVELDY do if not rawDown() then break end end
  for s = 1, 16 do
    if kelpItem(turtle.getItemDetail(s)) then
      turtle.select(s); turtle.dropUp()
    end
  end
  turtle.select(1)
  return true
end

-- Route the turtle HOME (climb to the travel plane, then BFS home unguarded --
-- going home is ALWAYS allowed).  Used after a guard abort so we never idle out
-- in the field.  Returns true if it actually reached home (0,0).
local function returnHome()
  return depositAtHome() and S.x == 0 and S.z == 0
end

-- Is the inventory JAMMED with non-kelp junk?  True when there is no free slot
-- AND no kelp to deposit (so depositAtHome can't free anything).  In that case
-- harvesting can't proceed -- HALT rather than loop digging into a full hold.
local function inventoryJammed()
  if freeSlots() > 0 then return false end
  for s = 1, 16 do
    if kelpItem(turtle.getItemDetail(s)) then return false end  -- kelp -> can deposit
  end
  return true
end

-- ---- ensure a kelp item is selected (for replanting via placeDown) -------
-- The descend harvests kelp into the inventory, so after digging a column we
-- always have raw kelp to replant.  Selects a slot holding kelp; returns true.
local function selectKelp()
  for s = 1, 16 do
    if kelpItem(turtle.getItemDetail(s)) then turtle.select(s); return true end
  end
  return false
end

-- ---- the PER-TARGET primitive: rise-then-descend-then-replant ------------
-- Precondition: standing AT the column cell (dx,dz) at TRAVELDY (navTo dug any
-- kelp top that was AT the travel plane to move in).
--   1. RISE within the column (open-air targets) digging any kelp above the
--      plane up to AIRDY, so we sit in the air ABOVE the tallest kelp.
--   2. DESCEND digging kelp until the block BELOW is "not kelp" (the seabed).
--      We are then in the base cell at BASEDY (one above the seabed).
--   3. PLANT a kelp via placeDown -> replant the base (leave exactly 1).
--   4. ASCEND back to the travel plane.
-- Digs ONLY kelp: digUp/digDown only when inspect shows kelp; never digs the
-- seabed/structure.  placeDown only onto the seabed solid.
-- Climb back to the travel plane from wherever we are (toward home; always
-- allowed while fueled -- matches KelpQueue.tla's unconditional Climb).
local function climbToPlane()
  while S.y < TRAVELDY do if not rawUp()   then return false end end
  while S.y > TRAVELDY do if not rawDown() then return false end end
  return true
end

-- Returns true on a COMPLETED column, false if it ABORTED before fully
-- descending because the per-step guard would otherwise strand us.  On abort
-- the turtle climbs back to the travel plane (it never commits to a move it
-- cannot return from), and the caller routes it home.
local function harvestTarget()
  -- Phase 1: RISE to the air above the kelp top (open-air column).  GUARD each
  -- step: only rise if, after spending the fuel, we can still get fully home
  -- from the resulting (higher) position.
  while S.y < AIRDY do
    if not canStepTo((S.y + 1) - TRAVELDY) then climbToPlane(); return false end
    local ok, du = turtle.inspectUp()
    if ok then
      if isKelp(du) then turtle.digUp()    -- kelp above the plane: harvest it
      else break end                        -- a non-kelp solid above: stop rising
    end
    if not rawUp() then break end           -- step up into clear air/water
  end
  -- Phase 2: DESCEND digging kelp until the block BELOW is NOT kelp (the seabed).
  -- This is the DEEP, expensive part that stranded the real turtle.  GUARD each
  -- step against the worst case: the cost to climb back from the RESULTING deeper
  -- cell to the travel plane PLUS the BFS path home.  If the next descent would
  -- leave us unable to return, ABORT and climb back -- never commit to it.
  while true do
    local ok, db = turtle.inspectDown()
    local belowIsKelp = ok and isKelp(db)
    if ok and not belowIsKelp then break end  -- seabed (non-kelp solid): stop
    if S.y <= BASEDY then break end           -- safety floor: never go below base
    if not canStepTo((S.y - 1) - TRAVELDY) then climbToPlane(); return false end
    if belowIsKelp then turtle.digDown() end  -- kelp below: harvest, then descend
    if not rawDown() then break end
  end
  -- Phase 3: go UP one (out of the base cell), then PLANT a kelp via placeDown
  -- onto the seabed -> the new kelp occupies the base cell (BASEDY).  This is the
  -- "go up one, replant the base, leave exactly 1" step.  (Climb toward home: no
  -- guard needed -- the descent guard already reserved this climb + the way home.)
  rawUp()
  if selectKelp() then turtle.placeDown() end
  turtle.select(1)
  -- Phase 4: ASCEND back to the travel plane.
  climbToPlane()
  return true
end

-- ---- main: pop the queue, loop forever -----------------------------------
local function main()
  load()
  -- Calibrate true facing from the dock neighbours (no "assume west").  Must be
  -- at HOME (placed origin) at startup, which is the deploy convention.
  if not calibrate() then
    printError("Could not calibrate facing: expected a hopper (N) or ladder (S) "
      .. "next to me at home. Place me at the dock origin and rerun.")
    return
  end
  print("kelpqueue harvester up. targets="..#TARGETS.." dir="..S.dir.." resume idx="..S.idx)
  ensureFuel()
  while not HALTED do
    -- pop the queue from the resume index to the end.
    while S.idx <= #TARGETS and not HALTED do
      ensureFuel()
      local t = TARGETS[S.idx]
      local dx, dz = t[1], t[2]

      -- ROBUSTNESS: inventory jammed with non-kelp junk (no free slot, no kelp to
      -- deposit)?  We can't harvest -- HALT cleanly instead of looping.
      if inventoryJammed() then
        halt("INVENTORY FULL of non-kelp -- clear it and rerun."); break
      end
      -- inventory heavy with kelp? deposit before harvesting more.
      if occupiedSlots() >= CFG.fullCarry then depositAtHome() end

      -- NEVER STRAND (whole-excursion reserve): only LEAVE home for this target
      -- if we can afford to reach it, run the full rise-then-descend excursion,
      -- and return -- i.e. fuel >= reserveHome() computed from the TARGET cell
      -- (worst case: full column climb-back from the deepest point + path home).
      local startReserve = distHomeFrom(dx, dz) + columnSpan() + CFG.margin
      if fuel() ~= math.huge and fuel() < startReserve then
        ensureFuel(startReserve * 2)            -- try to top up above the reserve
        if fuel() < startReserve then
          -- Can't safely venture: make sure we're HOME (never idle in the field)
          -- and stop with a clear message instead of stranding mid-excursion.
          returnHome()
          halt("OUT OF FUEL -- can't safely reach target "..S.idx
               .." ("..dx..","..dz.."). Add burnable fuel and rerun.")
          break
        end
      end

      -- move to the target at the travel plane (GUARDED), then run the per-target
      -- primitive.  The travel-out guard refuses any step that would strand; the
      -- excursion guards every vertical move.  If either bails, route HOME.
      local reached = navTo(dx, dz, true)
      if HALTED then returnHome(); break end
      if reached then
        local completed = harvestTarget()
        if HALTED then returnHome(); break end
        if not completed then
          -- excursion aborted to avoid stranding: go home, top up, and only stop
          -- if we truly have no fuel source (else we retry this target next loop).
          returnHome()
          ensureFuel(startReserve * 2)
          if fuel() ~= math.huge and fuel() < startReserve then
            halt("OUT OF FUEL -- aborted excursion at target "..S.idx
                 ..". Add burnable fuel and rerun.")
          end
          break   -- re-evaluate this same target on the next outer loop
        end
      else
        -- couldn't reach (guard refused the outward step, or a wall): if it was
        -- fuel, navTo already HALTed; otherwise just skip with a warning.
        if HALTED then returnHome(); break end
        print("WARN: could not reach target "..S.idx.." ("..dx..","..dz..")")
      end

      -- POP the target (only reached here on a COMPLETED column or a wall-skip).
      S.idx = S.idx + 1; save()

      if occupiedSlots() >= CFG.fullCarry then depositAtHome() end
    end
    if HALTED then break end

    -- queue drained: deposit, reset the queue, wait for regrowth, repeat forever.
    depositAtHome()
    S.idx = 1; save()
    sleep(CFG.tick)
  end
  if HALTED then
    returnHome()   -- final guarantee: end AT HOME, never stranded in the field.
  end
end

main()