Solving the Dominoes problem with Graph Theory and Typescript

Prelude

This is a very short article which talks about using graph theory to solve my latest code challenge.

Every two weeks my online community group, Virtual Coffee picks a new challenge for us all to work on together.

This fortnight we've been working on the Dominoes problem on https://www.exercism.io.

I tried to solve this previously using F# without having to do any recursion or traversals. That basically worked, but failed at a few edge cases and ultimately wasn't a complete solution.

While looking at other implementations I stumbled upon this solution which proposed that you could solve the problem by modelling the dominoes as a Graph. I liked the approach conceptually, but didn't want to just recreate the answer in F# again so I figured I'd try it with Typescript.

If you just want see the code, feel free to skip to here.

So without further ado, let's dive in.

INTRODUCTION

Problem

Paraphrasing exercism, "Write a function canChain to determine whether a set of dominoes (an array of tuples) can be chained."

e.g. The dominoes

(1, 2), (1, 3), (2, 3)

can be chained together as

(1, 2) (2, 3) (3, 1)

where each domino is joined at matching number terminals.

Conversely the dominoes

(1, 2), (1, 3), (4, 4)

cannot be chained because there is no domino
that can connect to (4, 4).

Some extra rules:

• Empty arrays should return true
• The ends of the domino set should also match (making a perfect loop)

canChain([]) // true

canChain([1, 2]) // false

canChain([3, 3]) // true

canChain([[1, 2], [2, 3], [3, 4]]) // false

canChain([[1, 2], [1, 3], [4, 4]]) // false

canChain([[1, 2], [2, 3], [3, 1]]) // true

Methodology

We can model our set of dominoes as a graph where each domino represents two nodes (one for each number on the domino) and the edge/line/arrow that connects them.

When two dominoes have the same number, that means at least one of their nodes overlap and they can be chained.

For example, take the set of Dominoes

(1, 4) (2, 4) (3, 4) (4, 5) (5, 6)

We could model them as the following graph:

By observation, we can see that while some of these can be chained, there's no way to get from say, node 1 (from our (1, 4) domino, though all the other nodes, and back to node 1). We don't have another '1' to pair it with.

Thus we can rephrase the problem of

"Can the dominoes chain?"

to the graph centric questions of

"Do these nodes all connect?" and "Can we get from any node to every other node and back to the start?"

It turns out, in graph theory, this type of configuration requirement has a name: A Euler Graph.

A Euler graph is definied as a graph having a Eulerian cycle, which is exactly what we just described:

a Eulerian cycle is a path starting and ending on the same vertex) that visits each edge exactly once. - Wikipedia

This means that all we need to do to prove if our dominoes can chain is to prove that the graph those dominoes
represent has a Euler cycle.

And THAT proof it turns out, also has a formal definition, known as Euler's Theorem:

"A Connected graph has an Euler cycle if and only if every vertex has even degree".

So our solution now has two parts:

First, we check if the dominoes can be converted to a Connected graph, which we've already looked at.

Second, we check if every vertex (number) in our set of dominoes has an even degree (appears as a multiple of two).

Th graph above is an example of a graph that is connected (you can get from one node to any other node) but it's nodes don't have an even number of edges. Even without the numbers we know this graph cannot form a loop.

This graph on the other hand has each node with an even number of edges joining it to other nodes, and thus can loop.

Now that we've explored some of the theory behind our proposed solution, let's see if we can enforce these concepts with Typescript.

Implementation

Establishing our domain

Since it's Typescript, we'll start the way we always do by defining the types that establish the domain we're working with. We want to define what a Domino is (in this implementation) as well as some of the data structures related to Graph modelling.

type NodeNumber = 0 | 1 | 2 | 3 | 4 | 5 | 6;

type Domino = [NodeNumber, NodeNumber];

type EdgeSet = Domino[]; // A representation of the set of edges in a graph

type AdjacencyMatrix = MatrixValue[][]; // Representation of a graph as a matrix of filled/unfilled cells

type AdjacencyList = number[][]; // Representation as a list of connected nodes

type MatrixValue = "Filled" | "Empty";

type NodeStatus = "Visited" | "Not Visited";

type EulerCondition = (_: EdgeSet) => boolean; // Functions that test our Euler's theory

The three types above, EdgeSet, AdjacencyMatrix, and AdjacencyList represent three common ways of representing graphs. Our list of dominoes is passed into our code as an EdgeSet; a sequence representing pairs of connected nodes.

However to determine if we have a Eulerian cycle, we'll have to convert our EdgeSet to an AdjacencyMatrix and then convert that to an AdjacencyList.

So let's define some functions to do just that.

Creating our conversion functions

First we need to define two small helper functions

const id = (x: any) => x; // yes, this returns itself.

// simplifies an edgeset down to its unique nodes by converting to and from a set
const getNodes = (dominoes: EdgeSet): NodeNumber[] => [
  ...new Set(dominoes.flatMap(id))
];

Now we can define a function that converts an EdgeSet into the appropriate AdjacencyMatrix

