inversion-slow.ex

defmodule Inversion do

  def summarize(a, b, acc, list_acc) do
    case {a, b} do
      {[], []} -> {list_acc, acc}
      {a, []} -> {list_acc ++ a, acc}
      {[], b} -> {list_acc ++ b, acc}
      {a,b} when hd(a) > hd(b) -> summarize(a, tl(b), length(a) + acc, list_acc ++ [hd(b)])
      {a,b} when hd(a) <= hd(b) -> summarize(tl(a), b, acc, list_acc ++ [hd(a)])
    end
  end

  def count_inversion(a) do
    case a do
      [] -> {[], 0}
      [x] -> {[x], 0}
      [x,y] when x > y -> {[y,x], 1}
      [x,y] when x <= y -> {[x,y], 0}
      a -> 
        n = length(a)
        half = div(n, 2)
        {sorted_b, x} = count_inversion(Enum.slice(a, (0 .. half-1)))
        {sorted_c, y} = count_inversion(Enum.slice(a, half..n-1))
        {sorted_a, z} = summarize(sorted_b, sorted_c, 0, [])
        {sorted_a, x + y + z}
    end
  end

  def read(filename) do
    data = File.read!(filename)
    l = String.split(String.trim(data), "\n")
    l = Enum.map(l, fn(x) -> String.to_integer(x) end)
    {sorted, ans} = count_inversion(l)
    ans
  end
end