Refactoring techniques: replace if with dictionary mapping

On Friday, my friend asked me to have a look at some code for a Boggle game implementation as a slack bot. The basics of the game are to find as many words on the grid composed of randomly generated letters as you can. The project is written under the hack days constraints – make a working prototype fast and refactor later (or never).

The code that we will have a look at today is responsible for part of the game creation process and it connects adjacent letters together and those are used in the word evaluation algorithm higher up the chain.

class CreateGame
  EIGHT_NEIGHBOURS  = [6, 7, 10, 11]
  LEFT_FIVE         = [5, 9]
  RIGHT_FIVE        = [8, 12]
  TOP_FIVE          = [2, 3]
  BOTTOM_FIVE       = [14, 15]

  # ...

  def create_links(game)
    game.letters.each do |letter|
      neighbours = []

      if EIGHT_NEIGHBOURS.include? letter.position
        neighbours << eight_neighbours(game, letter)
      elsif LEFT_FIVE.include? letter.position
        neighbours << left_five_neighbours(game, letter)
      elsif RIGHT_FIVE.include? letter.position
        neighbours << right_five_neighbours(game, letter)
      elsif TOP_FIVE.include? letter.position
        neighbours << top_five_neighbours(game, letter)
      elsif BOTTOM_FIVE.include? letter.position
        neighbours << bottom_five_neighbours(game, letter)
      elsif letter.position == 1
        neighbours << one_neighbours(game, letter)
      elsif letter.position == 4
        neighbours << four_neighbours(game, letter)
      elsif letter.position == 13
        neighbours << thirteen_neighbours(game, letter)
      elsif letter.position == 16
        neighbours << sixteen_neighbours(game, letter)
      end

      neighbours.flatten.each do |neighbour|
        Link.create!(from_letter: letter, to_letter: neighbour)
      end
    end
  end

  def eight_neighbours(game, letter)
    [ game.letters.select { |neighbour_letter| neighbour_letter.position == letter.position - 1 },
      game.letters.select { |neighbour_letter| neighbour_letter.position == letter.position + 1 },
      game.letters.select { |neighbour_letter| neighbour_letter.position == letter.position - 3 },
      game.letters.select { |neighbour_letter| neighbour_letter.position == letter.position + 3 },
      game.letters.select { |neighbour_letter| neighbour_letter.position == letter.position - 4 },
      game.letters.select { |neighbour_letter| neighbour_letter.position == letter.position + 4 },
      game.letters.select { |neighbour_letter| neighbour_letter.position == letter.position - 5 },
      game.letters.select { |neighbour_letter| neighbour_letter.position == letter.position + 5 },]
  end

  def left_five_neighbours(game, letter)
    [ game.letters.select { |neighbour_letter| neighbour_letter.position == letter.position + 1 },
      game.letters.select { |neighbour_letter| neighbour_letter.position == letter.position - 3 },
      game.letters.select { |neighbour_letter| neighbour_letter.position == letter.position + 5 },
      game.letters.select { |neighbour_letter| neighbour_letter.position == letter.position - 4 },
      game.letters.select { |neighbour_letter| neighbour_letter.position == letter.position + 4 },]
  end

  # ... 50 more lines of similar methods for other neighbours
end

From a computer science perspective, this code describes undirected graph so we could start by looking at some techniques how to represent it (e.g. adjancency list, adjacency matrix or incidence matrix) and after that maybe on the data structures and algorithms that are useful with these representations. But we don’t have to get fancy and look for an optimal way to solve this algorithm – firstly, the code above is basically an adjacency list representation of offsets and secondly, we are dealing with 16 vertices and a few indices – not a huge amount of data that would scream exponential eternity.

This algorithm is good enough for the problem on hand so we’ll focus on how to make it more readable and understandable. From that perspective there are three issues with it at the moment

  1. huge if statement,
  2. the amount of code repetition and
  3. slightly incorrect adjacent letter selection.

Fixing letter selection