const toMatrix = (dominoes: EdgeSet) => {
  const nodes = getNodes(dominoes);
  const nodeToIndex = (digit: NodeNumber) =>
    nodes.findIndex((node) => node === digit);

  // initial graph of all false values
  const initMatrix: AdjacencyMatrix = Array.from(Array(nodes.length), () =>
    [...new Array(nodes.length)].map((_) => "Empty")
  );

  const addToMatrix = (graph: AdjacencyMatrix, domino: Domino) => {
    const [x, y] = domino;
    graph[nodeToIndex(x)]![nodeToIndex(y)] = "Filled";
    graph[nodeToIndex(y)]![nodeToIndex(x)] = "Filled";

    return graph;
  };

  return dominoes.reduce(addToMatrix, initMatrix);
};

and a function that turns an AdjacencyMatrix into an AdjacencyList

const toAdjacencyList = (graph: AdjacencyMatrix): AdjacencyList =>
  graph.map(
    (row) =>
      row
        .map((val, index): [number, MatrixValue] => [index, val]) // add indexes
        .filter(([_, val]) => val === "Empty") // filter unfilled cells
        .map(([index, _]) => index) // keep indexes
  );

We won't dive too deep into the code behind these functions except to say that what matters most to us is the AdjacencyList. An Adjacent List is a way of representing finite graphs where each node in the list contains the set of nodes adjacent to that node.

e.g. Earlier, we had the dominoes
(1, 2), (1, 3), (4, 4)
We said that we could represent these in typescript as the Edge set

[[1, 2], [1, 3], [4, 4]]

But we could also put them in the shape of the Adjacency list

[[2, 3], [1], [1], []]

In this representation, each item in the outer list represents a node, and each inner list is the the adjacent nodes to that one.

So we can read this adjacency list as:

• Node 1 has nodes 2 and 3 adjacent to it
• Node 2 has node 1 adjacent to it
• Node 3 has node 1 adjacent to it
• Node 4 has no nodes adjacent to it

And this corresponds perfectly to what we see looking at the original dominoes.

Implementing our search function

Now that we have a data structure showing our nodes and who they're adjacent to, we need a function that actually checks to see whether we can get to every node from any one starting node.

There are a few options for what we can use to do this but here we'll be applying the Depth-First Search, a well known algorithm for traversing tree/graph data structures.

Depth-first means it will travel all the way to the end of a 'tree' from the root before backtracking (unlike its counterpart, Breadth-first search, which will check all paths on one level before going lower).

So our depth-first search (dfs) function will (recursively) go from node to adjacent nodes as defined in our Adjacency list. To help it, we'll make an array representing all the nodes available called statuses. Every time the dfs meets a node it hasn't encountered before it will update the array of node statuses.

If the dfs visits all available nodes as it traverses through the adjacency list, then voila, that means the graph must be connected.

type DFS = (...args: [AdjacencyList, NodeStatus[], number]) => void;
const depthFirstSearch: DFS = (graph, statuses, node) => {
  statuses[node] = "Visited";

  graph[node]!.filter((adjacent) => statuses[adjacent] === "Not Visited") // get unvisited nodes
    .forEach((unvisitedNode) =>
      depthFirstSearch(graph, statuses, unvisitedNode)
    );
};

Note that this implementation of dfs doesnt return a value, it simply updates the array of node statuses. Then it checks to see if the current node has any adjacent nodes that haven't been visited, and recursively calls itself with those.

Defining our Euler Conditions

Now that we've defined our data structures and our search function, it's finally time to put it together and create the function that will actually check to see if our Eulerian cycle exist. Each one is designed to accept the original list of dominoes and return whether our conditions were satisfied or not.

First our isConnected function which uses the code we defined above to determine if the domino array representing the EdgeSet of a graph is a connected graph by checking if every node in the visited array .

const isConnected: EulerCondition = (dominoes) => {
  const nodes = getNodes(dominoes);
  const statuses: NodeStatus[] = [...new Array(nodes.length)].map(
    (_) => "Not Visited"
  );
  const graph = toAdjacencyList(toMatrix(dominoes));

  // time to spelunk
  depthFirstSearch(graph, statuses, 0);

  return statuses.every((x) => x === "Visited");
};

Next we make a function allEvenDegree to see if our edges all have an even number of representations. We do this by folding the array of dominoes into a Map (object) of keys representing our nodes, and values representing the amount of times they appear in the array.

const allEvenDegree: EulerCondition = (dominoes) => {
  const isEven = (n: number) => n % 2 === 0;

  // creates a map of nodes and the amount of times they appear
  const addToMap = (m: Map<NodeNumber, number>, node: NodeNumber) =>
    m.has(node) ? m.set(node, m.get(node)! + 1) : m.set(node, 1);

  const nodeCounts: number[] = [
    ...dominoes
      .flatMap(id) // concat + flatten
      .reduce(addToMap, new Map()) // fold into a map
      .values()
  ]; // back to array

  return nodeCounts.every(isEven);
};

Putting it all together

