Optimizing an "almost-increasing" array problem

Thanks! I had previously tried a solution that sets a flag when the first bad result is found, but I wrote it so clumsily it didn’t work. Thank you for explaining the underlying reasoning.

oh, my bad then

Can you please check the updated version?

defmodule Example do
  @remove_limit 1

  # function head for a default argument
  def sample(list, previous \\ nil, removed_so_far \\ 0)

  # check if we have reached a remove limit
  def sample(_list, _previous, removed_so_far) when removed_so_far > @remove_limit, do: false

  # if a limit is not reached so far and a list have last item left 
  def sample([_head], _previous, _removed_so_far), do: true

  # if a limit is not reached so far and a list is empty 
  def sample([], _previous, _removed_so_far), do: true

  # ensure nil which as atom is bigger than any integer is not part of check
  def sample([nil | tail], previous, removed_so_far), do: sample(tail, previous, removed_so_far)

  # if first and second item are not a part of an increasing list
  # then function calls itself without a second argument
  # if that would fail (return false) then function calls again itself
  # but this time without a first argument instead
  def sample([first, second | tail], previous, removed_so_far) when first >= second do
    removed_so_far = removed_so_far + 1

    sample([first | tail], previous, removed_so_far) ||
      sample([previous, second | tail], previous, removed_so_far)
  end

  # in any other case we just skip a first item and perform check for a list's tail
  def sample([first, second | tail], _previous, removed_so_far) do
    sample([second | tail], first, removed_so_far)
  end
end

When removing first from unmatched check I have added previous to list in order to perform check properly in that specific case.

Ya know what else has to iterate over the whole list? List.delete_at, especially when called with length(list). A quick benchmark:

Mix.install([:benchee])

list1 = 1..100 |> Enum.to_list()
length1 = length(list1)

list2 = 1..1000 |> Enum.to_list()
length2 = length(list2)

list3 = 1..10000 |> Enum.to_list()
length3 = length(list3)

Benchee.run(
  %{
    "100 elements" => fn -> List.delete_at(list1, length1) end,
    "1000 elements" => fn -> List.delete_at(list2, length2) end,
    "10000 elements" => fn -> List.delete_at(list3, length3) end
  },
  time: 10,
  memory_time: 2
)

produces the output on my machine:

Operating System: macOS
CPU Information: Intel(R) Core(TM) i7-6820HQ CPU @ 2.70GHz
Number of Available Cores: 8
Available memory: 16 GB
Elixir 1.13.4
Erlang 25.0.2

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 10 s
memory time: 2 s
reduction time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 42 s

Benchmarking 100 elements ...
Benchmarking 1000 elements ...
Benchmarking 10000 elements ...

Name                     ips        average  deviation         median         99th %
100 elements        393.26 K        2.54 μs  ±1944.85%        1.85 μs        4.95 μs
1000 elements        80.38 K       12.44 μs   ±142.97%       10.82 μs       42.36 μs
10000 elements        6.85 K      145.95 μs    ±33.72%      143.90 μs      279.72 μs

Comparison: 
100 elements        393.26 K
1000 elements        80.38 K - 4.89x slower +9.90 μs
10000 elements        6.85 K - 57.40x slower +143.41 μs

Memory usage statistics:

Name              Memory usage
100 elements           3.18 KB
1000 elements         20.95 KB - 6.59x memory usage +17.77 KB
10000 elements       224.88 KB - 70.72x memory usage +221.70 KB

Even calling length on the input is not desirable, since it has to traverse the list all the way to the end.

Calling List.delete_at as part of a recursion is a quick way to end up in the O(N^2) Bad Place.

A different way to think about this problem is to ask the question: what are the outcomes of adding an element to the end of an already almost-increasing list?

To express this with functions, we can use Enum.reduce_while/3 because of the control flow it gives us:

Enum.reduce_while(list, initial_state, fn element, state ->
  # keep going:
  {:cont, new_state}
  # give up early:
  {:halt, final_state}
end)

The trick with reduce and friends is to pick the right shape for the “state” data.

In this problem, we have two important parts of the state:

• the last element we want to compare the new one to
• what have we seen so far?
  • almost-increasing with no errors
  • almost-increasing with one error
  • (no third case because we want to give up)

This suggests that “state” is a tuple of {status, last_element}.

Now we need an “initial” value. The empty list is almost-increasing, and we know the minimum value for elements is -105 so we can start with a value that will always be less than the first element of list:

Enum.reduce_while(list, {:all_increasing, -106}, fn element, {last_status, last_element} ->
  ...
end)

(Note: there’s nothing magical about :all_increasing, it’s chosen solely for human readability)

There are two factors that decide what to do next:

• the last state
• the comparison result between last_element and element

so let’s use a case:

