package dominoes type Domino [2]int // MakeChain returns a chain and true if the dominoes in input // can be arranged in a legal chain; otherwise it returns nil, false. func MakeChain(input []Domino) (chain []Domino, ok bool) { switch len(input) { case 0: return []Domino{}, true case 1: // A single is legal if the ends match. if input[0][0] == input[0][1] { return input, true } return nil, false } chain, ok = buildDominoChain(input) if !ok { return nil, false } return chain, true } // buildDominoChain looks for a matching domino chain using the 2 or more dominoes in d. func buildDominoChain(d []Domino) ([]Domino, bool) { permuteList := dominoPermutations(d, len(d)) for _, p := range permuteList { chain, ok := arrangeChain(p) if ok { return chain, true } } return nil, false } // arrangeChain uses the dominoes positionally in d[] attempting to make a matching chain; // reversing of sides of any domino is permitted, but the order of dominoes in d remains // the same left to right. func arrangeChain(d []Domino) (chain []Domino, ok bool) { // A good chain will match length of d, so preallocate the chain. chain = make([]Domino, len(d)) n := 0 // Put first domino into the chain for starting point. chain[n] = d[0] // Loop through the remaining dominoes in d, attempting to add them into the chain, // allowing a reverse of either single one in chain or the new domino t at each step. for i := 1; i < len(d); i++ { t := d[i] last := chain[n] if n == 0 && last[0] == t[0] { // reverse first and only item in chain to match t, and add t to chain. chain[n] = reverseDomino(last) chain[n+1] = t } else if n == 0 && last[0] == t[1] { // reverse only item in chain and t to match, and add reversed t to chain. chain[n] = reverseDomino(last) chain[n+1] = reverseDomino(t) } else if last[1] == t[0] { // add t as-is into chain. chain[n+1] = t } else if last[1] == t[1] { // reverse t to match last one in chain, and add reversed t to chain. chain[n+1] = reverseDomino(t) } else { // no match for this chain configuration of d, even with swapping. return nil, false } // chain is now filled in with one more domino. n++ } // Both ends of the chain must also match. if chain[0][0] != chain[len(chain)-1][1] { return nil, false } return chain, true } // reverseDomino returns given Domino x, with its sides reversed/rotated. func reverseDomino(x Domino) Domino { return Domino{x[1], x[0]} } // dominoPermutations returns a slice containing the r length permutations of the elements in iterable. // The implementation is modeled after the Python itertools.permutations(). func dominoPermutations(iterable []Domino, r int) (perms [][]Domino) { pool := iterable n := len(pool) if r > n { return } indices := make([]int, n) for i := range indices { indices[i] = i } cycles := make([]int, r) for i := range cycles { cycles[i] = n - i } result := make([]Domino, r) for i, el := range indices[:r] { result[i] = pool[el] } p := make([]Domino, len(result)) copy(p, result) perms = append(perms, p) for n > 0 { i := r - 1 for ; i >= 0; i-- { cycles[i]-- if cycles[i] == 0 { index := indices[i] for j := i; j < n-1; j++ { indices[j] = indices[j+1] } indices[n-1] = index cycles[i] = n - i } else { j := cycles[i] indices[i], indices[n-j] = indices[n-j], indices[i] for k := i; k < r; k++ { result[k] = pool[indices[k]] } p = make([]Domino, len(result)) copy(p, result) perms = append(perms, p) break } } if i < 0 { return } } return }