day22 part1

2 files changed, 267 insertions, 1 deletions

diff --git a/input22 b/input22
new file mode 100644
index 0000000..69ee3cf
--- /dev/null
+++ b/input22
@@ -0,0 +1,100 @@
+cut 9712
+deal with increment 23
+cut 6635
+deal with increment 18
+cut 887
+deal with increment 47
+deal into new stack
+deal with increment 53
+cut -1593
+deal with increment 3
+cut -6676
+deal with increment 69
+cut -4313
+deal with increment 55
+cut 609
+deal with increment 42
+deal into new stack
+deal with increment 51
+deal into new stack
+cut 880
+deal with increment 75
+cut -964
+deal with increment 33
+cut 7911
+deal with increment 71
+deal into new stack
+cut -5716
+deal with increment 52
+cut 5969
+deal with increment 30
+cut -3508
+deal with increment 25
+cut -7645
+deal with increment 29
+cut 8929
+deal into new stack
+cut 4850
+deal with increment 34
+cut -1
+deal with increment 55
+cut 7491
+deal with increment 74
+cut 3331
+deal with increment 35
+cut 8433
+deal into new stack
+deal with increment 66
+cut 3725
+deal with increment 3
+deal into new stack
+deal with increment 19
+deal into new stack
+cut -8821
+deal with increment 27
+deal into new stack
+cut -9853
+deal with increment 71
+cut -9286
+deal with increment 39
+deal into new stack
+cut 4288
+deal into new stack
+deal with increment 11
+deal into new stack
+deal with increment 50
+cut 153
+deal with increment 32
+cut 6836
+deal with increment 65
+cut 9504
+deal with increment 11
+deal into new stack
+cut -7646
+deal with increment 4
+cut 5795
+deal with increment 65
+deal into new stack
+deal with increment 23
+cut 7208
+deal with increment 17
+deal into new stack
+cut -5333
+deal with increment 18
+deal into new stack
+deal with increment 46
+deal into new stack
+deal with increment 73
+cut 1661
+deal with increment 34
+cut 7121
+deal with increment 13
+cut 1266
+deal with increment 71
+cut 2328
+deal with increment 6
+cut 6005
+deal with increment 49
+cut -3871
+deal with increment 9
+cut 8441
diff --git a/src/main.rs b/src/main.rs
index 9d42f8d..dbbed11 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1939,8 +1939,114 @@ fn day21() {
     }
 }
 
+#[derive(Clone, Copy)]
+enum ShuffleTechnique {
+    DealInto,
+    CutN { n: i64 },
+    DealInc { n: u128 },
+}
+
+impl ShuffleTechnique {
+    fn parse(input: &str) -> ShuffleTechnique {
+        if input == "deal into new stack" {
+            ShuffleTechnique::DealInto
+        } else if input.find("cut").is_some() {
+            let n = input.split_at(4).1.parse::<i64>().unwrap();
+            ShuffleTechnique::CutN { n }
+        }
+        else if input.find("deal with increment").is_some() {
+            let n = input.split_at(20).1.parse::<u128>().unwrap();
+            ShuffleTechnique::DealInc { n }
+        }
+        else {
+            panic!("unsupported technique")
+        }
+    }
+}
+
+struct SpaceCards {
+    deck: VecDeque<usize>,
+}
+
+impl SpaceCards {
+    fn new(size: usize) -> SpaceCards {
+        SpaceCards {
+            deck: (0..size).collect()
+        }
+    }
+
+    fn shuffle(&mut self, technique: ShuffleTechnique) {
+        match technique {
+            ShuffleTechnique::DealInto => {
+                self.deck = self.deck.iter().rev().copied().collect();
+            },
+            ShuffleTechnique::CutN { n } => {
+                if n >= 0 {
+                    self.deck.rotate_left(n as usize);
+                } else {
+                    self.deck.rotate_right(n.abs() as usize);
+                }
+            },
+            ShuffleTechnique::DealInc { n } => {
+                let mut deck = VecDeque::new();
+                deck.resize(self.deck.len(), 0);
+                let mut pos = 0;
+                for c in self.deck.iter() {
+                    deck[pos] = *c;
+                    pos += n as usize;
+                    pos %= self.deck.len();
+                }
+                self.deck = deck;
+            },
+        }
+    }
+
+    fn unshuffle(size: u128, pos: u128, technique: ShuffleTechnique) -> u128 {
+        match technique {
+            ShuffleTechnique::DealInto => {
+                size - pos - 1
+            },
+            ShuffleTechnique::CutN { n } => {
+                let shift = if n < 0 {
+                    size - (n.abs() as u128)
+                } else {
+                    n as u128
+                };
+                (pos + shift) % size
+            },
+            ShuffleTechnique::DealInc { n } => {
+                // n*x = t*size + pos
+                // x = (t*size + pos) / n
+                let mut x = None;
+                for t in 0..n {
+                    let tmp = t * size + pos;
+                    if tmp % n == 0 {
+                        x = Some(tmp / n);
+                        break;
+                    }
+                }
+                x.unwrap()
+            },
+        }
+    }
+}
+
+fn day22() {
+    let input = read_file("input22");
+    let input = input.trim_end();
+    let shuffles: Vec<ShuffleTechnique> = input.split('\n')
+                                               .map(|t| ShuffleTechnique::parse(t))
+                                               .collect();
+
+    let mut cards = SpaceCards::new(10007);
+    for technique in &shuffles {
+        cards.shuffle(*technique);
+    }
+    println!("22a: {}", cards.deck.iter().position(|&c| c == 2019).unwrap());
+}
+
 fn main() {
-    day21();
+    day22();
 }
 
 #[cfg(test)]
