1 files changed, 143 insertions, 0 deletions
diff --git a/2016/aoc9/src/main.rs b/2016/aoc9/src/main.rs
new file mode 100644
index 0000000..622819c
--- /dev/null
+++ b/2016/aoc9/src/main.rs
@@ -0,0 +1,143 @@
+use std::io::BufReader;
+use std::io::prelude::*;
+use std::fs::File;
+
+#[derive(Debug, Clone, Copy)]
+struct Marker {
+    take: usize,
+    repeat: usize
+}
+#[derive(Debug, Clone, Copy)]
+enum Token {
+    Marker(usize, Marker),
+    Literal(usize)
+}
+
+impl Token {
+    fn size(self) -> usize {
+        match self {
+            Token::Marker(x, _) => x,
+            Token::Literal(x) => x
+        }
+    }
+
+    fn is_marker(self) -> bool {
+        match self {
+            Token::Marker(_, _) => true,
+            Token::Literal(_) => false
+        }
+    }
+
+    fn unwrap_marker(self) -> Marker {
+        match self {
+            Token::Marker(_, marker) => marker,
+            Token::Literal(_) => panic!("Bad unwrap marker")
+        }
+    }
+}
+
+fn main() {
+    let mut tokens = parse(read_file());
+    tokens.reverse();
+    let mut length: u64 = 0;
+    
+    while tokens.len() > 0 {
+        let next = tokens.pop().unwrap();
+        
+        if next.is_marker() {
+            let marker = next.unwrap_marker();
+            let mut used_take = 0;
+            
+            let mut tokens_to_repeat = Vec::new();
+            while used_take < marker.take {
+                let next_token = tokens.pop().unwrap();
+                if used_take + next_token.size() <= marker.take {
+                    tokens_to_repeat.push(next_token);
+                }
+                else {
+                    assert!(!next_token.is_marker());
+                    //assume splits only happen on literals
+                    tokens_to_repeat.push(Token::Literal(marker.take - used_take));
+                    tokens.push(Token::Literal(next_token.size() - marker.take + used_take));
+                }
+                used_take += next_token.size();
+            }
+
+            tokens_to_repeat.reverse();
+            for _ in 0..marker.repeat {
+                for &token in &tokens_to_repeat {
+                    tokens.push(token);
+                }
+            }
+        } else {
+            length += next.size() as u64;
+        }
+    }
+    println!("Length: {}", length);
+}
+
+fn parse(text: String) -> Vec<Token> {
+    let mut tokens = Vec::new();
+    let mut chars = text.chars();
+    let mut current_char = chars.next();
+    while current_char.is_some() {
+        let c = current_char.unwrap();
+        if c == '(' {
+            let mut char_count = 1;
+            let mut take_str = String::new();
+            let mut repeat_str = String::new();
+            loop {
+                let n = chars.next().unwrap();
+                char_count += 1;
+                if n == 'x' { break; }
+                take_str.push(n);
+            }
+            loop {
+                let n = chars.next().unwrap();
+                char_count += 1;
+                if n == ')' { break; }
+                repeat_str.push(n);
+            }
+
+            let take: usize = take_str.parse().expect(format!("Tried to parse take {}", take_str).as_ref());
+            let repeat: usize = repeat_str.parse().expect(format!("Tried to parse repeat {}", repeat_str).as_ref());
+            tokens.push(Token::Marker(char_count , Marker{take: take, repeat:repeat}));
+        } else {
+            assert!(c != '(' && c != ')');
+            tokens.push(Token::Literal(1));
+        }
+        
+        current_char = chars.next();
+    }
+    collapse_literals(&mut tokens);
+    
+    tokens
+}
+
+fn collapse_literals(tokens: &mut Vec<Token>) {
+    let mut i = 0;
+    while i < tokens.len()-1 {
+        match (tokens[i], tokens[i+1]) {
+            (Token::Literal(l1), Token::Literal(l2)) => {
+                tokens[i] = Token::Literal(l1+l2);
+                tokens.remove(i+1);
+            },
+            _ => {
+                i += 1;
+            }
+        }
+    }
+}
+
+fn read_file() -> String {
+    let file = BufReader::new(File::open("input.txt").unwrap());
+    file.lines()
+        .map(|line| line.unwrap().trim().to_string())
+        .filter(|line| line.len() > 0)
+        .next()
+        .unwrap()
+        .trim()
+        .to_string()
+
+//    "(25x3)(3x3)ABC(2x3)XY(5x2)PQRSTX(18x9)(3x2)TWO(5x7)SEVEN".to_string()
+}