Advertisement
krzysz00

Advent of code, day 14

Dec 14th, 2017
148
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/env run-cargo-script
  2. // cargo-deps: itertools
  3. #![feature(inclusive_range_syntax)]
  4. extern crate itertools;
  5. use itertools::Itertools;
  6.  
  7. use std::io::{stdin};
  8.  
  9. fn reverse_circular<T>(array: &mut [T], from: usize, to: usize) {
  10.     // To can be over the length of the array, indexing is mod len
  11.     if to <= from {
  12.         return;
  13.     }
  14.     let to = to - 1;
  15.     let n_swaps = (to - from)/2 + 1;
  16.     for delta in 0..n_swaps {
  17.         let idx_a = (from + delta) % array.len();
  18.         let idx_b = (to - delta) % array.len();
  19.         array.swap(idx_a, idx_b);
  20.     }
  21. }
  22.  
  23. const EXTRA_LENGTHS: [usize; 5] = [17, 31, 73, 47, 23];
  24. fn sparse_hash(lengths: &[usize], n_rounds: usize) -> Vec<u8> {
  25.     let mut skip_length = 0;
  26.     let mut current_position = 0;
  27.  
  28.     let mut data: Vec<u8> = (0..=255).into_iter().collect();
  29.     for _ in 0..n_rounds {
  30.         for length in lengths.iter().chain(EXTRA_LENGTHS.iter()) {
  31.             reverse_circular(&mut data, current_position, current_position + length);
  32.             current_position = (current_position + length + skip_length) % data.len();
  33.             skip_length += 1;
  34.         }
  35.     }
  36.     data
  37. }
  38.  
  39. const BLOCK_SIZE: usize = 16;
  40. fn dense_hash(data: &[u8]) -> Vec<u8> {
  41.     data.chunks(BLOCK_SIZE)
  42.                 .map(|b| b.iter().cloned()
  43.                      .fold1(|x, y| x ^ y).expect("Empty block"))
  44.         .collect()
  45. }
  46.  
  47. const N_ROUNDS: usize = 64;
  48. const SQUARE_DIM: usize = 128;
  49.  
  50. fn propogate_region(matrix: &mut[usize], i: usize, j: usize, ld: usize,
  51.                     region_id: usize) -> bool {
  52.  
  53.     let idx = j + i * ld;
  54.     if matrix[idx] != 1 {
  55.         return false;
  56.     }
  57.  
  58.     matrix[idx] = region_id;
  59.     if i > 0 {
  60.         propogate_region(matrix, i - 1, j, ld, region_id);
  61.     }
  62.     if i + 1 < ld {
  63.         propogate_region(matrix, i + 1, j, ld, region_id);
  64.     }
  65.  
  66.     if j > 0 {
  67.         propogate_region(matrix, i, j - 1, ld, region_id);
  68.     }
  69.     if j + 1 < ld {
  70.         propogate_region(matrix, i, j + 1, ld, region_id);
  71.     }
  72.  
  73.     return true;
  74. }
  75.  
  76. fn solve(input: &str) -> (usize, usize) {
  77.     let mut part_a = 0;
  78.  
  79.     let mut matrix: [usize; SQUARE_DIM * SQUARE_DIM] = [0; SQUARE_DIM * SQUARE_DIM];
  80.  
  81.     for i in 0..SQUARE_DIM {
  82.         let data = format!("{}-{}", input, i);
  83.         let lengths: Vec<usize> = data.bytes().map(|x| x as usize).collect();
  84.         let sparse = sparse_hash(&lengths, N_ROUNDS);
  85.         let dense = dense_hash(&sparse);
  86.  
  87.         let popcount: usize = dense.iter().map(|x| x.count_ones() as usize).sum();
  88.         part_a += popcount;
  89.  
  90.         for (j, byte) in dense.iter().enumerate() {
  91.             for k in 0..8 {
  92.                 matrix[i + (j * 8 + k) * SQUARE_DIM] = ((byte >> (7 - k)) & 1) as usize;
  93.             }
  94.         }
  95.     }
  96.  
  97.     let mut next_id = 2;
  98.     for i in 0..SQUARE_DIM {
  99.         for j in 0..SQUARE_DIM {
  100.             if propogate_region(&mut matrix, i, j,
  101.                                 SQUARE_DIM, next_id) {
  102.                 next_id += 1;
  103.             }
  104.         }
  105.     }
  106.  
  107.     // next_id being 2 means 0 regions were found, so adjust
  108.     let part_b = next_id - 2;
  109.     (part_a, part_b)
  110. }
  111. fn main() {
  112.     let mut line: String = String::new();
  113.     stdin().read_line(&mut line).expect("Error reading input");
  114.  
  115.     let answer = solve(&line.trim());
  116.     println!("{:?}", answer);
  117. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement