Goridor: The Gopher Rest

After having been challenged on the use of the keyboard only and the mouse only, I expected to have to use another device such as a VR headset... Not at all! For this challenge, there is no UI, as I have to develop an API. I'm supposed to develop the backend of the game, this time with all the rules, and using the Go language.

In this article, I'll focus on my discovery of the Go language, and the particularities of unit tests in Go versus in other languages like Java. You can also jump to the conclusion to see the code I produced.

Let's ...

Go is a compiled language. When I think compiled, I think "slow". But I was suprised by the velocity of this language. It feels like using a scripting language.

The visibility of functions, variables, packages is controlled by capitalizing the first letter of the item declared. So if the function starts with an uppercase letter, this function is visible outside of the package, otherwise it is private. This very simple convention makes the code lighter.

I like the default tooling a lot. There are a bunch of commands to build, test, analyze the code. Another command, go get, retrieves and installs remote packages. These commands just work, they are fast and well documented.

At first, when I discovered that Go uses pointers, I remembered my C lectures. And all the problems I got with pointers: array overflows, memory allocation... But in Go, only pointers matter, and they are really easy to use (maybe it is due to my "long" experience... I am not a student anymore).

One thing that bothered me in Go is that the compiler is too scrict with unused packages. I was sometimes angry when my code didn't compile because I left the fmt package... only to use Println to debug my application? Wrong use? Sure, but no time to find a better solution.

Go is also suitable for parallel programming via the goroutine but I did not have the opportunity to use them.

Testing

When I write unit tests, I use the Given/When/Then pattern. I usually use only one assertion per test. In a unit test, I test only one behaviour of a function. The purpose of that rule is to have an easy to read and easy to understand test.

But in Go, it is not possible to reach this test quintessence. This is mainly due to the way that Go manages error handling. Go does not throw errors. You have to do it by yourself. So the return signature of the method contains the real value and the error value. In case of an error, you have to add a dummy value for the real one. Furthermore, you have to propagate the error from function to upper functions.

A Go unit test looks like this:

func TestAddFenceShouldAddTheFenceAtTheRightPlace(t *testing.T) {
   //Given
   assert := assert.New(t)
   newGame, _ := game.NewGame(3)
   expectedFences := [1]game.Fence{game.Fence{game.Position{0, 0}, false}}
   //When
   updatedGame, err := newGame.AddFence(game.Fence{game.Position{0, 0}, false})
   //Then
   if err != nil {
      t.Errorf("the game should exist: %s", err.Error())
      return
   }
   assert.Equals(updatedGame.Fences, expectedFences, "the game should contain one fence at the correct place.");
}

In order to avoid errors in the test execution, it is recommended to check before the assertion if an error occured. To have a readable test, it is necessary to avoid complex statements like if, switch, loops... With these statements, you think that the test checks different behaviours. So it is a pity to check in all tests if an error occured before real asserting. I'd prefer if the test framework did it for me, like JUnit.

But in another hand, it is easier to test errors in Go, as they are a return value of a function.

func TestNewBoardShouldNotBePossibleWithEvenNumber(t *testing.T) {
   //Given
   //When
   _, err := game.NewBoard(8)
   //Then
   if err == nil {
      t.Error("The size must be an odd number")
   }
}

It is more elegant than in Java 7, where you have to tell the test framework that the test must fail if no exceptions occurs...

@Test
public void TestNewBoardShouldNotBePossibleWithEvenNumber() {
   //Given
   //When
   try {}
      new Board(8);
      fail("create a board should not raise an exception");
   } catch (IllegalArgumentException e) { //Then
      assertThat(e.getMessage()).isEqual("The size must be an odd number"));
   }
}

With Java 8, you can use a lambda to ease the test reading:

@Test
public void TestNewBoardShouldNotBePossibleWithEvenNumber() {
   //Given
   //When
   Throwable thrown = catchThrowable(() -> { new Board(8); });
   //Then
   assertThat(thrown)
      .isInstanceOf(IllegalArgumentException.class)
      .hasMessageContaining("The size must be an odd number");
   }
}

Under the hood

Data Structure

I choose to ease the data structure. I remove the graph (see my previous challenge). This graph was mostly used by the pathfinding algorithm of a third party library.

type Game struct {
    ID       string
    Over     bool
    PawnTurn int
    Pawns    []Pawn
    Fences   []Fence
    Board    *Board
}

I only need the board, the list of fences and the pawns. It is enough to check if the pawn can be moved, if the fence can be put up. As I did not find a library to check whether a path still exists between a pawn and its goal line, I decided to code it with a logic which fits my data structure.

Pathfinding

func Path(board Board, fences []Fence, src Position, dest Positions) int {
    boardSize := board.BoardSize
    visited := make([][]bool, boardSize)
    for i := 0; i < boardSize; i++ {
        visited[i] = make([]bool, boardSize)
    }
    visited[src.Column][src.Row] = true;

    q := list.New()
    q.PushBack(QueueNode{src, 0})

    for q.Len() > 0 {
        curr := q.Front().Value.(QueueNode)
        pos := curr.Position
        if (dest.IndexOf(pos) != -1) {
            return curr.Distance
        }
        q.Remove(q.Front())
        ps:= NewPositionSquare(pos)
        positions := [4]Position{ps.EastPosition, ps.NorthPosition, ps.SouthPosition, ps.WestPosition}
        for _, position := range positions {
            if board.IsInBoard(position) && !visited[position.Column][position.Row] && CanCross(pos, position, fences) {
                visited[position.Column][position.Row] = true
                adjPosition := QueueNode{Position{position.Column, position.Row}, curr.Distance + 1 }
                q.PushBack(adjPosition)
            }
        }
    }
    return -1;
}

This "naive" algorithm visits all possible neighbours until a position matches the goal line (the list of positions). I could choose to code a better solution like the Dijkstra's algorithm or A* but I preferred to find one solution and finish the application. At marmelab, we prefer to show quickly a working solution and then improving the solution if needed. According to that principle, the game is persisted in memory.

Play the game

I am really happy that the game is fully playable for two with all the rules. Contrary to my previous challenge, I had to code my own pathfinding algorithm to detect whether putting up a fence is possible. That, and the discovery of the Go language, were my main challenges, as I am used to developping REST APIs.

Only a backend for that challenge, I hope this one will be used by a front end, maybe during my next challenge?

You can still have a look at the code in the marmelab/quoridor-go GitHub repository.