From 7a9ac1e71d92988411e54bdf7bb2c20f99177bdb Mon Sep 17 00:00:00 2001
From: Justin Worthe <justin@worthe-it.co.za>
Date: Thu, 14 Dec 2017 08:12:46 +0200
Subject: Day 14: defrag

---
 src/bin/day_14.rs | 52 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/lib.rs        | 48 ++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 100 insertions(+)
 create mode 100644 src/bin/day_14.rs

(limited to 'src')

diff --git a/src/bin/day_14.rs b/src/bin/day_14.rs
new file mode 100644
index 0000000..778a57f
--- /dev/null
+++ b/src/bin/day_14.rs
@@ -0,0 +1,52 @@
+extern crate advent_of_code_2017;
+use advent_of_code_2017::*;
+
+fn main() {
+    let args = AdventArgs::init();
+    let input = args.input[0].clone();
+
+    let mut used = 0;
+    let mut grid: Vec<Vec<bool>> = vec!(vec!(false; 128); 128);
+    for i in 0..128 {
+        let to_hash = format!("{}-{}", input, i);
+        let hash = knot_hash(&to_hash);
+        for (x1,c) in hash.chars().enumerate() {
+            let parsed = u32::from_str_radix(&c.to_string(), 16).unwrap();
+            used += parsed.count_ones();
+            for (x2,b) in format!("{:04b}",parsed).chars().enumerate() {
+                grid[i][4*x1+x2] = b == '1';
+            }
+        }
+    }
+
+    if args.part == 1 {
+        println!("{} is used", used);
+    } else {
+        let mut group_count = 0;
+        for start_y in 0..128 {
+            for start_x in 0..128 {
+                if grid[start_y][start_x] {
+                    group_count += 1;
+                    clear_group(&mut grid, Point{
+                        x: start_x as i32,
+                        y: start_y as i32
+                    });
+                }
+            }
+        }
+        println!("{} groups", group_count);
+        
+    }
+}
+
+fn clear_group(grid: &mut Vec<Vec<bool>>, point: Point) {
+    if point.x >= 0 && point.x < 128 && point.y >= 0 && point.y < 128 {
+        if grid[point.y as usize][point.x as usize] {
+            grid[point.y as usize][point.x as usize] = false;
+            clear_group(grid, point.up());
+            clear_group(grid, point.down());
+            clear_group(grid, point.left());
+            clear_group(grid, point.right());
+        }
+    }
+}
diff --git a/src/lib.rs b/src/lib.rs
index 2a7b73a..87d0c0b 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -150,3 +150,51 @@ impl Direction {
         }
     }
 }
+
+
+pub fn knot_hash(input: &String) -> String {
+    let suffix: [usize; 5] = [17, 31, 73, 47, 23];
+    let lengths: Vec<usize> = input.as_bytes()
+        .iter().map(|&x| x as usize)
+        .chain(suffix.iter().cloned())
+        .collect();
+
+    let mut position = 0;
+    let mut list: Vec<u32> = (0..256).collect();
+
+    for i in 0..64 {
+        let skip = lengths.len() * i;
+        knot_hash_round(&mut list, &lengths, &mut position, skip);            
+    }
+
+    let mut current_char = 0;
+    let mut result = String::new();
+    for (i, l) in list.iter().enumerate() {
+        current_char = current_char ^ l;
+        if i % 16 == 15 {
+            result.push_str(&format!("{:02x}", current_char));
+            current_char = 0;
+        }
+    }
+    result
+}
+
+fn knot_hash_round(list: &mut Vec<u32>, lengths: &Vec<usize>, position: &mut usize, skip: usize) {
+    for (inner_skip, &length) in lengths.iter().enumerate() {
+        knot_hash_reverse_segment(list, *position, length);
+        *position = (*position + length + skip + inner_skip) % list.len();
+    }
+}
+
+fn knot_hash_reverse_segment(list: &mut Vec<u32>, position: usize, length: usize) {
+    let mut a = position;
+    let mut b = position + length - 1;
+    let len = list.len();
+    while a < b {
+        list.swap(a%len, b%len);
+        
+        a += 1;
+        b -= 1;
+    }
+}
+    
-- 
cgit v1.2.3