I have recently been writing some code for a side project that needs to compute all possible combinations of a outcomes for a given slate of NFL games, along with the probability of each combination. For example, if Green Bay has a 70% chance of beating Chicago and Minnesota has a 55% chance of beating Detroit, I want to generate:

[
  %Outcome{ winners: [GB, MIN], probability: 0.385}, # 0.7 * 0.55 = 0.385
  %Outcome{ winners: [GB, DET], probability: 0.315}, # 0.7 * 0.45 = 0.315
  %Outcome{ winners: [CHI, MIN], probability: 0.165}, # 0.3 * 0.55 = 0.165
  %Outcome{ winners: [CHI, DET], probability: 0.135} # 0.3 * 0.45 = 0.135
]

My first attempt at this is below. Given a list of games, it recursively computes the outcomes for the tail of the list, then creates two new lists: one where the home team is added as the winner to all outcomes and another where the away team is added as the winner to all outcomes. Those lists are then combined and returned. As each game is added, the number of possible outcomes doubles. Computing the odds of a given outcome is straightforward: simply multiplying the probability of the other outcomes times the probability of the chosen team winning.

def outcomes(games), do: do_outcomes(games, [%Outcome{}])

defp do_outcomes([], results), do: results
defp do_outcomes([game | rest], results) do
  other_outcomes = do_outcomes(rest, results)

  away_outcomes = other_outcomes |> Enum.map(fn(o) -> add_winner(o, game.away_team, game.away_prob) end)
  home_outcomes = other_outcomes |> Enum.map(fn(o) -> add_winner(o, game.home_team, game.home_prob) end)

  away_outcomes ++ home_outcomes
end

defp add_winner(%Outcome{winners: winners, probability: probability}, winner, winner_probability) do
  %Outcome{ winners: [winner | winners], probability: probability * winner_probability }
end

I wrote tests to assert that it picks winners correctly, computes probabilities correctly and computes the correct number of outcomes.

defmodule ProbabilityTest do
  use ExUnit.Case
  doctest Gnarl

  test "it works for a single game" do
    games = [%Game{home_team: "GB", home_prob: 0.5, away_team: "CHI", away_prob: 0.5}]
    outcomes = Probability.outcomes(games)
    assert Enum.member?(outcomes, %Outcome{winners: ["GB"], probability: 0.5})
    assert Enum.member?(outcomes, %Outcome{winners: ["CHI"], probability: 0.5})
  end

  test "it computes probabilities" do
    games = [
      %Game{home_team: "GB", home_prob: 0.75, away_team: "CHI", away_prob: 0.25},
      %Game{home_team: "GB", home_prob: 0.75, away_team: "CHI", away_prob: 0.25},
      %Game{home_team: "GB", home_prob: 0.75, away_team: "CHI", away_prob: 0.25},
      %Game{home_team: "GB", home_prob: 0.75, away_team: "CHI", away_prob: 0.25},
    ]
    outcomes = Probability.outcomes(games)
    assert Enum.member?(outcomes, %Outcome{winners: ~w(CHI CHI CHI CHI), probability: :math.pow(0.25, 4)})
  end

  test "it computes all possible outcomes" do
    games = [
      %Game{home_team: "A0", home_prob: 0.75, away_team: "B0", away_prob: 0.25},
      %Game{home_team: "A1", home_prob: 0.75, away_team: "B1", away_prob: 0.25},
      # ... snip ...
      %Game{home_team: "AE", home_prob: 0.75, away_team: "BE", away_prob: 0.25},
      %Game{home_team: "AF", home_prob: 0.75, away_team: "BF", away_prob: 0.25},
    ]

    assert Enum.count(Probability.outcomes(games)) == :math.pow(2, Enum.count(games))
  end
end

I wasn’t happy with concatentating two lists, though, and after some time away from the keyboard I realized that I could accomplish the same thing with Enum.flat_map/2, turning each outcome generated by the recursive step into two new outcomes, one with the home team winning and one with the away team winning. No test changes were required, everything stayed green and do_outcomes looked like:

defp do_outcomes([game | rest], results) do
    rest
    |> do_outcomes(results)
    |> Enum.flat_map(fn(o) ->
      [
        add_winner(o, game.away_team, game.away_prob),
        add_winner(o, game.home_team, game.home_prob)
      ]
    end)
  end

