🎉 Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io 🎉 # angelikatyborska's solution

## to Dominoes in the Ruby Track

Published at Jul 13 2018 · 3 comments
Instructions
Test suite
Solution

#### Note:

This solution was written on an old version of Exercism. The tests below might not correspond to the solution code, and the exercise may have changed since this code was written.

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 halfs 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 exercism help 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
``````

## Submitting Incomplete Solutions

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

### dominoes_test.rb

``````require 'minitest/autorun'
require_relative 'dominoes'

# Common test data version: 2.0.0 b4ceaf4
class DominoesTest < Minitest::Test
def test_empty_input_empty_output
# skip
input_dominoes = []
output_chain = Dominoes.chain(input_dominoes)
assert_correct_chain(input_dominoes, output_chain)
end

def test_singleton_input_singleton_output
skip
input_dominoes = [[1, 1]]
output_chain = Dominoes.chain(input_dominoes)
assert_correct_chain(input_dominoes, output_chain)
end

def test_singleton_that_can_not_be_chained
skip
input_dominoes = [[1, 2]]
output_chain = Dominoes.chain(input_dominoes)
refute_correct_chain(input_dominoes, output_chain)
end

def test_three_elements
skip
input_dominoes = [[1, 2], [3, 1], [2, 3]]
output_chain = Dominoes.chain(input_dominoes)
assert_correct_chain(input_dominoes, output_chain)
end

def test_can_reverse_dominoes
skip
input_dominoes = [[1, 2], [1, 3], [2, 3]]
output_chain = Dominoes.chain(input_dominoes)
assert_correct_chain(input_dominoes, output_chain)
end

def test_can_not_be_chained
skip
input_dominoes = [[1, 2], [4, 1], [2, 3]]
output_chain = Dominoes.chain(input_dominoes)
refute_correct_chain(input_dominoes, output_chain)
end

def test_disconnected_simple
skip
input_dominoes = [[1, 1], [2, 2]]
output_chain = Dominoes.chain(input_dominoes)
refute_correct_chain(input_dominoes, output_chain)
end

def test_disconnected_double_loop
skip
input_dominoes = [[1, 2], [2, 1], [3, 4], [4, 3]]
output_chain = Dominoes.chain(input_dominoes)
refute_correct_chain(input_dominoes, output_chain)
end

def test_disconnected_single_isolated
skip
input_dominoes = [[1, 2], [2, 3], [3, 1], [4, 4]]
output_chain = Dominoes.chain(input_dominoes)
refute_correct_chain(input_dominoes, output_chain)
end

def test_need_backtrack
skip
input_dominoes = [[1, 2], [2, 3], [3, 1], [2, 4], [2, 4]]
output_chain = Dominoes.chain(input_dominoes)
assert_correct_chain(input_dominoes, output_chain)
end

def test_separate_loops
skip
input_dominoes = [[1, 2], [2, 3], [3, 1], [1, 1], [2, 2], [3, 3]]
output_chain = Dominoes.chain(input_dominoes)
assert_correct_chain(input_dominoes, output_chain)
end

def test_nine_elements
skip
input_dominoes = [[1, 2], [5, 3], [3, 1], [1, 2], [2, 4], [1, 6], [2, 3], [3, 4], [5, 6]]
output_chain = Dominoes.chain(input_dominoes)
assert_correct_chain(input_dominoes, output_chain)
end

# Problems in exercism evolve over time, as we find better ways to ask
# questions.
# The version number refers to the version of the problem you solved,
#
# Define a constant named VERSION inside of the top level BookKeeping
# module, which may be placed near the end of your file.
#
# In your file, it will look like this:
#
# module BookKeeping
#   VERSION = 1 # Where the version number matches the one in the test.
# end
#
# http://ruby-doc.org/docs/ruby-doc-bundle/UsersGuide/rg/constants.html
def test_bookkeeping
skip
assert_equal 1, BookKeeping::VERSION
end

# It's infeasible to use example-based tests for this exercise,
# because the list of acceptable answers for a given input can be quite large.
# Instead, we verify certain properties of a correct chain.

def assert_correct_chain(input_dominoes, output_chain)
refute_nil output_chain, "There should be a chain for #{input_dominoes}"
assert_same_dominoes(input_dominoes, output_chain)
return if output_chain.empty?
assert_consecutive_dominoes_match(output_chain)
assert_dominoes_at_end_match(output_chain)
end

def assert_same_dominoes(input_dominoes, output_chain)
input_normal = input_dominoes.map(&:sort).sort
output_normal = output_chain.map(&:sort).sort
assert_equal input_normal, output_normal,
'Dominoes used in the output must be the same as the ones given in the input'
end

def assert_consecutive_dominoes_match(chain)
chain.each_cons(2).with_index { |(d1, d2), i|
assert_equal d1.last, d2.first,
"In chain #{chain}, right end of domino #{i} (#{d1}) and left end of domino #{i + 1} (#{d2}) must match"
}
end

def assert_dominoes_at_end_match(chain)
first_domino = chain.first
last_domino = chain.last
assert_equal first_domino.first, last_domino.last,
"In chain #{chain}, left end of first domino (#{first_domino}) and right end of last domino (#{last_domino}) must match"
end

def refute_correct_chain(input_dominoes, output_chain)
assert_nil output_chain, "There should be no chain for #{input_dominoes}"
end
end``````

### book_keeping.rb

``````module BookKeeping
VERSION = 1
end``````

### domino.rb

``````class Domino
def initialize(left, right)
@value = [left, right]
end

def rotate!
@value = @value.reverse
end

def matches_right?(other_domino)
right == other_domino.left
end

def left
@value
end

def right
@value
end

def to_s
"[ #{left} | #{right} ]"
end
end``````

### domino_chain.rb

``````class DominoChain < Array
def loop?
empty? || last.matches_right?(first)
end

def matches_right?(domino)
empty? ||
last.matches_right?(domino) ||
(domino.rotate! && last.matches_right?(domino))
end

def to_s
map(&:to_s).join(' ')
end
end``````

### dominoes.rb

``````require_relative 'domino'
require_relative 'domino_chain'
require_relative 'book_keeping'

class Dominoes
class << self
def chain(values)
dominoes = DominoChain.new(values.map { |value| Domino.new(*value) })
chain = form_chain(DominoChain.new, dominoes)

if chain
chain.map { |domino| [domino.left, domino.right] }
end
end

def form_chain(current_chain, dominoes)
if dominoes.empty?
current_chain.loop? ? current_chain : nil
else
i = -1
chain = nil

while dominoes[i += 1] && !chain
chain = try_candidate(current_chain, dominoes, i)
end

chain
end
end

def try_candidate(current_chain, dominoes, i)
candidate = dominoes[i]
new_dominoes = dominoes.dup
new_dominoes.delete_at(i)

if current_chain.matches_right?(candidate)
new_chain = current_chain.dup
new_chain.push(candidate)
form_chain(new_chain, new_dominoes)
end
end
end
end`````` Solution Author
commented over 3 years ago

I just realized I can submit multiple files to exercism <3 no more cramming many classes into a single file. I just realized I can submit multiple files to exercism <3 no more cramming many classes into a single file.

Exercism for the win :)

Also, the code looks amazing. I especially love the naming!

### What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

• What compromises have been made?