matrices

matrices.ex

defmodule Matrices do
  @type permutation_map :: %{integer => integer}

  @spec build_permutation(Enumerable.t()) :: permutation_map
  def build_permutation(l) do
    n = Enum.count(l)

    Enum.zip(1..n, l)
    |> Map.new()
  end

  @type rotation :: {:rotation, 0..3}
  @type row_permutation :: {:row_permutation, permutation_map}
  @type basic_operation :: rotation | row_permutation
  @type operations :: [basic_operation]

  @spec compose(rotation, rotation) :: rotation
  def compose({:rotation, x}, {:rotation, y}), do: {:rotation, rem(x + y, 4)}

  @spec compose(row_permutation, row_permutation) :: row_permutation
  def compose({:row_permutation, perm_1}, {:row_permutation, perm_2}) do
    {:row_permutation, Map.new(perm_1, fn {i, p_i} -> {i, perm_2[p_i]} end)}
  end

  @spec rotate_c :: operations
  def rotate_c, do: [{:rotation, 1}]
  @spec rotate_cc :: operations
  def rotate_cc, do: [{:rotation, 3}]

  @spec horizontal_flip(integer) :: operations
  def horizontal_flip(n), do: [{:row_permutation, build_permutation(n..1)}]
  @spec vertical_flip(integer) :: operations
  def vertical_flip(n), do: rotate_c() ++ horizontal_flip(n) ++ rotate_cc()

  @spec shift_rows_up(integer) :: operations
  def shift_rows_up(n) do
    [
      {:row_permutation, build_permutation(Enum.to_list(2..n) ++ [1])}
    ]
  end

  @spec shift_rows_down(integer) :: operations
  def shift_rows_down(n) do
    [
      {:row_permutation, build_permutation([n] ++ Enum.to_list(1..(n - 1)))}
    ]
  end

  @spec shift_columns_left(integer) :: operations
  def shift_columns_left(n), do: rotate_cc() ++ shift_rows_up(n) ++ rotate_c()
  @spec shift_columns_right(integer) :: operations
  def shift_columns_right(n), do: rotate_cc() ++ shift_rows_down(n) ++ rotate_c()

  @spec simplify_same_type(operations) :: operations
  def simplify_same_type(operations), do: [Enum.reduce(operations, &compose/2)]

  @spec is_identity?(basic_operation) :: boolean
  def is_identity?({:rotation, 0}), do: true

  def is_identity?({:row_permutation, permutation}),
    do: Enum.all?(permutation, fn {i, p_i} -> i == p_i end)

  def is_identity?(_), do: false

  @spec simplify_pass(operations) :: operations
  def simplify_pass(operations) do
    operations
    # separate in chunks according to the first element of the tuple (:rotation or :row_permutation)
    |> Enum.chunk_by(&elem(&1, 0))
    |> Enum.flat_map(&simplify_same_type/1)
    |> Enum.reject(&is_identity?/1)
  end

  defp pprint(operations) do
    for operation <- operations do
      IO.inspect(operation)
    end
  end

  @spec simplify(operations) :: operations
  def simplify(operations) do
    simplified = simplify_pass(operations)

    if operations == simplified do
      IO.puts("STOP")
      operations
    else
      IO.puts("Simplified:\n")
      pprint(operations)
      simplify(simplified)
    end
  end

  def example do
    operations =
      rotate_c() ++
        vertical_flip(3) ++
        rotate_c() ++
        shift_rows_up(3) ++
        horizontal_flip(3) ++
        shift_rows_up(3) ++
        shift_rows_down(3) ++
        shift_columns_left(3) ++
        rotate_cc() ++
        shift_rows_up(3) ++
        shift_rows_up(3) ++
        rotate_c() ++
        shift_rows_up(3) ++
        rotate_cc() ++
        rotate_cc()

    simplify(operations)
  end
end