Walk

Computer Science Level 4

After an extremely intense chess game, the triumphant White King decides to expand his kingdom from an $8 \times 8$ board to an infinite grid, with all squares coloured white in his honour.

Admiring his pristine terra but desiring more colour and flair to his new land, he goes for a walk, initially facing north, following these instructions:

At a white square, turn $90^{\circ}$ right, colour the square to red, move forward one square.

At a red square, turn $90^{\circ}$ left, colour the square to white, move forward one square.

After $n$ moves, the king begins moving in a fixed, orderly pattern in the southeast direction. Find $n$ , rounding your answer to the nearest thousand.

The answer is 10000.

3 solutions

Jake Lai
Dec 15, 2014

Langton's Ant stops after approximately 10000 moves. Unfortunately, I am no coder so I don't have a CS solution.

Nice problem! I recommend bumping this to a Level 3 or 4.

Brian Brooks - 6 years, 5 months ago

Can't, I'm only a level 2, haha. I'm not into CS, I just found the concept of Langton's Ant interesting.

Jake Lai - 6 years, 5 months ago

Brock Brown
Jan 2, 2015

This code prints the king's position whenever he's in the south-east quadrant. I saw that after about 10245 moves he never broke back out of the south-east quadrant.

limit = 15000
direction = 'N'
color = {}
right = {'N':'E','E':'S','S':'W','W':'N'}
left = {'N':'W','W':'S','S':'E','E':'N'}
x, y = 0, 0
i = 0
while i <= limit:
    if (x, y) not in color:
        color[(x, y)] = 'W'
    if color[(x, y)] == 'W':
        direction = right[direction]
        color[(x, y)] = 'R'
    elif color[(x, y)] == 'R':
        direction = left[direction]
        color[(x, y)] = 'W'
    if direction == 'N':
        y += 1
    elif direction == 'S':
        y -= 1
    elif direction == 'W':
        x -= 1
    elif direction == 'E':
        x += 1
    if x < 0 and y < 0:
        print x, y, direction, i
    i += 1

Brian Brooks
Dec 31, 2014

C++ solution: https://github.com/brooksbp/practice/blob/master/c%2B%2B/Walk.cc

The solution is a straight-forward implementation of the chess-board and Knight movement.

The trickier part is finding the largest cycle aka detecting when the Knight is moving in a downward pattern. There should be two 'strings' or 'sequences' of moves that keep repeating. E.g. in the sequence D, D, U, R, L, R, U, D, L, R, U, D the largest cycle is L, R, U, D (two adjacent sequences of maximum cycle length K=4).

A naive first solution is to, after every 'step' or 'move', check for the existence of a cycle anywhere in the path and keep track of the largest cycle seen thus far. Quick optimization is to start looking for cycles larger than the largest seen thus far. (In my solution, see the #ifdef'd out FindCycleMax() ). This turns out to be too expensive; there is a lot of duplicated work between each call to this function after every step. The next thought was to memoize the calls to is_match(). However, the space required for this is way too large as well (when the key-space is a 3-tuple (x, y, K) and the numbers grow beyond 100 you're toast)

The next insight was that the path is append-only by a single move. If we could only look at the cycles that included that last move, we should be good. So, starting from the maximum cycle length (entire path length / 2) down to the max cycle length seen thus far, check for a cycle. This is more efficient.

Walk

The answer is 10000.

3 solutions

0 pending reports