inplace

defmodule InPlace.Examples.Sudoku do
  @moduledoc """
  Sudoku puzzle.
  The instance of puzzle is a string of DxD length
  , where D is a dimension of Sudoku puzzle (would be 9 by default).
  The values 1 to 9 represent pre-filled cells (clues, givens etc...);
  any other values represent hidden cells.
  """
  alias InPlace.ExactCover
  alias InPlace.BitSet
  alias InPlace.Array
  require Logger
  @numbers ?1..?9

  @doc """
  Solver
  """
  def solve(instance, opts \\ []) do
    ## Build the options for the exact cover, and some supplemental data
    %{options: options, dimension: d, instance: instance_array} = init(instance)
    opts = Keyword.merge(default_opts(), opts)
    ## Plug in solution handler
    top_solution_handler = Keyword.get(opts, :solution_handler)
    checker = Keyword.get(opts, :checker)

    opts =
      Keyword.put(opts, :solution_handler, fn solution ->
        solution
        |> solution_to_sudoku(instance_array, options, d)
        |> tap(fn solution -> checker && check_solution(solution) end)
        |> top_solution_handler.()
      end)

    ## Solve with exact cover
    ExactCover.solve(options, opts)
  end

  defp default_opts() do
    [
      solution_handler: fn solution -> Logger.info(inspect(solution)) end,
      checker: fn correct? -> !correct? && Logger.error("invalid solution") end
    ]
  end

  defp init(instance) when is_binary(instance) do
    l = String.length(instance)
    d = :math.sqrt(l) |> floor()
    if d * d != l, do: throw(:invalid_instance)
    sqrt_d = :math.sqrt(d) |> floor()
    if sqrt_d * sqrt_d != d, do: throw(:invalid_instance)

    %{
      options: init_exact_cover(instance, d),
      dimension: d,
      instance: instance_to_array(instance)
    }
  end

  defp init_exact_cover(instance, d) when is_binary(instance) do
    ## Turn the instance to a list of options
    ## columns (items in "exact-cover" terms):
    ## - one for each cell (d^2);
    ## - d^2 for columns: each of the d columns must have each possible value 1-d.
    ## - d^2 for rows: each of the d rows must have each possible value 1-d.
    ## - d^2 for blocks: Each of the d sqrt(d)×sqrt(d) blocks must have each possible value 1-d.
    ## ??  - initial state: Since there is an initial state for the board, one option will describe the initial state and this item ensures that it is always part of any solution found.

    ## Rows (options in "exact-cover" terms)
    ## There will be (d*d - num_open_cells) * d rows (options)
    ## for hidden cells, plus one that matches open cells
    ##

    covered_set = BitSet.new(0, d * d * 4)
    {_position, options} =
      for <<cell <- instance>>, reduce: {0, []} do
        {cell_number, options_acc} ->
          {cell_number + 1,
          if hidden_cell?(cell) do
             Enum.reduce(0..(d - 1), options_acc, fn value, opt_acc ->
              [create_option(cell_number * d + value, d) | opt_acc]
             end)
          else
            Enum.each(
              create_option(cell_number * d + cell_value(cell) - 1, d),
              fn val -> BitSet.put(covered_set, val) end)
            options_acc
          end
        }
      end

    Enum.reject(options, fn opt ->
      Enum.any?(opt, fn val -> BitSet.member?(covered_set, val) end)
    end)
  end

  defp hidden_cell?(ascii_code) do
    ascii_code not in @numbers
  end

  defp create_option(row, d) do
    [
      cell_item(row, d),
      row_item(row, d),
      column_item(row, d),
      block_item(row, d)
    ]
  end

  defp cell_value(ascii_code) do
    ascii_code - 48
  end

  def cell_item(row, d) do
    div(row, d)
  end

  def row_item(row, d) do
    d_squared = d * d
    d_squared + d * div(row, d_squared) + rem(row, d)
  end

  def column_item(row, d) do
    d_squared = d * d
    2 * d_squared + rem(row, d_squared)
  end

  def block_item(row, d) do
    d_squared = d * d
    sqrt_d = floor(:math.sqrt(d))

    3 * d_squared +
      div(row, sqrt_d * d_squared) * d * sqrt_d +
      (div(row, sqrt_d * d) |> rem(sqrt_d)) * d + rem(row, d)
  end

  defp instance_to_array(instance) when is_binary(instance) do
    l = String.length(instance)
    arr = Array.new(l, 0)
    for <<cell <- instance>>, reduce: 1 do
      acc ->
        !hidden_cell?(cell) && Array.put(arr, acc, cell_value(cell))
        acc + 1
    end
    arr
  end

  @doc """
    `solution` is a "cover" (list of indices into options
    built off the Sudoku instance).
    Note: the options only represent "hidden" cells.
  """
  def solution_to_sudoku(solution, instance, options, d) do
    grid_size = d * d

    solution
    |> Enum.each(fn opt_idx ->
      [_, r, c, _] = Enum.at(options, opt_idx)

      {val, row, col} =
        {
          rem(r - grid_size, d) + 1,
          div(r - grid_size, d),
          div(c - 2 * grid_size, d)
        }

      Array.put(instance, row * d + col + 1, val)
    end)
    Array.to_list(instance)
  end

  @spec check_solution([integer()]) :: boolean()
  @doc """
    `solution` is a list of integers
    representing the 'flattened' solved puzzle
  """
  def check_solution(solution) when is_list(solution) do
    dim = :math.sqrt(length(solution)) |> floor()
    grid = Enum.chunk_every(solution, dim)
    transposed = Enum.zip_with(grid, &Function.identity/1)
    squares = group_by_subsquares(grid)

    checker_fun = fn line -> Enum.sort(line) == Enum.to_list(1..dim) end

    Enum.all?([grid, transposed, squares], fn arrangement ->
      Enum.all?(arrangement, checker_fun)
    end)
  end

  defp group_by_subsquares(cells) do
    square = :math.sqrt(length(cells)) |> floor

    for i <- 0..(square - 1), j <- 0..(square - 1) do
      for k <- (i * square)..(i * square + square - 1),
          l <- (j * square)..(j * square + square - 1) do
        Enum.at(cells, k) |> Enum.at(l)
      end
    end
  end
end