Reconstructing input to encoder from output

Question

I would like to understand how to solve the Codility ArrayRecovery challenge, but I don't even know what branch of knowledge to consult. Is it combinatorics, optimization, computer science, set theory, or something else?

Edit: The branch of knowledge to consult is constraint programming, particularly constraint propagation. You also need some combinatorics to know that if you take k numbers at a time from the range [1..n], with the restriction that no number can be bigger than the one before it, that works out to be (n+k-1)!/k!(n-1)! possible combinations which is the same as the number of combinations with replacements of n things taken k at a time, which has the mathematical notation . You can read about why it works out like that here.

Peter Norvig provides an excellent example of how to solve this kind of problem with his Sudoku solver.

---

You can read the full description of the ArrayRecovery problem via the link above. The short story is that there is an encoder that takes a sequence of integers in the range 1 up to some given limit (say 100 for our purposes) and for each element of the input sequence outputs the most recently seen integer that is smaller than the current input, or 0 if none exists.

input 1, 2, 3, 4 => output 0, 1, 2, 3
input 2, 4, 3 => output 0, 2, 2

The full task is, given the output (and the range of allowable input), figure out how many possible inputs could have generated it. But before I even get to that calculation, I'm not confident about how to even approach formulating the equation. That is what I am asking for help with. (Of course a full solution would be welcome, too, if it is explained.)

I just look at some possible outputs and wonder. Here are some sample encoder outputs and the inputs I can come up with, with * meaning any valid input and something like > 4 meaning any valid input greater than 4. If needed, inputs are referred to as A1, A2, A3, ... (1-based indexing)

Edit #2

Part of the problem I was having with this challenge is that I did not manually generate the exactly correct sets of possible inputs for an output. I believe the set below is correct now. Look at this answer's edit history if you want to see my earlier mistakes.

output #1: 0, 0, 0, 4 
possible inputs: [>= 4, A1 >= * >= 4, 4, > 4]                     

output #2: 0, 0, 0, 2, 3, 4          # A5 ↴  See more in discussion below
possible inputs: [>= 2, A1 >= * >=2, 2, 3, 4, > 4]

output #3: 0, 0, 0, 4, 3, 1
possible inputs: none # [4, 3, 1, 1 >= * > 4, 4, > 1] but there is no number 1 >= * > 4 

The second input sequence is very tightly constrained compared to the first just by adding 2 more outputs. The third sequence is so constrained as to be impossible.

But the set of constraints on A5 in example #2 is a bit harder to articulate. Of course A5 > O5, that is the basic constraint on all the inputs. But any output > A4 and after O5 has to appear in the input after A4, so A5 has to be an element of the set of numbers that comes after A5 that is also > A4. Since there is only 1 such number (A6 == 4), A5 has to be it, but it gets more complicated if there is a longer string of numbers that follow. (Editor's note: actually it doesn't.)

As the output set gets longer, I worry these constraints just get more complicated and harder to get right. I cannot think of any data structures for efficiently representing these in a way that leads to efficiently calculating the number of possible combinations. I also don't quite see how to algorithmically add constraint sets together.

Here are the constraints I see so far for any given A_n

• A_n > O_n
• A_n <= min(Set of other possible numbers from O₁ to _n-1 > O_n). How to define the set of possible numbers greater than O_n?
  1. Numbers greater than O_n that came after the most recent occurrence of O_n in the input
• A_n >= max(Set of other possible numbers from O₁ to _n-1 < O_n). How to define the set of possible numbers less than O_n?
  1. Actually this set is empty because O_n is, by definition, the largest possible number from the previous input sequence. (Which it not to say it is strictly the largest number from the previous input sequence.)
  2. Any number smaller than O_n that came before the last occurrence of it in the input would be ineligible because of the "nearest" rule. No numbers smaller that O_n could have occurred after the most recent occurrence because of the "nearest" rule and because of the transitive property: if A_i < O_n and A_j < A_i then A_j < O_n
• Then there is the set theory:
  1. A_n must be an element of the set of unaccounted-for elements of the set of O_n+1 to O_m, where m is the smallest m > n such that O_m < O_n. Any output after such O_m and larger than O_m (which A_n is) would have to appear as or after A_m.
  2. An element is unaccounted-for if it is seen in the output but does not appear in the input in a position that is consistent with the rest of the output. Obviously I need a better definition than this in order to code and algorithm to calculate it.

