codetrotter_aoc_2019_solutions 0.9.0

/*
 * Copyright (c) 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!(8, print_solution, input_generator, INPUT, solve_part_1, solve_part_2);

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

/// ### Day 8: Space Image Format
///
/// [https://adventofcode.com/2019/day/8](https://adventofcode.com/2019/day/8)
///
/// The Elves' spirits are lifted when they realize you have an opportunity to
/// reboot one of their Mars rovers, and so they are curious if you would spend
/// a brief sojourn on Mars. You land your ship near the rover.
///
/// When you reach the rover, you discover that it's already in the process of
/// rebooting! It's just waiting for someone to enter a [BIOS](https://en.wikipedia.org/wiki/BIOS) password. The Elf
/// responsible for the rover takes a picture of the password (your puzzle
/// input) and sends it to you via the Digital Sending Network.
///
/// Unfortunately, images sent via the Digital Sending Network aren't encoded
/// with any normal encoding; instead, they're encoded in a special Space Image
/// Format.  None of the Elves seem to remember why this is the case. They send
/// you the instructions to decode it.
///
/// Images are sent as a series of digits that each represent the color of a
/// single pixel.  The digits fill each row of the image left-to-right, then
/// move downward to the next row, filling rows top-to-bottom until every pixel
/// of the image is filled.
///
/// Each image actually consists of a series of identically-sized *layers* that
/// are filled in this way. So, the first digit corresponds to the top-left
/// pixel of the first layer, the second digit corresponds to the pixel to the
/// right of that on the same layer, and so on until the last digit, which
/// corresponds to the bottom-right pixel of the last layer.
///
/// For example, given an image `3` pixels wide and `2` pixels tall, the image data
/// `123456789012` corresponds to the following image layers:
///
/// ```text
/// Layer 1: 123
///          456
///
/// Layer 2: 789
///          012
/// ```
///
/// The image you received is *`25` pixels wide and `6` pixels tall*.
///
/// To make sure the image wasn't corrupted during transmission, the Elves
/// would like you to find the layer that contains the *fewest `0` digits*.  On that
/// layer, what is *the number of `1` digits multiplied by the number of `2` digits?*
///
/// ### Solution
///
/// ⚠️ SPOILER ALERT ⚠️
///
/// ```
/// use codetrotter_aoc_2019_solutions::day_08::{INPUT, input_generator, solve_part_1};
/// assert_eq!(solve_part_1(&input_generator(INPUT)), 2032);
/// ```
pub fn solve_part_1 (input_image_data: &ImageData) -> usize
{
  let mut lowest_amount_of_zeros = usize::max_value();
  let mut answer = 0;

  for layer in input_image_data
  {
    let mut disregard_layer = false;

    let (mut num_zeros_in_layer, mut num_ones_il, mut num_twos_il) = (0,0,0);

    for &pixel_value in layer.iter()
    {
      if pixel_value == 0
      {
        num_zeros_in_layer += 1;
        if num_zeros_in_layer >= lowest_amount_of_zeros
        {
          disregard_layer = true;
          break;
        }
      }
      else if pixel_value == 1
        { num_ones_il += 1; }
      else if pixel_value == 2
        { num_twos_il += 1; }
    }

    if !disregard_layer
    {
      lowest_amount_of_zeros = num_zeros_in_layer;
      answer = num_ones_il * num_twos_il;
    }
  }

  answer
}

pub const IMAGE_WIDTH: usize = 25;
pub const IMAGE_HEIGHT: usize = 6;
pub const PIXELS_PER_LAYER: usize = IMAGE_WIDTH * IMAGE_HEIGHT;
pub type ImageData = Vec<LayerData>;
pub type LayerData = [u8; PIXELS_PER_LAYER];

pub fn input_generator (image_str: &str) -> ImageData
{
  let mut image_str = image_str.trim_end();

  let mut image_data = ImageData::new();

  loop
  {
    let chunk = &image_str[..PIXELS_PER_LAYER];
    image_str = &image_str[PIXELS_PER_LAYER..];

    let mut layer_pixels = [0; PIXELS_PER_LAYER];
    let hurr: Vec<_> = chunk.chars().map(|c| c.to_digit(10).unwrap() as u8).collect();
    layer_pixels.copy_from_slice(&hurr);
    image_data.push(layer_pixels);

    if image_str.len() == 0
      { break; }
  }

  image_data
}

/// ### Day 8, Part Two
///
/// [https://adventofcode.com/2019/day/8#part2](https://adventofcode.com/2019/day/8#part2)
///
/// Now you're ready to decode the image. The image is rendered by stacking the
/// layers and aligning the pixels with the same positions in each layer. The
/// digits indicate the color of the corresponding pixel: `0` is black, `1` is
/// white, and `2` is transparent.
///
/// The layers are rendered with the first layer in front and the last layer in
/// back. So, if a given position has a transparent pixel in the first and
/// second layers, a black pixel in the third layer, and a white pixel in the
/// fourth layer, the final image would have a *black* pixel at that position.
///
/// For example, given an image `2` pixels wide and `2` pixels tall, the image data
/// `0222112222120000` corresponds to the following image layers:
///
/// ```text
/// Layer 1: 02
///          22
///
/// Layer 2: 11
///          22
///
/// Layer 3: 22
///          12
///
/// Layer 4: 00
///          00
/// ```
///
/// Then, the full image can be found by determining the top visible pixel in
/// each position:
///
///   - The top-left pixel is *black* because the top layer is `0`.
///   - The top-right pixel is *white* because the top layer is `2` (transparent),
///     but the second layer is `1`.
///   - The bottom-left pixel is *white* because the top two layers are `2`, but
///     the third layer is `1`.
///   - The bottom-right pixel is *black* because the only visible pixel in that
///     position is `0` (from layer 4).
///
/// So, the final image looks like this:
///
/// ```text
/// 01
/// 10
/// ```
///
/// *What message is produced after decoding your image?*
///
/// ### Solution
///
/// ⚠️ SPOILER ALERT ⚠️
///
/// ```
/// use codetrotter_aoc_2019_solutions::day_08::{INPUT, input_generator, solve_part_2, FlattenedImage, PIXELS_PER_LAYER};
/// let flattened = FlattenedImage
/// {
///   flattened:
///   [
///     0,1,1,0,0,1,1,1,1,0,0,1,1,0,0,1,0,0,1,0,0,1,1,0,0, // "  XXXX    XXXXXXXX    XXXX    XX    XX    XXXX    "
///     1,0,0,1,0,1,0,0,0,0,1,0,0,1,0,1,0,0,1,0,1,0,0,1,0, // "XX    XX  XX        XX    XX  XX    XX  XX    XX  "
///     1,0,0,0,0,1,1,1,0,0,1,0,0,0,0,1,0,0,1,0,1,0,0,0,0, // "XX        XXXXXX    XX        XX    XX  XX        "
///     1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,1,0,1,0,1,1,0, // "XX        XX        XX        XX    XX  XX  XXXX  "
///     1,0,0,1,0,1,0,0,0,0,1,0,0,1,0,1,0,0,1,0,1,0,0,1,0, // "XX    XX  XX        XX    XX  XX    XX  XX    XX  "
///     0,1,1,0,0,1,0,0,0,0,0,1,1,0,0,0,1,1,0,0,0,1,1,1,0, // "  XXXX    XX          XXXX      XXXX      XXXXXX  "
///   ],
/// };
/// // XXX: Originally I was planning on decoding the image into a string,
/// //      but unless the whole font is embedded in our input and using
/// //      some kind of masking that we could figure out without too much
/// //      trouble and get the glyphs for all of the possible characters,
/// //      we are not able to decode the pictured string for all of the
/// //      different inputs that the AoC servers is able to give.
/// //      So, unfortunately we are left for now with just outputting
/// //      the flattened image and leaving the reading of the value shown
/// //      in the image to humans running the program.
/// assert_eq!(solve_part_2(&input_generator(INPUT)), flattened);
/// ```
pub fn solve_part_2 (input_image_data: &ImageData) -> FlattenedImage
{
  input_image_data.flatten()
}

pub struct FlattenedImage
{
  pub flattened: LayerData,
}

impl FlattenedImage
{
  fn new () -> Self
  {
    Self
    {
      flattened: [2; PIXELS_PER_LAYER],
    }
  }
}

impl std::fmt::Display for FlattenedImage
{
  fn fmt (&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result
  {
    for y in 0..IMAGE_HEIGHT
    {
      for x in 0..IMAGE_WIDTH
      {
        match self.flattened[y * IMAGE_WIDTH + x]
        {
          0 => write!(f, "  ")?,
          1 => write!(f, "XX")?,
          2 => write!(f, "  ")?,
          _ => unreachable!(),
        }
      }
      writeln!(f)?;
    }

    Ok(())
  }
}

impl std::fmt::Debug for FlattenedImage
{
  fn fmt (&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result
  {
    for y in 0..IMAGE_HEIGHT
    {
      for x in 0..IMAGE_WIDTH
      {
        write!(f, "{},", self.flattened[y * IMAGE_WIDTH + x])?;
      }
      writeln!(f)?;
    }

    Ok(())
  }
}

impl PartialEq for FlattenedImage
{
  fn eq (&self, other: &Self) -> bool
  {
    for (i, &pixel) in self.flattened.iter().enumerate()
    {
      if pixel != other.flattened[i]
        { return false; }
    }

    true
  }
}

trait Flatten
{
  fn flatten (&self) -> FlattenedImage;
}

impl Flatten for ImageData
{
  fn flatten (&self) -> FlattenedImage
  {
    let mut flattened = FlattenedImage::new();

    let mut pixels_remaining: Vec<_> = (0..PIXELS_PER_LAYER).collect();

    for layer in self
    {
      pixels_remaining.retain(|&i|
      {
        if layer[i] != 2
        {
          flattened.flattened[i] = layer[i];
          return false;
        }
        true
      });

      if pixels_remaining.len() == 0
        { break; }
    }

    flattened
  }
}