codetrotter_aoc_2019_solutions 0.9.0

/*
 * Copyright (c) 2019, 2020 Erik Nordstrøm <erik@nordstroem.no>
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

solution_printer!(4, print_solution, input_generator, INPUT, solve_part_1, solve_part_2);

pub const INPUT: &str = include_str!("../input/2019/day4.txt");

/// ### Day 4: Secure Container
///
/// [https://adventofcode.com/2019/day/4](https://adventofcode.com/2019/day/4)
///
/// You arrive at the Venus fuel depot only to discover it's protected by a
/// password.  The Elves had written the password on a sticky note, but
/// someone threw it out.
///
/// However, they do remember a few key facts about the password:
///
///   - It is a six-digit number.
///   - The value is within the range given in your puzzle input.
///   - Two adjacent digits are the same (like `22` in `122345`).
///   - Going from left to right, the digits *never decrease*; they only ever
///     increase or stay the same (like `111123` or `135679`).
///
/// Other than the range rule, the following are true:
///
///   - `111111` meets these criteria (double `11`, never decreases).
///   - `223450` does not meet these criteria (decreasing pair of digits `50`).
///   - `123789` does not meet these criteria (no double).
///
/// *How many different passwords* within the range given in your puzzle input
/// meet these criteria?
///
/// ### Examples
///
/// ```
/// use codetrotter_aoc_2019_solutions::day_04::{input_generator, solve_part_1};
/// assert_eq!(solve_part_1(&input_generator("111111-111111")), 1);
/// ```
///
/// ```
/// # use codetrotter_aoc_2019_solutions::day_04::{input_generator, solve_part_1};
/// assert_eq!(solve_part_1(&input_generator("223450-223450")), 0);
/// ```
///
/// ```
/// # use codetrotter_aoc_2019_solutions::day_04::{input_generator, solve_part_1};
/// assert_eq!(solve_part_1(&input_generator("123789-123789")), 0);
/// ```
///
/// ### Solution
///
/// ⚠️ SPOILER ALERT ⚠️
///
/// ```
/// use codetrotter_aoc_2019_solutions::day_04::{INPUT, input_generator, solve_part_1};
/// assert_eq!(solve_part_1(&mut input_generator(INPUT)), 1099);
/// ```
pub fn solve_part_1 (input_range: &DigitsNeverDecreasingRange) -> usize
{
  input_range.filter(|digits| any_digits_repeat(digits)).count()
}

#[derive(Copy, Clone)]
pub struct DigitsNeverDecreasingRange
{
  exhausted: bool,
  next_value: [u8; 6],
  end_value_inclusive: [u8; 6],
}

fn satisfy_digits_not_decreasing<F1, F2> (digits: &mut [u8; 6], f1: F1, f2: F2)
  where F1: Fn(&mut [u8; 6], usize) -> (),
        F2: Fn(&mut u8, u8) -> (),
{
  let mut prev_digit = digits[0];
  for (i, &mut digit) in digits.iter_mut().enumerate().skip(1)
  {
    if digit < prev_digit
    {
      f1(digits, i);
      for digit in digits[i..].iter_mut()
        { f2(digit, prev_digit); }
      break;
    }
    prev_digit = digit;
  }
}

impl DigitsNeverDecreasingRange
{
  fn new (lower_bound_inclusive: u32, upper_bound_inclusive: u32) -> Self
  {
    let mut initial_value = [0_u8; 6];
    initial_value.clone_from_slice(&get_digits_of_n(lower_bound_inclusive));
    satisfy_digits_not_decreasing(&mut initial_value, |_, _| (), |digit, prev_digit| *digit = prev_digit);

    let mut end_value_inclusive = [0_u8; 6];
    end_value_inclusive.clone_from_slice(&get_digits_of_n(upper_bound_inclusive));
    satisfy_digits_not_decreasing(&mut end_value_inclusive, |digits, i| digits[i - 1] -= 1, |digit, _| *digit = 9);

    let exhausted = initial_value > end_value_inclusive;

    Self
    {
      exhausted,
      next_value: initial_value,
      end_value_inclusive,
    }
  }
}

fn get_digits_of_n<'a> (n: u32) -> Vec<u8>
{
  (0..6).rev().map(|i| ((n / 10_u32.pow(i)) % 10) as u8).collect()
}

impl Iterator for DigitsNeverDecreasingRange
{
  type Item = [u8; 6];

  fn next (&mut self) -> Option<Self::Item>
  {
    if !self.exhausted
    {
      if self.next_value == self.end_value_inclusive
      {
        self.exhausted = true;
        return Some(self.next_value);
      }

      let ret = self.next_value;

      increment_to_next_non_decreasing_digits_value(&mut self.next_value);

      return Some(ret);
    }

    None
  }
}

fn increment_to_next_non_decreasing_digits_value (digits: &mut [u8]) -> u8
{
  let index_last_digit = digits.len() - 1;
  if digits[index_last_digit] < 9
  {
    digits[index_last_digit] += 1;
    return digits[index_last_digit];
  }
  else if index_last_digit > 0
  {
    let ret = increment_to_next_non_decreasing_digits_value(&mut digits[..index_last_digit]);
    digits[index_last_digit] = ret;
    return ret;
  }

  digits[index_last_digit] = 9;

  9
}

fn any_digits_repeat (digits: &[u8; 6]) -> bool
{
  let mut prev_digit = digits[0];
  for digit in digits.iter().skip(1)
  {
    if *digit == prev_digit
      { return true; }
    prev_digit = *digit;
  }
  false
}

pub fn input_generator (input_range_inclusive_str: &str) -> DigitsNeverDecreasingRange
{
  let ends: Vec<_> = input_range_inclusive_str.trim_end_matches('\n').split('-').map(|n_str| n_str.parse::<u32>().unwrap()).collect();
  let (lower_bound_inclusive, upper_bound_inclusive) = (ends[0], ends[1]);
  DigitsNeverDecreasingRange::new(lower_bound_inclusive, upper_bound_inclusive)
}

/// ### Day 4, Part Two
///
/// [https://adventofcode.com/2019/day/4#part2](https://adventofcode.com/2019/day/4#part2)
///
/// An Elf just remembered one more important detail: the two adjacent
/// matching digits *are not part of a larger group of matching digits*.
///
/// Given this additional criterion, but still ignoring the range rule, the
/// following are now true:
///
///   - `112233` meets these criteria because the digits never decrease and all
///     repeated digits are exactly two digits long.
///   - `123444` no longer meets the criteria (the repeated `44` is part of a
///     larger group of `444`).
///   - `111122` meets the criteria (even though `1` is repeated more than twice,
///     it still contains a double `22`).
///
/// *How many different passwords* within the range given in your puzzle input
/// meet all of the criteria?
///
/// ### Examples
///
/// ```
/// use codetrotter_aoc_2019_solutions::day_04::{input_generator, solve_part_2};
/// assert_eq!(solve_part_2(&input_generator("112233-112233")), 1);
/// ```
///
/// ```
/// # use codetrotter_aoc_2019_solutions::day_04::{input_generator, solve_part_2};
/// assert_eq!(solve_part_2(&input_generator("123444-123444")), 0);
/// ```
///
/// ```
/// # use codetrotter_aoc_2019_solutions::day_04::{input_generator, solve_part_2};
/// assert_eq!(solve_part_2(&input_generator("111122-111122")), 1);
/// ```
///
/// ### Solution
///
/// ⚠️ SPOILER ALERT ⚠️
///
/// ```
/// use codetrotter_aoc_2019_solutions::day_04::{INPUT, input_generator, solve_part_2};
/// assert_eq!(solve_part_2(&mut input_generator(INPUT)), 710);
/// ```
pub fn solve_part_2 (input_range: &DigitsNeverDecreasingRange) -> usize
{
  input_range.filter(|digits| any_digits_repeat_exactly_twice(digits)).count()
}

fn any_digits_repeat_exactly_twice (digits: &[u8; 6]) -> bool
{
  let mut prev_digit = digits[0];
  let mut curr_repeat_count = 1;
  let mut did_any_digits_repeat_only_twice_in_group = false;
  for digit in digits.iter().skip(1)
  {
    if *digit == prev_digit
      { curr_repeat_count += 1; }
    else
    {
      if curr_repeat_count == 2
        { did_any_digits_repeat_only_twice_in_group = true; }
      curr_repeat_count = 1;
    }
    prev_digit = *digit;
  }
  if curr_repeat_count == 2
    { did_any_digits_repeat_only_twice_in_group = true; }

  did_any_digits_repeat_only_twice_in_group
}