制作一个多米诺骨牌.

计算给出的多米诺骨牌的排序方法，使它们形成一个正确的多米诺骨牌链(石头的一半上的数值，与相邻石头的一半上的数值相匹配)，并且(第一块石头和最后一块石头)石头的一半上的数值没有邻居，且它们的数值匹配.

比如，给出石头[2|1]，[2|3]和[1|3]你应该计算一些类似[1|2] [2|3] [3|1]或[3|2] [2|1] [1|3]或[1|3] [3|2] [2|1]的东西等，其中第一个和最后一个数字是相同的。

对于以下石头[1|2]，[4|1]和[2|3]，它的结果骨牌链无效：[4|1] [1|2] [2|3]第一个和最后一个数字不一样。4!= 3

一些测试用例可以在一个骨牌链解决方案中，使用重复的石头，假设使用了多个骨牌集合。

pub fn chain(input: &[(u8, u8)]) -> Option<Vec<(u8, u8)>> {
   unimplemented!("From the given input '{:?}' construct a proper dominoes chain or return None if it is not possible.", input);
}

# #![allow(unused_variables)]
#fn main() {
// type Domino = (u8, u8);

#[derive(Debug)]
enum CheckResult {
   GotInvalid, // chain returned None
   Correct,
   ChainingFailure(Vec<Domino>), // failure to match the dots at the right side of one domino with
   // the one on the left side of the next
   LengthMismatch(Vec<Domino>),
   DominoMismatch(Vec<Domino>), // different dominoes are used in input and output
}

use CheckResult::*;

fn normalize(d: &Domino) -> Domino {
   match d {
       &(m, n) if m > n => (n, m),
       &(m, n) => (m, n),
   }
}

fn check(input: &[Domino]) -> CheckResult {
   let output = match chain(input) {
       None => return GotInvalid,
       Some(o) => o,
   };
   if input.len() != output.len() {
       return LengthMismatch(output);
   } else if input.len() == 0 {
       // and thus output.len() == 0
       return Correct;
   }

   let mut output_sorted = output.iter().map(|d| normalize(d)).collect::<Vec<Domino>>();
   output_sorted.sort();
   let mut input_sorted = input.iter().map(|d| normalize(d)).collect::<Vec<Domino>>();
   input_sorted.sort();
   if input_sorted != output_sorted {
       return DominoMismatch(output);
   }

   // both input and output have at least 1 element
   // This essentially puts the first element after the last one, thereby making it
   // easy to check whether the domino chains "wraps around".
   let mut fail = false;
   {
       let mut n = output[0].1;
       let iter = output.iter().skip(1).chain(output.iter().take(1));
       for &(first, second) in iter {
           if n != first {
               fail = true;
               break;
           }
           n = second
       }
   }
   if fail {
       ChainingFailure(output)
   } else {
       Correct
   }
}

fn assert_correct(input: &[Domino]) {
   match check(&input) {
       Correct => (),
       GotInvalid => panic!("Unexpectedly got invalid on input {:?}", input),
       ChainingFailure(output) => panic!(
           "Chaining failure for input {:?}, output {:?}",
           input, output
       ),
       LengthMismatch(output) => {
           panic!("Length mismatch for input {:?}, output {:?}", input, output)
       }
       DominoMismatch(output) => {
           panic!("Domino mismatch for input {:?}, output {:?}", input, output)
       }
   }
}

#[test]
fn empty_input_empty_output() {
   let input = &[];
   assert_eq!(chain(input), Some(vec![]));
}

#[test]
//#[ignore]
fn singleton_input_singleton_output() {
   let input = &[(1, 1)];
   assert_correct(input);
}

#[test]
//#[ignore]
fn singleton_that_cant_be_chained() {
   let input = &[(1, 2)];
   assert_eq!(chain(input), None);
}

#[test]
//#[ignore]
fn no_repeat_numbers() {
   let input = &[(1, 2), (3, 1), (2, 3)];
   assert_correct(input);
}

#[test]
//#[ignore]
fn can_reverse_dominoes() {
   let input = &[(1, 2), (1, 3), (2, 3)];
   assert_correct(input);
}

#[test]
//#[ignore]
fn no_chains() {
   let input = &[(1, 2), (4, 1), (2, 3)];
   assert_eq!(chain(input), None);
}

#[test]
//#[ignore]
fn disconnected_simple() {
   let input = &[(1, 1), (2, 2)];
   assert_eq!(chain(input), None);
}

