While my program does not give the correct answer, I was able to deduce the correct answer from my failed tests.
For this problem, Wikipedia was very helpful. It stated after about 10,000 steps
Finally the ant starts building a recurrent “highway” pattern of 104 steps that repeats indefinitely.
This allowed me to find the underlying pattern and solve. Unfortunately though, my tests weren’t passing. They kept being off by two. I added more tests to see if there was any sort of pattern to the errors. Always off by two. So, I decided to submit the answer this program gave for $n=10^{18}$ and when it was wrong, I subtracted two from this number and resubmitted. This gave the correct answer.
I’m sure I could fix my program to actually spit out the correct answer. However, I believe that in a way it has already given me the correct answer and therefore is good enough as it is.
UPDATE: Okay, I went and fixed the program anyway. Ends up my only mistake
was the value for my diff variable. It should be calculated as
diff = n - 14002
With this small change to the code below, the program now outputs the correct answer for all values without the need for guessing. I also added about 500 more tests just to make sure the code was correct, but I won’t include those here, I think you get enough of the point without them.
UPDATE: Oh, and I should probably mention that the completion of this problem has brought me to Level 10, meaning I’ve completed 250 problems! It told me that only 0.14% of members have made it as far as I have. That makes me feel pretty good. Though the remaining problems have definitely gotten much much harder, I am still really enjoying working on these. I intend to continue with them for some time.
from collections import defaultdict
def move(location, facing):
if facing == 0:
return location[0] + 1, location[1]
elif facing == 1:
return location[0], location[1] + 1
elif facing == 2:
return location[0] - 1, location[1]
else:
return location[0], location[1] - 1
def solve(n):
squares = defaultdict(int)
location = (0, 0)
facing = 0
pattern = []
for i in range(15000):
if i == n:
return sum(squares.values())
if squares[location] == 0:
# white square
facing = (facing - 1) % 4
else:
# black square
facing = (facing + 1) % 4
# flip the square
squares[location] = (squares[location] + 1) % 2
# move forward
location = move(location, facing)
# find the pattern
if i == 14000:
start = sum(squares.values())
elif i > 14000:
pattern.append(sum(squares.values()) - start)
diff = n - 14000
div, mod = divmod(diff, 104)
return start + div * pattern[103] + pattern[mod]
if __name__ == '__main__':
import sys
n = eval(sys.argv[1])
print(solve(n))
import pytest
from problem import solve
_test_solve = (
(0, 0),
(1, 1),
(2, 2),
(3, 3),
(4, 4),
(5, 3),
(6, 4),
(7, 5),
(8, 6),
(9, 7),
(10, 6),
(11, 7),
(12, 8),
(13, 9),
(14, 10),
(15, 9),
(16, 8),
(17, 7),
(18, 6),
(19, 7),
(20, 6),
(10**2, 20),
(10**3, 118),
(10**4, 720),
(10**5, 11108),
(10**6, 114952),
(10**7, 1153412),
(10**8, 11538026),
(10**9, 115384182),
)
@pytest.mark.parametrize('n,expect', _test_solve)
def test_solve(n, expect):
assert expect == solve(n)