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
101
102
103
104
105
106
107
108
109
110

use crate::input::Input;
use std::collections::HashSet;

pub fn solve(input: &mut Input) -> Result<String, String> {
    let number_of_cups = input.part_values(9, 1_000_000);
    let max_cup_value = number_of_cups;
    let crab_moves = input.part_values(100, 10_000_000);

    let input_bytes = input.text.as_bytes();
    let input_cup_values = if input_bytes.len() != 9 {
        return Err(format!(
            "Invalid input: Expected 9 characters as input, was {}",
            input_bytes.len()
        ));
    } else if !input_bytes.iter().all(u8::is_ascii_digit) {
        return Err("Invalid input: Not all characters are digits".to_string());
    } else if input_bytes.iter().collect::<HashSet<_>>().len() == 9 {
        input_bytes
            .iter()
            .map(|b| u32::from(b - b'0'))
            .collect::<Vec<u32>>()
    } else {
        return Err("Invalid input: Not 9 distinct digits".to_string());
    };

    // Indexed by cup values, the array contains information about the circuler
    // structure - the next cup value in the circle:
    let mut cups: Vec<u32> = vec![0; number_of_cups as usize + 1];

    for (input_idx, &cup_value) in input_cup_values.iter().enumerate() {
        cups[cup_value as usize] = if input.is_part_one() || input_idx < 8 {
            input_cup_values[(input_idx + 1) % 9]
        } else {
            10
        };
    }

    if input.is_part_two() {
        for cup_value in 10..=number_of_cups {
            cups[cup_value as usize] = if cup_value == max_cup_value {
                input_cup_values[0]
            } else {
                cup_value + 1
            };
        }
    }

    let mut current_cup_value = input_cup_values[0];

    for _move in 0..crab_moves {
        let pickup_1 = cups[current_cup_value as usize];
        let pickup_2 = cups[pickup_1 as usize];
        let pickup_3 = cups[pickup_2 as usize];

        let mut destination_cup = if current_cup_value == 1 {
            max_cup_value
        } else {
            current_cup_value - 1
        };
        while destination_cup == pickup_1
            || destination_cup == pickup_2
            || destination_cup == pickup_3
        {
            destination_cup = if destination_cup == 1 {
                max_cup_value
            } else {
                destination_cup - 1
            };
        }

        // Pick up the three cups following the current one:
        let (before_picked_up_sequence, after_picked_up_sequence) =
            (current_cup_value, cups[pickup_3 as usize]);
        cups[before_picked_up_sequence as usize] = after_picked_up_sequence;

        // Insert the picked up sequence after the destination cup:
        let after_destination_cup = cups[destination_cup as usize];
        cups[destination_cup as usize] = pickup_1;
        cups[pickup_3 as usize] = after_destination_cup;

        current_cup_value = cups[current_cup_value as usize];
    }

    let cup_after_one_value = cups[1];
    Ok(if input.is_part_one() {
        let mut result_string = String::new();
        let mut current_cup_value = cup_after_one_value;
        while (result_string.len() as u32) < number_of_cups - 1 {
            result_string.push((current_cup_value as u8 + b'0') as char);
            current_cup_value = cups[current_cup_value as usize];
        }
        result_string
    } else {
        let cup_after_that_value = cups[cup_after_one_value as usize];
        (u64::from(cup_after_one_value) * u64::from(cup_after_that_value)).to_string()
    })
}

#[test]
pub fn tests() {
    use crate::{test_part_one, test_part_two};

    let example = "389125467";
    test_part_one!(example => "67384529".to_string());
    test_part_two!(example => "149245887792".to_string());

    let real_input = include_str!("day23_input.txt");
    test_part_one!(real_input => "65432978".to_string());
    test_part_two!(real_input => "287230227046".to_string());
}