Curious George's Adventures On The Coordinate Plane

I solved this problem with a blind Depth First Search.Let us define a function $\color{#20A900} {\text{Visit(x,y)}}$ . Here is what $\color{#20A900} {\text{Visit(x,y)}}$ does when it is called:

1. Check if $(x,y)$ has previously been visited,if so return Nothing

2. If it hasn't been previously visited,do the below :

• Check if $(x,y+1)$ is accessible.If it is $\color{#20A900} {\text{Visit(x,y+1)}}$

• Check if $(x,y-1)$ is accessible.If it is $\color{#20A900} {\text{Visit(x,y-1)}}$

• Check if $(x+1,y)$ is accessible. If it is $\color{#20A900} {\text{Visit(x+1,y)}}$

• Check if $(x-1,y)$ is accessible. If its is $\color{#20A900} {\text{Visit(x-1,y)}}$

3. Add $(x,y)$ to the list of visited coordinates.

When $\color{#20A900} {\text{Visit(0,0)}}$ is called, it recursively checks all possible paths and stops when nothing is no more accessible.

Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

import sys
sys.setrecursionlimit(8000)
DDIG = dict(zip("0123456789", range(10)))

import sys
sys.setrecursionlimit(8000)

def Visit(x,y):
    if (x,y) in Visited:
        return None
    if 0 in (x,y):
        On_Axis.add((x,y))
    Visited.add((x,y))
    for v in [(0,1),(0,-1),(-1,0),(1,0)]:
        x1,y1=x+v[0],y+v[1]
        if accessible(x1,y1):
            Visit(x1,y1)

def digits(number, reverse=False):
    s = str(abs(number))
    if reverse: s = reversed(s)
    return (DDIG[c] for c in s)

def accessible(x, y):
    if x<0 or y<0:return False#As chandler mentioned,only count first quadrant
    return sum_digits(x) + sum_digits(y) <= 19

def sum_digits(x):
    return sum(digits(abs(x)))

On_Axis = set([])
Visited = set([])
DDIG = dict(zip("0123456789", range(10)))
Visit(0,0)
print len(Visited.difference(On_Axis))*4 + 2*len(On_Axis) - 1

Since consistently inter-converting between strings and integers to find the digits sum is costly, I used a dictionary (Table) to speed things up.

The code prints out the answer $\boxed{102485}$ in around 3 seconds on my machine.

first of all note that due to the absolute value we only need to search in the first quadrant. Python code:

import networkx as nx

digits = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4,
          '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}

def digit_sum(n):
    return sum([digits[i] for i in str(n)])

def get_bound(ds_lim):
    return 10**int(ds_lim/9) * ((ds_lim % 9) + 2) - 1

def is_accessible(x, y, ds_lim):
    return digit_sum(abs(x)) + digit_sum(abs(y)) <= ds_lim

def get_index(x, y, bound):
    return bound*x + y

def total_accessible_squares(ds_lim):
    bound = get_bound(ds_lim)

    G = nx.empty_graph()

    for x in range(bound):
        for y in range(bound):
            if is_accessible(x, y, ds_lim):
                index = get_index(x, y, bound)

                if is_accessible(x+1, y, ds_lim):
                    G.add_edge(index, get_index(x+1, y, bound))
                if is_accessible(x, y+1, ds_lim):
                    G.add_edge(index, get_index(x, y+1, bound))

                if x > 0:
                    if is_accessible(x-1, y, ds_lim):
                        G.add_edge(index, get_index(x-1, y, bound))
                if y > 0:
                    if is_accessible(x, y-1, ds_lim):
                        G.add_edge(index, get_index(x, y-1, bound))

    cc = len(nx.node_connected_component(G, 0))
    return 4*cc - 4*bound + 1

print total_accessible_squares(19)

I understand that we can use symmetry to solve this problem, but I didn't use it in my DFS-ish solution below (it's not DFS as I used a set instead of a stack, and the solution turned out to be fine). It is similar to that of Thaddeus Abiy:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

from math import floor, log

def sum_of_digits(num):
    if num == 0:
        return 0
    num_digits = floor(log(num, 10)) + 1
    sum_ = 0
    for _ in range(num_digits):
        digit = num % 10
        num = num // 10
        sum_ += digit
    return sum_


def count_reachable_points(limit):
    to_visit = {(0, 0)}
    visited = set()
    count = 0
    while to_visit:
        x, y = to_visit.pop()  # Removes a random element from the set.
        for point in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
            if (sum_of_digits(abs(point[0])) + sum_of_digits(abs(point[1]))) <= limit and point not in visited:
                to_visit.add(point)
        visited.add((x, y))
        count += 1
    return count


if __name__ == '__main__':
    print(count_reachable_points(19))