@@ -2247,4 +2353,64 @@ mod tests {
         }
         assert_eq!(values[0..8], [5,2,4,3,2,1,3,3]);
     }
+
+    #[test]
+    fn test_day22() {
+        let techniques = vec![
+            ShuffleTechnique::parse("deal with increment 7"),
+            ShuffleTechnique::parse("deal into new stack"),
+            ShuffleTechnique::parse("deal into new stack"),
+        ];
+        let mut cards = SpaceCards::new(10);
+
+        for technique in techniques {
+            cards.shuffle(technique);
+        }
+        assert_eq!(cards.deck, [0,3,6,9,2,5,8,1,4,7]);
+
+        let techniques = vec![
+            ShuffleTechnique::parse("cut 6"),
+            ShuffleTechnique::parse("deal with increment 7"),
+            ShuffleTechnique::parse("deal into new stack"),
+        ];
+        let mut cards = SpaceCards::new(10);
+        for technique in techniques {
+            cards.shuffle(technique);
+        }
+        assert_eq!(cards.deck, [3,0,7,4,1,8,5,2,9,6]);
+
+        let techniques = vec![
+            ShuffleTechnique::parse("deal into new stack"),
+            ShuffleTechnique::parse("cut -2"),
+            ShuffleTechnique::parse("deal with increment 7"),
+            ShuffleTechnique::parse("cut 8"),
+            ShuffleTechnique::parse("cut -4"),
+            ShuffleTechnique::parse("deal with increment 7"),
+            ShuffleTechnique::parse("cut 3"),
+            ShuffleTechnique::parse("deal with increment 9"),
+            ShuffleTechnique::parse("deal with increment 3"),
+            ShuffleTechnique::parse("cut -1"),
+        ];
+        let mut cards = SpaceCards::new(10);
+        for technique in techniques {
+            cards.shuffle(technique);
+        }
+        assert_eq!(cards.deck, [9,2,5,8,1,4,7,0,3,6]);
+
+
+        assert_eq!(SpaceCards::unshuffle(10, 2, ShuffleTechnique::DealInto), 7);
+        assert_eq!(SpaceCards::unshuffle(10, 8, ShuffleTechnique::DealInto), 1);
+
+        assert_eq!(SpaceCards::unshuffle(10, 0, ShuffleTechnique::CutN {n: 3}), 3);
+        assert_eq!(SpaceCards::unshuffle(10, 3, ShuffleTechnique::CutN {n: 3}), 6);
+        assert_eq!(SpaceCards::unshuffle(10, 0, ShuffleTechnique::CutN {n: -4}), 6);
+        assert_eq!(SpaceCards::unshuffle(10, 8, ShuffleTechnique::CutN {n: -4}), 4);
+
+        assert_eq!(SpaceCards::unshuffle(10, 0, ShuffleTechnique::DealInc {n: 3}), 0);
+        assert_eq!(SpaceCards::unshuffle(10, 3, ShuffleTechnique::DealInc {n: 3}), 1);
+        assert_eq!(SpaceCards::unshuffle(10, 6, ShuffleTechnique::DealInc {n: 3}), 2);
+        assert_eq!(SpaceCards::unshuffle(10, 9, ShuffleTechnique::DealInc {n: 3}), 3);
+        assert_eq!(SpaceCards::unshuffle(10, 2, ShuffleTechnique::DealInc {n: 3}), 4);
+        assert_eq!(SpaceCards::unshuffle(10, 7, ShuffleTechnique::DealInc {n: 3}), 9);
+    }
 }