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)}
2. 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) <= max_digit_sum
def neighbors(point):
"""Return a list of the neighbors of '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))
visited = set([start])
queue = deque([start])
while queue:
point = queue.pop()
for neighbor in neighbors(point):
if neighbor not in visited and accessible(neighbor, max_digit_sum):
visited.add(neighbor)
queue.append(neighbor)
return visited
if __name__ == '__main__':
print(len(accessible_points((0, 0), 19)))
How fast is it compared to yours?
>>> timeit(lambda:len(accessible_points((0, 0), 19)), number=1)
0.833313750976231
That's more than a thousand times faster!