Enum.reduce_while(list, {:all_increasing, -106}, fn element, {last_status, last_element} ->
  case {last_status, el > last_element} do

  end
end)

The first case is easy: if the list is almost-increasing and el is bigger, then the list is still almost-increasing and we should next look at element:

Enum.reduce_while(list, {:all_increasing, -106}, fn element, {last_status, last_element} ->
  case {last_status, element > last_element} do
    {:all_increasing, true} ->
      {:cont, {:all_increasing, element}}
  end
end)

The next-easiest case is when we’ve already found a “bad” element and we find another one. In that case, it’s time to give up:

Enum.reduce_while(list, {:all_increasing, -106}, fn element, {last_status, last_element} ->
  case {last_status, element > last_element} do
    {:all_increasing, true} ->
      {:cont, {:all_increasing, element}}

    {:one_wrong, false} ->
      {:halt, :not_increasing}
  end
end)

Almost as easy: if we’ve seen one wrong element but the current one is increasing, keep going:

Enum.reduce_while(list, {:all_increasing, -106}, fn element, {last_status, last_element} ->
  case {last_status, element > last_element} do
    {:all_increasing, true} ->
      {:cont, {:all_increasing, element}}

    {:one_wrong, true} ->
       {:cont, {:one_wrong, element}} 

    {:one_wrong, false} ->
      {:halt, :not_increasing}
  end
end)

The tricky one is if the current element is “bad” but there are no previous errors. In that case, we continue noting that there’s been an error AND skip el (since it’s bad):

Enum.reduce_while(list, {:all_increasing, -106}, fn element, {last_status, last_element} ->
  case {last_status, element > last_element} do
    {:all_increasing, true} ->
      {:cont, {:all_increasing, element}}

    {:all_increasing, false} ->
       {:cont, {:one_wrong, last_element}}

    {:one_wrong, true} ->
       {:cont, {:one_wrong, element}} 

    {:one_wrong, false} ->
      {:halt, :not_increasing}
  end
end)

Without passing last_element in that case, sequences like [1,2,1,2] aren’t correctly detected.

Finally, the result of Enum.reduce_while is the last accumulator so it needs to be cleaned up into the boolean result.

Final code with some cleanup:

defmodule Sequence do
  def almost_increasing(sequence) do
    case Enum.reduce_while(sequence, {:all_increasing, -1000}, &do_almost_increasing/2) do
      {:all_increasing, _} -> true
      {:one_wrong, _} -> true
      :not_increasing -> false
    end
  end

  defp do_almost_increasing(el, {state, last_element}) do
    case {state, el > last_element} do
      {:all_increasing, true} ->
        {:cont, {:all_increasing, el}}

      {:all_increasing, false} ->
        {:cont, {:one_wrong, last_element}}

      {:one_wrong, true} ->
        {:cont, {:one_wrong, el}}

      {:one_wrong, false} ->
        {:halt, :not_increasing}
    end
  end
end

Thanks to you and @cmo for your responses. There are a few test cases that defeat @Eiji’s solution (it incorrectly returns true when given [1,2,1,2]) but it uses tail recursion, which is the right way to go, I think. Here’s what I wound up with:

def solution(sequence) do
    solution(sequence, length(sequence))
end

def solution(sequence, count) when count <= 0 do
    is_ascending?(List.delete_at(sequence, count))
end

def solution(sequence, count) do
   is_ascending?(List.delete_at(sequence, count)) or solution(sequence, count - 1)
end

def is_ascending?([_]),        do: true
def is_ascending?([a,b|tail]), do: b > a and is_ascending?([b|tail])

I think that, in cases where you’re dealing with very long lists, the Enum module is gonna be too slow much of the time because it always enumerates over the whole list. In cases like that, you want tail recursion instead.

How about this one?

defmodule Example do
  @remove_limit 1

  # function head for a default argument
  def sample(list, removed_so_far \\ 0)

  # check if we have reached a remove limit
  def sample(_list, removed_so_far) when removed_so_far > @remove_limit, do: false

  # if a limit is not reached so far and a list have last item left 
  def sample([_head], _removed_so_far), do: true

  # if a limit is not reached so far and a list is empty 
  def sample([], _removed_so_far), do: true

  # if first and second item are not a part of an increasing list
  # then function calls itself without a second argument
  # if that would fail (return false) then function calls again itself
  # but this time without a first argument instead
  def sample([first, second | tail], removed_so_far) when first >= second do
    removed_so_far = removed_so_far + 1
    sample([first | tail], removed_so_far) || sample([second | tail], removed_so_far)
  end

  # in any other case we just skip a first item and perform check for a list's tail
  def sample([_first, second | tail], removed_so_far) do
    sample([second | tail], removed_so_far)
  end
end

Try doing it with recursion, checking each pair (or the one before if you’re skipping this one), rather than checking the entire array every iteration.