@doc """
    Calculates the reduced product of a set of integers

    An element of the reduced product R_k is equal to U / M_k, where U = M_0 * M_1 * ... * M_k
  """
  def reduced_product(l) when is_list(l) do
    # Calculate the product of the set
    # It isn't super readable, but &*/2 is a pointer (hence the "&") to the multiplication function, which has an arity of two, hence the "/2" at the end
    # So all we're doing is multiplying each element of l by the accumulator
    u = Enum.reduce(l, &*/2)

    # Divide u by each element of l to get the reduced product
    # Because m will always divide u, truncate the result, to ensure that we're dealing with integers
    Enum.map(l, fn(m) -> trunc(u / m) end)
  end

  @doc """
    Finds the mod-m reciprocal of n, i.e. mod_reciprocal(11, 38) == 7

    Uses the extended Euclidean algorithm
  """
  def mod_reciprocal(n, m) do
    # Create a list of quotients of m and n
    quotients(m, n)
      # The next element t_(n+1) is determined by
      # t_(n+1) = t_(n-1) - q_n * t_n
      # In order to implement this, we reduce the list of quotients, starting with the tuple {0, 1}, which represents t_0 = 0 and t_1 = 1.
      # Then, we calculate the tuple {t_1, t_2}, which is equal to {t_1, t_1 - q_1 * t_2}
      # Then, we calculate {t_2, t_3} etc
      # Until we get the tuple {t_(n-1), t_n}
      |> Enum.reduce({0, 1}, fn(q, {t1, t2}) ->      {t2, t1 - q * t2} end)
      # t_(n-1) is the mod reciprocal, so we only need to return the first element of the final tuple
      |> elem(0)
  end

  @doc """
    Calculates the magic tuple of a set of integers

    The magic tuple is a set of integers such that each G_j = R_j * mod_reciprocal(R_j, M_j)
  """
  def magic_tuple(m) do
    r = reduced_product(m)

    r
      |> Enum.zip(m)
      |> Enum.map(fn({r, m}) -> mod_reciprocal(r, m) end)
      |> Enum.zip(r)
      |> Enum.map(fn({rec, r}) -> rec * r end)
  end

  @doc """
    Calculates the magic tuple of a set of integers and reduces it by modulo-U, where U is the second argument
  """
  def magic_tuple(m, u) do
    magic_tuple(m)
      |> Enum.map(fn(m) -> rem(m, u) end)
  end

  @doc """
    Calculates the value for x such that
      x % m_i = x % r_i, for each given m_i in m and each given r_i in r
  """
  def chinese_remainder(r, m) when is_list(r) and is_list(m) do
    u = Enum.reduce(m, &*/2)

    magic_tuple(m)
      |> Enum.zip(r)
      |> Enum.map(fn({g, r}) -> g * r end)
      |> Enum.map(fn(g) -> mod(g, u) end)
      |> Enum.reduce(&+/2)
      |> mod(u)
  end