Last night, I had another go at the Google Kickstart online competition. As a whole, it's one of my favorite online competitions, as the questions tend to be quite interesting. While I didn't do as well as I would have liked, I'm pleased with my solution for the first question. I also think it's an enjoyable question, so well worth sharing here and discussing. The question is called Wiggle Walk and can be found on the Google Kickstart competition website.

## Intuition for a solution

Simple simulation approaches almost never work on the large input for these problems (although they do sometimes work on the small). If they did work, the problems would be far too easy. So from the start, I realized I probably needed to do something a little smarter.

An early observation I made was that after the robot steps off a square, we want to remove that square from the grid. The north and south neighbors should be directly linked to each other, as should the east and west neighbors. In essence, we start with a simple grid-shaped graph, but then with each move, we modify some of the links to remove cells (nodes) that should no longer be used.

My initial attempt at programming this was unfortunate, as I overlooked the massive number of cells in the grid, and attempted to make an explicit graph with an adjacency list. This was a regrettable error. I realized my mistake before I submitted though, so modified my code to use what I call an implicit graph.

### An example

Before attempting to explain my approaches, it helps to understand fully how the graph changes with each move. In these diagrams, black squares represent cells that are no longer reachable, and red arrows represent cells that have neighbors that weren't their original grid-neighbors.

In this example, the grid has 4 rows and 5 columns. The robot starts at (3, 3) and will be following the program N E E W.

#### Step 1: move north

When the robot steps north from the starting position of (3, 3) to (2, 3), the neighbors of (3, 3) change some of their neighbors so that they no longer point to (3, 3).

#### Step 2: move east

When the robot steps east from (2, 3) to (2, 4), some of the neighbors of (2, 3) change neighbors. Notice how (1, 3) and (4, 3) are now linked directly.

#### Step 3: move east

When the robot steps east from (2, 4) to (2, 5), some of the neighbors of (2, 4) now change neighbors.

#### Step 4: move west

The final instruction requires the robot to step west from (2, 5). Because there is a red arrow going west out of (2, 5), the robot follows that and is taken to (2, 2).

This was the final instruction, so the answer for this test case is (2, 2).

Shown this way, my initial algorithm might seem obviously silly. But remember, I developed this explanation after the competition.

## A naive solution

Overlooking the maximums for `R` and `C`, one possible solution is to create an adjacency list to represent the graph. When the robot moves out of a cell, we just need to do a re-linking operation that links the cell's east and west neighbors, and its north and south neighbors.

### The code for my naive solution

Warning: I haven't made an effort to debug this code (not to mention, there's some repetition in places). It probably has bugs :-)

``````
def cells(rows, cols):
for row in range(1, rows + 1):
for col in range(1, cols + 1):
yield row, col

def build_graph(rows, cols):
for row, col in cells(rows, cols):
"N": (row - 1, col) if row > 1 else None,
"E": (row, col + 1) if col < cols else None,
"W": (row, col - 1) if col > 1 else None,
"S": (row + 1, col) if row < rows else None,
}

def solve_case(graph, start, dirs):
current_position = start
for dir in dirs:
new_position = graph[current_position][dir]
current_position = new_position
return current_position

T = int(input())
for t in range(1, T + 1):
N, R, C, Sr, Sc = [int(x) for x in input().split()]
dirs = list(str(input()))
graph = build_graph(R, C)
answer = solve_case(graph, (Sr, Sc), dirs)
``````

### The time cost of the naive solution

Each robot move takes constant `O(1)` time. Applying the `N` moves therefore takes `O(N)` time, which sounds pretty good given that `N` is at most `50,000` on the large.

However, we haven't yet considered the initial graph creation. Before we even begin to look at robot moves, the time limit might already be up (I never tried to run this on Google's servers though, perhaps it would get through a few test cases at least). The code is explicitly creating `R * C` nodes and defining their links. The number of rows and columns could potentially be `50,000` each. Multiply that together, and you get a total of `50,000 * 50,000 = 2,500,000,000` nodes in the graph. Creating 2.5 billion nodes is not a cheap operation, especially not in Python!

I'm not too sure whether or not this approach would be fast enough with C++. I would hope not, but it's amazing what people slip through with C++ in programming competitions sometimes.

## A far better solution: ImplicitGraph

So, I was back to thinking, with unfortunately some time wasted. `N` is often small compared to `R * C`. What if instead I could make a solution with time proportional to `N` instead of `R * C`? After a few minutes of thinking, I came up with a way, which I call an `ImplicitGraph`. I made `ImplicitGraph` its own class. While normally I'd fully pull the problem logic out of the data structure, this time I just kept track of the robot location within the class as this was fairly straightforward. I might do a refactored version that separates it.

The `ImplicitGraph` class, like its name hopefully suggests, behaves like a graph without actually storing a graph in the traditional sense. The constructor needs to know how many rows and columns there are, along with the starting position of the robot. But unlike before, the cost of running the constructor is `O(1)`, instead of `O(R*C)`. Then, each step the robot takes is a constant `O(1)` operation, so with `N steps` to take, the total time needed to run a test case is `O(N)`.

It does this by recognizing that on the largest examples, the neighbors of most cells will never change. Determining the neighbor of a cell in a (unmodified) grid is easy. So, we should only store information about cells' whose neighbors have actually changed.

### The code

Here's the code for my `ImplicitGraph` solution. Below the code, I've put explanations of the core methods.

``````

class ImplicitGraph(object):

