Return to Revisions

I originally wrote a way over-complicated answer to this. For whatever reason I missed the much simpler solutions. AJFaraday, however, was a lot smarter about things, and posted a nice answer (go upvote that!).

Still, I feel the same thing can be accomplished in a more Ruby-esque manner. Namely:

def almost_increasing_sequence?(array)
  breaks = array.each_cons(2).count { |a, b| a >= b }
  breaks <= 1
end

which basically says, "for every two consecutive elements, count the ones that aren't increasing (i.e. sequence breaks) and if that count end up greater than 1, the sequence can't be 'fixed'".

AJFaraday also added a tolerance argument to the method; that too can be added here (and the method shortened while we're at it):

def almost_increasing_sequence?(array, tolerance = 1)
  array.each_cons(2).count { |a, b| a >= b } <= tolerance
end

The major difference, however, is that this will work its way through the entire array before delivering a verdict - even if the array can be deemed unfixable almost immediately.

An early return version can however be made, for instance by using #reduce to keep track of the sequence breaks:

def almost_increasing_sequence?(array, tolerance = 1)
  array.each_cons(2).reduce(0) do |breaks, (a, b)|
    breaks += 1 if a >= b
    return false if breaks > tolerance
    breaks
  end
  true
end

My earlier answer included a section on testing, which I'll include here, since it's still relevant, regardless of the exact implementation (which is how tests should work). The only thing missing (as that came about after I written it), is the idea of a tolerance argument. Adding tests for that functionality is however left as an exercise to the reader.

For testing, there are a lot of good test frameworks in Ruby (and I highly encourage you to look into them!), but for something this simple it's quicker to write something yourself:

[
  [[1, 2, 3, 4, 99, 5, 6], true],
  [[1, 3, 2], true],
  [[10, 1, 2, 3, 4, 5], true],
  [[0, -2, 5, 6], true],
  [[1, 2, 3, 4, 3, 6], true],
  [[1, 1], true],
  [[100, 200, 300, 400, 99, 500, 600], true],
  [[1, 2, 1, 2], false],
  [[1, 2, 3, 4, 5, 3, 5, 6], false],
  [[40, 50, 60, 10, 20, 30], false],
  [[1, 3, 2, 1], false],
  [[1, 4, 10, 4, 2] , false],
  [[1, 1, 1, 2, 3], false],
  [[10, 1, 2, 3, 4, 5, 6], true],
  [[5, 7, 8, 90, 91, 92, 93], true]
].each do |array, expected|
  if almost_increasing_sequence?(array) != expected
    puts "FAIL Should get #{expected} for #{array}"
  else
    puts "PASS"
  end
end

Or, if you want, you can use minitest (included in Ruby's stdlib since 2.0) for more formal testing (I prefer the spec style, as I usually use RSpec, not minitest):

require 'minitest/autorun'

def almost_increasing_sequence?(array, tolerance = 1)
  # implementation here
end

describe 'almost_increasing_sequence?' do
  it 'returns true for an already increasing sequence' do
    almost_increasing_sequence?((1..10).to_a).must_equal true
  end

  it 'returns true for an empty sequence' do
    almost_increasing_sequence?([]).must_equal true
  end

  it 'returns true for a 1- or 2-element sequence' do
    almost_increasing_sequence?([1]).must_equal true
    almost_increasing_sequence?([100, 1]).must_equal true
  end

  it 'returns false for a "flat" sequence' do
    almost_increasing_sequence?([1] * 10).must_equal false
  end

  it 'returns false for a sequence with multiple "breaks"' do
    almost_increasing_sequence?([1, 99, 2, 99, 4]).must_equal false
  end

  it 'returns true if removing the greater side of the break fixes the sequence' do
    almost_increasing_sequence?([1, 99, 2, 3]).must_equal true
  end

  it 'returns true if removing the lesser side of the break fixes the sequence' do
    almost_increasing_sequence?([1, 2, 1, 3]).must_equal true
  end
end

Again, full specs aren't necessary, but writing it out helps break the problem down, rather than just staring at some example input and trying to figure out why it doesn't work.