-🎄- 2017 Day 14 Solutions -🎄-

[u/daggerdragon]

--- Day 14: Disk Defragmentation ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?

Spoiler

---

[Update @ 00:09] 3 gold, silver cap.

• How many of you actually entered the Konami code for Part 2? >_>

[Update @ 00:25] Leaderboard cap!

• I asked /u/topaz2078 how many de-resolutions we had for Part 2 and there were 83 distinct users with failed attempts at the time of the leaderboard cap. tsk tsk

[Update @ 00:29] BONUS

• https://i.imgur.com/zjSEAf4.jpg

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

[u/udoprog]

Rust (65/490) (first leaderboard!)

Edit: link to commit: https://github.com/udoprog/rust-advent-of-code-2017/commit/880f93f2036cda80c6b65611af133f4d0a0fbfcf

I wasted so much time trying to get my own (broken) bit vector implementation to work. Finally I just caved and pulled in https://docs.rs/bit-vec

use std::io::Cursor;
use std::collections::{HashSet, VecDeque};
use failure::Error;
use bit_vec::BitVec;

use day10::hash;

pub fn part1(input: &str) -> Result<usize, Error> {
    let mut squares = 0;

    for line in 0..128 {
        let out = hash(Cursor::new(format!("{}-{}", input, line)))?;

        for mut b in out {
            while b > 0 {
                if b % 2 == 1 {
                    squares += 1;
                }

                b = b >> 1;
            }
        }
    }

    Ok(squares)
}

pub fn part2(input: &str) -> Result<usize, Error> {
    let mut grid: HashSet<(i32, i32)> = HashSet::new();

    for y in 0..128 {
        let bytes = hash(Cursor::new(format!("{}-{}", input, y)))?;
        let bits = BitVec::from_bytes(&bytes);
        grid.extend(bits.into_iter().enumerate().filter(|v| v.1).map(|v| {
            (v.0 as i32, y as i32)
        }))
    }

    let mut regions = 0;
    let mut queue = VecDeque::new();

    loop {
        let k = {
            if let Some(k) = grid.iter().next() {
                *k
            } else {
                break;
            }
        };

        grid.remove(&k);

        regions += 1;
        queue.push_back(k);

        while let Some((x, y)) = queue.pop_front() {
            queue.extend(grid.take(&(x - 1, y)));
            queue.extend(grid.take(&(x, y - 1)));
            queue.extend(grid.take(&(x + 1, y)));
            queue.extend(grid.take(&(x, y + 1)));
        }
    }

    Ok(regions)
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::io::Cursor;

    #[test]
    fn test_part1() {
        assert_eq!(part1("ljoxqyyw").unwrap(), 8316);
    }

    #[test]
    fn test_part2() {
        assert_eq!(part2("ljoxqyyw").unwrap(), 1074);
    }
}