Day 20: Trench Map

The problem doesn't mention anything about how to handle enhancement[0] being #, which would always turn on every pixel in the infinite image. There should be an infinite number of lit pixels after 1 pass--why isn't there? The sample doesn't cover this at all.

use std::env;
use std::io::{self};
use std::collections::HashMap;

type Point = (isize,isize);

fn pixel_from(ch: char) -> bool {
    match ch {
        '#' => true,
        '.' => false,
        _ => unreachable!(),
    }
}

fn enhancement_index(pt: &Point, map: &HashMap<Point,bool>, canvas: bool) -> usize {
    let square_indices = vec![
        (pt.0-1,pt.1-1),
        (pt.0+0,pt.1-1),
        (pt.0+1,pt.1-1),
        (pt.0-1,pt.1+0),
        (pt.0+0,pt.1+0),
        (pt.0+1,pt.1+0),
        (pt.0-1,pt.1+1),
        (pt.0+0,pt.1+1),
        (pt.0+1,pt.1+1),
        ];
    let mut index = String::new();
    for square in square_indices {
        match map.get(&square) {
            Some(true) => index.push_str("1"),
            Some(false) => index.push_str("0"),
            _ => {
                match canvas {
                    true => index.push_str("0"),
                    false => index.push_str("1"),
                }
            }
        }
    }
    usize::from_str_radix(&index,2).unwrap()
}

fn map_extents(map: &HashMap<Point,bool>) -> (isize,isize,isize,isize) {
    let xmin = &map.keys().map(|&pt| pt.0).min().unwrap();
    let ymin = &map.keys().map(|&pt| pt.1).min().unwrap();
    let xmax = &map.keys().map(|&pt| pt.0).max().unwrap();
    let ymax = &map.keys().map(|&pt| pt.1).max().unwrap();
    (*xmin,*ymin,*xmax,*ymax)
}

fn solve(input: &str) -> io::Result<()> {
    // Input
    let input_str = std::fs::read_to_string(input).unwrap();
    let input_str = input_str.trim();
    let input: Vec<_> = input_str.split("\n\n").collect();

    // Build algorithm
    let algorithm: HashMap<usize,bool> = 
        input[0]
        .chars()
        .enumerate()
        .map(|(i,ch)| (i,pixel_from(ch)))
        .collect();
    
    // Build initial image
    let mut image: HashMap<Point,bool> = HashMap::new();
    for (y,line) in input[1].split("\n").enumerate() {
        for (x,ch) in line.chars().enumerate() {
            let (x,y) = (x.try_into().unwrap(),y.try_into().unwrap());
            image.insert((x,y),pixel_from(ch));
        }
    }

    // Apply algorithm
    let mut part1 = 0;
    for step in 0..50 {
        let image_before = image.clone();
        let (xmin,ymin,xmax,ymax) = map_extents(&image_before);
        let canvas = step % 2 == 0;

        for y in (ymin-1)..=(ymax+1) {
            for x in (xmin-1)..=(xmax+1) {
                let new_px = algorithm[&enhancement_index(&(x,y),&image_before,canvas)];
                image.insert((x,y),new_px);
            }
        }

        if step == 2 { part1 = image.iter().filter(|&(_,v)| *v).count(); }
    }

    println!("Part 1: {}", part1); // 5395
    
    let part2 = image.iter().filter(|&(_,v)| *v).count();
    println!("Part 2: {}", part2); // 17584

    Ok(())
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    solve(&filename).unwrap();
}

The only tricky thing here is to keep a close eye on your puzzle input, especially the "enhancement string".

def enhancement_index(map, x, y)
  [
    [-1, -1], [0, -1], [+1, -1],
    [-1,  0], [0,  0], [+1,  0],
    [-1, +1], [0, +1], [+1, +1]
  ].map { |dx, dy| [x + dx, y + dy] }
   .map { |nx, ny| map[[nx,ny]] }
   .join
   .tr('.#', '01')
   .to_i(2)
end

def enhance_map(map, enhancement)
  min_x = map.keys.map { |k| k[0] }.min
  max_x = map.keys.map { |k| k[0] }.max
  min_y = map.keys.map { |k| k[1] }.min
  max_y = map.keys.map { |k| k[1] }.max

  output = Hash.new('.')
  output.default = enhancement[enhancement_index(map, 999999999, 999999999)]

  ((min_x-1)..(max_x+1)).each do |x|
    ((min_y-1)..(max_y+1)).each do |y|
      output[[x,y]] = enhancement[enhancement_index(map, x, y)]
    end
  end

  return output
end

def print_map(map)
  min_x = map.keys.map { |k| k[0] }.min
  max_x = map.keys.map { |k| k[0] }.max
  min_y = map.keys.map { |k| k[1] }.min
  max_y = map.keys.map { |k| k[1] }.max

  output = Hash.new('.')

  ((min_y-2)..(max_y+2)).each do |y|
    ((min_x-2)..(max_x+2)).each do |x|
      print map[[x,y]]
    end
    print "\n"
  end
