🎉 Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io 🎉
Avatar of srwatlanta

srwatlanta's solution

to Dominoes in the Ruby Track

Published at Jan 21 2021 · 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

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.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
class Dominoes
  attr_reader :dominoes

  def self.chain?(dominoes)
    return true if dominoes.empty?
    return false unless pair_check(dominoes)
    tree(dominoes).valid?
  end

  def self.tree(dominoes)
    SearchNode.new([], dominoes)
  end

  def self.pair_check(dominoes)
    dominoes.flatten.tally.all?{|_, v| v.even? }
  end
end

class SearchNode
  attr_reader :history, :dominoes, :children

  def initialize(history = [], dominoes = [])
    @history = history
    @dominoes = dominoes
    @children = []
    place_domino unless empty_dominoes?
  end

  def valid?
    empty_dominoes? ? cycle? : @children.any?(&:valid?)
  end

  def cycle?
    start == finish
  end

  def empty_dominoes?
    @dominoes.empty?
  end

  def start
    @history[0][0]
  end

  def finish
    @history[-1][1]
  end

  def place_domino
    @dominoes.each_with_index do |d, i|
      domino =  next_domino(d)
      add_to_children(domino, i) if domino
    end
  end

  def add_to_children(d, i)
    @children.push(SearchNode.new(@history.dup.push(d), @dominoes.dup.tap { |x| x.delete_at(i) }))
  end

  def next_domino(d)
    return d if @history.empty? || d[0] == finish

    flip_domino(d) if d[1] == finish
  end

  def flip_domino(d)
    d.reverse
  end
end

Community comments

Find this solution interesting? Ask the author a question to learn more.

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?
  • Are there new concepts here that you could read more about to improve your understanding?