Mix.install([{:queue, "~> 0.1.0"}, {:ex2ms, "~> 1.0"}])

defmodule Main do
  def run() do
    get_input()
    |> Enum.map(&String.to_charlist/1) |> mkgrid()
    |> solve2()
	end

  # assumptions:
  #  - square grid, odd dimensions
  #  - "S" exactly in the middle
  #  - clear paths horiz and vert through "S" and along all sides

  # probably won't work for n close to a multiple of mod (=131)

  def get_input() do
    # "testinput21.1"
    "input21"
    |> File.read!() |> String.trim() |> String.split("\n")
  end

  def mkgrid(ls) do
    for {row, r} <- Enum.with_index(ls),
        {val, c} <- Enum.with_index(row),
        into: %{}, do: {{r,c}, val}
  end

  def addt({a,b},{c,d}), do: {a+c,b+d}

  # uses :q, an empty ets table
  # precompute Map.keys(gr)
  def dists_from(table,gr,keys) do
    qq = Queue.pop(:q)
    if qq != nil do
      {p,d,tf} = qq
      for dir <- [{-1,0},{1,0},{0,1},{0,-1}] do
        np = addt(p,dir)
        if np in keys and gr[np] != ?# and not :ets.member(table,np) do
          Queue.push(:q,{np,d+1,not tf})
          :ets.insert(table, {np, d+1, not tf})
        end
      end
      dists_from(table,gr,keys)
    end
  end

  def xor(true,true), do: false
  def xor(false,false), do: false
  def xor(true,false), do: true
  def xor(false,true), do: true

  def prep_calc(grid,n) do
    par = (rem(n,2) == 1)

    {{rc,cc},_} = Enum.find(grid,fn {_,v} -> v == ?S end)
    {rmax,_} = Enum.max_by(Map.keys(grid), &elem(&1,0))
    {_,cmax} = Enum.max_by(Map.keys(grid), &elem(&1,1))

    mod = rmax+1
    t1remd = rem(n-1,mod)
    t1par = xor( rem(n-t1remd,2)==1 , par)
    t2remd = mod+t1remd
    t2par = not t1par
    ax1remd = rem(n - rc - 1,mod)
    ax1par = xor( (rem(n-ax1remd,2) == 1), par)
    {ax2remd,ax2par} = {(if ax1remd < rc, do: mod+ax1remd, else: 0), not ax1par}

    Queue.new(:q)
    for {t,s} <- [{:cc,{rc,cc}}, {:ul,{0,0}}, {:uc,{0,cc}}, {:ur,{0,cmax}}, {:cr,{rc,cmax}},
                  {:dr,{rmax,cmax}}, {:dc,{rmax,cc}}, {:dl,{rmax,0}}, {:cl,{rc,0}}] do
      :ets.new(t, [:named_table])
      :ets.insert(t,{s,0,false}) # assuming all starting points are "even"
      Queue.push(:q,{s,0,false})
      dists_from(t,grid,Map.keys(grid))
    end
    
    ## part 1 solution:
    # :ets.select(:cc,[ {{:"$1", :"$2", :"$3"}, [{:andalso, {:"=<", :"$2", 64}, {:==, :"$3", false}}], [:"$1"]} ])
    # |> Enum.count()

    ## getting the select parameter:
    ## in iex:
    ## > Mix.install([{:ex2ms, "~> 1.0"}])
    ## > import Ex2ms
    ## > fun do {p,d,tf} = z when d <= 64 and tf == false -> p end
    ## (copy output)

    for {l,t,d,p} <- [{:full,:cc,mod,par},{:fulli,:cc,mod,not par},
                      {:t1ur,:dl,t1remd,t1par}, {:t1ul,:dr,t1remd,t1par},
                      {:t1dl,:ur,t1remd,t1par}, {:t1dr,:ul,t1remd,t1par},
                      {:t2ur,:dl,t2remd,t2par}, {:t2ul,:dr,t2remd,t2par},
                      {:t2dl,:ur,t2remd,t2par}, {:t2dr,:ul,t2remd,t2par},
                      {:ax1r,:cl,ax1remd,ax1par}, {:ax2r,:cl,ax2remd,ax2par},
                      {:ax1l,:cr,ax1remd,ax1par}, {:ax2l,:cr,ax2remd,ax2par},
                      {:ax1u,:dc,ax1remd,ax1par}, {:ax2u,:dc,ax2remd,ax2par},
                      {:ax1d,:uc,ax1remd,ax1par}, {:ax2d,:uc,ax2remd,ax2par} ], into: %{} do
      {l, :ets.select(t,[ {{:"$1", :"$2", :"$3"}, [{:andalso, {:"=<", :"$2", d}, {:==, :"$3", p}}], [:"$1"]} ]) |> Enum.count()}

    end
  end

  def calc(grid,n) do
    # precalc = prep_calc(grid,n) # 15 seconds
    # |> IO.inspect()
    precalc = %{ full: 7651, fulli: 7699, t1ur: 973, t1ul: 992, t1dl: 987, t1dr: 977, t2ur: 6710, t2ul: 6708, t2dl: 6715, t2dr: 6705, ax1r: 5764, ax2r: 0, ax1l: 5772, ax2l: 0, ax1u: 5767, ax2u: 0, ax1d: 5769, ax2d: 0 }

    {{rc,_},_} = Enum.find(grid,fn {_,v} -> v == ?S end)
    {rmax,_} = Enum.max_by(Map.keys(grid), &elem(&1,0))

    mod = rmax+1
    kk = div(n+1,mod)
    full_tls = 1 + 4 * div(kk-1,2) * (div(kk-1,2)+1)
    full_tls_i = 4 * div(kk,2) * div(kk,2)
    t1diag_tls = (if rem(n+1,mod) in [0,1], do: kk-1, else: kk)
    t2diag_tls = t1diag_tls - 1
    ax1remd = rem(n - rc - 1,mod)
    ax2_tls = (if ax1remd < rc-1, do: 1, else: 0)
 
    full_tls * precalc[:full] + full_tls_i * precalc[:fulli] +
      t1diag_tls * (precalc[:t1ur]+precalc[:t1ul]+precalc[:t1dl]+precalc[:t1dr]) +
      t2diag_tls * (precalc[:t2ur]+precalc[:t2ul]+precalc[:t2dl]+precalc[:t2dr]) +
      precalc[:ax1r]+precalc[:ax1l]+precalc[:ax1u]+precalc[:ax1d] +
      ax2_tls * (precalc[:ax2r]+precalc[:ax2l]+precalc[:ax2u]+precalc[:ax2d])

  end
  
  def solve2(grid) do
    # calc(grid,17)
    calc(grid, 26501365)
  end

end

:timer.tc(&Main.run/0)
|> IO.inspect(charlists: :as_lists)