Let’s start from the bottom and focus on the adjacent letter selection first.

neighbours.flatten.each do |neighbour|
  # ...do something with the neighbour
end


[game.letters.select { |neighbour_letter| neighbour_letter.position == letter.position + 1 },
 # ...
 game.letters.select { |neighbour_letter| neighbour_letter.position == letter.position - 3 }]

We don’t have to worry about any ActiveRecord or database performance as the letters are not retrieved from the database but the issue here is that we are using a wrong method of selection. There is always just one letter for each position, but we are iterating through the whole collection by using Enumerable#select which selects all letters that matches the condition in passed block. As a result we have to Enumerable#flatten the collection of single item arrays. Not ideal.

Instead we can use appropriate Enumerable#find which returns the first element matching the condition. The equivalent in ActiveRecord would be the difference between QueryMethods#where and Finder#find (well, at least from this perspective as there is a few other differences that we don’t want to go into right now). So, if we use find we can get rid of the unnecessary flatten as well.

neighbours.each do |neighbour|
  # ...do something with the neighbour
end

[game.letters.find { |neighbour_letter| neighbour_letter.position == letter.position + 1 }
 # ...
 game.letters.find { |neighbour_letter| neighbour_letter.position == letter.position - 3 } ]

Removing code repetition

Now when we have sorted this minor issue out with the code let’s attack the code repetition.

def eight_neighbours(game, letter)
  [ game.letters.find { |neighbour_letter| neighbour_letter.position == letter.position - 1 },
    game.letters.find { |neighbour_letter| neighbour_letter.position == letter.position + 1 },
    game.letters.find { |neighbour_letter| neighbour_letter.position == letter.position - 3 },
    game.letters.find { |neighbour_letter| neighbour_letter.position == letter.position + 3 },
    game.letters.find { |neighbour_letter| neighbour_letter.position == letter.position - 4 },
    game.letters.find { |neighbour_letter| neighbour_letter.position == letter.position + 4 },
    game.letters.find { |neighbour_letter| neighbour_letter.position == letter.position - 5 },
    game.letters.find { |neighbour_letter| neighbour_letter.position == letter.position + 5 },]
end

def left_five_neighbours(game, letter)
  [ game.letters.find { |neighbour_letter| neighbour_letter.position == letter.position + 1 },
    game.letters.find { |neighbour_letter| neighbour_letter.position == letter.position - 3 },
    game.letters.find { |neighbour_letter| neighbour_letter.position == letter.position + 5 },
    game.letters.find { |neighbour_letter| neighbour_letter.position == letter.position - 4 },
    game.letters.find { |neighbour_letter| neighbour_letter.position == letter.position + 4 },]
end

The problem is quite easy to tackle with a simple method extraction and passing letter offsets as parameters.

def eight_neighbours(game, letter)
  neighbours(game, letter, [1, -1, 3, -3, 4, -4, 5, -5])
end

def left_five_neighbours(game, letter)
  neighbours(game, letter, [1, -3, 5, -4, 4])
end

def neighbours(game, letter, offsets)
  offsets.map do |position_offset|
    game.letters.find { |neighbour_letter| neighbour_letter.position == letter.position + position_offset }
  end
end

This refactoring is a major improvement to the code quality and it will allow us to do the final step where we get rid of the if statement.

Using hash for configuration mapping

Firstly, let me emphasize that this technique is not a silver bullet and you should not refactor every if statement to a dictionary and feel like a functional guru. I have seen it overused many times and in combination with other techniques like dynamically loading the mappings from the database, where the dynamic portion wasn’t ever needed. It could lead to more obscure and hard to understand code.

But in this situation, where we have a hard configuration of the domain problem captured in an if statement, it’s the right tool for the job.

if EIGHT_NEIGHBOURS.include? letter.position
  neighbours << eight_neighbours(game, letter)
elsif LEFT_FIVE.include? letter.position
  neighbours << left_five_neighbours(game, letter)
