Heidi Newton

Google Kickstart: Wiggle Walk!

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).

A diagram showing how the cell neighbors change when the robot moves one step north from his starting position of (3, 3), to (2, 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):
    adj_list = {}
    for row, col in cells(rows, cols):
        adj_list[(row, col)] = {
            "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,
            }
    return adj_list


def remove_link(graph, position):
    west_link = graph[position]["W"]
    east_link = graph[position]["E"]
    if west_link is not None:
        graph[west_link]["E"] = east_link
    if east_link is not None:
        graph[east_link]["W"] = west_link
    north_link = graph[position]["N"]
    south_link = graph[position]["S"]
    if north_link is not None:
        graph[north_link]["S"] = south_link
    if south_link is not None:
        graph[south_link]["N"] = north_link


def solve_case(graph, start, dirs):
    current_position = start
    for dir in dirs:
        new_position = graph[current_position][dir]
        remove_link(graph, current_position)
        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)
    print("Case #{}: {} {}".format(t, *answer))

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
        self.changed_links = {}

    # 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:
            return self.changed_links[(row, col, dir)]
        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:
            self.changed_links[(*north, "S")] = south
        if south is not None:
            self.changed_links[(*south, "N")] = north
        if east is not None:
            self.changed_links[(*east, "W")] = west
        if west is not None:
            self.changed_links[(*west, "E")] = east

    # 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)
    answer = graph.get_current_location()
    print("Case #{}: {} {}".format(t, *answer))

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!

Your thoughts

In order to post, you'll need to log in.

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))