2
$\begingroup$

I came across this question in a coding interview and couldn't figure out a good solution.

You are given 6 dominoes. A domino has 2 halves each with a number of spots. You are building a 3-level pyramid of dominoes. The bottom level has 3 dominoes, the middle level has 2, and the top has 1.

The arrangement is such that each level is positioned over the center of the level below it. Here is a visual:

         [ 3 | 4 ]
    [ 2 | 3 ] [ 4 | 5 ]
[ 1 | 2 ][ 3 | 4 ][ 5 | 6 ]

The pyramid must be set up such that the number of spots on each domino half should be the same as the number on the half beneath it. This doesn't apply to neighboring dominoes on the same level.

Is it possible to build a pyramid from 6 dominoes in the arrangement described above? Dominoes can be freely arranged and rotated.

Write a function that takes an array of 12 ints (such that arr[0], arr[1] are the first domino, arr[2], arr[3] are the second domino, etc.) and return "YES" or "NO" if it is possible or not to create a pyramid with the given 6 dominoes.

Thank you.

$\endgroup$
  • 2
    $\begingroup$ Hint: There must be at least two domino pieces which are the same (up to rotation). Can you figure out why? $\endgroup$ – dkaeae Jan 31 '19 at 9:34
  • $\begingroup$ One domino in the top level and second on the bottom level. But this condition is not enough to solve the problem. $\endgroup$ – Alona Korzhnev Jan 31 '19 at 16:36
  • $\begingroup$ @AlonaKorzhnev No, but there are not too many valid options left after you fix these two dominos. You can simply try them all. $\endgroup$ – Discrete lizard Feb 13 '19 at 22:10
1
$\begingroup$

I can think of a brute force solution. Try all 6!*(2^6) options. i.e. create all legal permutations of the pyramid and test each one if it holds the condition. It will take around 50K iterations to do.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This is not a very good solution. Have a look at dkaeae's hint to get a much more efficient solution. $\endgroup$ – Discrete lizard Feb 13 '19 at 22:08
  • $\begingroup$ It does have the virtue of being easy to implement, though... $\endgroup$ – D.W. Mar 15 '19 at 23:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.