Beginner Exercism • javascript

Dominoes

Challenge Overview

Make a chain of dominoes.

Introduction

In Toyland, the trains are always busy delivering treasures across the city, from shiny marbles to rare building blocks. The tracks they run on are made of colorful domino-shaped pieces, each marked with two numbers. For the trains to move, the dominoes must form a perfect chain where the numbers match.

Today, an urgent delivery of rare toys is on hold. You’ve been handed a set of track pieces to inspect. If they can form a continuous chain, the train will be on its way, bringing smiles across Toyland. If not, the set will be discarded, and another will be tried.

The toys are counting on you to solve this puzzle. Will the dominoes connect the tracks and send the train rolling, or will the set be left behind?

Instructions

Make a chain of dominoes.

Compute a way to order a given set of domino stones so that they form a correct domino chain. In the chain, the dots on one half of a stone must match the dots on the neighboring half of an adjacent stone. Additionally, the dots on the halves of the stones without neighbors (the first and last stone) must match each other.

For example given the stones [2|1], [2|3] and [1|3] you should compute something like [1|2] [2|3] [3|1] or [3|2] [2|1] [1|3] or [1|3] [3|2] [2|1] etc, where the first and last numbers are the same.

For stones [1|2], [4|1] and [2|3] the resulting chain is not valid: [4|1] [1|2] [2|3]’s first and last numbers are not the same. 4 != 3

Some test cases may use duplicate stones in a chain solution, assume that multiple Domino sets are being used.

Source: Exercism javascript/dominoes

💡 View Solution

export const chain = (dominoes) => {
  if (dominoes.length === 0) return [];
  if (dominoes.length === 1) {
    return dominoes[0][0] === dominoes[0][1] ? dominoes : null;
  }

  const solve = (currentChain, remaining) => {
    if (remaining.length === 0) {
      const first = currentChain[0][0];
      const last = currentChain[currentChain.length - 1][1];
      return first === last ? currentChain : null;
    }

    const lastVal = currentChain[currentChain.length - 1][1];
    for (let i = 0; i < remaining.length; i++) {
      const [d1, d2] = remaining[i];
      const nextRemaining = [...remaining.slice(0, i), ...remaining.slice(i + 1)];
      
      if (d1 === lastVal) {
        const res = solve([...currentChain, [d1, d2]], nextRemaining);
        if (res) return res;
      }
      if (d2 === lastVal) {
        const res = solve([...currentChain, [d2, d1]], nextRemaining);
        if (res) return res;
      }
    }
    return null;
  };

  for (let i = 0; i < dominoes.length; i++) {
    const res = solve([dominoes[i]], [...dominoes.slice(0, i), ...dominoes.slice(i + 1)]);
    if (res) return res;
    const resRev = solve([[dominoes[i][1], dominoes[i][0]]], [...dominoes.slice(0, i), ...dominoes.slice(i + 1)]);
    if (resRev) return resRev;
  }

  return null;
};