end

def compute_p1(input)
  enhancement = input.lines.first.chomp

  map = Hash.new('.')
  row, col = 0, 0

  input.lines[2..].each do |line|
    line.chomp.chars.each do |c|
      map[[col, row]] = c
      col += 1
    end
    row += 1; col = 0
  end

  step_one = enhance_map(map, enhancement)
  step_two = enhance_map(step_one, enhancement)

  step_two.values.tally['#']
end

A little slow on the runtime here, there's certainly room to optimize, but 15s isn't bad.

def compute_p2(input)
  enhancement = input.lines.first.chomp

  map = Hash.new('.')
  row, col = 0, 0

  input.lines[2..].each do |line|
    line.chomp.chars.each do |c|
      map[[col, row]] = c
      col += 1
    end
    row += 1; col = 0
  end

  50.times do
    map = enhance_map(map, enhancement)
  end

  map.values.tally['#']
end

I use a struct to store the pixels, the algorithm, image dimensions (as it grows) and the canvas colour.

(struct image (index pixels top-left bottom-right canvas) #:transparent)
(define dark "0")
(define light "1")
(define (light? v) (string=? light v))
(define index-value vector-ref)

The algorithm/index is just an array for lookup.
The image is a hash from co-ordinate -> colour.
I only store the lit pixels in the image though, so the colour is always light.
I save the size of the image too since it's needed later (and to display the image)

(define (read-image ls)
  (define index (create-index (first ls)))
  (define-values (pixels xmax ymax) (create-image (drop ls 2)))
  (image index pixels (list 0 0) (list xmax ymax) dark))

(define (create-index s)
  (for/vector ([c (in-string s)])
    (if (eq? c #\.) dark light)))

(define (create-image ps)
  (for*/fold ([pixels (hash)]
              [xmax 0]
              [ymax 0])
             ([(row y) (in-indexed ps)]
              [(c x) (in-indexed row)])
    (values (hash-set pixels (list x y)
                      (if (eq? c #\#)
                          light dark))
            (max xmax x)
            (max ymax y))))

(define (show-image I)
  (match-define (image index pixels top-left bottom-right outside) I)
  (match-define (list xmin ymin) top-left)
  (match-define (list xmax ymax) bottom-right)
  (for ([y (in-inclusive-range ymin ymax)])
    (for ([x (in-inclusive-range xmin xmax)])
      (printf "~a" (if (light? (hash-ref pixels (list x y))) "#" " ")))
    (printf "\n"))
  (printf "\n"))

I noticed at the start that my 'algorithm' sets any dark pixel surrounded by dark pixels to light and vice-versa. So I knew I couldn't rely on anything not stored in the pixel hash to be dark.
This means the infinite image was going to change from light to dark so I store the current 'canvas' colour.
Anything out of range of the current image dimensions will be canvas colour and any point not saved in pixels will be dark (since I'm only storing light pixels).

(define (part-01 input)
  (define I (read-image input))
  (lit-pixels (progressive-enhancement I 2)))

(define (lit-pixels I)
  (hash-count (image-pixels I)))

(define (progressive-enhancement I n)
  (for/fold ([I I]) ([_ n]) (enhance I)))

(define (enhance I)
  (match-define (image index pixels top-left bottom-right canvas) I)
  (match-define (list xmin ymin) top-left)
  (match-define (list xmax ymax) bottom-right)
  (for*/fold ([P+ (hash)]
              #:result (image index P+
                              (map sub1 top-left) (map add1 bottom-right)
                              (if (light? canvas)
                                  (index-value index 511)
                                  (index-value index 0))))
             ([y (in-inclusive-range (sub1 ymin) (add1 ymax))]
              [x (in-inclusive-range (sub1 xmin) (add1 xmax))])
    (define i (binary-value (neighbours I (list x y))))
    (define new-pixel (index-value index i))
    (values (if (light? new-pixel)
                (hash-set P+ (list x y) new-pixel)
                P+))))

(define (neighbours I p)
  (match-define (image index pixels top-left bottom-right canvas) I)
  (match-define (list xmin ymin) top-left)
  (match-define (list xmax ymax) bottom-right)
  (match-define (list x y) p)
  (for*/list ([iy (in-inclusive-range (sub1 y) (add1 y))]
              [ix (in-inclusive-range (sub1 x) (add1 x))])
    (if (out-of-bounds? ix iy xmin xmax ymin ymax)
        canvas
        (hash-ref pixels (list ix iy) dark))))

(define (out-of-bounds? x y xmin xmax ymin ymax)
  (not (and (<= xmin x xmax)
            (<= ymin y ymax))))

(define (binary-value ds)
  (string->number (apply string-append ds) 2))

CSI levels of enhancement.

(define (part-02 input)
  (define I (read-image input))
  (lit-pixels (progressive-enhancement I 50)))