Algorithm Solving Issue

Simplify this problem by generalizing it

(Sorry, I swapped the order of k and n.)

If you leave off the last digit of a tight number, you get another tight number, and their last digits differ by at most 1.

Assume you have all the numbers c(n, k, l) of tight numbers of length n with last digit l. Then the number of tight numbers of length n + 1 and last digit l is c(n + 1, k, l) = c(n, k, l - 1) + c(n, k, l) + c(n, k, l + 1).

The base case is simple: n=1 means one tight number, i.e. c(1, k, l) = 1.

Test (Python):

def c(n, k, l):
    if l > k or l < 0:
        return 0
    if n == 1:
        return 1
    return sum(c(n - 1, k, i) for i in range(l - 1, l + 2))

def f(n, k):
    tight = sum(c(n, k, l) for l in range(k + 1))
    return tight / (k + 1) ** n

Examples:

>>> print(f(1,4))
1.0
>>> print(f(4, 1))
1.0
>>> print(f(5, 2))
0.4074074074074074
>>> print(f(5, 3))
0.173828125
>>> print(f(7, 8))
0.0010129691411338857

For really big numbers, this becomes slow, because the same numbers are computed over and over. These can be cached ("memoized") by adding the following two lines at the start of the program (the second lines decorate the following function c(n, k, l) with a cache):

import functools
@functools.lru_cache()

Example:

>>> f(100,9)
1.0051226793648084e-53

My reading is a little different from yours: as I understand it, the first number is the size of the alphabet, and the second is the length of the words over that alphabet that one must consider, so:

4 1 => 100%

Seems like a matter of definition; the likely rationale is that since the digits in words of length 1 do not have any neighbors, they cannot differ from them by more than 1, independent of the size of the alphabet, so words of length 1 are considered “tight” by definition.

2 5 => 40.74074%

So this is words of length 5 over a ternary (3-digit) alphabet, {0,1,2}. There are, as you observe, 3^5 possible such words. The non-tight words are those (where x means “don't care”) like “xxx02”, “xxx20”, “xx02x”, “xx20x”, “x02xx”, “x20xx”, “02xxx” and “20xxx” which have a 2 adjacent to a zero. Each of these 8 patterns has 27 variations (there are 3 x's in each case, and each can have any of 3 values), but of course there's a lot of overlap: “02020” ends up in 3 of them.

So, if I understand correctly, in the absence of any short-cuts, the solution must be to generate all the combinations, examine pairs of adjacent digits in every combination (you can bug out early once you know that a word is not tight), and then count either the number of tight or non-tight words (either gives you the other, since you know the total size of the set.

Our problem is to find the number of tight words with length n, ie a[1 .. n]. Below is a solution based on dynamic programming. The idea is to assume that we have the answer up to length i - 1, we construct an equation to calculate answer for length i.

Let C(i, d) is the total number of tight words that has length i, ie a[1 .. i], with the final digit a[i] = d, 0 <= d <= k. Observing that a[i - 1] - 1 <= a[i] <= a[i - 1] - 1 (definition of tight word), we have the following recursive relationship:

For i = 1: 
  C(1, d) = 1

For i > 1: 
  C(i, d) = 
    C(i - 1, 0) + C(i - 1, 1) -- if d == 0
    C(i - 1, k - 1) + C(i - 1, k) -- if d == k
    C(i - 1, d - 1) + C(i - 1, d) + C(i - 1, d + 1) -- otherwise

Then what we're after is simply:

N(n) = C(n, 0) + C(n, 1) + ... C(n, k)

CODE:

And this is a nodejs program that was tested to generate same answers in your sample input (it's not yet dynamic programming since I haven't cache C(i, p) -- there are lot of repeated calculations, but should be easy to do that)

// tight_words.js

var k = 2;
var n = 5;

function N(i) {
    var n = 0;

    for (d = 0; d <= k; ++d)
        n += C(i, d);

    return n;
}

function C(i, d) {
    if (i == 1)
        return 1;

    if (d == 0)
        return C(i - 1, 0) + C(i - 1, 1);

    if (d == k)
        return C(i - 1, k - 1) + C(i - 1, k);

    return C(i - 1, d - 1) + C(i - 1, d) + C(i - 1, d + 1);
}

var total = Math.pow(k + 1, n);
var c = N(n);
console.log('k = ' + k + ', n = ' + n);
console.log('==> percentage = ' + c / total);

Based on WolframH's answer, I tried the problem for the sample inputs in C++ and it seems to work. I also tried the phython solution, which worked fine with the sample inputs. What comes interesting is, when I increased the input to a bit bigger numbers (i.e., 3 and 18), both solutions I have in C++ and in phython hang for indeterminate time.

What has gone wrong?

Very coincidentally I just happened to go through my Dynamic Programming notes yesterday night, and read about the Weighted Independent Set Problem. Aha! We are doing far too much work than we are supposed to! In:

#include <math.h>
#include <iomanip>
#include <iostream>
using namespace std;

void get_tight_number(int base_max, int length)
{
  double result = 0;
  int _tight_numbers = 0;
  double total = pow(base_max + 1, length);
  for (int i = 0; i <= base_max; ++i)
  {
    _tight_numbers += get_tight_number_help(base_max, length, i);
  }
  result = 100 * _tight_numbers / total;
  cout << fixed << setprecision(5) << result << "\n";
}

int get_tight_number_help(int base_max, int length, int endwith)
{
  cout << "Length: " << length << "endwith: " << endwith << endl;
  if (length < 1 || endwith < 0 || endwith > base_max)
    return 0;
  if (length == 1)
  {
    return 1;
  } else 
  {
    return get_tight_number_help(base_max, length - 1, endwith)
         + get_tight_number_help(base_max, length - 1, endwith + 1)
         + get_tight_number_help(base_max, length - 1, endwith - 1);
  }
}

int main()
{
  get_tight_number(8, 7);
  return 0;
}

With bunch of prints and correct result 0.10130. If I do grep "endwith:" | wc -l I get 7719, which means, for this input, the helper function was called more than 7000 times! To just have an idea how many times it is called on other inputs, I got:

Input    #
8, 8     22254
8, 6     2682
8, 5     933

not very good... We are doing too much recalculation. Instead I put together the bottom up solution for the reference array:

int** tight_number_bottom_up(int base_max, int length)
{
  int** result = new int*[base_max + 1];
  for (int i = 0; i < base_max + 1; ++i)
  {
    result[i] = new int[length];
  }
  //Ends with i, i.e., looping over them
  for (int j = 0; j < length + 1; ++j)
  {
    for (int i = 0; i < base_max + 1; ++i)
    {
      if (j == 0)
      {
        result[i][j] = 0;
      } else if (j == 1)
      {
        result[i][j] = 1;
      } else
      {
        int bigger = i == base_max ? 0 : result[i + 1][j - 1];
        cout << "bigger: " << bigger << endl;
        int smaller = i == 0 ? 0 : result[i - 1][j - 1];
        cout << "smaller: " << smaller << endl;
        result[i][j] = result[i][j - 1] + bigger + smaller;
      }
    }
  }
  return result;
}

I am sure that the number of iterations in forming the bottom up table is maximum (base_max + 1) * (length + 1), happy that I finished writing and happy that it gives the correct results.

Follow-up question (if you are still with me)

double seems to be not enough for inputs like 9, 100 or even 9, 50, what can I do to make a "long"er double?