Solution to trustpilot pony challenge

This is complete solution to trustpilot's pony challenge.

Check solution to trustpilots anagram code challenge here in the repository alexvish/trustpilot-anagram

A company named Trustpilot hires developers. Candidates should submit solution to thier code challenge. This is the solution to pony challenge.

The task

Trustpilot provides game api (swagger) that allows you to create maze, and then direct pony to exit. Domokun (monster) chases the pony. If pony reaches the exit, you win, if Domokun overtakes pony you loose.

The maze that is generated by api looks to be a prefect maze, which means there is one and only one path between any of two cells. This means that when both pony and domokun make prefect moves (which is realized on difficulty level 10) then it is wholy determined by initial position whether player looses or wins. Also, in non-prefect mazes there could be a "cycles" that can be used by pony to fool domokun.

But the maze is prefect, so for this game I use this strategy:

1. Calculate path from pony location to exit exitPath
2. Follow the exit path until exit is reached or next cell on exit path is either occupied by domokun, or within domokuns one step range.
3. In the later case calculate the longest possible route that pony can follow within maze exitRoute, and follow exitRoute, adding the current Pony cell to the end of exitPath. If the next point on exitPath become out of reach for domokun (he makes wrong move), forget escape route and follow the exit path.

Here are the pictures:

Exit Path (green):

01234567891011121314151601234567891011121314EPD

Escape route (red)

0123456789101112131401234567891011121314151617EPD

Solution

The code for solving maze problem resides in package dashthroughmaze. This package contains jest unit tests, including TestDash.test.ts that actually plays the game, talking to trustpilot api server.

Execute tests with:

# In the root directory of cloned git repository https://github.com/alexvish/ponychallenge-trustpilot.git
$ npm install
$ npm run test

Code

dash.ts contains the code that is used to work with mazes.

It contains definitions of Trustpilot api objects, and class Maze, that actually works with mazes.

In constructor of Maze trustpilot's wierd flat maze structure converted into two dimensional maze array, each cell is defined by number which is an or bitmask of these locations of walls:

export const TOP=1;
export const LEFT=2;
export const BOTTOM=4;
export const RIGHT=8;

Method Maze.possibleMoveLocations(p:Point) returns an array of cell points, which are reachable from the point provided as argument. This method determines edges in a cell graph.

Method Maze.exitPath(p) calculates exitPath, using depth first search through the cell graph. Maze define non-directional cell graph (A->B === B->A), so there is no need to use white-gray-black node marks when executing dfs search (if maze contained directional semi-transparent walls, we would be needed to use it).

Thus, dfs search is very simple in our case, we only need to mark cells as visited (white-black) apporach.

Here is the code for calculating exit path:

  exitPath():Point[] {
    return this.dfsExitPath(this.pony, {currentPath:[], visitedCells:{}}) || [];
  }
  
  /*
   
   interface DfsContext {
     currentPath: Point[];
     visitedCells:{
       [pointStringKey: string]: boolean /*always true*/;
     };
   }

  */
  
  dfsExitPath (p: Point, dfsContext: DfsContext ): Point[] | undefined {
    // mark current visited
    dfsContext.visitedCells[toStringKey(p)] = true;
    // push current to path
    dfsContext.currentPath.push(p);

    if (eqPoint(p, this.exit)) {
      // found exit
      return dfsContext.currentPath.slice(0); // clone array
    }
    let reachable: Point[] = this.possibleMoveLocations(p);
    // filter out visited
    reachable = reachable.filter(nextP => !dfsContext.visitedCells[toStringKey(nextP)]);
    for (let next of reachable) {
      let path = this.dfsExitPath(next,dfsContext);
      if (path) {
        return path;
      }
    }
    // remove point from current path
    dfsContext.currentPath.pop();
    return undefined;
  }

During the pony move, and when calculating escape route we use method Maze.isDomokunNearPoint(p: Point): boolean to find out whether Domockun is either in the point or point is within one-step reach of Domokun.

Escape route is calculated in method Maze.escapeRute(): Point[], using the following apporach:

1. Start with a path, that contains only pony location. Create array of paths for step 0 and puth this single path.
2. For each paths from prevous step, derive paths, that can be created by moving further. Add all found paths to array of paths for this step.
3. If array of paths for step is empty, use first path from array of paths of previous step.

Web application

First of all, creation of web applicaiton was never a requirement, I spent a lot of effort to do it. The jest test runner is more then enough.

Trustpilot API does not provide CORS headers, so it is not possible to talk to API directly from browser, unless you are Trustpilot employee and can deploy app to trustpilot server.

So, simple api proxy has been developed, using express, that adds CORS headers to API responses. Start proxy as follows:

# In the root directory of cloned git repository https://github.com/alexvish/ponychallenge-trustpilot.git

# Execute npm install
$ npm install

# Start api proxy
$ npm run proxy

After proxy is started, switch to Proxy page, click "Test" button, then switch to Play page, fill in game form and start game. Games can be run in step-by-step or autoplay modes. There are surprise URLs from trustpilot, when you win or loose.

Lessons learned when developing this web applicaitons.

Typescript

I mostly use typescript, but still do not understand whether it is good or evil. It helps you a little, and hits you sometimes, but not too hard. I think I'd stick to it for a while.

Storybooks

Storybooks are mega-useful, for UI component development. You basically start your components in isolation within storybook page until it is ready for integration with the rest of components.

Run storybooks for this project:

$ npm run storybook

# open browser on http://localhost:6006/

Animation

React-motion is the most easy to use package for animation. I went to react-motion when I had memory problems with another package I used for animation: my storybook entry crashed after a while. When switched to react-motion problems went away.

Redux-saga

Trustpilot API is tricky for consumption by web applicaiton, because you need to chain api requests. (E.g. with first request you move pony, with second get new domokun location) This is where redux-saga comes extremely handy: it allows to define chains of async executions in javascript, using generator function syntax (function* yield and yield*). For example check saga function* move(action: NextMoveAction) defined in src/reducer/play.ts.

Server side rendering

There are no fancy SSR requirements for this application, but I want this exact page, that you are reading right now to be easily indexed by google and other crawlers. So, I implemented SSR for index route in compile time using webpack and static site generator webpack plugin. I could not find a clean recepie on internet on how to implement it, so I probably need to blog about this solution.