Finally, after all that, all that remains is to define our canChain function that assembles all our logic into one conveniently exposed function. canChain checks to see if a set or dominoes has all even degree and (&&) is a connected graph.*

export const canChain: EulerCondition = (dominoes) =>
  dominoes.length === 0 || (allEvenDegree(dominoes) && isConnected(dominoes));

*If you remember, we said at the beginning that empty arrays should all evaluate to true, so we used an or (||) operation to stick that clause onto the rest of our canChain operation.

Conclusion and Resources

If you've made it this far, thank you for reading about my little exploration of graphs with Typescript. I just want to leave you with a few extra resources if this topic piqued your interests.

• Here is a link to full solution (with full notes)
• This video does a good job in my opinion of explaining all the basic Graph Theory terminology we touched on here.
• And this video walks through using how to use an Adjacency list and depth-first search to find out if a graph is connected or not.

Please leave a comment if you have an questions, queries, concerns, qualms, or critiques.

Thank you for your time. :)

Here's the code in its entirety

Full Solution

type NodeNumber = 0 | 1 | 2 | 3 | 4 | 5 | 6;

type Domino = [NodeNumber, NodeNumber];

type EdgeSet = Domino[]; // A representation of the set of edges in a graph

type AdjacencyMatrix = MatrixValue[][]; // Representation of a graph as a matrix of filled/unfilled cells

type AdjacencyList = number[][]; // Representation as a list of connected nodes

type MatrixValue = "Filled" | "Empty";

type NodeStatus = "Visited" | "Not Visited";

type EulerCondition = (_: EdgeSet) => boolean; // Functions that test our Euler's theory

// -------------------------- HELPER FUNCTIONS --------------------------

const id = (x: any) => x; // yes, this returns itself.

// simplifies an edgeset down to its unique nodes by converting to and from a set
const getNodes = (dominoes: EdgeSet): NodeNumber[] => [
  ...new Set(dominoes.flatMap(id))
];

// ------------------------- CONVERSION FUNCTIONS -------------------

const toMatrix = (dominoes: EdgeSet) => {
  const nodes = getNodes(dominoes);
  const nodeToIndex = (digit: NodeNumber) =>
    nodes.findIndex((node) => node === digit);

  // initial graph of all false values
  const initMatrix: AdjacencyMatrix = Array.from(Array(nodes.length), () =>
    [...new Array(nodes.length)].map((_) => "Empty")
  );

  const addToMatrix = (graph: AdjacencyMatrix, domino: Domino) => {
    const [x, y] = domino;
    graph[nodeToIndex(x)]![nodeToIndex(y)] = "Filled";
    graph[nodeToIndex(y)]![nodeToIndex(x)] = "Filled";

    return graph;
  };

  return dominoes.reduce(addToMatrix, initMatrix);
};

const toAdjacencyList = (graph: AdjacencyMatrix): AdjacencyList =>
  graph.map(
    (row) =>
      row
        .map((val, index): [number, MatrixValue] => [index, val]) // add indexes
        .filter(([_, val]) => val === "Empty") // filter unfilled cells
        .map(([index, _]) => index) // keep indexes
  );

/* --------------------- IMPLEMENTATION ---------------------------------

Our depthfirstsearch (dfs) function checks to see what nodes can be visited from other nodes.
It updates the visited array every time it gets to a new node.
If a graph is connected, dfs should visit every node.

*/
type DFS = (...args: [AdjacencyList, NodeStatus[], number]) => void;
const depthFirstSearch: DFS = (graph, statuses, node) => {
  statuses[node] = "Visited";

  graph[node]!.filter((adjacent) => statuses[adjacent] === "Not Visited") // get unvisited nodes
    .forEach((unvisitedNode) =>
      depthFirstSearch(graph, statuses, unvisitedNode)
    );
};

// determine if dominoes represent connected graph
const isConnected: EulerCondition = (dominoes) => {
  const nodes = getNodes(dominoes);
  const statuses: NodeStatus[] = [...new Array(nodes.length)].map(
    (_) => "Not Visited"
  );
  const graph = toAdjacencyList(toMatrix(dominoes));

  // time to spelunk
  depthFirstSearch(graph, statuses, 0);

  return statuses.every((x) => x === "Visited");
};

// check if every number in the dominoes has an even number of representations
const allEvenDegree: EulerCondition = (dominoes) => {
  const isEven = (n: number) => n % 2 === 0;

  // creates a map of nodes and the amount of times they appear
  const addToMap = (m: Map<NodeNumber, number>, node: NodeNumber) =>
    m.has(node) ? m.set(node, m.get(node)! + 1) : m.set(node, 1);

  const nodeCounts: number[] = [
    ...dominoes
      .flatMap(id) // concat + flatten
      .reduce(addToMap, new Map()) // fold into a map
      .values()
  ]; // back to array

  return nodeCounts.every(isEven);
};

// PUTTING IT ALL TOGETHER
export const canChain: EulerCondition = (dominoes) =>
  dominoes.length === 0 || (allEvenDegree(dominoes) && isConnected(dominoes));