Guest User

Two Boys in a Canoe

a guest
Mar 15th, 2016
100
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. type WeightType = u32;
  2. const TARGET_WEIGHT: WeightType = 150;
  3.  
  4. #[derive(Clone, Debug)]
  5. pub struct Boy {
  6.     name: String,
  7.     weight: WeightType,
  8. }
  9.  
  10. pub type CubPack = Vec<Boy>;
  11.  
  12. #[derive(Debug)]
  13. pub enum Canoe {
  14.     Solo(Boy),
  15.     Duet(Boy, Boy),
  16. }
  17.  
  18. impl Canoe {
  19.     fn weight(&self) -> WeightType {
  20.         match *self {
  21.             Canoe::Solo(ref boy) => boy.weight,
  22.             Canoe::Duet(ref b0, ref b1) => b0.weight + b1.weight,
  23.         }
  24.     }
  25. }
  26.  
  27. pub type Canoes = Vec<Canoe>;
  28.  
  29. pub fn assign_canoes(cubs: &CubPack) -> Canoes {
  30.     let mut canoes: Canoes = Vec::new();
  31.     let mut cubs = cubs.clone();
  32.     cubs.sort_by_key(|boy| boy.weight + 0);
  33.     let mut assigned: Vec<bool> = cubs.iter().map(|_| false).collect();
  34.     let mut heavy = cubs.len();
  35.     for light in 0..cubs.len() {
  36.         if assigned[light] {
  37.             continue;
  38.         }
  39.         while !assigned[light] && heavy > light + 1 {
  40.             if cubs[light].weight + cubs[heavy - 1].weight <= TARGET_WEIGHT {
  41.                 assigned[light] = true;
  42.                 assigned[heavy - 1] = true;
  43.                 canoes.push(Canoe::Duet(cubs[light].clone(),
  44.                                         cubs[heavy - 1].clone()));
  45.             }
  46.             heavy -= 1;
  47.         }
  48.         if !assigned[light] {
  49.             canoes.push(Canoe::Solo(cubs[light].clone()));
  50.             assigned[light] = true;
  51.         }
  52.     }
  53.     canoes
  54. }
  55.  
  56. fn cub_pack() -> CubPack {
  57.     vec![
  58.         Boy { name: "Billy".to_string(), weight: 93 },
  59.         Boy { name: "Timmy".to_string(), weight: 67 },
  60.         Boy { name: "Johnny".to_string(), weight: 119 },
  61.         Boy { name: "Bobby".to_string(), weight: 113 },
  62.         Boy { name: "Ralphie".to_string(), weight: 110 },
  63.         Boy { name: "Bart".to_string(), weight: 114 },
  64.         Boy { name: "Carter".to_string(), weight: 83 },
  65.         Boy { name: "Davey".to_string(), weight: 101 },
  66.         Boy { name: "Kevin".to_string(), weight: 47 },
  67.         Boy { name: "Alan".to_string(), weight: 112 },
  68.         Boy { name: "Eric".to_string(), weight: 49 },
  69.         Boy { name: "Craig".to_string(), weight: 54 },
  70.         Boy { name: "Brad".to_string(), weight: 85 },
  71.     ]
  72. }
  73. fn main() {
  74.     let canoes = assign_canoes(&cub_pack());
  75.     for canoe in canoes {
  76.         match canoe {
  77.             Canoe::Solo(ref boy) => {
  78.                 println!("{} lb: {}", canoe.weight(), boy.name)
  79.             }
  80.             Canoe::Duet(ref b0, ref b1) => {
  81.                 println!("{} lb: {}, {}", canoe.weight(), b0.name, b1.name)
  82.             }
  83.         }
  84.     }
  85. }
  86.  
  87. #[cfg(test)]
  88. mod tests {
  89.     use super::*;
  90.  
  91.     #[test]
  92.     fn test_none() {
  93.         let cub_pack: CubPack = vec![];
  94.         let canoes = assign_canoes(&cub_pack);
  95.         assert!(canoes.len() == 0);
  96.     }
  97.  
  98.     #[test]
  99.     fn test_solos() {
  100.         let cub_pack: CubPack = vec![
  101.             Boy { name: "Billy".to_string(), weight: 85 },
  102.             Boy { name: "Timmy".to_string(), weight: 80 },
  103.             ];
  104.         let canoes = assign_canoes(&cub_pack);
  105.         assert!(canoes.len() == 2);
  106.         if let Canoe::Solo(ref boy) = canoes[0] {
  107.             assert!(boy.name == "Timmy");
  108.             assert!(boy.weight == 80);
  109.         } else {
  110.             panic!("");
  111.         }
  112.         if let Canoe::Solo(ref boy) = canoes[1] {
  113.             assert!(boy.name == "Billy");
  114.             assert!(boy.weight == 85);
  115.         } else {
  116.             panic!("");
  117.         }
  118.     }
  119.  
  120.     #[test]
  121.     fn test_duet() {
  122.         let cub_pack: CubPack = vec![
  123.             Boy { name: "Billy".to_string(), weight: 80 },
  124.             Boy { name: "Timmy".to_string(), weight: 70 },
  125.             ];
  126.         let canoes = assign_canoes(&cub_pack);
  127.         assert!(canoes.len() == 1);
  128.         if let Canoe::Duet(ref b0, ref b1) = canoes[0] {
  129.             assert!(b0.name == "Timmy");
  130.             assert!(b0.weight == 70);
  131.             assert!(b1.name == "Billy");
  132.             assert!(b1.weight == 80);
  133.         } else {
  134.             panic!("");
  135.         }
  136.     }
  137.  
  138.     #[test]
  139.     fn test_mixed() {
  140.         let cub_pack: CubPack = vec![
  141.             Boy { name: "Billy".to_string(), weight: 80 },
  142.             Boy { name: "Kevin".to_string(), weight: 70 },
  143.             Boy { name: "Timmy".to_string(), weight: 70 },
  144.             ];
  145.         let canoes = assign_canoes(&cub_pack);
  146.         assert!(canoes.len() == 2);
  147.         if let Canoe::Duet(ref b0, ref b1) = canoes[0] {
  148.             assert!(b0.name == "Kevin");
  149.             assert!(b0.weight == 70);
  150.             assert!(b1.name == "Billy");
  151.             assert!(b1.weight == 80);
  152.         } else {
  153.             panic!("");
  154.         }
  155.         if let Canoe::Solo(ref boy) = canoes[1] {
  156.             assert!(boy.name == "Timmy");
  157.             assert!(boy.weight == 70);
  158.         } else {
  159.             panic!("");
  160.         }
  161.     }
  162. }
RAW Paste Data