def __init__(self, rows, cols, start_position):
self.rows = rows
self.cols = cols
self.cur_position = start_position

# Gets the neighbour of cell (row, col) in the given dir.
def _neighbour(self, position, dir):
row, col = position
if (row, col, dir) in self.changed_links:
else:
if dir == "E" and col < self.cols:
return (row, col + 1)
elif dir == "W" and col > 1:
return (row, col - 1)
elif dir == "N" and row > 1:
return (row - 1, col)
elif dir == "S" and row < self.rows:
return (row + 1, col)
else:
return None

# Remove the robot's current position from the graph.
# This involves linking the north and south neighbours,
# and the east and west neighbours.
def _remove_current_position(self):
north = self._neighbour(self.cur_position, "N")
south = self._neighbour(self.cur_position, "S")
east = self._neighbour(self.cur_position, "E")
west = self._neighbour(self.cur_position, "W")
if north is not None:
if south is not None:
if east is not None:
if west is not None:

# Move the robot in the given dir.
def move_in_dir(self, dir):
new_pos = self._neighbour(self.cur_position, dir)
self._remove_current_position()
self.cur_position = new_pos

# Get the current location of the robot.
def get_current_location(self):
return self.cur_position

T = int(input())
for t in range(1, T + 1):
N, R, C, Sr, Sc = [int(x) for x in input().split()]
dirs = list(str(input()))
graph = ImplicitGraph(R, C, (Sr, Sc))
for dir in dirs:
graph.move_in_dir(dir)

``````

The key underlying idea is the `self.changed_links` dictionary. This dictionary contains tuple keys of the form `(row, col, dir)`, and tuple values of the form `(neighbor_row, neighbor_col)`. Each `key: value` pair means that the neighbor of cell `(row, col)` in direction `dir` is `(neighbor_row, neighbor_col)`.

The private `_neighbor(self, row, col, dir)` method returns the neighbor of `(row, cell)` in direction `dir`. It works by firstly looking for the key `(row, col, dir)` in `self.changed_links`. If the key exists, the corresponding value is returned. Otherwise, the neighbor is assumed to be the default grid neighbor, and so is calculated and returned.

The private `_remove_current_position(self)` method "removes" the cell the robot is currently on by adding entries to `self.changed_links` to re-link the north and south neighbors to each other, and then the same for the east and west neighbors. The cell isn't explicitly removed but is no longer reachable from any other cell. There might be entries in `self.changed_links` for the removed cell, however, these out-of-date entries are untouched as the robot can never re-enter that cell.

The public `move_in_dir(self, dir)` method moves the robot 1 step in direction `dir`. using the `_neighbor(...)` method, and removes the cell the robot was on by calling `_self._remove_current_position()`.

### Some improvements when I refactor

When I refactor this code, I'll fix a number of things I did during the competition but in hindsight aren't great.

• The `ImplicitGraph` class should not know about the robot's current location. This logic should be in the main function instead. One way to do this would be to remove the `move_in_dir(...)` method and instead make `_get_neighbor(...)` public, and add a new `remove_cell(self, row, col)` method that removes the cell at row, col, using similar logic to `_remove_current_position(self)`.
• `_remove_current_position(self)` should be removed, its functionality based on the new `remove_cell(...)` method.
• The N/S/E/W logic could instead use a dictionary to define the relationships, and then iterate over it. This would remove the repetition.

## Closing thoughts

The step up from the small to the large, along with the very generous time limit for the large, initially seemed unusual to me. I wondered how so many people could pass the small, but not the large. The success rates for the Wiggle Walk question, provided on the competition page. The red bar represents people who attempted the question but did not get it correct.

But then I realized. They will have been using a simulation-based approach, possibly one that used a set to keep track of any cells that are no longer accessible. Then each robot move would involve moving the robot step-by-step until it was on a square not in the set. It seems likely that the availability of this very straightforward algorithm was why the small was worth so few points.

Overall, this is one of my favorite questions. It's one of the easier questions, but has a fairly unique flavor of solution. Nice work Google!

### Mridul Sharma says...

I am also using similar sort of approach(space complexity - O(n^2) ) but I am getting Memory Limit Exceeded Error

class Node: def init(self): self.row = -1 self.col = -1 self.left = None self.right = None self.up = None self.down = None

def delete(node): north = node.up south = node.down east = node.right west = node.left if(north != None): north.down = south if(south != None): south.up = north if(east != None): east.left = west if(west != None): west.right = east

t = int(input()) for _ in range(t): l,n,m,sr,sc = list(map(int, input().split())) dic = {} for i in range(1,n+1): for j in range(1,1+m): dic[(i,j)] = Node() for i in range(1,n+1): for j in range(1,m+1): temp = dic[(i,j)] temp.row = i temp.col = j if((i,j-1) in dic.keys()): temp.left = dic[(i,j-1)] if((i,j+1) in dic.keys()): temp.right = dic[(i,j+1)] if((i-1,j) in dic.keys()): temp.up = dic[(i-1,j)] if((i+1,j) in dic.keys()): temp.down = dic[(i+1,j)]

``````s = input()
curr = dic[(sr,sc)]
char = 0
while(char<l):

if(s[char]=="E"):
nex = curr.right

elif(s[char]=="W"):
nex = curr.left
elif(s[char]=="N"):
nex = curr.up
else:
nex = curr.down
delete(curr)
curr = nex
char = char + 1

print("Case #"+str(_+1)+": "+str(curr.row)+" "+str(curr.col))
``````