Algorithm Problem

Question

[Demand]
The given is the alphabet {0, 1, ..., k}, 0 & leq; k? 9. We say that a word of length n over this alphabet is dense if any two digits of the neighbor in the word do not differ by more than 1. The input is a sequence of lines, each line contains two integers k and n, 1 & leq; n? 100. For each input line, output the percentage of compressed words of length n over the alphabet {0, 1, ..., k} with 5 fractional digits.

[entrance]

4 1 2 5 3 5 8 7 

[output]

 100.00000 40.74074 17.38281 0.10130 

First of all, I can’t understand this quiz. Example if input 2, 5 . I do not know why the answer is 40.74074.

In this situation, if it is "tight." The average should be 1.

Example

 00000 00001 00002 00010 00011 00012 .... 

So,

The whole case here: 3 ⁵ = 243

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

So, the output should be 81/243 = 0.3333333333333333333 = 33.333333%

Did I miss something?

And any good algorithm to solve this problem?

Answer 1

Here is some ruby ​​code whose output matches the sample data:

 #!/usr/bin/env ruby def isTight( x ) for i in (1..x.length-1) return false if 1 < (x[i].to_i-x[i-1].to_i).abs end return true end def getWord( x, base, n ) retval = [] 1.upto(n) do x, r = x.divmod(base) retval.unshift r end retval.join end def percent( k, n ) nwords = (k+1) ** n count = 0 for i in (0..nwords-1) word = getWord( i, k+1, n ) count += 1 if isTight( word ) end return 100.0 * count / nwords end STDIN.each_line do |line| line.chomp! puts line+' '+percent(*line.split(' ').map { |i| i.to_i }).to_s end 

It takes 4 lines

 4 1 2 5 3 5 8 7 

as inputs and outputs

 4 1 100.0 2 5 40.74074074074074 3 5 17.3828125 8 7 0.10129691411338856 

(sorry not 5 decimal places)

---

EDIT: In practice, you will undoubtedly want to use the WolframH recursive solution included here for completeness:

 #!/usr/bin/env ruby $cache = Hash.new def count( k, n, last ) key = "#{k}:#{n}:#{last}" return $cache[key] if $cache.has_key?(key) return 0 if !(0 <= last && last <= k) # last digit must be in range return 1 if n == 1 # single digit numbers are always tight return $cache[key] = (-1..1).inject(0) { |sum,i| sum + count(k,n-1,last+i) } end def percent( k, n ) ntight = (0..k+1).inject(0) { |sum,last| sum + count(k,n,last) } return 100.0 * ntight / (k+1)**n end puts percent( 1, 4 ) puts percent( 2, 5 ) puts percent( 3, 5 ) puts percent( 8, 7 ) puts percent( 9, 100 ) 

Using the $ cache, this runs very quickly on the i64-364 processor (Intel Core i3-3240 with Intel Core i3-340 processor):

 $ time ./tight.rb 100.0 40.74074074074074 17.3828125 0.10129691411338856 1.0051226793648083e-51 real 0m0.016s user 0m0.010s sys 0m0.005s 

Answer 2

Simplify this problem by summarizing it.

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

If you leave the last digit of a dense number, you will get another dense number, and their last digits differ by no more than 1 .

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

The main case is simple: n=1 means one dense 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 large numbers, this becomes slow because the same numbers are calculated again and again. They can be cached ("memoized") by adding the following two lines at the beginning of the program (the second line will decorate the following function c(n, k, l) cache):

 import functools @functools.lru_cache() 

Example:

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

Answer 3

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 words over this alphabet, which must be taken into account, so:

 4 1 => 100% 

It seems to be a matter of definition; the likely justification is that since the numbers in words of length 1 have no neighbors, they cannot differ from them by more than 1, regardless of the size of the alphabet, so words of length 1 are considered to be "dense" by definition.

2 5 => 40.74074%

So, these are words of length 5 over a triple (3-digit) alphabet, {0,1,2}. There are, as you noticed, 3-5 possible words. Non-rigid words are those (where x means "don't care"), such as "xxx02", "xxx20", "xx02x", "xx20x", "x02xx", "x20xx", "02xxx" and "20xxx" 2 adjacent to zero. Each of these 8 patterns has 27 variations (in each case 3 x, and each can have any of 3 values), but, of course, there are many overlaps: "02020" ends with 3 of them.

So, if I understand correctly, in the absence of any short abbreviations, the solution should be to generate all combinations, to study pairs of adjacent digits in each combination (you can make mistakes early, as soon as you know that the word is not dense), and then count the number of hard or soft words (or gives you another, as you know the total size of the set.

Answer 4

Our task is to find the number of hard words with length n, i.e. a[1 .. n] . The following is a solution based on dynamic programming. The idea is to assume that we answer up to length i - 1 , we build an equation to calculate the answer for length i .

Let C(i, d) be the total number of hard words with length i, i.e. a[1 .. i] , with the last digit a[i] = d , 0 <= d <= k . Observing that a[i - 1] - 1 <= a[i] <= a[i - 1] - 1 (definition of a dense word), we have the following recursive relation:

 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 we just:

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

CODE:

And this is the nodejs program, which was tested to get the same answers in your input example (this is not dynamic programming yet, since I don't have C(i, p) cache - there are a lot of repeated calculations, but it 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); 

Answer 5

Based on WolframH's answer, I tried the problem for sample inputs in C ++ and it seems to work. I also tried the phython solution, which worked fine with input samples. The interesting thing is that when I increased the input to larger numbers (i.e. 3 and 18), both solutions that I have in C ++ and in phython hang for an indefinite time,

Something went wrong?

Quite by accident, I just went through my Dynamic Programming last night's notes and read about The Problem of Weighted Independent Typing . Yeah! We are doing too much work than we expect! 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 a bunch of prints and the correct result is 0.10130 . If I do grep "endwith:" | wc -l grep "endwith:" | wc -l , I get 7719 , which means that an auxiliary function was called more than 7000 times for this input! To just understand 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 recount. Instead, I put together a bottom up solution for a 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, ie, 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 when forming the bottom table is the maximum (base_max + 1) * (length + 1) , pleased that I finished writing and am happy that it gives the correct results.

Follow up question (if you are still with me)

double seems insufficient for inputs like 9, 100 or even 9, 50 , what can I do to make a long double?