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
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100

fn run_until<F>(condition: F) -> Result<Vec<u8>, String>
where
    F: Fn(&Vec<u8>) -> bool,
{
    const MAX_ITERATIONS: i32 = 100_000_000;

    let mut scores = Vec::with_capacity(25_000_000);
    scores.push(3_u8);
    scores.push(7_u8);

    let push_score = |scores: &mut Vec<u8>, score: u8| {
        scores.push(score);
        condition(scores)
    };

    let mut elf_positions = (0_u32, 1_u32);

    let mut loop_count = 0;
    loop {
        let score_0 = scores[elf_positions.0 as usize];
        let score_1 = scores[elf_positions.1 as usize];
        let current_recipes_score = score_0 + score_1;

        let done = if current_recipes_score < 10 {
            push_score(&mut scores, current_recipes_score)
        } else {
            push_score(&mut scores, current_recipes_score / 10)
                || push_score(&mut scores, current_recipes_score % 10)
        };
        if done {
            return Ok(scores);
        }

        elf_positions.0 = (elf_positions.0 + 1 + u32::from(score_0)) % scores.len() as u32;
        elf_positions.1 = (elf_positions.1 + 1 + u32::from(score_1)) % scores.len() as u32;

        loop_count += 1;
        if loop_count > MAX_ITERATIONS {
            return Err(format!("Aborted after {} iterations", MAX_ITERATIONS));
        }
    }
}

pub fn part1(input_string: &str) -> Result<String, String> {
    let input_num_recipes = input_string
        .parse::<u32>()
        .map_err(|error| format!("Invalid input: {}", error.to_string()))?
        as usize;
    let num_recipes_after = 10;
    let desired_length = input_num_recipes + num_recipes_after;

    let scores = run_until(|scores| scores.len() >= desired_length)?;

    Ok(scores
        .iter()
        .skip(input_num_recipes)
        .take(num_recipes_after)
        .fold(String::new(), |acc, score| acc + &score.to_string()))
}

pub fn part2(input_string: &str) -> Result<usize, String> {
    let input_bytes: Vec<u8> = input_string
        .chars()
        .map(|b| {
            b.to_digit(10)
                .map(|b| b as u8)
                .ok_or_else(|| "Invalid input".to_string())
        })
        .collect::<Result<Vec<_>, String>>()?;

    if input_bytes.len() > 20 {
        return Err("Too long input".to_string());
    }

    let scores = run_until(|scores| scores.ends_with(&input_bytes))?;
    Ok(scores.len() - input_string.len())
}

#[test]
fn tests_part1() {
    assert_eq!(Ok("5158916779".to_string()), part1("9"));
    assert_eq!(Ok("0124515891".to_string()), part1("5"));
    assert_eq!(Ok("9251071085".to_string()), part1("18"));
    assert_eq!(Ok("5941429882".to_string()), part1("2018"));

    assert_eq!(
        Ok("1150511382".to_string()),
        part1(include_str!("day14_input.txt"))
    );
}

#[test]
fn tests_part2() {
    assert_eq!(Ok(9), part2("51589"));
    assert_eq!(Ok(5), part2("01245"));
    assert_eq!(Ok(18), part2("92510"));
    assert_eq!(Ok(2018), part2("59414"));

    assert_eq!(Ok(20_173_656), part2(include_str!("day14_input.txt")));
}