elsif RIGHT_FIVE.include? letter.position
  neighbours << right_five_neighbours(game, letter)
elsif TOP_FIVE.include? letter.position
  neighbours << top_five_neighbours(game, letter)
elsif BOTTOM_FIVE.include? letter.position
  neighbours << bottom_five_neighbours(game, letter)
elsif letter.position == 1
  neighbours << one_neighbours(game, letter)
elsif letter.position == 4
  neighbours << four_neighbours(game, letter)
elsif letter.position == 13
  neighbours << thirteen_neighbours(game, letter)
elsif letter.position == 16
  neighbours << sixteen_neighbours(game, letter)
end


def eight_neighbours(game, letter)
  neighbours(game, letter, [1, -1, 3, -3, 4, -4, 5, -5])
end

def left_five_neighbours(game, letter)
  neighbours(game, letter, [1, -3, 5, -4, 4])
end

# ...

We need to capture the mapping between positions and their offsets. To do so, we’ll extract them into a hash.

POSITION_TO_NEIGHBOUR_OFFSETS = {
  [6, 7, 10, 11] => [1, -1, 3, -3, 4, -4, 5, -5],
  [5, 9] => [1, -3, 5, -4, 4],
  [8, 12] => [-1, -4, 4, -5, 3],
  [2, 3] => [-1, 1, 3, 4, 5],
  [14, 15] => [-1, 1, -3, -4, -5],
  [1] => [1, 5, 4],
  [4] => [-1, 4, 3],
  [13] => [1, -3, -4],
  [16] => [-1, -4, -5]
}

With that mapping we need a way to retrieve the offsets for a certain position.

def neighbour_offsets(position)
  key = POSITION_TO_NEIGHBOUR_OFFSETS.keys.find { |key| key.include?(position) }
  POSITION_TO_NEIGHBOUR_OFFSETS[key]
end

And lastly we put all the pieces together with a method that gets adjacent neighbours for any letter passed in.

def neighbours(game, letter)
  neighbour_offsets(letter.position).map do |position_offset|
    game.letters.find { |neighbour_letter| neighbour_letter.position == letter.position + position_offset }
  end
end

Conclusion and the final code

From a class that was hard to understand and difficult to reason about we ended up with a nice configuration captured in dictionary and a few small methods that use it to populate the adjacent links between letters. As a side effect we reduced the class by almost three times from 120 lines to barely 50.

Don’t forget that each of those refactoring steps has its place and there are certainly drawbacks that you have to consider each time you apply them. In programming there is never a solution that will fit all problems and you constantly juggle between pros and cons of your approach.

class CreateGame
  POSITION_TO_NEIGHBOUR_OFFSETS = {
    [6, 7, 10, 11] => [1, -1, 3, -3, 4, -4, 5, -5],
    [5, 9] => [1, -3, 5, -4, 4],
    [8, 12] => [-1, -4, 4, -5, 3],
    [2, 3] => [-1, 1, 3, 4, 5],
    [14, 15] => [-1, 1, -3, -4, -5],
    [1] => [1, 5, 4],
    [4] => [-1, 4, 3],
    [13] => [1, -3, -4],
    [16] => [-1, -4, -5]
  }

  # ...

  def create_links(game)
    game.letters.each do |letter|
      neighbours(game, letter).each do |neighbour|
        Link.create!(from_letter: letter, to_letter: neighbour)
      end
    end
  end

  def neighbours(game, letter)
    neighbour_offsets(letter.position).map do |position_offset|
      game.letters.find { |neighbour_letter| neighbour_letter.position == letter.position + position_offset }
    end
  end

  def neighbour_offsets(position)
    key = POSITION_TO_NEIGHBOUR_OFFSETS.keys.find { |key| key.include?(position) }
    POSITION_TO_NEIGHBOUR_OFFSETS[key]
  end
end

Would you like to get the most interesting content about programming every Monday?
Sign up to Programming Digest and stay up to date!