The next thing I wanted to do was to trim down the number of generated outcomes by removing ones that cannot happen. Once a team loses, it’s probability of winning drops to zero and that team can then be excluded from all generated outcomes. So I wrote a test that looked like this:

test "it excludes outcomes where the away team cannot win" do
  games = [
    %Game{home_team: "A0", home_prob: 0.75, away_team: "B0", away_prob: 0.25},
    %Game{home_team: "A1", home_prob: 0.75, away_team: "B1", away_prob: 0.25},
    %Game{home_team: "A2", home_prob: 1, away_team: "B2", away_prob: 0},
    %Game{home_team: "A3", home_prob: 0.75, away_team: "B3", away_prob: 0.25}
  ]
  outcomes = Probability.outcomes(games)
  refute Enum.any?(outcomes, fn(outcome) -> outcome.probability == 0 end)
end

And I wrote an identical test asserting that home teams are excluded, too.

Initially, I tried to implement this logic with an if statement that would control which games get passed to add_winner. However, when I was Googling for the (non-existent) syntax for an elsif block, I remembered how rare if statements are in Elixir. With a little more thought I recognized this as a natural application for pattern matching in function heads, and added two new do_outcomes functions:

defp do_outcomes([game = %Game{away_prob: 0} | rest], results) do
  rest
  |> do_outcomes(results)
  |> Enum.map(fn(o) -> add_winner(o, game.home_team, game.home_prob) end)
end
defp do_outcomes([game = %Game{home_prob: 0} | rest], results) do
  rest
  |> do_outcomes(results)
  |> Enum.map(fn(o) -> add_winner(o, game.away_team, game.away_prob) end)
end

The tests ran green, I felt good about using pattern matching and I moved on.

About a week later, I was reading through the code again and noticed that my eagerness to pattern match had resulted in some duplicated code. Each implemention of do_outcomes started the same way:

rest
|> do_outcomes(results)
|> Enum.{flat_|}map

Trusting my test coverage, I was able to quickly extract the duplicated code out into a single function. The first step was making sure that all 3 functions were using the same duplicated code. That meant changing Enum.map/2 to Enum.flat_map/2 and returning a list of one element from the mapping function. For example:

defp do_outcomes([game = %Game{away_prob: 0} | rest], results) do
  rest
  |> do_outcomes(results)
  |> Enum.flat_map(fn(o) -> [add_winner(o, game.home_team, game.home_prob)] end)
end

Then, it was just a matter of consolidating the three do_outcomes/2 functions into one, and extracting the different mapping functions:

defp do_outcomes([game | rest], results) do
  rest
  |> do_outcomes(results)
  |> Enum.flat_map(possible_winners_fn(game))
end

defp possible_winners_fn(%Game{away_prob: 0, home_team: team, home_prob: prob}) do
  fn(o) -> [add_winner(o, team, prob)] end
end
defp possible_winners_fn(%Game{home_prob: 0, away_team: team, away_prob: prob}) do
  fn(o) -> [add_winner(o, team, prob)] end
end
defp possible_winners_fn(game) do
  fn(o) ->
    [
      add_winner(o, game.away_team, game.away_prob),
      add_winner(o, game.home_team, game.home_prob)
    ]
  end
end

After making sure the tests were still green, I made one final refactor, using Elixir’s & shortcut for definining the function returned by possible_winners_fn/1 when a team cannot win:

defp possible_winners_fn(%Game{away_prob: 0, home_team: team, home_prob: prob}) do
  &([add_winner(&1, team, prob)])
end

This wasn’t a very intensive refactoring, but it highlighted and re-inforced a few tenets of Elixir programming (and programming in general):

  1. Test coverage helps you refactor with confidence, a fast test suite all the moreso. I could quickly verify that my changes were correct by running the tests I had written, and the tests would routinely run in 0.1 seconds.

  2. Guard clauses and pattern matching in function heads are cleaner than if statements. I was able to encapsulate the logic for dealing with games where the outcome was decided in their own functions, which lead to shorter, easier to understand functions.

  3. Eliminate (or at least reduce) the amount of duplicated code caused by pattern matching in function heads. Removing the duplicated code from the multiple do_outcomes functions revealed that all I really needed were different functions for mapping over the list of other outcomes, based on the current game.

  4. Functions are powerful. Being able to return a function from a function is a powerful concept. My everyday language has been Ruby for the past 5 years, and I’m not sure I could come up with a solution to this problem as clean as the one I arrived at with Elixir.