It seems like perhaps some kind of set theory and/or combinatorics or maybe linear algebra would help with figuring out the number of possible sequences that would account for all of the unaccounted-for outputs and fit the other constraints. (Editor's note: actually, things never get that complicated.)

Answer 1

The code below passes all of Codility's tests. The OP added a main function to use it on the command line.

The constraints are not as complex as the OP thinks. In particular, there is never a situation where you need to add a restriction that an input be an element of some set of specific integers seen elsewhere in the output. Every input position has a well-defined minimum and maximum.

The only complication to that rule is that sometimes the maximum is "the value of the previous input" and that input itself has a range. But even then, all the values like that are consecutive and have the same range, so the number of possibilities can be calculated with basic combinatorics, and those inputs as a group are independent of the other inputs (which only serve to set the range), so the possibilities of that group can be combined with the possibilities of other input positions by simple multiplication.

Algorithm overview

The algorithm makes a single pass through the output array updating the possible numbers of input arrays after every span, which is what I am calling repetitions of numbers in the output. (You might say maximal subsequences of the output where every element is identical.) For example, for output 0,1,1,2 we have three spans: 0, 1,1 and 2. When a new span begins, the number of possibilities for the previous span is calculated.

This decision was based on a few observations:

• For spans longer than 1 in length, the minimum value of the input allowed in the first position is whatever the value is of the input in the second position. Calculating the number of possibilities of a span is straightforward combinatorics, but the standard formula requires knowing the range of the numbers and the length of the span.
• Every time the value of the output changes (and a new span beings), that strongly constrains the value of the previous span:
  1. When the output goes up, the only possible reason is that the previous input was the value of the new, higher output and the input corresponding to the position of the new, higher output, was even higher.
  2. When an output goes down, new constraints are established, but those are a bit harder to articulate. The algorithm stores stairs (see below) in order to quantify the constraints imposed when the output goes down

The aim here was to confine the range of possible values for every span. Once we do that accurately, calculating the number of combinations is straightforward.

Because the encoder backtracks looking to output a number that relates to the input in 2 ways, both smaller and closer, we know we can throw out numbers that are larger and farther away. After a small number appears in the output, no larger number from before that position can have any influence on what follows.

So to confine these ranges of input when the output sequence decreased, we need to store stairs - a list of increasingly larger possible values for the position in the original array. E.g for 0,2,5,7,2,4 stairs build up like this: 0, 0,2, 0,2,5, 0,2,5,7, 0,2, 0,2,4.

Using these bounds we can tell for sure that the number in the position of the second 2 (next to last position in the example) must be in (2,5], because 5 is the next stair. If the input were greater than 5, a 5 would have been output in that space instead of a 2. Observe, that if the last number in the encoded array was not 4, but 6, we would exit early returning 0, because we know that the previous number couldn't be bigger than 5.

The complexity is O(n*lg(min(n,m))).

Functions

• CombinationsWithReplacement - counts number of combinations with replacements of size k from n numbers. E.g. for (3, 2) it counts 3,3, 3,2, 3,1, 2,2, 2,1, 1,1, so returns 6 It is the same as choose(n - 1 + k, n - 1).

• nextBigger - finds next bigger element in a range. E.g. for 4 in sub-array 1,2,3,4,5 it returns 5, and in sub-array 1,3 it returns its parameter Max.

• countSpan (lambda) - counts how many different combinations a span we have just passed can have. Consider span 2,2 for 0,2,5,7,2,2,7.

  1. When curr gets to the final position, curr is 7 and prev is the final 2 of the 2,2 span.
  2. It computes maximum and minimum possible values of the prev span. At this point stairs consist of 2,5,7 then maximum possible value is 5 (nextBigger after 2 in the stair 2,5,7). A value of greater than 5 in this span would have output a 5, not a 2.
  3. It computes a minimum value for the span (which is the minimum value for every element in the span), which is prev at this point, (remember curr at this moment equals to 7 and prev to 2). We know for sure that in place of the final 2 output, the original input has to have 7, so the minimum is 7. (This is a consequence of the "output goes up" rule. If we had 7,7,2 and curr would be 2 then the minimum for the previous span (the 7,7) would be 8 which is prev + 1.

  4. It adjusts the number of combinations. For a span of length L with a range of n possibilities (1+max-min), there are possibilities, with k being either L or L-1 depending on what follows the span.

     • For a span followed by a larger number, like 2,2,7, k = L - 1 because the last position of the 2,2 span has to be 7 (the value of the first number after the span).
     • For a span followed by a smaller number, like 7,7,2, k = L because the last element of 7,7 has no special constraints.

  5. Finally, it calls CombinationsWithReplacement to find out the number of branches (or possibilities), computes new res partial results value (remainder values in the modulo arithmetic we are doing), and returns new res value and max for further handling.

• solution - iterates over the given Encoder Output array. In the main loop, while in a span it counts the span length, and at span boundaries it updates res by calling countSpan and possibly updates the stairs.

  • If the current span consists of a bigger number than the previous one, then:
    1. Check validity of the next number. E.g 0,2,5,2,7 is invalid input, becuase there is can't be 7 in the next-to-last position, only 3, or 4, or 5.
    2. It updates the stairs. When we have seen only 0,2, the stairs are 0,2, but after the next 5, the stairs become 0,2,5.
  • If the current span consists of a smaller number then the previous one, then:
    1. It updates stairs. When we have seen only 0,2,5, our stairs are 0,2,5, but after we have seen 0,2,5,2 the stairs become 0,2.
  • After the main loop it accounts for the last span by calling countSpan with -1 which triggers the "output goes down" branch of calculations.
• normalizeMod, extendedEuclidInternal, extendedEuclid, invMod - these auxiliary functions help to deal with modulo arithmetic.

_{For stairs I use storage for the encoded array, as the number of stairs never exceeds current position.}

#include <algorithm>
#include <cassert>
#include <vector>
#include <tuple>

const int Modulus = 1'000'000'007;

int CombinationsWithReplacement(int n, int k);

template <class It>
auto nextBigger(It begin, It end, int value, int Max) {
    auto maxIt = std::upper_bound(begin, end, value);
    auto max = Max;
    if (maxIt != end) {
        max = *maxIt;
    }
    return max;
}

auto solution(std::vector<int> &B, const int Max) {
    auto res = 1;
    const auto size = (int)B.size();
    auto spanLength = 1;
    auto prev = 0;
    // Stairs is the list of numbers which could be smaller than number in the next position
    const auto stairsBegin = B.begin();
    // This includes first entry (zero) into stairs
    // We need to include 0 because we can meet another zero later in encoded array
    // and we need to be able to find in stairs
    auto stairsEnd = stairsBegin + 1;

    auto countSpan = [&](int curr) {
        const auto max = nextBigger(stairsBegin, stairsEnd, prev, Max);
        // At the moment when we switch from the current span to the next span
        // prev is the number from previous span and curr from current.
        // E.g. 1,1,7, when we move to the third position cur = 7 and prev = 1.
        // Observe that, in this case minimum value possible in place of any of 1's can be at least 2=1+1=prev+1.
        // But if we consider 7, then we have even more stringent condition for numbers in place of 1, it is 7
        const auto min = std::max(prev + 1, curr);
        const bool countLast = prev > curr;
        const auto branchesCount = CombinationsWithReplacement(max - min + 1, spanLength - (countLast ? 0 : 1));
        return std::make_pair(res * (long long)branchesCount % Modulus, max);
    };

    for (int i = 1; i < size; ++i) {
        const auto curr = B[i];
        if (curr == prev) {
            ++spanLength;
        }
        else {
            int max;
            std::tie(res, max) = countSpan(curr);
            if (prev < curr) {
                if (curr > max) {
                    // 0,1,5,1,7 - invalid because number in the fourth position lies in [2,5]
                    // and so in the fifth encoded position we can't something bigger than 5
                    return 0;
                }
                // It is time to possibly shrink stairs.
                // E.g if we had stairs 0,2,4,9,17 and current value is 5,
                // then we no more interested in 9 and 17, and we change stairs to 0,2,4,5.
                // That's because any number bigger than 9 or 17 also bigger than 5.
                const auto s = std::lower_bound(stairsBegin, stairsEnd, curr);
                stairsEnd = s;
                *stairsEnd++ = curr;
            }
            else {
                assert(curr < prev);
                auto it = std::lower_bound(stairsBegin, stairsEnd, curr);
                if (it == stairsEnd || *it != curr) {
                    // 0,5,1 is invalid sequence because original sequence lloks like this 5,>5,>1
                    // and there is no 1 in any of the two first positions, so
                    // it can't appear in the third position of the encoded array
                    return 0;
                }
            }
            spanLength = 1;
        }
        prev = curr;
    }
    res = countSpan(-1).first;
    return res;
}

template <class T> T normalizeMod(T a, T m) {
    if (a < 0) return a + m;
    return a;
}

template <class T> std::pair<T, std::pair<T, T>> extendedEuclidInternal(T a, T b) {
    T old_x = 1;
    T old_y = 0;
    T x = 0;
    T y = 1;
    while (true) {
        T q = a / b;
        T t = a - b * q;
        if (t == 0) {
            break;
        }
        a = b;
        b = t;
        t = x; x = old_x - x * q; old_x = t;
        t = y; y = old_y - y * q; old_y = t;
    }
    return std::make_pair(b, std::make_pair(x, y));
}

// Returns gcd and Bezout's coefficients
template <class T> std::pair<T, std::pair<T, T>> extendedEuclid(T a, T b) {
    if (a > b) {
        if (b == 0) return std::make_pair(a, std::make_pair(1, 0));
        return extendedEuclidInternal(a, b);
    }
    else {
        if (a == 0) return std::make_pair(b, std::make_pair(0, 1));
        auto p = extendedEuclidInternal(b, a);
        std::swap(p.second.first, p.second.second);
        return p;
    }
}

template <class T> T invMod(T a, T m) {
    auto p = extendedEuclid(a, m);
    assert(p.first == 1);
    return normalizeMod(p.second.first, m);
}


int CombinationsWithReplacement(int n, int k) {
    int res = 1;
    for (long long i = n; i < n + k; ++i) {
        res = res * i % Modulus;
    }
    int denom = 1;
    for (long long i = k; i > 0; --i) {
        denom = denom * i % Modulus;
    }
    res = res * (long long)invMod(denom, Modulus) % Modulus;
    return res;
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
// Only the above is needed for the Codility challenge. Below is to run on the command line.
//
// Compile with: gcc -std=gnu++14 -lc++ -lstdc++ array_recovery.cpp
//
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <string.h>

// Usage: 0 1 2,3, 4 M
// Last arg is M, the max value for an input.
// Remaining args are B (the output of the encoder) separated by commas and/or spaces
// Parentheses and brackets are ignored, so you can use the same input form as Codility's tests: ([1,2,3], M)
int main(int argc, char* argv[]) {
  int Max;
  std::vector<int> B;
  const char* delim = " ,[]()";

  if (argc < 2 ) {
    printf("Usage: %s M 0 1 2,3, 4... \n", argv[0]);
    return 1;
  }

  for (int i = 1; i < argc; i++) {
    char* parse;
    parse = strtok(argv[i], delim);
    while (parse != NULL)
    {
       B.push_back(atoi(parse));
       parse = strtok (NULL, delim);
    }
  }
  Max = B.back();
  B.pop_back();

  printf("%d\n", solution(B, Max));
  return 0;
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
// Only the above is needed for the Codility challenge. Below is to run on the command line.
//
// Compile with: gcc -std=gnu++14 -lc++ -lstdc++ array_recovery.cpp
//
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <string.h>

// Usage: M 0 1 2,3, 4
// first arg is M, the max value for an input.
// remaining args are B (the output of the encoder) separated by commas and/or spaces
int main(int argc, char* argv[]) {
  int Max;
  std::vector<int> B;
  const char* delim = " ,";

  if (argc < 3 ) {
    printf("Usage: %s M 0 1 2,3, 4... \n", argv[0]);
    return 1;
  }

  Max = atoi(argv[1]);
  for (int i = 2; i < argc; i++) {
    char* parse;
    parse = strtok(argv[i], delim);
    while (parse != NULL)
    {
       B.push_back(atoi(parse));
       parse = strtok (NULL, delim);
    }
  }


  printf("%d\n", solution(B, Max));
  return 0;
}

Let's see an example:

Max = 5
Array is
0 1 3 0 1 1 3
1
1 2..5
1 3 4..5
1 3 4..5 1
1 3 4..5 1 2..5
1 3 4..5 1 2..5 >=..2 (sorry, for a cumbersome way of writing)
1 3 4..5 1 3..5 >=..3 4..5
Now count:
1 1 2 1 3 2 which amounts to 12 total.

Answer 2

Here's an idea. One known method to construct the output is to use a stack. We pop it while the element is greater or equal, then output the smaller element if it exists, then push the greater element onto the stack. Now what if we attempted to do this backwards from the output?

First we'll demonstrate the stack method using the c∅dility example.

[2, 5, 3, 7, 9, 6]
2: output 0, stack [2]
5: output 2, stack [2,5]
3: pop 5, output, 2, stack [2,3]
7: output 3, stack [2,3,7]
... etc.

Final output: [0, 2, 2, 3, 7, 3]

Now let's try reconstruction! We'll use stack both as the imaginary stack and as the reconstituted input:

(Input: [2, 5, 3, 7, 9, 6])
Output: [0, 2, 2, 3, 7, 3]

* Something >3 that reached 3 in the stack
stack = [3, 3 < *]

* Something >7 that reached 7 in the stack
but both of those would've popped before 3
stack = [3, 7, 7 < x, 3 < * <= x]

* Something >3, 7 qualifies
stack = [3, 7, 7 < x, 3 < * <= x]

* Something >2, 3 qualifies
stack = [2, 3, 7, 7 < x, 3 < * <= x]

* Something >2 and >=3 since 3 reached 2
stack = [2, 2 < *, 3, 7, 7 < x, 3 < * <= x]

Let's attempt your examples:

Example 1:

[0, 0, 0, 2, 3, 4]

* Something >4
stack = [4, 4 < *]

* Something >3, 4 qualifies
stack = [3, 4, 4 < *]

* Something >2, 3 qualifies
stack = [2, 3, 4, 4 < *]

* The rest is non-increasing with lowerbound 2
stack = [y >= x, x >= 2, 2, 3, 4, >4]

Example 2:

[0, 0, 0, 4]

* Something >4
stack [4, 4 < *]

* Non-increasing
stack = [z >= y, y >= 4, 4, 4 < *]

Calculating the number of combinations is achieved by multiplying together the possibilities for all the sections. A section is either a bounded single cell; or a bound, non-increasing subarray of one or more cells. To calculate the latter we use the multi-choose binomial, (n + k - 1) choose (k - 1). Consider that we can express the differences between the cells of a bound, non-increasing sequence of 3 cells as:

(ub - cell_3) + (cell_3 - cell_2) + (cell_2 - cell_1) + (cell_1 - lb) = ub - lb

Then the number of ways to distribute ub - lb into (x + 1) cells is

(n + k - 1) choose (k - 1)
or
(ub - lb + x) choose x

For example, the number of non-increasing sequences between
(3,4) in two cells is (4 - 3 + 2) choose 2 = 3: [3,3] [4,3] [4,4]

And the number of non-increasing sequences between
(3,4) in three cells is (4 - 3 + 3) choose 3 = 4: [3,3,3] [4,3,3] [4,4,3] [4,4,4]

(Explanation attributed to Brian M. Scott.)

Rough JavaScript sketch (the code is unreliable; it's only meant to illustrate the encoding. The encoder lists [lower_bound, upper_bound], or a non-increasing sequence as [non_inc, length, lower_bound, upper_bound]):

function f(A, M){
  console.log(JSON.stringify(A), M);
  let i = A.length - 1;
  let last = A[i];
  let s = [[last,last]];
  if (A[i-1] == last){
    let d = 1;
    s.splice(1,0,['non_inc',d++,last,M]);
    while (i > 0 && A[i-1] == last){
      s.splice(1,0,['non_inc',d++,last,M]);
      i--
    }
  } else {
    s.push([last+1,M]);
    i--;
  }
  if (i == 0)
    s.splice(0,1);

  for (; i>0; i--){
    let x = A[i];

    if (x < s[0][0])
      s = [[x,x]].concat(s);

    if (x > s[0][0]){
      let [l, _l] = s[0];
      let [lb, ub] = s[1];
      s[0] = [x+1, M];
      s[1] = [lb, x];
      s = [[l,_l], [x,x]].concat(s);
    }

    if (x == s[0][0]){
      let [l,_l] = s[0];
      let [lb, ub] = s[1];
      let d = 1;
      s.splice(0,1);
      while (i > 0 && A[i-1] == x){
        s =
    [['non_inc', d++, lb, M]].concat(s);
        i--;
      }
      if (i > 0)
        s = [[l,_l]].concat(s);
    }
  }

  // dirty fix
  if (s[0][0] == 0)
    s.splice(0,1);

  return s; 
}

var a = [2, 5, 3, 7, 9, 6]
var b = [0, 2, 2, 3, 7, 3]
console.log(JSON.stringify(a));
console.log(JSON.stringify(f(b,10)));
b = [0,0,0,4]
console.log(JSON.stringify(f(b,10)));
b = [0,2,0,0,0,4]
console.log(JSON.stringify(f(b,10)));
b = [0,0,0,2,3,4]
console.log(JSON.stringify(f(b,10)));
b = [0,2,2]
console.log(JSON.stringify(f(b,4)));
b = [0,3,5,6]
console.log(JSON.stringify(f(b,10)));
b = [0,0,3,0]
console.log(JSON.stringify(f(b,10)));