Letter Square: Post Mortem (a Boggle clone in LiveView)
Tags: elixir, gamedev
Published: 2021-03-03 21:22:57

Recently I wanted to learn [Phoenix LiveView](https://hexdocs.pm/phoenix_live_view/Phoenix.LiveView.html), an Elixir library based on the Phoenix framework to build real-time applications.

Its main characteristic is that it renders the HTML on the server side, allowing the application to be written entirely in Elixir (though it can't replace Javascript for every use case, and still rely on it to set up the websocket and update the DOM).

Anyway, I've got my eyes on it ever since it was announced, but never got the time to actually try it. I finally found that time and to learn it, Idecided to make a Boggle clone: [Letter Square](https://lettersquare.gigalixirapp.com).

My plan was:
- A dynamic Boggle on the web (check [the rules](https://en.wikipedia.org/wiki/Boggle) if you're not familiar with the game).
- People can play together on the same grid of letters.
- At the end of a game, a ranking is displayed and players can chat for a while until the next game starts.
- I also wanted to push things a bit further by actually deploying it online and polishing it as much as possible.

Let's talk about what I learned in the different steps of its 3 weeks-long development.

## Coding the Boggle game

Before diving into LiveView, I programmed the rules and some helpers for the game itself. That includes generating a grid of letters, finding the words in it (from a list of words) and computing the score.

### Finding words inside a grid

As an algorithm lover, that was one of the most fun parts for me. The general idea of the algorithm I implemented is the following:
- Start from one position in the grid
- Use backtracking to follow all valid paths from this position. At each step:
  - if the current path forms a word that is present in the dictionary, add it to the list.
  - if no word in the dictionary starts with the current sequence of letters, do not explore further.
- Repeat for every position in the grid.

In order to efficiently check if a word is in the dictionary, or if any word starts by a given prefix, I used a [trie](https://en.wikipedia.org/wiki/Trie). I found [Retrieval](https://github.com/Rob-bie/retrieval), a tiny Elixir library that did just what I needed.

It was working just fine, until I deployed it on my free Gigalixir instance, limited to 500MB of memory. Loading the 5MB dictionary and turning it into a trie turned out to use a bit too much memory.

I found an elegant solution for that: load the dictionary by chunks. For every chunk, I can see it as a smaller dictionary and use the algorithm from above to find *some* of the words. Then I repeat for every chunk until I have covered the whole dictionary. Using a [Stream](https://hexdocs.pm/elixir/Stream.html), doing that was dead easy, and I didn't even have to update my initial function:

```elixir
defmodule WordSearch do
  def list_all(grid, dictionary) when is_list(dictionary) do
    # My initial implementation, taking a list of words
  end

  def list_all(%Grid{} = grid, dict_stream) do
    dict_stream
    |> Stream.chunk_every(5_000)
    |> Stream.map(fn subdictionary ->
      list_all(grid, subdictionary)
    end)
    |> Enum.into([])
    |> List.flatten()
    |> Enum.sort_by(&String.length/1, :desc)
  end

  # ...
end
```

### Generate a grid

My first implementation for the random generation of the grid was pretty simple: each letter was chosen independently, and the probability of a letter being chosen depended on its frequency in the language.

Using this technique, I quickly faced a problem: the number of words to find was often very small, making the grids too hard and not very fun. Many grids had too many consonants not connected to any vowel.

So I tried another technique. Instead of generating letters independently, I generate random paths of letters inside the grid. The first letter of a path is chosen completely randomly, but the next ones are chosen depending on the preceding letter in the path. The probability is based on the frequency of bigrams (pairs of letters), computed from the dictionary. Using this technique, I make sure that letters which are likely to be found next to each other in the dictionary are also more likely to be together in the grid.

This is a quite complex technique but it paid off as the average number of words per grid took off (though I did not measure it). Very long words became also much more frequent.

### Finding a list of words

Another thing that I didn't expect to be a challenge, but actually took me an entire evening, is finding a good list of words to use as dictionary.

Some official list of words used for Scrabble can be found online, but it seems they cannot be used freely. Other lists can be found here and there on abandoned web pages and repos, but it's never clear how good they are, and they often come in weird or annoying formats (e.g. XLS). In the end I used one from [this GitHub repository](https://github.com/dwyl/english-words) but I'm still not convinced of its quality.

## Phoenix LiveView & Surface

### What I liked

After that I implemented the behaviour of the interface with Phoenix LiveView. Apart from a few hiccups, it felt very easy and comfortable. I loved being able to do everything only in Elixir, without having to care about JavaScript and building an API to link the two, which would have been much more complex. In the end, I even wonder if I did not spend more time trying the get the CSS right.

I also did not use "vanilla" LiveView, as I used the [Surface](https://github.com/msaraiva/surface) library. This is a wrapper around LiveView that brings a whole new syntax to make the experience even more comfortable.

As an example, here is the code of one of my components, that displays the remaining time:

![Code for the Timer component](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/973a1fv6acv75440zze4.png)

As you can see, Surface brings the `~H` sigil for the template, which allows to use a syntax very similar to Vue, using `{{ }}` for Elixir interpolation. I've never liked Phoenix's syntax and always preferred Vue-like syntax, so that immediately convinced me to try Surface.

Like Vue, loops and conditions are done with special attributes inside the HTML tag, instead of outside, preventing additional levels of nesting.

With standard Phoenix:

```elixir
<ul>
  <%= for item <- @items do %>
    <li>
      <%= item.name %>
    </li>
  <% end %>
</ul>
```

With Surface:

```elixir
<ul>
  <li :for={{ item <- @items }}>
    {{ item.name }}
  </li>
</ul>
```

Properties, internal data, slots or events are defined on top of the module, which makes them instantly visible. The component's name can then be used in other components, just like the `Stat` component from the example. Here again, it is easier and more expressive than the LiveView way, which would be:

```elixir
<%= live_component @socket, Timer, seconds: @seconds %>
```

While Surface allows me to do just:

```elixir
<Timer seconds={{ @seconds }} />
```

Given how young both LiveView and Surface are, I am amazed at what they achieve together and I can't wait to see how they will evolve.

### What could have been better

There were a few things that made me lose a bit of time:
* LiveView is often described as a way to make interactive pages without the need to write JavaScript (I even did it in this post). Still, there are cases where JavaScript is required or more adapted. In such cases, it can be more difficult to find the motivation to do JavaScript when it was not necessary so far. I am not yet certain where to put the limit.
* Similarly, the separation between LiveView and Surface was a bit unclear at times. On the one hand, I was not always sure whether I was allowed or supposed to use functions from LiveView itself, or if I had to rely on Surface. On the other hand, the documentation of Surface often assumes that you already know how LiveView works, "forcing" you to know beforehand about things you're not going to use in the end.
* About Surface again, the fact that it *looks like* Vue made me expect that everything would work like Vue. That is not an issue per se, but if you come from Vue, beware that it can be slightly confusing at times. Events, in particular, do not really work the same way.
* In a LiveView, the [`mount`](https://hexdocs.pm/phoenix_live_view/Phoenix.LiveView.html#c:mount/3) callback is called twice. There is [a good reason](https://kobrakai.de/kolumne/liveview-double-mount/) for that, and it is mentioned in the documentation. However I had missed that and it boggled my mind at first (pun intended). I had an issue because I was triggering a rather heavy operation from there and I really didn't want to do it twice, only on the second mount. I still don't really get why the two mounts must be done with the same function.

## Deploying with Gigalixir

For deployment, I used the free option of [Gigalixir](https://gigalixir.com/). As said before I was limited to 500MB, which made one part tricky. But for the price, that's quite a lot already.

I have very few things to say about it except that it was a breeze. In less than an hour, I had my application running, and updates were just a `git push` away. I also got easy access to the logs and a console to monitor the CPU and memory access.

I had one tiny issue because I followed the [Deploying on Gigalixir](https://hexdocs.pm/phoenix/gigalixir.html) documentation of Phoenix, that does not mention that you can give the app a name (and a region). So I got a default name `quirky-barren-canvasback` (which is used in the URL) and had no choice but to destroy the instance and create a new one just to change the name.

## Conclusion

In conclusion, that was a great experience and I can't wait to do more projects involving LiveView and Surface. None of the issues I stumbled upon were huge blockers, and most of them are probably due to the fact that both projects are still quite young. I have no doubt that they will keep getting better and I hope to be able to contribute at some point.