"Tractor" Python implementation

This is the Tractor problem from the Kattis problems archive.

Problem Statement


Bessie the Cow has stolen Farmer John’s tractor and is running wild on the coordinate plane! She, however, is a terrible driver, and can only move according to the following rules:


Each of her movements is in the same direction as either the positive x-axis or the positive y-axis.
Her \$\text{nth}\$ movement takes her \$2^{n−1}\$ units forward in her chosen direction. (On her first movement, \$n = 1\$, so she moves 1 unit.)
Farmer John’s farm is on the coordinate plane, in the shape of a rectangle with corners at \$(0, 0), (A, 0), (0, B) \text{and} (A, B)\$. If Bessie starts at (0, 0), how many points inside the farm, including the boundary, could she reach?

Input Format


The input begins with an integer \$N (1 \le N \le 100)\$ on a line by itself, indicating the number of test cases that follow. Each of the following N lines contains two space separated integers A and B \$(1 \le A, B \le 10^8)\$, describing the upper-right corner of Farmer John’s farm.

Output Format


Output N lines, with the Nth line containing the number of points that Bessie could possibly reach in the Nth test case.


In the first test case of the sample, Bessie can reach the following six points: \$(0, 0), (0, 1), (1, 0), (1, 2), (2, 1) and (3, 0)\$.

Sample Input

2
2 3
7 7

Sample Output

6
15

Solution

```
def next_steps():
n = 1
while True:
yield n
n <<= 1

def moves(a, b):
current_positions = [(0, 0)]
moves = []
for step in next_steps():
next_positions = []
while current_positions:
x, y = current_positions.pop(0)
moves.append((x, y))
if x + step <= a:
next_positions.append((x+step, y))
if y + step <= b:
next_positions.append((x, y+step))
if not next_positions:
break
else:
curren

for loop

Use a for loop when iterating over a collection:

for (x, y) in current_positions:
        moves.append((x, y))

for has less power than while (theoretically) and its simplicity makes it a better choice over while.

Avoid premature optimization

Just multiply by two:

n *= 2

Some tests:

>>> import timeit
>>> timeit.timeit("10 >> timeit.timeit("10 * 2")
0.03209113599950797
>>> 0.029866752000089036 / 0.03209113599950797
0.9306854079751793

<< is just 7% faster than *2

And the majority of your time is spent branching if x + step <= a: and playing with lists moves.append((x, y)), so the final improvement would be tiny, not worth the loss in readability.

Optimizing the algorithm

Your algorithm has exponential time complexity:

print(step, len(current_positions))

Gives:

1 2
2 4
4 8
8 16
16 32
32 64
64 74
128 0

At each iteration, the number of current_positions is doubling, and this can get out of hand really quickly.

Arguments name

a and b are not acceptable argument names. I suggest width and height.

Some plotting always gives ideas

Following @ErikR suggestion, I made a graph of the reachable points and noticed a serious regularity, still doing graphs is a nice skill to have, so I encourage you to reproduce this graph by yourself.

StackExchange Code Review Q#106721, answer score: 3