Algorithm Solving Issue

Question

[Requirement]
Given is an alphabet {0, 1, ... , k}, 0 ≤ k ≤ 9. We say that a word of length n over this alphabet is tight if any two neighbor digits in the word do not differ by more than 1. Input is a sequence of lines, each line contains two integer numbers k and n, 1 ≤ n ≤ 100. For each line of input, output the percentage of tight words of length n over the alphabet {0, 1, ... , k} with 5 fractional digits.

[Input]

4 1
2 5
3 5
8 7

[Output]

100.00000
40.74074
17.38281
0.10130

First, I can't understand this quiz. Example, if the input is 2, 5. I don't know why the answer is 40.74074.

In this situation, if it will be "tight". The middle number has to be 1.

Example,

00000 00001 00002
00010 00011 00012
....

So,

All of the case in here is, 3⁵ = 243

And the last digit has to be 1, so 3⁴ = 81 will be the "tight" case.

So, the output has to be 81/243 = 0.33333333333333333 = 33.333333%

Did i missed something?

And any good algorithm to solve this?

Answer 1

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

Answer 2

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.