A better algorithm
Thanks to ErikR and Caridorc for providing the base and image used to produce this answer:

From image one sees a clear diagonal pattern which can be expressed using the following function based upon \$x\$ and \$n\$:
$$
f(x, n) = 2^n -1 - x
$$
Added: This function denotes the \$y\$ coordinate of the dots in the image. Let \$x\$ range from \$0\$ through \$A\$, first for \$n=0\$ which gives the \$(0, 0)\$ point (and a lot of points outside the coordinate plane). For \$n=1\$ it gives the \$(1, 0)\$ and \$(0, 1)\$, and so it continues. To calculate for \$f(0, 3)\$ you need to find to use \$2^3\$ (aka print 2**3
in python), which then gives:
$$
f(0, 3) = 2^n - 1 - x = 8 -1 -0 = 7
$$
Which in turn gives us the \$y\$ of the fourth diagonal in the diagram (counting diagonals from the lower left including the one consisting of just the point \$(0, 0)\$, that is the point \$(0, f(0, 3)) = (0, 7)\$
Further since this function has a constant drop of 1 pr increase in \$x\$, the difference between the \$x_{start}\$ and the \$x_{end}\$ plus 1
of any given diagonal indicates how many places/moves this diagonal contributes to the final amount of legal moves. Finally, the \$x_{start}\$ needs either to be on the left or top edge or it is uninteresting, and the \$x_{end}\$ needs to be at the bottom or right edge to have any interest.
Added: \$x_{start}\$ is the x coordinate of the leftmost point in any given diagonal, and the \$x_{end}\$ is the x coordinate of the rightmost in the same diagonal. For \$n\$ diagonals you'll have \$n\$ pairs of \$x_{start}\$ and \$x_{end}\$, in the image \$5\$ diagonals are shown including the \$(0, 0)\$ diagonal.
Formalisation of previous statements:
- Left edge – If \$f(0, n) < B\$ for current \$n\$, then \$x_{start}\$ is 0
- Top edge – If \$f(0, n) > B\$ for current \$n\$, then find the \$x\$ where \$f(x, n) == B\$. That is let \$x_{start} = 2^n - 1 - B\$
- If \$x_{start} > A\$, then it is uninteresting as the diagonal doesn't cross our coordinate plane, we can then use \$x_{start} = A + 1\$
- Bottom edge – Find \$f(x, n) = 0\$ for current \$n\$. That is \$x_{end}\ = 2^n - 1\$
- If \$x_{end} > A\$ then limit it to \$x_{end} = A\$
- Places contribution is only valid if \$x_{start} <= A\$ and \$x_{start} <= x_{end}\$, and if valid the contribution is: \$x_{end} - x_{start} + 1\$
Do the calcuation for \$n = 3\$
- Left edge – \$f(0, 3) = 2^3 - 1 - 0 = 7\$, which is lower than B, let \$x_{start} = 0\$
- Bottom edge – \$x_{end} = 2^3 -1 = 7\$, which is lower than A, let \$x_{end} = 7\$
- Valid contribution – \$7 - 0 + 1 = 8\$
Do the calculation for \$n = 4\$
- Left edge – \$f(0, 4) = 2^4 - 1 - 0 = 15\$, which is above B
- Top edge – Let \$x_{start} = 2^4 - 1 - 10 = 5\$, which is lower than \$A\$ so it's valid
- Bottom edge – Let \$x_{end} = 2^4 - 1 = 15\$, which is larger than \$A\$, so limit it to \$x_{end} = 10\$
- Valid contribution – \$10 - 5 + 1 = 6\$
Code refactor
When refactoring for coding an optimal calculation I add the following statements:
- When the \$x_{start}\$ leaves the left edge, it will never come back down again, and similarily when it passes \$A\$ it is for ever lost
- When the \$x_{end}\$ crosses the right edge, it can always be limited to \$A\$
This leads to the following code using generators for calculating the next diagonal x pairs:
def x_start_generator(a, b):
"""Generate start x-coordinate of the n'th diagonal"""
above_b = False # Indicates if an earlier x_start=0 has y > b
beyond_a = False # Indicates if an earlier x_start > a
two_pow_n = 1 # Iterates 2**n, instead of calculating it
while True:
# print('two_pow_n: {}, diag: {}, above_b: {}, beyond_a: {}'.format(
# two_pow_n, diagonal_function(0, two_pow_n), above_b, beyond_a))
# if x_start has been bigger than a, then it will continue to be bigger
# so we always return a+1
if beyond_a:
yield a+1
continue
# Verify if x_start is on left edge (that is 'not above_b')
if not above_b:
above_b = (two_pow_n - 1) > b
# If on left edge, return start_x = 0 ...
if not above_b:
yield 0
else:
# ... else find x_start on line at height b
x_start = two_pow_n - 1 - b
# Check if x_start is beyond the value of a, and store this
beyond_a = x_start > a
# If not beyond return x_start matching the top edge
if not beyond_a:
yield x_start
# Prepare for next n
two_pow_n *= 2
def x_end_generator(a, b):
"""Generate end x-coordinate of the n'th diagonal"""
beyond_a = False # Indicates if an earlier x_end > b
two_pow_n = 1
while True:
# If x_end has once been larger than a, limit it to a
if beyond_a:
yield a
continue
# Find end coordinate when diagonal crosses y=0
x_end = two_pow_n - 1
# Check if we've passed a, and store this
beyond_a = x_end > a
# If not passed, return x coordinate
if not beyond_a:
yield x_end
# Prepare for next iteration
two_pow_n *= 2
def find_legal_places(a, b, print_xtras=False):
"""Return number of legal places within (0, 0) -> (a, b)
Using the x_start_generator() and x_end_generator() find the start
and end coordinators of the n'th diagonal. If it's a valid diagonal
add the legal places from this diagonal to the total. When not any
more valid coordinates are found, return the total.
If wanted, print_xtras=True, you can get print outs of the coordinates
as we tag along, and a nice total.
"""
x_start_range = x_start_generator(a, b)
x_end_range = x_end_generator(a, b)
legal_places = 0
n = 0
while True:
x_start = next(x_start_range)
x_end = next(x_end_range)
if x_start < a and x_start <= x_end:
legal_places += x_end - x_start + 1
if print_xtras:
print('n: {: 4d}, x_start: {: 12d}, x_end: {: 12d}, legal places: {: 12d}'.format(
n, x_start, x_end, legal_places))
else:
break
n += 1
if print_xtras:
print(' For A={} and B={} there are {} legal places\n'.format(a, b, legal_places))
return legal_places
def main():
print 'Sample Output 1'
for (a, b) in [(2, 3), (7, 7)]:
print(find_legal_places(a, b))
print
find_legal_places(10, 10, True)
print('a=10**1000, b=10**1000, legal_places={}'.format(find_legal_places(10**1000, 10**1000)))
if __name__ == '__main__':
main()
When running my main()
with a few test cases of varying magnitude, it all completed in less then a second. Cases run are (a, b) in [(2, 3), (7, 7), (10, 10), (10**1000, 10**1000)
. The latter would according to ErikR require quite a lot of iterations...
The output of this run was as follows:
Sample Output 1
6
15
n: 0, x_start: 0, x_end: 0, legal places: 1
n: 1, x_start: 0, x_end: 1, legal places: 3
n: 2, x_start: 0, x_end: 3, legal places: 7
n: 3, x_start: 0, x_end: 7, legal places: 15
n: 4, x_start: 5, x_end: 10, legal places: 21
For A=10 and B=10 there are 21 legal places
a=10**1000, b=10**1000, legal_places=20000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
That last number is 2
followed by 999 0
's and ending with a 1
, or put another way 2 * 10^1000 + 1
. It seems like when \$a = b = x\$, then there is \$2 * x + 1\$ legal places1.
1I tested for all cases up through \$10^{1000}\$