Dynamic Programming for printing additive numbers up to digits n

Question

Edit: I am hoping to get some review / make sure I am understanding dynamic programming correctly.

I am trying to print out all additive numbers up to digits n using dynamic programming. Additive numbers are those like 123, 1235, etc., where the sum of every 2 digits from left to right is equal to the third digit. In this definition, non-trivial additive numbers must necessarily be at least 3 digits long, though for numbers of 2 digits or less one could trivially print out all digits 0-99. Furthermore, this definition implies the set of additive numbers is finite and relatively tiny.

If there is a better definition of an additive number or I have misunderstood it, feel free to point out.

I believe dynamic programming is a good approach to this problem, because the solutions of n - 1 need to be re-used to compute the solutions to n. A brute force algorithm is possible, but I think far more inefficient.

Here is my solution in Python. It will print them all out and also return the trellis that contains the solutions for each digit. Note that for n >= 9, there are no more additive numbers.

# -*- coding: utf-8 -*-

"""Dynamic programming
"""

BASE_CASE = 3

def print_additive_numbers(n=BASE_CASE):
    """Prints all additive numbers up to n digits

    Additive numbers are numbers of the form 123, 1235, etc.
    where the sum of every 2 digits is equal to the third digit
    in the digit expansion of the number.

    We use dynamic programming to iteratively generate
    additive numbers for increasing digits, as the solutions to
    n = 3 are re-used for n = 4, n = 5, etc.


    Args:
        n: the maximum number of digits for each representation

    Returns:
        A dictionary mapping each number of digits to all
        possible additive numbers.

    """
    if n < BASE_CASE:
        raise ValueError, "additive numbers always have 3 or more digits"
    #build the initial trellis
    trellis = {}
    trellis[BASE_CASE] = {}
    for i in xrange(1, 9):
        row = []
        for j in xrange(0, 9):
            if i + j <= 9:
                print str(i) + str(j) + str(i + j)
                row.append(str(j) + str(i + j))
        trellis[BASE_CASE][i] = row
    for m in xrange(BASE_CASE + 1, n + 1):
        trellis[m] = {}
        for key in trellis[m - 1].keys():
            row = []
            for digits in trellis[m - 1][key]:
                first_digit = int(digits[-2])
                second_digit = int(digits[-1])
                new_digit = first_digit + second_digit
                if new_digit <= 9:
                    row.append(digits + str(new_digit))
                    print str(key) + digits + str(new_digit)
            trellis[m][key] = row                               
    return trellis


t = print_additive_numbers(9)

Answer 1

1. Review

1. I like that you've written a docstring, but it is not quite correct. It claims that the function returns:

   A dictionary mapping each number of digits to all
   possible additive numbers.
   

   but when I run it I get a more complicated data structure:

   >>> from pprint import pprint
   >>> pprint(additive_numbers(3))
   {3: {1: ['01', '12', '23', '34', '45', '56', '67', '78', '89'],
        2: ['02', '13', '24', '35', '46', '57', '68', '79'],
        3: ['03', '14', '25', '36', '47', '58', '69'],
        4: ['04', '15', '26', '37', '48', '59'],
        5: ['05', '16', '27', '38', '49'],
        6: ['06', '17', '28', '39'],
        7: ['07', '18', '29'],
        8: ['08', '19']}}
   

   Either the docstring or the result should be changed so that they match.

2. The code is not portable to Python 3 due to the use of the raise and print statements and the xrange function. It would be easy to make it portable, using range instead of xrange, the print function instead of the statement, and the modern form of raise:

   raise ValueError("additive numbers always have 3 or more digits")
   

3. The function print_additive_numbers does three things: (i) it computes the numbers, (ii) it prints them, and (iii) it returns an internal data structure used in the computation. It's generally good practice for a function to have a single purpose, and then compose or combine functions to make a program. So I would redesign the function so that it does task (i); we can call print on the result if we need (ii). I don't think (iii) is necessary at all.

4. The code stores the last two digits of each additive number in the trellis structure in the form of a string. But this means that when it gets the digits out again it has to call int. This conversion back and forth is wasteful: it would be better to store the tuple (j, i + j) instead of the string str(j) + str(i + j).

5. The initial loop looks like this:

   for i in xrange(1, 9):
   

   but Python ranges are exclusive at the top, so this never generates the digit 9 and thus fails to find the additive numbers 909 and 9099. The initial loop needs to say range(1, 10).

6. The initial two loops look like this after correcting the problems noted above:

   trellis[BASE_CASE] = {}
   for i in range(1, 10):
       row = []
       for j in range(0, 10):
           if i + j <= 9:
               row.append((j, i + j))
       trellis[BASE_CASE][i] = row
   

   but the if could be omitted if we changed the bounds on j, like this:

   trellis[BASE_CASE] = {}
   for i in range(1, 10):
       row = []
       for j in range(10 - i):
           row.append((j, i + j))
       trellis[BASE_CASE][i] = row
   

   or, using a list comprehension:

   trellis[BASE_CASE] = {}
   for i in range(1, 10):
       trellis[BASE_CASE][i] = [(j, i + j) for j in range(10 - i)]
   

2. A better algorithm

This is a problem for which dynamic programming is unnecessary! That's because dynamic programming is a technique that you use when you have to consult the answers to multiple overlapping subproblems in order to answer the current problem. But when generating additive numbers, there isn't really a problem to solve. Once you've chosen the first two digits, all the other digits follow without any choice.

So I would implement it like this:

def additive_numbers(n):
    """Generate additive numbers up to n digits, in numerical order.

    Additive numbers are numbers of the form 123, 1235, etc. where the
    sum of every 2 digits is equal to the third digit in the digit
    expansion of the number.

    >>> list(additive_numbers(3))
    ... # doctest: +NORMALIZE_WHITESPACE
    [101, 112, 123, 134, 145, 156, 167, 178, 189, 202, 213, 224, 235,
     246, 257, 268, 279, 303, 314, 325, 336, 347, 358, 369, 404, 415,
     426, 437, 448, 459, 505, 516, 527, 538, 549, 606, 617, 628, 639,
     707, 718, 729, 808, 819, 909]

    The longest additive number is 8 digits long:

    >>> list(additive_numbers(8)) == list(additive_numbers(9))
    True
    >>> max(additive_numbers(8))
    10112358

    """
    for digits in range(3, n + 1):
        # Choose the first two digits.
        for i in range(1, 10):
            for j in range(10 - i):
                # m is the number generated so far, z is its last
                # digit, and y the penultimate digit.
                m, y, z = i * 10 + j, i, j
                for _ in range(digits - 2):
                    y, z = z, y + z
                    if z > 9:
                        break
                    m = m * 10 + z
                else:
                    yield m

The examples in the docstring can be executed using the doctest module.