Advent of Code 2017 solutions in Rust

1
2
3
4
5
6
7
8
9
pub fn star_1(input: &&str) -> SolType {
    let input = input.trim();
    input
        .bytes()
        .zip(input.bytes().cycle().skip(1))
        .filter(|(a, b)| a == b)
        .map(|(a, _)| (a - b'0') as SolType)
        .sum()
}

1
2
3
4
5
6
7
8
pub fn star_2(input: &&str) -> SolType {
    let b = input.trim().as_bytes();
    b.iter()
        .zip(b[b.len() >> 1..].iter().chain(b.iter()))
        .filter(|(a, b)| a == b)
        .map(|(a, _)| (a - b'0') as SolType)
        .sum()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    pub fn test_star_1() {
        assert_eq!(3, star_1(&"1122"));
        assert_eq!(4, star_1(&"1111"));
        assert_eq!(0, star_1(&"1234"));
        assert_eq!(9, star_1(&"91212129"));
    }

    #[test]
    pub fn test_star_2() {
        assert_eq!(6, star_2(&"1212"));
        assert_eq!(0, star_2(&"1221"));
        assert_eq!(4, star_2(&"123425"));
        assert_eq!(12, star_2(&"123123"));
        assert_eq!(4, star_2(&"12131415"));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
pub mod input {
    #[derive(Debug)]
    pub struct PuzzleData(pub Vec<Vec<usize>>);

    impl From<&str> for PuzzleData {
        fn from(s: &str) -> Self {
            Self(
                s.lines()
                    .map(|l| {
                        l.split_ascii_whitespace()
                            .map(str::parse)
                            .collect::<Result<_, _>>()
                            .unwrap()
                    })
                    .collect(),
            )
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
pub fn star_1(PuzzleData(rows): &PuzzleData) -> SolType1 {
    rows.iter()
        .map(|row| {
            row.iter().fold((usize::MAX, usize::MIN), |(mn, mx), &v| {
                (mn.min(v), mx.max(v))
            })
        })
        .map(|(mn, mx)| mx - mn)
        .sum()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
pub fn star_2(PuzzleData(rows): &PuzzleData) -> SolType2 {
    rows.iter()
        .map(|row| {
            row.iter()
                .enumerate()
                .filter_map(|(k1, &v1)| {
                    row[k1 + 1..]
                        .iter()
                        .map(|&v2| (v1.max(v2), v1.min(v2)))
                        .filter(|(a, b)| a % b == 0)
                        .map(|(a, b)| a / b)
                        .next()
                })
                .next()
                .unwrap()
        })
        .sum()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
pub fn coord(idx: isize) -> (isize, isize) {
    assert!(idx > 0);
    if idx == 1 {
        return (0, 0);
    }

    let n = (0..).find(|n| 1 + 4 * n * (n + 1) >= idx).unwrap();
    let m = idx - 2 - 4 * (n - 1) * n;
    match m / (2 * n) {
        0 => (n, (n - 1) - m % (2 * n)),  // right
        1 => ((n - 1) - m % (2 * n), -n), // top
        2 => (-n, m % (2 * n) - (n - 1)), // left
        3 => (m % (2 * n) - (n - 1), n),  // bottom
        _ => unreachable!("v = {}, m = {}, n = {}", idx, m, n),
    }
}

pub fn star_1(input: &&str) -> SolType1 {
    let (x, y) = coord(input.trim().parse().unwrap());
    (x.abs() + y.abs()) as _
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
pub fn spiral_idx((x, y): (isize, isize)) -> isize {
    if (x, y) == (0, 0) {
        return 1;
    }

    let n = x.abs().max(y.abs());
    (4 * n * n + 1)
        + if x == n && y < n {
            -3 * n - y // right
        } else if y == -n && x < n {
            -n - x // top
        } else if x == -n && y > -n {
            n + y // left
        } else if y == n && x > -n {
            3 * n + x // bottom
        } else {
            unreachable!()
        }
}

pub fn star_2(input: &&str) -> SolType2 {
    let lim = input.trim().parse().unwrap();
    const D: [(isize, isize); 8] = [
        (1, 0),
        (1, -1),
        (0, -1),
        (-1, -1),
        (-1, 0),
        (-1, 1),
        (0, 1),
        (1, 1),
    ];
    (2..)
        .map(coord)
        .scan(Vec::from([1]), |list, (x, y)| {
            let v = D
                .iter()
                .map(|(dx, dy)| spiral_idx((x + dx, y + dy)))
                .filter_map(|idx| list.get((idx - 1) as usize))
                .sum();
            list.push(v);
            Some(v)
        })
        .find(|&v| v > lim)
        .unwrap()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    pub fn test_coord() {
        assert_eq!((0, 0), coord(1));

        assert_eq!((1, 0), coord(2));
        assert_eq!((1, -1), coord(3));
        assert_eq!((0, -1), coord(4));
        assert_eq!((-1, -1), coord(5));
        assert_eq!((-1, 0), coord(6));
        assert_eq!((-1, 1), coord(7));
        assert_eq!((0, 1), coord(8));
        assert_eq!((1, 1), coord(9));

        assert_eq!((2, 1), coord(10));
        assert_eq!((0, -2), coord(15));
        assert_eq!((-2, 1), coord(20));
        assert_eq!((2, 2), coord(25));

        assert_eq!((4, 3), coord(50));
        assert_eq!((1, -4), coord(60));
        assert_eq!((-4, 1), coord(70));
        assert_eq!((3, 4), coord(80));
    }

    #[test]
    pub fn test_value() {
        assert_eq!(spiral_idx((0, 0)), 1);

        assert_eq!(spiral_idx((1, 0)), 2);
        assert_eq!(spiral_idx((1, -1)), 3);
        assert_eq!(spiral_idx((0, -1)), 4);
        assert_eq!(spiral_idx((-1, -1)), 5);
        assert_eq!(spiral_idx((-1, 0)), 6);
        assert_eq!(spiral_idx((-1, 1)), 7);
        assert_eq!(spiral_idx((0, 1)), 8);
        assert_eq!(spiral_idx((1, 1)), 9);

        assert_eq!(spiral_idx((2, 1)), 10);
        assert_eq!(spiral_idx((0, -2)), 15);
        assert_eq!(spiral_idx((-2, 1)), 20);
        assert_eq!(spiral_idx((2, 2)), 25);

        assert_eq!(spiral_idx((4, 3)), 50);
        assert_eq!(spiral_idx((1, -4)), 60);
        assert_eq!(spiral_idx((-4, 1)), 70);
        assert_eq!(spiral_idx((3, 4)), 80);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
pub fn star_1(input: &&str) -> SolType {
    input
        .lines()
        .filter(|l| {
            l.split_ascii_whitespace()
                .scan(HashSet::new(), |set, word| Some(set.insert(word)))
                .all(|v| v)
        })
        .count()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
pub fn star_2(input: &&str) -> SolType {
    input
        .lines()
        .filter(|l| {
            l.split_ascii_whitespace()
                .map(|word| {
                    let mut word = word.bytes().collect::<Vec<_>>();
                    word.sort_unstable();
                    word
                })
                .scan(HashSet::new(), |set, word| Some(set.insert(word)))
                .all(|v| v)
        })
        .count()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
pub mod input {
    #[derive(Debug)]
    pub struct PuzzleData(pub Vec<isize>);

    impl From<&str> for PuzzleData {
        fn from(s: &str) -> Self {
            Self(s.lines().map(str::parse).collect::<Result<_, _>>().unwrap())
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
pub fn star_1(PuzzleData(offsets): &PuzzleData) -> SolType1 {
    (1..)
        .scan((0, offsets.to_owned()), |(pos, offsets), steps| {
            let off = &mut offsets[*pos as usize];
            (*pos, *off) = (*pos + *off, *off + 1);
            Some((steps, *pos))
        })
        .find(|&(_, pos)| pos < 0 || pos >= offsets.len() as isize)
        .unwrap()
        .0
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
pub fn star_2(PuzzleData(offsets): &PuzzleData) -> SolType2 {
    (1..)
        .scan((0, offsets.to_owned()), |(pos, offsets), steps| {
            let off = &mut offsets[*pos as usize];
            (*pos, *off) = (*pos + *off, if *off >= 3 { *off - 1 } else { *off + 1 });
            Some((steps, *pos))
        })
        .find(|&(_, pos)| pos < 0 || pos >= offsets.len() as isize)
        .unwrap()
        .0
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#[cfg(test)]
mod tests {
    use super::*;

    const CONTENT: &str = r#"0
3
0
1
-3
"#;

    #[test]
    pub fn test_star_1() {
        assert_eq!(5, star_1(&CONTENT.into()));
    }

    #[test]
    pub fn test_star_2() {
        assert_eq!(10, star_2(&CONTENT.into()));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
pub mod input {
    #[derive(Debug)]
    pub struct PuzzleData(pub Vec<usize>);

    impl From<&str> for PuzzleData {
        fn from(s: &str) -> Self {
            Self(
                s.trim()
                    .split_ascii_whitespace()
                    .map(|v| v.parse().unwrap())
                    .collect(),
            )
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
pub fn star_1_2(PuzzleData(blocks): &PuzzleData) -> SolType {
    let len = blocks.len();
    let mut seen = HashMap::from([(blocks.to_owned(), 0)]);
    let mut blocks = blocks.to_owned();
    let (mut prev_cycles, mut cycles) = (0, 0);
    while prev_cycles == cycles {
        cycles += 1;

        let (k, &v) = blocks
            .iter()
            .enumerate()
            .max_by_key(|&(k, &v)| (v, !k))
            .unwrap();

        blocks[k] = 0;
        for j in k + 1..=k + v {
            blocks[j % len] += 1;
        }

        prev_cycles = *seen.entry(blocks.clone()).or_insert(cycles);
    }
    (cycles, cycles - prev_cycles).into()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#[cfg(test)]
mod tests {
    use super::*;

    const CONTENT: &str = r#"0 2 7 0"#;

    #[test]
    pub fn test_from() {
        let PuzzleData(blocks) = PuzzleData::from(CONTENT);
        assert_eq!(vec![0, 2, 7, 0], blocks);
    }

    #[test]
    pub fn test_star_1_2() {
        assert_eq!(Solutions::from((5, 4)), star_1_2(&CONTENT.into()));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
pub mod input {
    use crate::{Program, Tower};

    impl<'a> From<&'a str> for Program<'a> {
        fn from(s: &'a str) -> Self {
            let mut words = s.split_ascii_whitespace();
            let name = words.next().unwrap();
            let weight = words
                .next()
                .unwrap()
                .trim_matches::<&[char]>(&['(', ')'])
                .parse()
                .unwrap();
            words.next(); // skip " -> "
            let children = words.map(|word| word.trim_end_matches(',')).collect();
            Self {
                name,
                weight,
                children,
                total_weight: Default::default(),
            }
        }
    }

    impl<'a> From<&'a str> for Tower<'a> {
        fn from(s: &'a str) -> Self {
            Self {
                programs: s.lines().map(Program::from).map(|p| (p.name, p)).collect(),
                root: Default::default(),
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Program<'a> {
    name: &'a str,
    weight: SolType2,
    children: HashSet<&'a str>,
    total_weight: RefCell<Option<SolType2>>,
}

#[derive(Debug)]
pub struct Tower<'a> {
    programs: HashMap<&'a str, Program<'a>>,
    root: RefCell<Option<&'a str>>,
}

impl Tower<'_> {
    pub fn root(&self) -> &str {
        if let Some(&root) = self.root.borrow().as_ref() {
            return root;
        }

        let root = *self
            .programs
            .keys()
            .find(|&name| self.programs.values().all(|p| !p.children.contains(name)))
            .unwrap();
        *self.root.borrow_mut() = Some(root);
        root
    }
}

pub fn star_1(tower: &Tower) -> SolType1 {
    tower.root().into()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
impl Program<'_> {
    pub fn total_weight(&self, tower: &Tower) -> SolType2 {
        if let Some(&total_weight) = self.total_weight.borrow().as_ref() {
            return total_weight;
        }

        // calculate total weight and store for later use
        let total_weight = self.weight
            + self
                .children
                .iter()
                .map(|child| tower.programs[child].total_weight(tower))
                .sum::<SolType2>();
        *self.total_weight.borrow_mut() = Some(total_weight);
        total_weight
    }
}

pub fn fix_wrong(name: &str, tower: &Tower) -> Option<SolType2> {
    let program = &tower.programs[name];

    // with less than 3 children, there cannot be a single child which has
    // the wrong weight
    if program.children.len() < 3 {
        return None;
    }

    // get children sorted by total weight
    let mut ws = program
        .children
        .iter()
        .map(|child| &tower.programs[child])
        .collect::<Vec<_>>();
    ws.sort_unstable_by_key(|child| child.total_weight(tower));

    // get min, max and mid, the latter has total weight equal
    // to either min's or max's total weight
    let min = ws[0];
    let mid = ws[1];
    let max = ws[ws.len() - 1];

    // if min and max have equal total weight, there is no imbalance
    if min.total_weight(tower) == max.total_weight(tower) {
        return None;
    }

    let (ok, nok) = match mid.total_weight(tower) == min.total_weight(tower) {
        true => (min, max),
        false => (max, min),
    };

    // recurse; if children are balanced, I am wrong
    fix_wrong(nok.name, tower)
        .or_else(|| Some(nok.weight + ok.total_weight(tower) - nok.total_weight(tower)))
}

pub fn star_2(tower: &Tower) -> SolType2 {
    fix_wrong(tower.root(), tower).unwrap()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#[cfg(test)]
mod tests {
    use super::*;

    const CONTENT: &str = r#"pbga (66)
xhth (57)
ebii (61)
havc (66)
ktlj (57)
fwft (72) -> ktlj, cntj, xhth
qoyq (66)
padx (45) -> pbga, havc, qoyq
tknk (41) -> ugml, padx, fwft
jptl (61)
ugml (68) -> gyxo, ebii, jptl
gyxo (61)
cntj (57)
"#;

    #[test]
    pub fn test_from() {
        let tower = Tower::from(CONTENT);
        println!("{:?}", tower);
    }

    #[test]
    pub fn test_star_1() {
        assert_eq!("tknk", star_1(&CONTENT.into()));
    }

    #[test]
    pub fn test_star_2() {
        assert_eq!(60, star_2(&CONTENT.into()));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
pub mod input {
    #[derive(Debug)]
    pub struct PuzzleData<'a>(pub Vec<(&'a str, i32, &'a str, &'a str, i32)>);

    impl<'a> From<&'a str> for PuzzleData<'a> {
        fn from(s: &'a str) -> Self {
            Self(
                s.lines()
                    .map(str::split_ascii_whitespace)
                    .map(|mut w| {
                        (
                            w.next().unwrap(),
                            if Some("inc") == w.next() { 1 } else { -1 }
                                * w.next().unwrap().parse::<i32>().unwrap(),
                            w.nth(1).unwrap(), // skip "if"
                            w.next().unwrap(),
                            w.next().unwrap().parse().unwrap(),
                        )
                    })
                    .collect(),
            )
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
pub fn star_1(PuzzleData(instructions): &PuzzleData) -> SolType {
    instructions
        .iter()
        .fold(
            HashMap::new(),
            |mut regs, &(r_tar, val_tar, r_pred, cmp, val_pred)| {
                let a = *regs.get(r_pred).unwrap_or(&0);
                if match cmp {
                    "<" => a < val_pred,
                    "<=" => a <= val_pred,
                    "==" => a == val_pred,
                    "!=" => a != val_pred,
                    ">=" => a >= val_pred,
                    ">" => a > val_pred,
                    _ => panic!(),
                } {
                    *regs.entry(r_tar).or_insert(0) += val_tar;
                }
                regs
            },
        )
        .values()
        .max()
        .copied()
        .unwrap()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
pub fn star_2(PuzzleData(instructions): &PuzzleData) -> SolType {
    let (mx, _) = instructions.iter().fold(
        (0, HashMap::new()),
        |(mut mx, mut regs), &(r_tar, val_tar, r_pred, cmp, val_pred)| {
            let a = *regs.get(r_pred).unwrap_or(&0);
            if match cmp {
                "<" => a < val_pred,
                "<=" => a <= val_pred,
                "==" => a == val_pred,
                "!=" => a != val_pred,
                ">=" => a >= val_pred,
                ">" => a > val_pred,
                _ => panic!(),
            } {
                let v = regs.entry(r_tar).or_insert(0);
                *v += val_tar;
                mx = mx.max(*v);
            }
            (mx, regs)
        },
    );
    mx
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#[cfg(test)]
mod tests {
    use super::*;

    const CONTENT: &str = r#"b inc 5 if a > 1
a inc 1 if b < 5
c dec -10 if a >= 1
c inc -20 if c == 10
"#;

    #[test]
    pub fn test_from() {
        let PuzzleData(instructions) = PuzzleData::from(CONTENT);
        assert_eq!(
            vec![
                ("b", 5, "a", ">", 1),
                ("a", 1, "b", "<", 5),
                ("c", 10, "a", ">=", 1),
                ("c", -20, "c", "==", 10),
            ],
            instructions,
        );
    }

    #[test]
    pub fn test_star_1() {
        assert_eq!(1, star_1(&CONTENT.into()));
    }

    #[test]
    pub fn test_star_2() {
        assert_eq!(10, star_2(&CONTENT.into()));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
pub fn process<B, T, A, G, F>(st: B, init: &T, acc: A, gc: G, fin: F) -> (T, usize)
where
    B: AsRef<[u8]>,          // stream type, convertible to &[u8]
    T: Clone,                // value type
    A: Fn(T, T) -> T + Copy, // accumulate to values
    G: Fn(T) -> T + Copy,    // update value to collect garbage
    F: Fn(T) -> T + Copy,    // finalize value before returning
{
    let st = st.as_ref();
    assert!(st[0] == b'{');
    let (mut pos, mut gb, mut v) = (1, false, init.to_owned());
    loop {
        (pos, gb, v) = match st[pos] {
            b'!' if gb => (pos + 2, gb, v),
            b'>' if gb => (pos + 1, false, v),
            b'<' if !gb => (pos + 1, true, v),
            b'}' if !gb => break,
            b'{' if !gb => {
                let (sub_v, sub_len) = process(&st[pos..], init, acc, gc, fin);
                (pos + sub_len, false, acc(v, sub_v))
            }
            _ if gb => (pos + 1, gb, gc(v)),
            _ => (pos + 1, gb, v),
        };
    }
    (fin(v), pos + 1)
}

pub fn star_1(st: &&str) -> SolType {
    // value type is a tuple of score and nested group count

    // add scores and nested groups count
    let acc = |(s0, n0), (s1, n1)| (s0 + s1, n0 + n1);
    // identity - do not collect garbage
    let gc = |v| v;
    // include self by adding it to nested groups counts and
    // adding 1 for each nested group to score
    let fin = |(s, n)| (s + n + 1, n + 1);

    let ((s, _), _) = process(st, &(0, 0), acc, gc, fin);
    s
}

1
2
3
4
5
6
7
pub fn star_2(st: &&str) -> SolType {
    // value type is a scalar representing collected garbage
    // gc increments by 1, final processing is identity

    let (cl, _) = process(st, &0, |v1, v2| v1 + v2, |v| v + 1, |v| v);
    cl
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    pub fn test_star_1() {
        assert_eq!(1, star_1(&"{}"));
        assert_eq!(6, star_1(&"{{{}}}"));
        assert_eq!(5, star_1(&"{{},{}}"));
        assert_eq!(16, star_1(&"{{{},{},{{}}}}"));
        assert_eq!(1, star_1(&"{<a>,<a>,<a>,<a>}"));
        assert_eq!(9, star_1(&"{{<ab>},{<ab>},{<ab>},{<ab>}}"));
        assert_eq!(9, star_1(&"{{<!!>},{<!!>},{<!!>},{<!!>}}"));
        assert_eq!(3, star_1(&"{{<a!>},{<a!>},{<a!>},{<ab>}}"));
    }

    #[test]
    pub fn test_star_2() {
        assert_eq!(0, star_2(&"{<>}"));
        assert_eq!(17, star_2(&"{<random characters>}"));
        assert_eq!(3, star_2(&"{<<<<>}"));
        assert_eq!(2, star_2(&"{<{!>}>}"));
        assert_eq!(0, star_2(&"{<!!>}"));
        assert_eq!(0, star_2(&"{<!!!>>}"));
        assert_eq!(10, star_2(&r#"{<{o"i!a,<{i<a>}"#));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
pub mod input {
    #[derive(Debug)]
    pub struct PuzzleData<'a>(pub &'a str, pub Vec<u8>);

    impl<'a> From<&'a str> for PuzzleData<'a> {
        fn from(s: &'a str) -> Self {
            Self(
                s.trim(),
                s.trim()
                    .split(',')
                    .filter(|v| !v.is_empty())
                    .map(|v| v.parse().unwrap())
                    .collect(),
            )
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
fn knot(buf: Vec<u8>, pos: usize, skip: usize, lengths: &[u8]) -> (Vec<u8>, usize, usize) {
    let buf_len = buf.len();
    lengths
        .iter()
        .map(|&len| len as usize)
        .fold((buf, pos, skip), |(mut buf, pos, skip), len| {
            if pos + len > buf.len() {
                let mut temp = vec![0; len];
                temp[..buf_len - pos].copy_from_slice(&buf[pos..]);
                temp[buf_len - pos..].copy_from_slice(&buf[..len + pos - buf_len]);
                temp.reverse();
                buf[pos..].copy_from_slice(&temp[..buf_len - pos]);
                buf[..len + pos - buf_len].copy_from_slice(&temp[buf_len - pos..]);
            } else {
                buf[pos..pos + len].reverse();
            }
            (buf, (pos + len + skip) % buf_len, skip + 1)
        })
}

pub fn star_1(PuzzleData(_, lengths): &PuzzleData) -> SolType1 {
    let (buf, _, _) = knot((0..=255).collect(), 0, 0, lengths);
    buf[0] as u32 * buf[1] as u32
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const DIGITS: [char; 16] = [
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f',
];

pub fn knot_hash<T: AsRef<[u8]>>(text: T) -> String {
    let lengths = [text.as_ref(), &[17, 31, 73, 47, 23]].concat();

    let (buf, _, _) = (0..64).fold(((0..=255).collect(), 0, 0), |(buf, pos, skip), _| {
        knot(buf, pos, skip, &lengths)
    });

    (0..=255)
        .step_by(16)
        .map(|k| (k..k + 16).fold(0, |v, k| v ^ buf[k]))
        .fold(String::with_capacity(32), |mut s, v| {
            s.push(DIGITS[(v >> 4) as usize]);
            s.push(DIGITS[(v & 15) as usize]);
            s
        })
}

pub fn star_2(PuzzleData(text, _): &PuzzleData) -> SolType2 {
    knot_hash(text)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#[cfg(test)]
mod tests {
    use super::*;

    const CONTENT: &str = r#"3,4,1,5"#;

    #[test]
    pub fn test_knot() {
        let PuzzleData(_, lengths) = &CONTENT.into();
        let (buf, pos, skip) = knot((0..5).collect(), 0, 0, lengths);
        assert_eq!(vec![3, 4, 2, 1, 0], buf);
        assert_eq!((4, 4), (pos, skip));
    }

    #[test]
    pub fn test_knot_hash() {
        assert_eq!("a2582a3a0e66e6e86e3812dcb672a272", knot_hash(""));
        assert_eq!("33efeb34ea91902bb2f59c9920caa6cd", knot_hash("AoC 2017"));
        assert_eq!("3efbe78a8d82f29979031a4aa0b16a9d", knot_hash("1,2,3"));
        assert_eq!("63960835bcdc130f0b66d7ff4f6a5a8e", knot_hash("1,2,4"));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
fn go(step: &str, (x, y): (SolType, SolType)) -> (SolType, SolType) {
    match step {
        "ne" => (x + 1, y - 1),
        "n" => (x, y - 2),
        "nw" => (x - 1, y - 1),
        "sw" => (x - 1, y + 1),
        "s" => (x, y + 2),
        "se" => (x + 1, y + 1),
        _ => panic!("Unknown: '{}'", step),
    }
}

pub fn star_1(path: &&str) -> SolType {
    let (x, y) = path
        .trim()
        .split(',')
        .fold((0, 0), |(x, y), step| go(step, (x, y)));

    x.abs() + (y.abs() - x.abs()).max(0) / 2
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
pub fn star_2(path: &&str) -> SolType {
    path.trim()
        .split(',')
        .scan((0, 0), |(x, y), step| {
            (*x, *y) = go(step, (*x, *y));
            Some(x.abs() + (y.abs() - x.abs()).max(0) / 2)
        })
        .max()
        .unwrap()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    pub fn test_star_1() {
        assert_eq!(3, star_1(&"ne,ne,ne"));
        assert_eq!(0, star_1(&"ne,ne,sw,sw"));
        assert_eq!(2, star_1(&"ne,ne,s,s"));
        assert_eq!(3, star_1(&"se,sw,se,sw,sw"));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
pub mod input {
    use std::collections::HashMap;

    use crate::SolType;

    #[derive(Debug)]
    pub struct PuzzleData {
        pub map: HashMap<SolType, Vec<SolType>>,
    }

    impl From<&str> for PuzzleData {
        /// parse the puzzle input
        fn from(s: &str) -> Self {
            let map = s
                .lines()
                .map(|l| l.split_once(" <-> ").unwrap())
                .map(|(a, b)| {
                    (
                        a.parse::<SolType>().unwrap(),
                        b.split(", ")
                            .map(|n| n.parse::<SolType>().unwrap())
                            .collect::<Vec<_>>(),
                    )
                })
                .collect();
            Self { map }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
pub fn group(n: SolType, map: &HashMap<SolType, Vec<SolType>>) -> HashSet<SolType> {
    let mut group = HashSet::from([n]);
    let mut queue = Vec::from([n]);
    while let Some(n) = queue.pop() {
        for &m in map.get(&n).unwrap() {
            if group.insert(m) {
                queue.push(m);
            }
        }
    }
    group
}

pub fn star_1(data: &PuzzleData) -> SolType {
    group(0, &data.map).len()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
pub fn star_2(data: &PuzzleData) -> SolType {
    let mut numbers: HashSet<SolType> = HashSet::from_iter(data.map.keys().cloned());
    let mut count = 0;
    while !numbers.is_empty() {
        let g = group(*numbers.iter().next().unwrap(), &data.map);
        numbers.retain(|n| !g.contains(n));
        count += 1;
    }
    count
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#[cfg(test)]
mod tests {
    use super::*;

    const CONTENT: &str = r#"0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5
"#;

    #[test]
    pub fn test_from() {
        let data = PuzzleData::from(CONTENT);
        println!("{data:?}");
    }

    #[test]
    pub fn test_star_1() {
        let data = PuzzleData::from(CONTENT);
        assert_eq!(6, star_1(&data));
    }

    #[test]
    pub fn test_star_2() {
        let data = PuzzleData::from(CONTENT);
        assert_eq!(2, star_2(&data));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
pub mod input {
    #[derive(Debug)]
    pub struct PuzzleData(pub Vec<(usize, usize)>);

    impl From<&str> for PuzzleData {
        fn from(s: &str) -> Self {
            Self(
                s.lines()
                    .map(|l| l.split_once(": ").unwrap())
                    .map(|(d, r)| (d.parse().unwrap(), r.parse().unwrap()))
                    .collect(),
            )
        }
    }
}

1
2
3
4
5
6
7
pub fn star_1(PuzzleData(layers): &PuzzleData) -> SolType1 {
    layers
        .iter()
        .filter(|&&(depth, range)| depth % (2 * range - 2) == 0)
        .map(|&(depth, range)| depth * range)
        .sum()
}

1
2
3
4
5
6
7
8
9
pub fn star_2(PuzzleData(layers): &PuzzleData) -> SolType2 {
    (0..)
        .find(|delay| {
            layers
                .iter()
                .all(|(depth, range)| (depth + delay) % (2 * range - 2) != 0)
        })
        .unwrap()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#[cfg(test)]
mod tests {
    use super::*;

    const CONTENT: &str = r#"0: 3
1: 2
4: 4
6: 4
"#;

    #[test]
    pub fn test_from() {
        let PuzzleData(layers) = PuzzleData::from(CONTENT);
        assert_eq!(vec![(0, 3), (1, 2), (4, 4), (6, 4)], layers);
    }

    #[test]
    pub fn test_star_1() {
        assert_eq!(24, star_1(&CONTENT.into()));
    }

    #[test]
    pub fn test_star_2() {
        assert_eq!(10, star_2(&CONTENT.into()));
    }
}

1
2
3
4
5
6
7
pub fn star_1(&prefix: &&str) -> SolType1 {
    (0..128)
        .map(|suffix| {
            knot_hash(&format!("{}-{}", prefix.trim(), suffix)).fold(0, |s, b| s + b.count_ones())
        })
        .sum()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
pub fn star_2(&prefix: &&str) -> SolType2 {
    const USED: u8 = b'1';
    const D: [(isize, isize); 4] = [(1, 0), (0, -1), (-1, 0), (0, 1)];
    const W: usize = 128;

    let s = (0..128).fold(String::new(), |s, suffix| {
        knot_hash(&format!("{}-{}", prefix.trim(), suffix)).fold(s, |mut s, v| {
            let _ = write!(s, "{:08b}", v);
            s
        })
    });
    let grid = s.as_bytes();

    let mut processed = vec![false; W * W];
    let mut regions = 0;
    let mut p0 = 0;
    while let Some(p) = (p0..W * W).find(|&p| grid[p] == USED && !processed[p]) {
        p0 = p;
        regions += 1;

        processed[p] = true;
        let mut queue = VecDeque::from([(p % W, p / W)]);
        while let Some((x, y)) = queue.pop_front() {
            for (x_adj, y_adj) in D
                .iter()
                .map(|&(d_x, d_y)| (x.wrapping_add_signed(d_x), y.wrapping_add_signed(d_y)))
                .filter(|&(x_adj, y_adj)| x_adj < W && y_adj < W && grid[x_adj + W * y_adj] == USED)
            {
                if !processed[x_adj + W * y_adj] {
                    processed[x_adj + W * y_adj] = true;
                    queue.push_back((x_adj, y_adj));
                }
            }
        }
    }
    regions
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
pub mod input {
    #[derive(Debug)]
    pub struct PuzzleData(pub u64, pub u64);

    impl From<&str> for PuzzleData {
        fn from(s: &str) -> Self {
            let mut vals = s.lines().map(|l| l[24..].parse().unwrap());
            Self(vals.next().unwrap(), vals.next().unwrap())
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
const F_A: u64 = 16_807;
const F_B: u64 = 48_271;
const M: u64 = 2_147_483_647;
const MASK: u64 = (1 << 16) - 1;

pub fn star_1(&PuzzleData(init_a, init_b): &PuzzleData) -> SolType {
    successors(Some(init_a), |&a| Some((a * F_A) % M))
        .zip(successors(Some(init_b), |&b| Some((b * F_B) % M)))
        .take(40_000_000)
        .filter(|&(a, b)| a & MASK == b & MASK)
        .count()
}

1
2
3
4
5
6
7
8
pub fn star_2(&PuzzleData(init_a, init_b): &PuzzleData) -> SolType {
    successors(Some(init_a), |&a| Some((a * F_A) % M))
        .filter(|&a| a & 3 == 0)
        .zip(successors(Some(init_b), |&b| Some((b * F_B) % M)).filter(|&b| b & 7 == 0))
        .take(5_000_000)
        .filter(|&(a, b)| a & MASK == b & MASK)
        .count()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
pub mod input {
    use crate::Move;

    #[derive(Debug)]
    pub struct Dance(pub Vec<Move>);

    impl From<&str> for Move {
        fn from(s: &str) -> Self {
            let mut vals = s[1..].split('/');
            match s.as_bytes()[0] {
                b's' => Self::S(vals.next().unwrap().parse().unwrap()),
                b'x' => Self::X(
                    vals.next().unwrap().parse().unwrap(),
                    vals.next().unwrap().parse().unwrap(),
                ),
                b'p' => Self::P(
                    vals.next().unwrap().as_bytes()[0] as _,
                    vals.next().unwrap().as_bytes()[0] as _,
                ),
                _ => panic!("What should I do with {}", s),
            }
        }
    }

    impl From<&str> for Dance {
        fn from(s: &str) -> Self {
            Self(s.split(',').map(Move::from).collect())
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#[derive(Debug, PartialEq, Eq, Clone, Copy)]
pub enum Move {
    S(usize),
    X(usize, usize),
    P(char, char),
}

impl Move {
    pub fn dance(self, mut f: Vec<char>) -> Vec<char> {
        match self {
            Self::S(offset) => f.rotate_right(offset),
            Self::X(a, b) => (f[a], f[b]) = (f[b], f[a]),
            Self::P(a, b) => {
                // single pass linear search
                let (a, b) = f
                    .iter()
                    .enumerate()
                    .scan((None, None), |(c_a, c_b), (k, &v)| {
                        (*c_a, *c_b) = (
                            if v == a { Some(k) } else { *c_a },
                            if v == b { Some(k) } else { *c_b },
                        );
                        Some((*c_a, *c_b))
                    })
                    .filter_map(|(a, b)| a.and_then(|a| b.map(|b| (a, b))))
                    .next()
                    .unwrap();
                (f[a], f[b]) = (f[b], f[a]);
            }
        }
        f
    }
}

pub fn star_1(Dance(moves): &Dance) -> SolType {
    moves
        .iter()
        .fold(('a'..='p').collect::<Vec<_>>(), |f, &m| m.dance(f))
        .iter()
        .collect()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
pub fn star_2(Dance(moves): &Dance) -> SolType {
    let f0 = ('a'..='p').collect::<Vec<_>>();
    let mut f = f0.clone();

    let mut cnt = 0;
    loop {
        cnt += 1;
        f = moves.iter().fold(f, |f, m| m.dance(f));
        if f == f0 {
            break;
        }
    }

    // fast forward
    let n = 1_000_000_000;
    let cnt = (n / cnt) * cnt;

    // remaining simulation
    for _ in cnt..n {
        f = moves.iter().fold(f, |f, m| m.dance(f));
    }

    f.iter().collect()
}