#[test]
//#[ignore]
fn disconnected_double_loop() {
   let input = &[(1, 2), (2, 1), (3, 4), (4, 3)];
   assert_eq!(chain(input), None);
}

#[test]
//#[ignore]
fn disconnected_single_isolated() {
   let input = &[(1, 2), (2, 3), (3, 1), (4, 4)];
   assert_eq!(chain(input), None);
}

#[test]
//#[ignore]
fn need_backtrack() {
   let input = &[(1, 2), (2, 3), (3, 1), (2, 4), (2, 4)];
   assert_correct(input);
}

#[test]
//#[ignore]
fn separate_loops() {
   let input = &[(1, 2), (2, 3), (3, 1), (1, 1), (2, 2), (3, 3)];
   assert_correct(input);
}

#[test]
//#[ignore]
fn nine_elements() {
   let input = &[
       (1, 2),
       (5, 3),
       (3, 1),
       (1, 2),
       (2, 4),
       (1, 6),
       (2, 3),
       (3, 4),
       (5, 6),
   ];
   assert_correct(input);
}

#}

# #![allow(unused_variables)]
#fn main() {
use std::iter;

pub type Domino = (u8, u8);

/// A table keeping track of available dominoes.
///
/// Effectively a 6x6 matrix. Each position denotes whether a domino is available with that column
/// dots and row dots. Positions are mirrored ((3,4) == (4,3)), except for positions with equal row
/// and column numbers.
struct AvailabilityTable {
   m: Vec<u8>,
}

impl AvailabilityTable {
   fn new() -> AvailabilityTable {
       AvailabilityTable {
           m: iter::repeat(0).take(6 * 6).collect(),
       }
   }

   fn get(&self, x: u8, y: u8) -> u8 {
       self.m[((x - 1) * 6 + (y - 1)) as usize]
   }

   fn set(&mut self, x: u8, y: u8, v: u8) {
       let m = &mut self.m[..];
       m[((x - 1) * 6 + (y - 1)) as usize] = v;
   }

   fn add(&mut self, x: u8, y: u8) {
       if x == y {
           let n = self.get(x, y);
           self.set(x, y, n + 1) // Along the diagonal
       } else {
           let m = self.get(x, y);
           self.set(x, y, m + 1);
           let n = self.get(y, x);
           self.set(y, x, n + 1);
       }
   }

   fn remove(&mut self, x: u8, y: u8) {
       if self.get(x, y) > 0 {
           if x == y {
               let n = self.get(x, y);
               self.set(x, y, n - 1) // Along the diagonal
           } else {
               let m = self.get(x, y);
               self.set(x, y, m - 1);
               let n = self.get(y, x);
               self.set(y, x, n - 1);
           }
       } else {
           // For this toy code hard explicit fail is best
           panic!("remove for 0 stones: ({:?}, {:?})", x, y)
       }
   }

   fn pop_first(&mut self, x: u8) -> Option<u8> {
       for y in 1..7 {
           if self.get(x, y) > 0 {
               self.remove(x, y);
               return Some(y);
           }
       }
       None
   }
}

pub fn chain(dominoes: &[Domino]) -> Option<Vec<Domino>> {
   match dominoes.len() {
       0 => Some(vec![]),
       1 => if dominoes[0].0 == dominoes[0].1 {
           Some(vec![dominoes[0]])
       } else {
           None
       },
       _ => {
           // First check if the total number of each amount of dots is even, if not it's not
           // possible to complete a cycle. This follows from that it's an Eulerian path.
           let mut v: Vec<u8> = vec![0, 0, 0, 0, 0, 0];
           // Keep the mutable borrow in a small scope here to allow v.iter().
           {
               let vs = &mut v[..];
               for dom in dominoes.iter() {
                   vs[dom.0 as usize - 1] += 1;
                   vs[dom.1 as usize - 1] += 1;
               }
           }
           for n in v.iter() {
               if n % 2 != 0 {
                   return None;
               }
           }
           let chain = chain_worker(dominoes);
           if chain.len() == dominoes.len() {
               Some(chain)
           } else {
               None
           }
       }
   }
}

fn chain_worker(dominoes: &[Domino]) -> Vec<Domino> {
   let mut doms = dominoes.to_vec();
   let first = doms.pop().unwrap();
   let mut t = AvailabilityTable::new();
   for dom in doms.iter() {
       t.add(dom.0, dom.1)
   }
   let mut v: Vec<Domino> = Vec::new();
   v.push(first);
   let mut n = first.1; // Number to connect to
   while let Some(m) = t.pop_first(n) {
       v.push((n, m));
       n = m;
   }
   v
}

#}