-- This file:
--   http://anggtwu.net/LUA/tictactoetree.lua.html
--   http://anggtwu.net/LUA/tictactoetree.lua
--          (find-angg "LUA/tictactoetree.lua")
-- Author: Eduardo Ochs <eduardoochs@gmail.com>
--
-- Original version:         2009dec22
-- Version with test blocks: 2019sep29

toBA = function (B)  return split(B, "(.)") end
toB  = function (BA) return table.concat(BA) end
otherplayer = function (s) return s=="o" and "x" or "o" end

win1 = function(BA, a, b, c, s)
    return BA[a] == s and BA[b] == s and BA[c] == s
  end
win9 = function(BA, s)
    return win1(BA, 1,2,3, s) or win1(BA, 4,5,6, s) or win1(BA, 7,8,9, s) or
           win1(BA, 1,4,7, s) or win1(BA, 2,5,8, s) or win1(BA, 3,6,9, s) or
           win1(BA, 1,5,9, s) or win1(BA, 3,5,7, s)
  end
win_ = function (B)
    local BA = toBA(B)
    if win9(BA, "o") then return "o" end
    if win9(BA, "x") then return "x" end
    return "."
  end
win_memo = {}
win = function (B)
    if win_memo[B] then return win_memo[B] end
    win_memo[B] = win_(B)
    return win_memo[B]
  end

play1 = function (B, p, s)
    return B:sub(1, p-1)..s..B:sub(p+1)
  end
-- play1("abcdef", 2, "!")
followers_memo = {}
followers_ = function (B, s)
    local F = {}
    for i=1,9 do
      if B:sub(i, i)=="." then table.insert(F, play1(B, i, s)) end
    end
    return F
  end
followers = function (B, s)
    if followers_memo[B] == nil then
      if win(B)=="." then
        followers_memo[B] = followers_(B, s)
      else
        followers_memo[B] = {}
      end
    end
    return followers_memo[B]
  end


--[[
* (eepitch-lua51)
* (eepitch-kill)
* (eepitch-lua51)
dofile "tictactoetree.lua"
PP(followers("...oooxxx", "o"))
PP(followers("...oo.xx.", "o"))
PP(followers_memo)
= ("abcdef"):sub(3,3)
PP(win("...ooo..."))
PP(win("x..xoox.."))
PP(win("........."))
PP(win_memo)

--]]

dfs_play = function (B, s)
    if not followers_memo[B] then
      local other_s = otherplayer(s)
      for _,new_B in ipairs(followers(B, s)) do
        PP(new_B, other_s)
        dfs_play(new_B, other_s)
      end
    end
  end

--[[
* (eepitch-lua51)
* (eepitch-kill)
* (eepitch-lua51)
dofile "tictactoetree.lua"
dfs_play("o.o.x.o.x", "x")
dfs_play(".........", "o")
PP(followers("o.o.x.o.x", "x"))

--]]