List possible train routes on a given model railway

Question

I want to calculate the available routes on a given model railway.

Assumptions:

• All trains only start and stop on defined points which are called train stations.
• Trains do not collide during their trip. No need to worry about that.
• We don't have to think about the length of a train. We assume it is one locomotive which takes the space of an atom.
• On one train station only one train can stop.
• A train can start and stop on the same train station.

The start position and the end position of all trains are stored in a map. All permutations are stored in a list. Example:

iex(1)> Trains.list_routes(["ICE"], ["Hamburg", "Frankfurt"])
[
  %{end: %{"ICE" => "Hamburg"}, start: %{"ICE" => "Hamburg"}},
  %{end: %{"ICE" => "Frankfurt"}, start: %{"ICE" => "Frankfurt"}},
  %{end: %{"ICE" => "Frankfurt"}, start: %{"ICE" => "Hamburg"}},
  %{end: %{"ICE" => "Hamburg"}, start: %{"ICE" => "Frankfurt"}}
]

A model railway could look like this (the red numbers indicate the train stations):

For two trains on that model railway the function would be called this way:

Trains.list_routes([:red_train, :blue_train], ["1", "2", "3", "4", "5"])

Here's my current code:

defmodule Trains do
  @moduledoc """
  Documentation for `Trains`.
  """

  @doc """
  Returns a list of all possible routes.

  ## Examples

      iex> Trains.list_routes([:red_train, :blue_train], ["Station 1", "Station 2"])
      [
        %{
          end: %{blue_train: "Station 2", red_train: "Station 1"},
          start: %{blue_train: "Station 2", red_train: "Station 1"}
        },
        %{
          end: %{blue_train: "Station 1", red_train: "Station 2"},
          start: %{blue_train: "Station 1", red_train: "Station 2"}
        },
        %{
          end: %{blue_train: "Station 1", red_train: "Station 2"},
          start: %{blue_train: "Station 2", red_train: "Station 1"}
        },
        %{
          end: %{blue_train: "Station 2", red_train: "Station 1"},
          start: %{blue_train: "Station 1", red_train: "Station 2"}
        }
      ]
  """
  def list_routes([], []) do
    []
  end

  def list_routes([train], [station]) do
    [
      %{start: %{train => station}, end: %{train => station}}
    ]
  end

  def list_routes([train], [station1, station2]) do
    [
      %{start: %{train => station1}, end: %{train => station1}},
      %{start: %{train => station2}, end: %{train => station2}},
      %{start: %{train => station1}, end: %{train => station2}},
      %{start: %{train => station2}, end: %{train => station1}}
    ]
  end

  def list_routes([train1, train2], [station1, station2]) do
    [
      %{
        start: %{train1 => station1, train2 => station2},
        end: %{train1 => station1, train2 => station2}
      },
      %{
        start: %{train1 => station2, train2 => station1},
        end: %{train1 => station2, train2 => station1}
      },
      %{
        start: %{train1 => station1, train2 => station2},
        end: %{train1 => station2, train2 => station1}
      },
      %{
        start: %{train1 => station2, train2 => station1},
        end: %{train1 => station1, train2 => station2}
      }
    ]
  end

  def list_routes(trains, train_stations) do
    # ???
  end
end

How can I loop through all combinations with list_routes(trains, train_stations) when the number of trains and the number of train_stations is bigger than 1?

Answer 1

Here's a solution for the problem. It uses Formulae.

mix.exs

def deps do
  [{:formulae, "~> 0.8"}]
end

lib/trains.ex

def list_routes([], []) do
  []
end

def list_routes(trains, train_stations)
    when is_list(trains) and
            is_list(train_stations) and 
            length(train_stations) >= length(trains) do
  possible_states =
    Enum.map(Formulae.permutations(train_stations, length(trains)), &Enum.zip(trains, &1))

  for state_start <- possible_states, state_end <- possible_states do
    %{start: state_start, end: state_end}
  end
end

The result:

iex(1)> Trains.list_routes([:red_train, :blue_train], ["Station 1", "Station 2"])
[
  %{
    end: [red_train: "Station 1", blue_train: "Station 2"],
    start: [red_train: "Station 1", blue_train: "Station 2"]
  },
  %{
    end: [red_train: "Station 2", blue_train: "Station 1"],
    start: [red_train: "Station 1", blue_train: "Station 2"]
  },
  %{
    end: [red_train: "Station 1", blue_train: "Station 2"],
    start: [red_train: "Station 2", blue_train: "Station 1"]
  },
  %{
    end: [red_train: "Station 2", blue_train: "Station 1"],
    start: [red_train: "Station 2", blue_train: "Station 1"]
  }
]

Answer 2

It is unclear why the same start and end station is allowed for the case of one train %{start: %{train => station1}, end: %{train => station1}} but not allowed for two trains, according to the code you’ve posted.

The good start would be somewhat along these lines:

iex|1 ▶ {trains, stations} =
  {~w|red_train blue_train|a, ~w|1 2|}  
#⇒ {[:red_train, :blue_train], ["1", "2"]}
iex|2 ▶ (for t1 <- trains, t2<- trains, t1 != t2,
             s1 <- stations, s2 <- stations,
             do: Enum.sort([{t1, s1}, {t2, s2}])
        ) |> Enum.uniq()
#⇒ [
#   [blue_train: "1", red_train: "1"],
#   [blue_train: "2", red_train: "1"],
#   [blue_train: "1", red_train: "2"],
#   [blue_train: "2", red_train: "2"]
# ]

In any case, Kernel.SpecialForms.for/1 comprehension is your best friend here. Whether you need combinations and/or permutations, you might want to take a look at my Formulae library, specifically at Formulae.Combinators.