Programming Puzzle #1 - No Consecutive Ones (Please leave my code feedback)

[Solzhenitsyn]

Edit: Really not sure where to post this, but I would really like to get feedback from more programmers who are more knowledgeable than I am so that I can continue to progress in the correct direction.

 

I started programming about four months ago, and I have found that the best way to improve problem solving abilities is to solve difficult problems. I don't have anyone who I can compare my answers with. If anyone else would like to solve problems that they find interesting, and then discuss strategies and techniques, I would really appreciate it. 

 

I have been using Python, but I think that learning about specific language features is less important than learning about concepts which can be applied to any (most?) languages. I am also avoiding the use of any non-builtin function, as that is cheating. 

 

 

Problem #1:

Write a function which computes every combination of n-length integers, such that each n-digit integer uses digit values of only 1 and 9, and no integer contains two or more consecutive ones.

 

Examples:

>> no_consecutive_ones(2):
99
91
19

>> no_consecutive_ones(3):
999
991
919
199
191

>> no_consecutive_ones(4):
9999
9991
9919
9199
9191
1999
1991
1919

Solutions:

 

Python 3 (@Solzhenitsyn)

def no_consecutive_ones(n):
    cache = {}

    def get_list_of_digits(n):
        if n == 0:  # Base case - return an empty list if n is zero as there are no valid values.
            return [[]]
        if n == 1:  # Base case - return a list containing singleton lists of 9 and 1, which are the only
            return [[9], [1]] # valid values for an integer of length 1.
        else:
            if n - 1 not in cache:  # Avoid making duplicate recursive calls be storing the results of previous
                cache[n - 1] = get_list_of_digits(n - 1)  # recursive calls in a dictionary.
            if n - 2 not in cache:
                cache[n - 2] = get_list_of_digits(n - 2)
            nines_first = cache[n - 1]
            ones_first = cache[n - 2]
            return [[9] + previous_digits for previous_digits in nines_first] \
                   + [[1, 9] + previous_digits for previous_digits in ones_first]

    # Convert a list of digits into an integer.
    def combine_digits(digits, k=0):
        if len(digits) == 0:
            return k
        else:
            return combine_digits(digits[1:], k + digits[0] * 10 ** (len(digits) - 1))

    return [combine_digits(digits) for digits in get_list_of_digits(n)]

    '''
    Remarks:
    A call to n-2 will always yield a list of lists where each sublist has one fewer element than a call
    to n-1.

    With an argument of 1, the following values are valid:
        - 9
        - 1

    With an argument of 2, the following values are valid:
        - 99
        - 91
        - 19

    Wtih an argument of 3, the following values are valid:
        - 999
        - 991
        - 919
        - 199
        - 191

    Notice:
        - All results of n=3 beginning with 9 be produced by adding a digit of 9 to the beginning
          of each value produced in the call of n=2.
        - All results of n=3 beginning with 1 can be produced by adding the two digits of 1,9 to
          the beginning of each value produced in the call of n=1.
    '''

Please leave me feedback on my code.

Edited October 13, 2016 by Solzhenitsyn

[Botre]

Mhm, I'll do this one in Java tomorrow and post it here so you can compare

[Ericthecmh]

Overall, your code's pretty clean and efficient. The only suggestion I'd have is looking into using an iterative approach rather than a recursive one like you've done here.

 

Reason being:

 

Recursion is generally slower. This is because function calls require pushing the current execution point to the stack before executing the function, so that the system knows where to go when the function returns. If you do recursion, you're essentially pushing a lot of things onto the stack over and over, which can get very very slow.

 

Iteration avoids the stack, and can get several times faster in practice. In addition, note how in the line:

return [[9] + previous_digits for previous_digits in nines_first] \
+ [[1, 9] + previous_digits for previous_digits in ones_first]

You are creating new lists repeatedly, which is slow. An iterative approach can avoid this.

 

 

In this case, using iteration probably won't save much, since you're caching results, which essentially linearizes your recursion tree.

 

 

I will post my own solution tomorrow if you wanna compare

Edited October 20, 2016 by Ericthecmh

[Solzhenitsyn]

 

The only suggestion I'd have is looking into using an iterative approach rather than a recursive one like you've done here.

 

Will do.

 

 

I will post my own solution tomorrow if you wanna compare 

 

 

Please, and thanks for your reply. :-)