Check if a spelled number is in a range in C++

I want to check the (numeric) input against a list of ranges (min,max) while the input is partially typed in; in other words, I need an elegant algorithm to check the prefix of a number against a range (without using regular expressions).

Sample testcases:

 1 is in (  5,   9) -> false
 6 is in (  5,   9) -> true
 1 is in (  5,  11) -> true  (as 10 and 11 are in the range)
 1 is in (  5, 200) -> true  (as e.g. 12 and 135 are in the range)
11 is in (  5,  12) -> true
13 is in (  5,  12) -> false 
13 is in (  5,  22) -> true
13 is in (  5, 200) -> true  (as 130 is in the range)
 2 is in (100, 300) -> true  (as 200 is in the range)

Do you have any idea?

Solution 1:

I believe it's true that the input is acceptable if and only if either:

• It is a prefix substring of the lower bound converted to string

or

• The input followed by any number of additional zeros (possibly none) falls into the range

The first rule is required by e.g. 13 is in range (135, 140). The second rule is required by e.g. 2 is in range (1000, 3000).

The second rule can be efficiently tested by a series of multiplies by 10, until the scaled input exceeds the upper bound.

Solution 2:

An iterative formulation:

bool in_range(int input, int min, int max)
{
  if (input <= 0)
    return true;    // FIXME handle negative and zero-prefixed numbers
  int multiplier = 1;
  while ((input + 1) * multiplier - 1 < min)         // min <= [input]999
    multiplier *= 10;    // TODO consider overflow
  return input * multiplier <= max;                  //        [input]000 <= max
}

A simpler [edit: and more efficent; see below] method is to use truncating integer division:

bool in_range(int input, int min, int max)
{
  if (input <= 0)
    return true;
  while (input < min) {
    min /= 10;
    max /= 10;
  }
  return input <= max;
}

Testing and profiling:

#include <iostream>
#include <chrono>

bool ecatmur_in_range_mul(int input, int min, int max)
{
  int multiplier = 1;
  while ((input + 1) * multiplier - 1 < min)         // min <= [input]999
    multiplier *= 10;    // TODO consider overflow
  return input * multiplier <= max;                  //        [input]000 <= max
}

bool ecatmur_in_range_div(int input, int min, int max)
{
  while (input < min) {
    min /= 10;
    max /= 10;
  }
  return input <= max;
}

bool t12_isInRange(int input, int min, int max)
{
    int multiplier = 1;
    while(input*multiplier <= max)
    {
        if(input >= min / multiplier) return true;
        multiplier *= 10;
    }
    return false;
}

struct algo { bool (*fn)(int, int, int); const char *name; } algos[] = {
{ ecatmur_in_range_mul, "ecatmur_in_range_mul"},
{ ecatmur_in_range_div, "ecatmur_in_range_div"},
{ t12_isInRange, "t12_isInRange"},
};

struct test { int input, min, max; bool result; } tests[] = {
{  1,   5,   9, false },
{  6,   5,   9, true },
{  1,   5,  11, true }, // as 10 and 11 are in the range
{  1,   5, 200, true }, // as e.g. 12 and 135 are in the range
{ 11,   5,  12, true },
{ 13,   5,  12, false },
{ 13,   5,  22, true },
{ 13,   5, 200, true }, // as 130 is in the range
{  2, 100, 300, true }, // as 200 is in the range
{ 13, 135, 140, true }, // Ben Voigt
{ 13, 136, 138, true }, // MSalters
};
int main() {
    for (auto a: algos)
        for (auto t: tests)
            if (a.fn(t.input, t.min, t.max) != t.result)
                std::cout << a.name << "(" << t.input << ", " << t.min << ", " << t.max << ") != "
                    << t.result << "\n";

    for (auto a: algos) {
        std::chrono::time_point<std::chrono::system_clock> start = std::chrono::system_clock::now();
        for (auto t: tests)
            for (int i = 1; i < t.max * 2; ++i)
                for (volatile int j = 0; j < 1000; ++j) {
                    volatile bool r = a.fn(i, t.min, t.max);
                    (void) r;
                }
        std::chrono::time_point<std::chrono::system_clock> end = std::chrono::system_clock::now();
        std::cout << a.name << ": "
            << std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() << '\n';
    }
}

Surprisingly (at least to me) iterated division comes out fastest:

ecatmur_in_range_mul: 17331000
ecatmur_in_range_div: 14711000
t12_isInRange: 15646000

Solution 3:

bool isInRange(int input, int min, int max)
{
    int multiplier = 1;
    while(input*multiplier <= max)
    {
        if(input >= min / multiplier) return true;
        multiplier *= 10;
    }
    return false;
}

It pass all your testcases.