Advent of Code 2015 solutions in Rust

1
2
3
4
pub fn star_1(data: &&str) -> SolType1 {
    data.bytes()
        .fold(0, |f, b| if b == b'(' { f + 1 } else { f - 1 })
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
pub fn star_2(data: &&str) -> SolType2 {
    data.bytes()
        .scan(0isize, |f, b| {
            *f = if b == b'(' { *f + 1 } else { *f - 1 };
            Some(*f)
        })
        .position(|f| f < 0)
        .unwrap()
        + 1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
pub mod input {
    use crate::SolType;

    #[derive(Debug)]
    pub struct PuzzleData(pub Vec<(SolType, SolType, SolType)>);

    impl From<&str> for PuzzleData {
        /// parse the puzzle input
        fn from(s: &str) -> Self {
            Self(
                s.lines()
                    .map(|l| l.split('x').map(|v| v.parse().unwrap()))
                    .map(|mut it| (it.next().unwrap(), it.next().unwrap(), it.next().unwrap()))
                    .collect(),
            )
        }
    }
}

1
2
3
4
5
6
pub fn star_1(PuzzleData(boxes): &PuzzleData) -> SolType {
    boxes
        .iter()
        .map(|&(l, w, h)| 2 * l * w + 2 * w * h + 2 * h * l + (l * w).min(w * h).min(h * l))
        .sum()
}

1
2
3
4
5
6
pub fn star_2(PuzzleData(boxes): &PuzzleData) -> SolType {
    boxes
        .iter()
        .map(|&(l, w, h)| l * w * h + 2 * (l + w).min(w + h).min(h + l))
        .sum()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
pub fn star_1(dirs: &&str) -> SolType1 {
    let mut houses: HashSet<(isize, isize)> = HashSet::from([(0, 0)]);
    let mut pos = (0, 0);
    for dir in dirs.bytes() {
        pos = match dir {
            b'>' => (pos.0 + 1, pos.1),
            b'^' => (pos.0, pos.1 + 1),
            b'<' => (pos.0 - 1, pos.1),
            b'v' => (pos.0, pos.1 - 1),
            _ => panic!(),
        };
        houses.insert(pos);
    }
    houses.len()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
pub fn star_2(dirs: &&str) -> SolType2 {
    let mut houses: HashSet<(isize, isize)> = HashSet::from([(0, 0)]);
    let mut pos = [(0, 0), (0, 0)];
    for (k, dir) in dirs.bytes().enumerate() {
        pos[k & 1] = match dir {
            b'>' => (pos[k & 1].0 + 1, pos[k & 1].1),
            b'^' => (pos[k & 1].0, pos[k & 1].1 + 1),
            b'<' => (pos[k & 1].0 - 1, pos[k & 1].1),
            b'v' => (pos[k & 1].0, pos[k & 1].1 - 1),
            _ => panic!(),
        };
        houses.insert(pos[k & 1]);
    }
    houses.len()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
pub fn solve<F: Fn(&[u8]) -> bool>(data: &[u8], k0: usize, f: F) -> SolType {
    let mut hash = [0; 16];
    let mut hasher = Md5::new();

    (k0..)
        .find(|&k| {
            hasher.update(data);
            hasher.update(k.to_string().as_bytes());
            hasher.finalize_into_reset((&mut hash).into());
            f(&hash)
        })
        .unwrap()
}

const F1: fn(&[u8]) -> bool = |hash| hash[0] == 0 && hash[1] == 0 && hash[2] >> 4 == 0;

pub fn star_1(data: &&str) -> SolType {
    solve(data.trim().as_bytes(), 0, F1)
}

1
2
3
4
5
const F2: fn(&[u8]) -> bool = |hash| hash[0] == 0 && hash[1] == 0 && hash[2] == 0;

pub fn star_2(data: &&str) -> SolType {
    solve(data.trim().as_bytes(), 0, F2)
}

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

    #[test]
    pub fn test_solve() {
        assert_eq!(609_043, solve("abcdef".as_bytes(), 609_043, F1));
        assert_eq!(1_048_970, solve("pqrstuv".as_bytes(), 1_048_970, F1));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
pub fn is_nice_1(l: &[u8]) -> bool {
    l.iter().filter(|b| b"aeiou".contains(b)).count() >= 3
        && l.iter().zip(l[1..].iter()).all(|p| {
            p != (&b'a', &b'b') && p != (&b'c', &b'd') && p != (&b'p', &b'q') && p != (&b'x', &b'y')
        })
        && l.iter().zip(l[1..].iter()).any(|(a, b)| a == b)
}

pub fn star_1(input: &&str) -> SolType {
    input.lines().filter(|l| is_nice_1(l.as_bytes())).count()
}

1
2
3
4
5
6
7
8
pub fn is_nice_2(l: &[u8]) -> bool {
    (0..l.len() - 3).any(|k1| (k1 + 2..l.len() - 1).any(|k2| l[k1..k1 + 2] == l[k2..k2 + 2]))
        && (0..l.len() - 2).any(|k| l[k] == l[k + 2])
}

pub fn star_2(input: &&str) -> SolType {
    input.lines().filter(|l| is_nice_2(l.as_bytes())).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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
pub fn range(range: &str) -> impl Iterator<Item = (usize, usize)> {
    let (f, t) = range.split_once(" through ").unwrap();
    let (f_x, f_y) = f
        .split_once(',')
        .map(|(x, y)| (x.parse().unwrap(), y.parse().unwrap()))
        .unwrap();
    let (t_x, t_y) = t
        .split_once(',')
        .map(|(x, y)| (x.parse().unwrap(), y.parse().unwrap()))
        .unwrap();

    (f_x..=t_x).flat_map(move |x| (f_y..=t_y).map(move |y| (x, y)))
}

const WIDTH: usize = 1_000;
const PRE_ON: &str = "turn on ";
const PRE_OFF: &str = "turn off ";
const PRE_TOGGLE: &str = "toggle ";

pub fn star_1(instructions: &&str) -> SolType {
    let mut lights = vec![false; WIDTH * WIDTH];
    let mut count = 0;
    for l in instructions.lines() {
        if let Some(stripped) = l.strip_prefix(PRE_ON) {
            for (x, y) in range(stripped) {
                if !lights[x + WIDTH * y] {
                    count += 1;
                    lights[x + WIDTH * y] = true;
                }
            }
        } else if let Some(stripped) = l.strip_prefix(PRE_OFF) {
            for (x, y) in range(stripped) {
                if lights[x + WIDTH * y] {
                    count -= 1;
                    lights[x + WIDTH * y] = false;
                }
            }
        } else if let Some(stripped) = l.strip_prefix(PRE_TOGGLE) {
            for (x, y) in range(stripped) {
                (count, lights[x + WIDTH * y]) = if lights[x + WIDTH * y] {
                    (count - 1, false)
                } else {
                    (count + 1, true)
                };
            }
        }
    }
    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
pub fn star_2(instructions: &&str) -> SolType {
    let mut lights = vec![0; WIDTH * WIDTH];
    let mut bright = 0;
    for l in instructions.lines() {
        if let Some(stripped) = l.strip_prefix(PRE_ON) {
            for (x, y) in range(stripped) {
                bright += 1;
                lights[x + WIDTH * y] += 1;
            }
        } else if let Some(stripped) = l.strip_prefix(PRE_OFF) {
            for (x, y) in range(stripped) {
                if lights[x + WIDTH * y] > 0 {
                    bright -= 1;
                    lights[x + WIDTH * y] -= 1;
                }
            }
        } else if let Some(stripped) = l.strip_prefix(PRE_TOGGLE) {
            for (x, y) in range(stripped) {
                bright += 2;
                lights[x + WIDTH * y] += 2;
            }
        }
    }
    bright
}

 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
pub mod input {
    use std::collections::HashMap;

    use crate::{Gate, Source};

    #[derive(Debug)]
    pub struct PuzzleData<'a>(pub HashMap<&'a str, Gate<'a>>);

    impl<'a> From<&'a str> for Source<'a> {
        fn from(s: &'a str) -> Self {
            match s.as_bytes()[0] {
                b'0'..=b'9' => Self::Value(s.parse().unwrap()),
                _ => Self::Wire(s),
            }
        }
    }

    impl<'a> From<&'a str> for Gate<'a> {
        fn from(s: &'a str) -> Self {
            let mut words = s.split_ascii_whitespace();
            match (words.next(), words.next(), words.next()) {
                (Some(lhs), Some("LSHIFT"), Some(rhs)) => Self::LShift(lhs.into(), rhs.into()),
                (Some(lhs), Some("RSHIFT"), Some(rhs)) => Self::RShift(lhs.into(), rhs.into()),
                (Some(lhs), Some("AND"), Some(rhs)) => Self::And(lhs.into(), rhs.into()),
                (Some(lhs), Some("OR"), Some(rhs)) => Self::Or(lhs.into(), rhs.into()),
                (Some("NOT"), Some(rhs), None) => Self::Not(rhs.into()),
                (Some(v), None, None) => Self::Value(v.into()),
                _ => panic!(),
            }
        }
    }

    impl<'a> From<&'a str> for PuzzleData<'a> {
        fn from(s: &'a str) -> Self {
            Self(
                s.lines()
                    .map(|l| l.split_once(" -> ").unwrap())
                    .map(|(gate, tar)| (tar, Gate::from(gate)))
                    .collect(),
            )
        }
    }
}

#[derive(Debug, PartialEq, Eq, Clone)]
pub enum Source<'a> {
    Value(ValType),
    Wire(&'a str),
}

#[derive(Debug, PartialEq, Eq, Clone)]
pub enum Gate<'a> {
    Value(Source<'a>),
    LShift(Source<'a>, Source<'a>),
    RShift(Source<'a>, Source<'a>),
    And(Source<'a>, Source<'a>),
    Or(Source<'a>, Source<'a>),
    Not(Source<'a>),
}

 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
impl<'a> Source<'a> {
    pub fn get(
        &self,
        gates: &HashMap<&'a str, Gate<'a>>,
        cache: &mut HashMap<&'a str, ValType>,
    ) -> ValType {
        match *self {
            Source::Value(value) => value,
            Source::Wire(wire) => match cache.get(wire).copied() {
                Some(value) => value,
                _ => {
                    let value = gates[wire].get(gates, cache);
                    cache.insert(wire, value);
                    value
                }
            },
        }
    }
}

impl<'a> Gate<'a> {
    pub fn get(
        &self,
        gates: &HashMap<&'a str, Gate<'a>>,
        cache: &mut HashMap<&'a str, ValType>,
    ) -> ValType {
        match self {
            Gate::Value(val) => val.get(gates, cache),
            Gate::LShift(lhs, rhs) => lhs.get(gates, cache) << rhs.get(gates, cache),
            Gate::RShift(lhs, rhs) => lhs.get(gates, cache) >> rhs.get(gates, cache),
            Gate::And(lhs, rhs) => lhs.get(gates, cache) & rhs.get(gates, cache),
            Gate::Or(lhs, rhs) => lhs.get(gates, cache) | rhs.get(gates, cache),
            Gate::Not(rhs) => !rhs.get(gates, cache),
        }
    }
}

pub fn star_1_2(PuzzleData(gates): &PuzzleData) -> SolType {
    let sol1 = Source::Wire("a").get(gates, &mut HashMap::new());

    let mut gates = gates.to_owned();
    gates.insert("b", Gate::Value(Source::Value(sol1)));
    let sol2 = Source::Wire("a").get(&gates, &mut HashMap::new());

    (sol1, sol2).into()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
pub fn star_1(data: &&str) -> SolType {
    data.lines()
        .map(|l| l.as_bytes())
        .map(|d| {
            let (mut k, mut len) = (0, 0);
            while k < d.len() {
                (k, len) = match (d[k], d.get(k + 1)) {
                    (b'"', _) => (k + 1, len + 1),
                    (b'\\', Some(b'x')) => (k + 4, len + 3),
                    (b'\\', _) => (k + 2, len + 1),
                    _ => (k + 1, len),
                };
            }
            len
        })
        .sum()
}

1
2
3
4
5
pub fn star_2(data: &&str) -> SolType {
    data.lines()
        .map(|l| l.bytes().filter(|&b| b == b'"' || b == b'\\').count() + 2)
        .sum()
}

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

    const CONTENT: &str = r#"""
"abc"
"aaa\"aaa"
"\x27"
"#;

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

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

 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
pub mod input {
    use std::collections::HashMap;

    use crate::SolType;

    #[derive(Debug)]
    pub struct PuzzleData(pub Vec<SolType>, pub usize);

    impl From<&str> for PuzzleData {
        fn from(s: &str) -> Self {
            let mut ids = HashMap::new();
            let mut temp = Vec::new();
            for (n1, n2, dist) in s.lines().map(|l| {
                let mut words = l.split_ascii_whitespace();
                (
                    words.next().unwrap(),
                    words.nth(1).unwrap(),
                    words.nth(1).unwrap().parse().unwrap(),
                )
            }) {
                let len = ids.len();
                let id1 = *ids.entry(n1).or_insert(len);
                let len = ids.len();
                let id2 = *ids.entry(n2).or_insert(len);
                temp.push((id1, id2, dist));
            }

            let n = ids.len();
            let dists = temp.iter().fold(
                vec![0; ids.len() * ids.len()],
                |mut dists, &(id1, id2, dist)| {
                    dists[id1 + n * id2] = dist;
                    dists[id2 + n * id1] = dist;
                    dists
                },
            );

            Self(dists, n)
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
pub fn star_1(PuzzleData(dists, n): &PuzzleData) -> SolType {
    Permutations::from(0..*n)
        .map(|p| {
            p.iter()
                .zip(p[1..].iter())
                .map(|(id1, id2)| dists[id1 + n * id2])
                .sum()
        })
        .min()
        .unwrap()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
pub fn star_2(PuzzleData(dists, n): &PuzzleData) -> SolType {
    Permutations::from(0..*n)
        .map(|p| {
            p.iter()
                .zip(p[1..].iter())
                .map(|(id1, id2)| dists[id1 + n * id2])
                .sum()
        })
        .max()
        .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#"London to Dublin = 464
London to Belfast = 518
Dublin to Belfast = 141
"#;

    #[test]
    pub fn test_from() {
        let PuzzleData(dists, n) = PuzzleData::from(CONTENT);
        assert_eq!(vec![0, 464, 518, 464, 0, 141, 518, 141, 0], dists);
        assert_eq!(3, n);
    }

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

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

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

    impl From<&str> for PuzzleData {
        fn from(s: &str) -> Self {
            Self(s.trim().bytes().map(|b| b - b'0').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
pub fn update(data: &[u8], upd: &mut Vec<u8>) {
    upd.truncate(0);
    let mut k = 0;
    while k < data.len() {
        let a = data[k];
        let mut len = 1;
        while k + len < data.len() && data[k + len] == a {
            len += 1;
        }
        k += len;

        upd.push(len as _);
        upd.push(a);
    }
}

pub fn star_1(PuzzleData(data): &PuzzleData) -> SolType {
    let mut data = data.to_owned();
    let mut upd = Vec::with_capacity(data.len());
    for _ in 0..40 {
        update(&data, &mut upd);
        (data, upd) = (upd, data);
    }
    data.len()
}

1
2
3
4
5
6
7
8
9
pub fn star_2(PuzzleData(data): &PuzzleData) -> SolType {
    let mut data = data.to_owned();
    let mut upd = Vec::with_capacity(data.len());
    for _ in 0..50 {
        update(&data, &mut upd);
        (data, upd) = (upd, data);
    }
    data.len()
}

 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
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    pub fn test_update() {
        let mut upd = Vec::new();

        println!("1");
        update(&[1], &mut upd);
        assert_eq!(vec![1, 1], upd);

        println!("2");
        update(&[1, 1], &mut upd);
        assert_eq!(vec![2, 1], upd);

        println!("3");
        update(&[2, 1], &mut upd);
        assert_eq!(vec![1, 2, 1, 1], upd);

        println!("4");
        update(&[1, 2, 1, 1], &mut upd);
        assert_eq!(vec![1, 1, 1, 2, 2, 1], upd);

        println!("5");
        update(&[1, 1, 1, 2, 2, 1], &mut upd);
        assert_eq!(vec![3, 1, 2, 2, 1, 1], upd);

        println!("Loop");
        let mut data = vec![1];
        let mut upd = Vec::new();
        for _ in 0..5 {
            update(&data, &mut upd);
            (data, upd) = (upd, data);
        }
        assert_eq!(vec![3, 1, 2, 2, 1, 1], data);
    }
}

 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
pub fn next(a: &mut [u8]) {
    for k in (0..a.len()).rev() {
        if a[k] < b'z' {
            a[k] += 1;
            break;
        } else {
            assert!(k > 0);
            a[k] = b'a';
        }
    }
}

pub fn is_valid(a: &[u8]) -> bool {
    match (0..5).find(|&k| a[k] == a[k + 1]) {
        Some(k0) => {
            (k0 + 2..7).any(|k| a[k] == a[k + 1] && a[k] != a[k0])
                && (0..6).any(|k| a[k] + 1 == a[k + 1] && a[k] + 2 == a[k + 2])
                && a.iter().all(|&b| b != b'i' && b != b'l' && b != b'o')
        }
        _ => false,
    }
}

pub fn star_1_2(pwd: &&str) -> Solutions<String, String> {
    let mut a = pwd.trim().bytes().collect::<Vec<_>>();

    next(&mut a);
    while !is_valid(&a) {
        next(&mut a);
    }
    let sol1 = a.iter().map(|&b| b as char).collect();

    next(&mut a);
    while !is_valid(&a) {
        next(&mut a);
    }
    let sol2 = a.iter().map(|&b| b as char).collect();

    (sol1, sol2).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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
mod input {
    use std::collections::HashMap;

    use crate::SolType;

    #[derive(Debug, PartialEq, Eq)]
    pub enum Element {
        Number(SolType),
        String(String),
        Array(Vec<Element>),
        Object(HashMap<String, Box<Element>>),
    }

    fn parse_rec(data: &[u8]) -> (Element, usize) {
        match data.first().copied() {
            Some(b'"') => {
                let s = (1..)
                    .take_while(|&k| k < data.len() && data[k] != b'"')
                    .map(|k| data[k] as char)
                    .collect::<String>();
                let len = s.len() + 2;
                (Element::String(s), len)
            }
            Some(b'[') => {
                let mut p = 1;
                let mut values = Vec::new();
                while data[p] != b']' {
                    let (value, len) = parse_rec(&data[p..]);
                    p += len;
                    if data[p] == b',' {
                        p += 1;
                    }
                    values.push(value);
                }
                (Element::Array(values), p + 1)
            }
            Some(b'{') => {
                let mut p = 1;
                let mut map = HashMap::new();
                while data[p] != b'}' {
                    let (key, len) = parse_rec(&data[p..]);
                    let Element::String(key) = key else { panic!() };
                    p += len + 1;
                    let (value, len) = parse_rec(&data[p..]);
                    p += len;
                    if data[p] == b',' {
                        p += 1;
                    }
                    map.insert(key, Box::new(value));
                }
                (Element::Object(map), p + 1)
            }
            Some(a) => {
                let (sig, val) = match a {
                    b'-' => (-1, 0),
                    b'+' => (1, 0),
                    _ => (1, (a - b'0') as SolType),
                };

                let (val, len) = (1..)
                    .take_while(|&k| k < data.len() && data[k] >= b'0' && data[k] <= b'9')
                    .fold((val, 1), |(val, len), k| {
                        (10 * val + (data[k] - b'0') as SolType, len + 1)
                    });

                (Element::Number(sig * val), len)
            }
            _ => panic!(),
        }
    }

    impl<T: AsRef<[u8]>> From<T> for Element {
        fn from(value: T) -> Self {
            parse_rec(value.as_ref()).0
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
pub fn sum_numbers(element: &Element, include_red: bool) -> SolType {
    match element {
        Element::Number(v) => *v,
        Element::Array(vec) => vec.iter().map(|e| sum_numbers(e, include_red)).sum(),
        Element::Object(map)
            if include_red
                || map
                    .values()
                    .all(|e| e.as_ref() != &Element::String("red".to_string())) =>
        {
            map.values()
                .map(|e| sum_numbers(e.as_ref(), include_red))
                .sum()
        }
        _ => 0,
    }
}

pub fn star_1(element: &Element) -> SolType {
    sum_numbers(element, true)
}

1
2
3
pub fn star_2(element: &Element) -> SolType {
    sum_numbers(element, false)
}

 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
#[cfg(test)]
mod tests {
    use std::collections::HashMap;

    use super::*;

    #[test]
    pub fn test_star_1() {
        assert_eq!(6, star_1(&r#"[1,2,3]"#.into()));
        assert_eq!(6, star_1(&r#"{"a":2,"b":4}"#.into()));
        assert_eq!(3, star_1(&r#"[[[3]]]"#.into()));
        assert_eq!(0, star_1(&r#"{"a":[-1,1]}"#.into()));
        assert_eq!(0, star_1(&r#"[-1,{"a":1}]"#.into()));
        assert_eq!(0, star_1(&r#"[]"#.into()));
        assert_eq!(0, star_1(&r#"{}"#.into()));
    }

    #[test]
    pub fn test_element_from() {
        assert_eq!(
            Element::Array(vec![
                Element::Number(1),
                Element::Number(2),
                Element::Number(3)
            ]),
            Element::from(r#"[1,2,3]"#)
        );
        assert_eq!(
            Element::Object(HashMap::from([
                ("a".to_string(), Element::Number(2).into()),
                ("b".to_string(), Element::Number(4).into())
            ])),
            Element::from(r#"{"a":2,"b":4}"#)
        );
        assert_eq!(
            Element::Array(vec![Element::Array(vec![Element::Array(vec![
                Element::Number(3)
            ])])]),
            Element::from(r#"[[[3]]]"#)
        );
        assert_eq!(
            Element::Object(HashMap::from([(
                "a".to_string(),
                Element::Array(vec![Element::Number(-1), Element::Number(1)]).into()
            )])),
            Element::from(r#"{"a":[-1,1]}"#)
        );
    }
}

 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
pub mod input {
    use std::collections::HashMap;

    use crate::SolType;

    #[derive(Debug)]
    pub struct PuzzleData {
        pub len: usize,
        pub scores: Vec<SolType>,
    }

    impl From<&str> for PuzzleData {
        fn from(s: &str) -> Self {
            let mut ids = HashMap::new();
            let temp = s
                .lines()
                .map(|l| {
                    let mut words = l.split_ascii_whitespace();

                    let len = ids.len();
                    let n1 = *ids.entry(words.next().unwrap()).or_insert(len);

                    let v = match (
                        words.nth(1).unwrap(),
                        words.next().unwrap().parse::<SolType>().unwrap(),
                    ) {
                        ("gain", v) => v,
                        (_, v) => -v,
                    };

                    let len = ids.len();
                    let n2 = *ids
                        .entry(words.nth(6).unwrap().trim_end_matches('.'))
                        .or_insert(len);

                    ((n1, n2), v)
                })
                .collect::<Vec<_>>();
            let len = ids.len();
            let mut scores = vec![0; len * len];
            for ((n1, n2), score) in temp {
                scores[n1 + len * n2] = score;
            }

            Self {
                len: ids.len(),
                scores,
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
pub fn solve(len: usize, scores: &[SolType]) -> SolType {
    Permutations::from(0..len)
        .map(|seating| {
            (0..len)
                .map(|k| {
                    scores[seating[k] + len * seating[(k + 1) % len]]
                        + scores[seating[k] + len * seating[(k + len - 1) % len]]
                })
                .sum()
        })
        .max()
        .unwrap()
}

pub fn star_1(PuzzleData { len, scores }: &PuzzleData) -> SolType {
    solve(*len, scores)
}

1
2
3
4
5
6
7
pub fn star_2(PuzzleData { len, scores }: &PuzzleData) -> SolType {
    let mut temp = vec![0; (len + 1) * (len + 1)];
    for k in 0..*len {
        temp[k * (len + 1)..k * (len + 1) + len].copy_from_slice(&scores[k * len..k * len + len]);
    }
    solve(len + 1, &temp)
}

 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
#[cfg(test)]
mod tests {
    use super::*;

    const CONTENT: &str = r#"Alice would gain 54 happiness units by sitting next to Bob.
Alice would lose 79 happiness units by sitting next to Carol.
Alice would lose 2 happiness units by sitting next to David.
Bob would gain 83 happiness units by sitting next to Alice.
Bob would lose 7 happiness units by sitting next to Carol.
Bob would lose 63 happiness units by sitting next to David.
Carol would lose 62 happiness units by sitting next to Alice.
Carol would gain 60 happiness units by sitting next to Bob.
Carol would gain 55 happiness units by sitting next to David.
David would gain 46 happiness units by sitting next to Alice.
David would lose 7 happiness units by sitting next to Bob.
David would gain 41 happiness units by sitting next to Carol.
"#;

    #[test]
    pub fn test_from() {
        let PuzzleData { len, scores } = PuzzleData::from(CONTENT);
        println!("{}, {:?}", len, scores);
        assert_eq!(4, len);
    }

    #[test]
    pub fn test_star_1() {
        assert_eq!(330, star_1(&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
43
44
45
46
47
48
49
pub mod input {
    #[derive(PartialEq, Eq, Debug, Clone)]
    pub struct Reindeer<'a> {
        pub name: &'a str,
        pub speed: usize,
        pub flying_time: usize,
        pub resting_time: usize,
    }

    impl<'a> From<&'a str> for Reindeer<'a> {
        /// # Examples
        /// ```
        /// # use mr_kaffee_2015_14::input::Reindeer;
        /// let reindeer = Reindeer::from("Rudolph can fly 100 km/s for 11 seconds, but then must rest for 29 seconds.");
        /// assert_eq!(Reindeer { name: "Rudolph", speed: 100, flying_time: 11, resting_time: 29 }, reindeer);
        /// ```
        fn from(s: &'a str) -> Self {
            let mut words = s.split(' ');
            let name = words.next().unwrap();
            let mut words = words.skip(2); // can fly
            let speed = words.next().unwrap().parse().unwrap();
            let mut words = words.skip(2); // km/s for
            let flying_time = words.next().unwrap().parse().unwrap();
            let mut words = words.skip(6); // seconds, but then must rest for
            let resting_time = words.next().unwrap().parse().unwrap();

            Self {
                name,
                speed,
                flying_time,
                resting_time,
            }
        }
    }

    #[derive(PartialEq, Eq, Debug)]
    pub struct PuzzleData<'a> {
        pub reindeers: Vec<Reindeer<'a>>,
    }

    impl<'a> From<&'a str> for PuzzleData<'a> {
        /// parse the puzzle input
        fn from(s: &'a str) -> Self {
            Self {
                reindeers: s.lines().map(Reindeer::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
42
43
44
45
46
47
48
impl Reindeer<'_> {
    /// distance increment travel in second t
    ///
    /// # Examples
    /// ```
    /// # use mr_kaffee_2015_14::input::Reindeer;
    /// let speed = 100;
    /// let flying_time = 11;
    /// let resting_time = 29;
    /// let reindeer = Reindeer { name: "Rudolph", speed, flying_time, resting_time };
    ///
    /// assert_eq!(speed, reindeer.inc(0));
    /// assert_eq!(speed, reindeer.inc(flying_time - 1));
    /// assert_eq!(0, reindeer.inc(flying_time));
    /// assert_eq!(0, reindeer.inc(flying_time + resting_time - 1));
    /// assert_eq!(speed, reindeer.inc(flying_time + resting_time));
    /// ```
    pub fn inc(&self, t: usize) -> usize {
        if t % (self.flying_time + self.resting_time) < self.flying_time {
            self.speed
        } else {
            0
        }
    }

    /// distance traveled until after second t
    ///
    /// # Examples
    /// ```
    /// # use mr_kaffee_2015_14::input::Reindeer;
    /// let speed = 100;
    /// let flying_time = 11;
    /// let resting_time = 29;
    /// let reindeer = Reindeer { name: "Rudolph", speed, flying_time, resting_time };
    ///
    /// assert_eq!(flying_time * speed, reindeer.distance(flying_time + resting_time));
    ///
    /// let mut distance = 0;
    /// for t in 0..100 {
    ///     distance += reindeer.inc(t);
    ///     assert_eq!(distance, reindeer.distance(t + 1));
    /// }
    /// ```
    pub fn distance(&self, t: usize) -> usize {
        t / (self.flying_time + self.resting_time) * self.flying_time * self.speed
            + (t % (self.flying_time + self.resting_time)).min(self.flying_time) * self.speed
    }
}

1
2
3
4
5
6
7
8
9
pub const T: usize = 2503;

pub fn star_1(data: &PuzzleData) -> usize {
    data.reindeers
        .iter()
        .map(|reindeer| reindeer.distance(T))
        .max()
        .unwrap_or(0)
}

 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
pub fn scores(data: &PuzzleData, t: usize) -> Vec<usize> {
    // number of reindeers
    let n = data.reindeers.len();

    // loop over simulation steps (seconds)
    let (scores, _) = (0..t).fold((vec![0; n], vec![0; n]), |(mut s, mut d), t| {
        // increment distances (as side effect) and determine max distance
        let m = (0..n).fold(0, |m, k| {
            d[k] += data.reindeers[k].inc(t);
            m.max(d[k])
        });
        // increment scores for reindeers at max distance
        (0..n).filter(|k| d[*k] == m).for_each(|k| s[k] += 1);
        // updated scores and distances
        (s, d)
    });

    // return scores
    scores
}

/// Calculates max score at `t =` [`T`] using [`scores`]
pub fn star_2(data: &PuzzleData) -> usize {
    scores(data, T).into_iter().max().unwrap_or(0)
}

 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
#[cfg(test)]
mod tests {
    use mr_kaffee_aoc::err::PuzzleError;

    use super::*;

    const CONTENT: &str = r#"Comet can fly 14 km/s for 10 seconds, but then must rest for 127 seconds.
Dancer can fly 16 km/s for 11 seconds, but then must rest for 162 seconds."#;

    fn exp_data() -> PuzzleData<'static> {
        PuzzleData {
            reindeers: vec![
                Reindeer {
                    name: "Comet",
                    speed: 14,
                    flying_time: 10,
                    resting_time: 127,
                },
                Reindeer {
                    name: "Dancer",
                    speed: 16,
                    flying_time: 11,
                    resting_time: 162,
                },
            ],
        }
    }

    #[test]
    pub fn test_parse() -> Result<(), PuzzleError> {
        let data = PuzzleData::from(CONTENT);
        assert_eq!(exp_data(), data);

        Ok(())
    }

    #[test]
    pub fn test_reindeer_distance() {
        assert_eq!(
            vec![1120, 1056],
            exp_data()
                .reindeers
                .iter()
                .map(|r| r.distance(1000))
                .collect::<Vec<_>>()
        )
    }

    #[test]
    pub fn test_scores() {
        assert_eq!(vec![312, 689], scores(&exp_data(), 1000));
    }
}

 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
pub mod input {
    use crate::{SolType, PROPS};

    #[derive(Debug)]
    pub struct PuzzleData(pub Vec<[SolType; PROPS]>);

    fn parse_line(l: &str) -> [SolType; PROPS] {
        let mut words = l
            .split_ascii_whitespace()
            .skip(2)
            .step_by(2)
            .map(|w| w.trim_end_matches(',').parse().unwrap());
        [
            words.next().unwrap(),
            words.next().unwrap(),
            words.next().unwrap(),
            words.next().unwrap(),
            words.next().unwrap(),
        ]
    }

    impl From<&str> for PuzzleData {
        fn from(s: &str) -> Self {
            Self(s.lines().map(parse_line).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
42
43
44
45
46
47
pub const TOTAL: SolType = 100;

pub fn solve(ingredients: &[[SolType; PROPS]], calories: Option<SolType>) -> SolType {
    let len = ingredients.len();
    let mut q = vec![0; len];
    let mut score = 0;
    loop {
        let s = (0..len - 1).map(|k| q[k]).sum::<SolType>();
        q[len - 1] = TOTAL - s;

        let sums =
            q.iter()
                .zip(ingredients.iter())
                .fold([0; PROPS], |mut sums, (q, ingredient)| {
                    for k in 0..PROPS {
                        sums[k] += q * ingredient[k]
                    }
                    sums
                });

        if calories
            .map(|calories| calories == sums[PROPS - 1])
            .unwrap_or(true)
        {
            score = score.max(sums[0..PROPS - 1].iter().map(|&sum| sum.max(0)).product());
        }

        let mut sum = 0;
        for k in (0..len - 1).rev() {
            let s = TOTAL - (0..k).map(|k| q[k]).sum::<SolType>();
            if q[k] < s {
                q[k] += 1;
                sum += q[k];
                break;
            }
            q[k] = 0;
        }
        if sum == 0 {
            break;
        }
    }
    score
}

pub fn star_1(PuzzleData(ingredients): &PuzzleData) -> SolType {
    solve(ingredients, None)
}

1
2
3
pub fn star_2(PuzzleData(ingredients): &PuzzleData) -> SolType {
    solve(ingredients, Some(500))
}

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

    const CONTENT: &str = r#"Butterscotch: capacity -1, durability -2, flavor 6, texture 3, calories 8
Cinnamon: capacity 2, durability 3, flavor -2, texture -1, calories 3
"#;

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

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

    #[test]
    pub fn test_star_2() {
        assert_eq!(57_600_000, 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 mod input {
    use crate::{
        Sue, AKITAS, CARS, CATS, CHILDREN, GOLDFISH, PERFUMES, POMERANIANS, SAMOYEDS, TREES,
        VIZSLAS,
    };

    #[derive(Debug)]
    pub struct PuzzleData(pub Vec<Sue>);

    impl From<&str> for Sue {
        fn from(s: &str) -> Self {
            let words = s.split_ascii_whitespace().collect::<Vec<_>>();
            (0..words.len())
                .step_by(2)
                .map(|k| (words[k], words[k + 1]))
                .map(|(name, value)| (name, value.trim_end_matches([',', ':']).parse().unwrap()))
                .fold(Self::default(), |mut sue, (name, value)| {
                    match name {
                        "children:" => sue.0[CHILDREN] = Some(value),
                        "cats:" => sue.0[CATS] = Some(value),
                        "samoyeds:" => sue.0[SAMOYEDS] = Some(value),
                        "pomeranians:" => sue.0[POMERANIANS] = Some(value),
                        "akitas:" => sue.0[AKITAS] = Some(value),
                        "vizslas:" => sue.0[VIZSLAS] = Some(value),
                        "goldfish:" => sue.0[GOLDFISH] = Some(value),
                        "trees:" => sue.0[TREES] = Some(value),
                        "cars:" => sue.0[CARS] = Some(value),
                        "perfumes:" => sue.0[PERFUMES] = Some(value),
                        "Sue" => (),
                        _ => panic!("Unknown attribute: {}", name),
                    };
                    sue
                })
        }
    }

    impl From<&str> for PuzzleData {
        fn from(s: &str) -> Self {
            Self(s.lines().map(Sue::from).collect())
        }
    }
}