Grid walk problem

CodeEval's "Grid Walk" problem is as follows:


There is a monkey which can walk around on a planar grid. The monkey can move one space at a time left, right, up or down. That is, from (x, y) the monkey can go to (x+1, y), (x-1, y), (x, y+1), and (x, y-1). Points where the sum of the digits of the absolute value of the x coordinate plus the sum of the digits of the absolute value of the y coordinate are lesser than or equal to 19 are accessible to the monkey. For example, the point (59, 79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 19. Another example: the point (-5, -7) is accessible because abs(-5) + abs(-7) = 5 + 7 = 12, which is less than 19. How many points can the monkey access if it starts at (0, 0), including (0, 0) itself?

Here is my solution. I'd appreciate any advice on my code style.

points = [[0,0]]

def sum_of_digits(number):
    return sum(map(int, str(number)))

def is_good(x, y):
    return sum_of_digits(abs(x))+sum_of_digits(abs(y)) = len(points):
            break

    print len(points)

1. Comments on your code

-
There are no docstrings. What do your functions do and how am I supposed to call them?

-
This kind of code is a good opportunity to write some doctests.

-
Your program takes a very long time to run:

$ time python2.7 cr33220.py
real 21m42.537s
user 20m6.233s
sys 0m9.336s


There are two main reasons for this: the int-to-string-to-int conversions in sum_of_digits (see §1.4 below), and the use of a list to maintain the set of visited positions (see §1.8 below).

-
Your sum_of_digits function has to convert back and forth between numbers and strings. It would be substantially faster if you worked with numbers throughout. On my machine, your version of the function takes 7.4 seconds to sum the digits the numbers below a million:

>>> from timeit import timeit
>>> timeit(lambda:sum(sum_of_digits(i) for i in range(10**6)), number=1)
7.442514896392822

But with a pure-number implementation it only takes 1.7 seconds:

def sum_of_digits(number):
    result = 0
    while number > 0:
        result += number % 10
        number //= 10
    return result

>>> timeit(lambda:sum(sum_of_digits(i) for i in range(10**6)), number=1)
1.6833391189575195

-
A name like accessible would be clearer than is_good (good in what way?).

-
You have three different ways of representing positions: (i) as a pair of variables i and j; (ii) as a tuple (i, j); (iii) as a list [i, j]. This kind of variation makes it hard to remember what kinds of value to pass to functions, and in a larger program could easily lead to errors like this:

>>> [0, 0] in [(0, 0), (1, 1)]
False

I would recommend sticking to a single representation of positions throughout, and this representation should be a tuple, for the reason given in §1.8 below.

-
The use of the global variable points means that you can only solve the problem once. If you wanted to solve it again (for example, with a different starting position, or a different value of 19, or in order to time its performance), it wouldn't work because points would already be full up. It would be better to make points a local variable.

-
You use the points list for two different purposes: (i) to ensure that you don't visit a point more than once, and (ii) to maintain a queue of positions whose neighbours need to be visited.

However, a list is not suitable for purpose (i): in order to evaluate [i, j] not in points, Python has to scan the whole list and compare [i, j] with each item. When there are many thousands of items in the list (as in this program) this takes a long time. It would be much more efficient to use a set for this purpose, as sets have (amortized) constant lookup time. It would also be convenient to use collections.deque for purpose (ii).

Note that objects have to be hashable in order to store them in a set, so this is why you have to represent your points as tuples rather than lists.

-
Because most of the code runs at top level in your program, it is hard for you to test your code from the interactive interpreter. You should put the code into a function and call it from the top level, like this:

def accessible_points(start, max_digit_sum):
    """... docstring here ..."""
    # ... implementation here ...
    return visited

if __name__ == "__main__":
    print(len(accessible_points((0, 0), 19))

This makes it possible to run tests interactively:

>>> accessible_points((0, 0), 2)
{(0, 1), (-1, 1), (0, 0), (-2, 0), (0, -2), (1, 1), (2, 0),
 (-1, -1), (0, -1), (1, 0), (1, -1), (0, 2), (-1, 0)}

1. Revised code

Putting all this together, here's how I'd write it:

```
def sum_of_digits(number):
"""Return the sum of digits in the decimal representation of 'number'.

>>> sum_of_digits(123)
6
>>> sum_of_digits(999999)
54

"""
result = 0
while number > 0:
result += number % 10
number //= 10
return result

def accessible(point, max_digit_sum):
"""Return True if 'point' is accessible: that is, if the sum of its
digits is less than or equal to 'max_digit_sum'; return False
otherwise.

>>> accessible((19, 28), 19)
False
>>> accessible((-5, -77), 19)
True

"""
return sum(sum_of_digits(abs(i)) for i in point) >> neighbors((0, 0))
[(1, 0), (0, 1), (-1, 0), (0, -1)]

"""
x, y = point
return [(x+1, y), (x, y+1), (x-1, y), (x, y-1)]

def accessible_points(start, max_digit_sum):
"""Return the set of points that are reachable from 'start' via a
chain of accessible points (that is, points whose digit sum is
less than or equal to 'max_digit_sum').

>>> accessible_points((0, 0), 1)
{(0, 1), (0, -1), (1, 0), (0, 0), (-1, 0)}
>>> [len(accessible_points((0, 0), i)) for i in range(10)]
[1, 5, 13, 25, 41, 61, 85, 113, 145, 505]

"""
from collections import deque
assert(accessible(start, max_digit_sum))

StackExchange Code Review Q#33220, answer score: 5