Published at May 29 2019
·
0 comments

Instructions

Test suite

Solution

Make a chain of dominoes.

Compute a way to order a given set of dominoes in such a way that they form a correct domino chain (the dots on one half of a stone match the dots on the neighbouring half of an adjacent stone) and that dots on the halves of the stones which don't have a neighbour (the first and last stone) 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.

For installation and learning resources, refer to the Ruby resources page.

For running the tests provided, you will need the Minitest gem. Open a terminal window and run the following command to install minitest:

```
gem install minitest
```

If you would like color output, you can `require 'minitest/pride'`

in
the test file, or note the alternative instruction, below, for running
the test file.

Run the tests from the exercise directory using the following command:

```
ruby dominoes_test.rb
```

To include color from the command line:

```
ruby -r minitest/pride dominoes_test.rb
```

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

```
require 'minitest/autorun'
require_relative 'dominoes'
# Common test data version: 2.1.0 b5bc74d
class DominoesTest < Minitest::Test
def test_empty_input_empty_output
# skip
dominoes = []
assert Dominoes.chain?(dominoes)
end
def test_singleton_input_singleton_output
skip
dominoes = [[1, 1]]
assert Dominoes.chain?(dominoes)
end
def test_singleton_that_can_not_be_chained
skip
dominoes = [[1, 2]]
refute Dominoes.chain?(dominoes)
end
def test_three_elements
skip
dominoes = [[1, 2], [3, 1], [2, 3]]
assert Dominoes.chain?(dominoes)
end
def test_can_reverse_dominoes
skip
dominoes = [[1, 2], [1, 3], [2, 3]]
assert Dominoes.chain?(dominoes)
end
def test_can_not_be_chained
skip
dominoes = [[1, 2], [4, 1], [2, 3]]
refute Dominoes.chain?(dominoes)
end
def test_disconnected_simple
skip
dominoes = [[1, 1], [2, 2]]
refute Dominoes.chain?(dominoes)
end
def test_disconnected_double_loop
skip
dominoes = [[1, 2], [2, 1], [3, 4], [4, 3]]
refute Dominoes.chain?(dominoes)
end
def test_disconnected_single_isolated
skip
dominoes = [[1, 2], [2, 3], [3, 1], [4, 4]]
refute Dominoes.chain?(dominoes)
end
def test_need_backtrack
skip
dominoes = [[1, 2], [2, 3], [3, 1], [2, 4], [2, 4]]
assert Dominoes.chain?(dominoes)
end
def test_separate_loops
skip
dominoes = [[1, 2], [2, 3], [3, 1], [1, 1], [2, 2], [3, 3]]
assert Dominoes.chain?(dominoes)
end
def test_nine_elements
skip
dominoes = [[1, 2], [5, 3], [3, 1], [1, 2], [2, 4], [1, 6], [2, 3], [3, 4], [5, 6]]
assert Dominoes.chain?(dominoes)
end
end
```

```
module Dominoes
module_function
def chain?(dominoes)
return true if dominoes.empty?
eulerian_cycle?(dominoes) && connected_graph?(dominoes)
end
# https://en.wikipedia.org/wiki/Eulerian_path
def eulerian_cycle?(dominoes)
dominoes
.flatten
.group_by(&:itself)
.values
.map(&:length)
.all?(&:even?)
end
private_class_method :eulerian_cycle?
def connected_graph?(dominoes)
head, *tail = dominoes
loop do
# tail represents a set of disjoints
# https://en.wikipedia.org/wiki/Intersection_(set_theory)#Intersecting_and_disjoint_sets
intersections, tail = tail.partition { |edge| intersects?(edge, head) }
return true if tail.empty?
return false if intersections.empty?
head.append(*intersections.flatten)
end
end
private_class_method :connected_graph?
def intersects?(edge, head)
(edge & head).any?
end
private_class_method :intersects?
end
```

My initial solution of comparing first/last elements of arrays just couldn't seem to pass tests where there were multiple loops in the data set. Having a look at Paolo Brasolin's solution (https://exercism.io/tracks/ruby/exercises/dominoes/solutions/d3c422716a134de5b4205acc641653d6) completely changed my thinking and got me doing some wikipedia-ing, so kudos to him for a mathematical-yet-still-straightforward-to-understand solution.

Level up your programming skills with 3,373 exercises across 50 languages, and insightful discussion with our volunteer team of welcoming mentors.
Exercism is
**100% free forever**.

## Community comments