Github Repo

Gogen is a puzzle published daily in the London Evening Standard, and tends to be my go-to activity if I happen to have a seat and a pen on the evening trip home. While on my trip last year I came across it somewhere else in the world and thought I’d attempt to not only write a solver for this puzzle but also try to solve a non-trivial problem in other programming languages that I am not overly familiar with. I started in the Ruby, the language I’m most familiar with, in order to iron out a first attempt at the algorithm, and then made attempts in Go, Elixir and Clojure. This was a really fascinating exercise in the end, and I’ve attempted to document some of the interesting points in this blog post and the linked Github Repo.

The basic algorithm came about after doing some research on existing techniques for Sudoku solvers and is pretty much a brute force approach:

1. Ingest the input text file and split into a grid string and word string.

2. Convert the grid into a two dimensional matrix (or array of arrays) to allow us to target positions with co-ordinates e.g [0,1]

3. Reduce the words list into a hash map of letter and an array of adjacent letters e.g. VERB, DOOR,… would lead to { “R” => [“O”, ”E”, ”B”] }

4. Reduce the current grid into a hash map of letters and a set of possible positions, which I’ll name the letter_positions_map. For known letters this is simply a one element set, for all unknown letters this is a set containing all possible remaining positions e.g. { “V” => Set([0,1],[0,2]…) }

5. From there, step through each letter inletters_position_map, which I’ll name top_letter. From the example in step 3, this could be R

   1. Then step through all adjacencies to that letter, which I’ll name adj_letter. From the example in step 3 this would be O, then E and then B.
   2. If the position set of the top_letter has length 1, then we’ve solved the position for that letter, so escape the inner loop.
   3. If the position set of the top_letter has more than 1 element, attempt to update the position set using the position set of the adj_letter.
   4. For each of the positions in the adj_letter position list, build a surrounding neighbourhood, then flatten all the neighbourhoods into one list and filter out non-distinct positions. The idea here is to give us a set of positions the original top_letter could take, namely the overlap of the surrounding neighbourhoods of all it’s adjacent letters.
   5. For this set, remove all known positions (the set of all single positions for found letters) with a set difference operation.
   6. Finally, update the position set for the top_letter with the set intersection of the existing position set and the set found in the above step.

6. Repeat until all letters only have one element in their position set.

You can find the code on Github along with some of the main notes on each language that I wrote during the process, but overall my main takeaways were:

1. Ruby’s set methods on arrays are awesome and a great help in the main solve step, as was the Cartesian product method of arrays.
2. Go is quickest to run once compiled, but the lack of built-in set data structure and functional paradigms like map and reduce made the move from Ruby slow at first.
3. Elixir’s pipe syntax and list comprehensions were fantastic to use and made writing some of the helper methods informative.
4. Elixir’s forced me to rethink the main solve step as I wasn’t allowed to modify the letters_position_map outside of the main loop nor really use a while/until statement. As you can see in the Github notes after multiple attempts I ended up using a mixture of guard clauses, multiple functions and a double reduce to write the solve step.
5. Clojure had a steep learning curve due not knowing the standard library very well, and I frequently found myself stuck by functions turning vectors into lists or vice versa, but overall I didn’t mind the Lisp syntax.
6. Writing Elixir first and getting into a more functional mindset definitely made writing the Clojure solution easier,
7. After doing Elixir and Clojure I now would have definitely written Ruby in more functional way.

I’m definitely not versed in the idioms or conventions are any of these languages so any comments of my style or improvements are more than welcome!