Strictly Increasing Sequence of Integers

[leorio]

Hey, guys. This is a problem on CodeFights that I'm trying to solve. Given a sequence of integers as an array, I have to determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.
I am passing 15/17 test cases, and here are the two test cases I am failing.

Input: sequence: [40, 50, 60, 10, 20, 30]
Output: true
Expected Output: false

Input: sequence: [1, 2, 5, 3, 5]
Output: false
Expected Output: true

I know where the flaws in my code occurs for these test cases, but I'm not sure how to fix this. I want to make my code as simple as possible.

  bool almostIncreasingSequence(std::vector<int> sequence) 
{        int count = 0; 
        for (int i = 0; i < sequence.size() - 1; i++)
        {
                 if (sequence[i + 1] <= sequence[i])
                 {
                         count++;
                         if (sequence[i + 2] == sequence[i])
                         {
                                 count++;

                         }
                 }
                 if(count > 1)
                {
                        return false;
                }
             
                  
        
        } return true;
                
} 

[jonnin]

(sequence[i + 2] == sequence[i])
I really don't understand this equality check.

AND it would appear that on occasion i+2 > size of vector (??)

---------

seems to me like all you need is
for(i = 0; i<size-2; i++) //say size is 10, its indexed 0-9, so your last check is [9] vs [8] where 8 is size-2...
 if s[i+1] > s[i]
    c++;

if c > 1, fail else succeed.

[JLBorges]

bool almost_strictly_increasing( const std::vector<int>& seq )
{
    if( seq.size() < 2 ) return true ;

    int cnt_non_increasing = 0 ;

    int prev = seq.front() ;
    for( std::size_t i = 1 ; i < seq.size() && cnt_non_increasing < 2 ; ++i )
    {
        if( prev < seq[i] ) prev = seq[i] ;

        else ++cnt_non_increasing ; 
    }

    return cnt_non_increasing < 2 ;
}

[Duthomhas]

@JLBorges
You didn’t check that against OP’s second sequence. (Both prev and i need more careful adjustment in the else clause. I also recommend making prev an index into seq instead of a value.)

[JLBorges]

#include <iostream>
#include <vector>

bool almost_strictly_increasing( const std::vector<int>& seq )
{
    if( seq.size() < 2 ) return true ;

    int cnt_non_increasing = 0 ;

    int prev = seq.front() ;
    for( std::size_t i = 1 ; i < seq.size() && cnt_non_increasing < 2 ; ++i )
    {
        if( prev < seq[i] ) prev = seq[i] ;
        else ++cnt_non_increasing ;
    }

    return cnt_non_increasing < 2 ;
}

bool almost_strictly_non_decreasing( const std::vector<int>& seq )
{
    if( seq.size() < 2 ) return true ;

    int cnt_decreasing = 0 ;

    int prev = seq.front() ;
    for( std::size_t i = 1 ; i < seq.size() && cnt_decreasing < 2 ; ++i )
    {
        if( prev <= seq[i] ) prev = seq[i] ;
        else ++cnt_decreasing ;
    }

    return cnt_decreasing < 2 ;
}

int main()
{
    std::cout << std::boolalpha

              // first sequence
              << almost_strictly_increasing( { 40, 50, 60, 10, 20, 30 } ) << '\n' // false
              << almost_strictly_non_decreasing( { 40, 50, 60, 10, 20, 30 } ) << '\n' // false

              // secons sequence
              << almost_strictly_increasing( { 1, 2, 5, 3, 5 } ) << '\n' // false
              << almost_strictly_non_decreasing( { 1, 2, 5, 3, 5 } ) << '\n' ; // true

}

http://coliru.stacked-crooked.com/a/f2dfb7b695524c89

[lastchance]

1, 2, 5, 3, 5 is almost strictly increasing.

If you remove the middle 5 then the sequence is 1, 2, 3, 5.
That test should return true.

[JLBorges]

That is right.
I see now what Duthomhas meant by "need more careful adjustment in the else clause."

[lastchance]

Somebody else had a go at this problem recently:
http://www.cplusplus.com/forum/beginner/226505/#msg1032980
It's obviously the "in" challenge!
(@rabster's code at the end of that thread also fails this particular test.)

#include <iostream>                        
#include <sstream>
#include <vector>
using namespace std;

template<class T> bool almostIncreasing( const vector<T> &a )
{
   bool available = true;               
   int last = a.size() - 1;
   for ( int i = 1; i <= last; i++ )
   {
      if ( a[i] <= a[i-1] )                         // Must remove either a[i] or a[i-1]
      {                                              
         if ( !available ) return false;            // No lives left; bye-bye
         if ( i == last )  return true;             // Got this far: just remove the last one

         if ( i > 1 )                               // If a[0]>=a[1] remove a[0]; so only check when i > 1
         {
            bool ok = ( a[i-2] < a[i-1] && a[i-1] < a[i+1] )  ||  ( a[i-2] < a[i] && a[i] < a[i+1] );
            if ( !ok ) return false;                // Neither removal will work
         }
         available = false;                         // Last life just went
      }
   }
   return true;
}

//======================================================================

int main()
{
   vector<int> a;
   int i;
   string line;
   cout << "Input an array as a single line: ";   getline( cin, line );
   stringstream ss( line );
   while( ss >> i ) a.push_back( i );

   cout << "Almost strictly increasing? " << boolalpha << almostIncreasing( a );
}

Input an array as a single line: 40 50 60 10 20 30
Almost strictly increasing? false

Input an array as a single line: 1 2 5 3 5
Almost strictly increasing? true

[jonnin]

tricksey ... I see now that mine fails the first seq.

[rabster]

Fixed generic version

#include <algorithm>
#include <iostream>

template<typename T>
bool solveableSequence(const T& container) {
    if (container.size() == 0) {
        return false;
    }
    if (container.size() == 1) {
        return true; //depends on whether or not a sequence with 1 element qualfies
    }
    
    std::size_t operations = 0;
    const auto begin = std::begin(container);
    auto last = begin;
    for (auto iter = last, end = std::prev(std::end(container)); iter != end;) {
        auto next = std::next(iter);
        
        if (!(*last < *next)) { //< is for strict ascending, <= is for loose ascending 
            ++operations;
            if (last != begin) {
                auto prev = std::prev(last);
                if (*prev < *next) {
                    last = next;
                }
                
                if (operations > 1) {
                    return false;
                }   
            }
        }
        else {
            last = next;
        }
        iter = next;
    }
    return operations == 1; // <= for already sorted data;
}
template<typename T>
void solveSequence(const T& container) {
    std::cout << std::boolalpha << solveableSequence(container) << std::endl;
}
using initList = std::initializer_list<int>;
int main() {
    solveSequence(initList{1, 2, 1, 2});
    solveSequence(initList{8, 8, 8, 7, 7, 7});
    solveSequence(initList{1, 2, 2, 3});
    solveSequence(initList{1, 2, 3, 2, 3});
    solveSequence(initList{1, 2, 3, 2, 4});
    solveSequence(initList{1, 2, 3, 6, 5});
    solveSequence(initList{9, 8, 7});
    solveSequence(initList{1, 2, 3, 6, 5, 4});
    solveSequence(initList{1, 2, 5, 3, 5});
    solveSequence(initList{40, 50, 60, 10, 20, 30});
}

[Duthomhas]

This challenge is a little trickier than it appears at first glance.

Here’s my entry.

template <typename Iterator>
bool almost_strictly_increasing( Iterator first, Iterator last )
{
  if (std::distance( first, last ) < 3) return true;
  
  auto u = std::adjacent_find( first, last, std::greater_equal <decltype(*first)> () );
  if (u == last) return true;

  auto v = std::adjacent_find( u + 1, last, std::greater_equal <decltype(*first)> () );
  if (v != last) return false;
    
  auto a = (  u ==  first) or (u[-1] < u[1]);
  auto b = (++u == --last) or (u[-1] < u[1]);
  
  return a or b;
}

template <typename T>
bool almost_strictly_increasing( const std::vector <T> & seq )
{
  return almost_strictly_increasing( seq.begin(), seq.end() );
}

Just so you all know, I did some pretty extensive testing with this (which y’all should have done!) and lastchance is the only other poster who got it right.

And by extensive, I mean permuting every possible combination of a sequence and testing against a no-fail (but O(n³)) algorithm.

────────────────────────────────────────────────────────────

@leorio
Your idea of testing against items separated by a middle item is a good one. It fails, however, in specific edge cases.

What you need to do is verify that there are a maximum of two strictly increasing sequences. At the join between the sequences, you have two possible cases:

 • the first element of the disordered pair needs to be ignored

      1 2 5 3 4
          ↑

 • the second element of the disordered pair needs to be ignored

      6 7 5
          ↑

Both of these are edge cases. The first may occur as the first item in a sequence, and the second may occur as the last.

So you must test for those for conditions.

────────────────────────────────────────────────────────────

@rabster

Perform automated tests over a permuted sequence ([Y]/n)?
Values to permute? 1 2 3 4
1 2 3 4 ----FAIL (true, false)
1 2 4 3 pass (true)
1 3 2 4 pass (true)
1 3 4 2 pass (true)
1 4 2 3 pass (true)
1 4 3 2 pass (false)
2 1 3 4 pass (true)
2 1 4 3 pass (false)
2 3 1 4 pass (true)
2 3 4 1 pass (true)
2 4 1 3 pass (false)
2 4 3 1 pass (false)
3 1 2 4 ----FAIL (true, false)
3 1 4 2 pass (false)
3 2 1 4 pass (false)
3 2 4 1 pass (false)
3 4 1 2 pass (false)
3 4 2 1 pass (false)
4 1 2 3 ----FAIL (true, false)
4 1 3 2 pass (false)
4 2 1 3 pass (false)
4 2 3 1 pass (false)
4 3 1 2 pass (false)
4 3 2 1 pass (false)
FAILED 3 of 24 tests.

Perform automated tests over a permuted sequence ([Y]/n)?
Values to permute? 1 5 5 7
1 5 5 7 pass (true)
1 5 7 5 pass (true)
1 7 5 5 pass (false)
5 1 5 7 ----FAIL (true, false)
5 1 7 5 pass (false)
5 5 1 7 pass (false)
5 5 7 1 pass (false)
5 7 1 5 pass (false)
5 7 5 1 pass (false)
7 1 5 5 pass (false)
7 5 1 5 pass (false)
7 5 5 1 pass (false)
FAILED 1 of 12 tests.

You also erroneously return false for an empty sequence. By definition, an empty sequence is sorted.

Hope this helps.

[rabster]

Yeah, I should have tested against more values but at the time of writing I was at school and a bit rushed. I'll make sure to test in these kinds of situations.

#include <algorithm>
#include <iostream>

template<typename T>
bool solveableSequence(const T& container) {
    if (container.size() <= 1) {
        return true; 
    }
    
    const auto begin = std::begin(container);
    auto last = begin;
    std::size_t operations = 0;
    
    for (auto iter = last, end = std::prev(std::end(container)); iter != end;) {
        auto next = std::next(iter);
        
        if (!(*last < *next)) { //< is for strict ascending, <= is for loose ascending 
            if (operations) {
                return false;
            }
            ++operations;
            
            if (last != begin) {
                auto prev = std::prev(last);
                if (*prev < *next) {
                    last = next;
                }   
            }
            else if (*next < *last) {
                last = next;
            }
        }
        else {
            last = next;
        }
        iter = next;
    }
    return operations <= 1; // <= for already sorted data;
}
template<typename T>
void solveSequence(const T& container) {
    std::cout << std::boolalpha << solveableSequence(container) << std::endl;
}
using initList = std::initializer_list<int>;
int main() {
    solveSequence(initList{1, 2, 1, 2});
    solveSequence(initList{8, 8, 8, 7, 7, 7});
    solveSequence(initList{1, 2, 2, 3});
    solveSequence(initList{1, 2, 3, 2, 3});
    solveSequence(initList{1, 2, 3, 2, 4});
    solveSequence(initList{1, 2, 3, 6, 5});
    solveSequence(initList{9, 8, 7});
    solveSequence(initList{1, 2, 3, 6, 5, 4});
    solveSequence(initList{1, 2, 5, 3, 5});
    solveSequence(initList{40, 50, 60, 10, 20, 30});
    solveSequence(initList{5, 1, 5, 7});
}