Day 20: Trench Map

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python with any of the "short names" listed in this page of supported languages):

<details>
<summary>Part 1</summary>

```python
```

</details>

1. 
wycy
(edited )
I think I'm 99% of the way there but I don't understand the catch. Edit: Ultimately got it, phew Question The problem doesn't mention anything about how to handle enhancement being #, which...

I think I'm 99% of the way there but I don't understand the catch.

Edit: Ultimately got it, phew

Question

The problem doesn't mention anything about how to handle enhancement 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.

Rust
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"),
}
}
}
}
}

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 = input_str.trim();
let input: Vec<_> = input_str.split("\n\n").collect();

// Build algorithm
let algorithm: HashMap<usize,bool> =
input
.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.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;
solve(&filename).unwrap();
}

1. bhrgunatha
Answer & spoiler There are , but the sample input was chosen carefully to hide that. In the sample: Any dark pixel surrounded by 8 dark neighbours becomes binary value 000000000 (0) and the...
Answer & spoiler There are , but the sample input was chosen carefully to hide that. In the sample:
• Any dark pixel surrounded by 8 dark neighbours becomes binary value 000000000 (0) and the example algorithm leaves that dark. enhancement = "."
• Any light pixel surrounded by 8 light neighbours becomes binary value 111111111 (511) and the example algorithm leaves that light. enhancement = "#"

This means the example images displayed seem as if the surr9ounding image would always be dark.

My real algorithm (and it seems yours too) has a dark pixel surrounded by dark pixel changing to light and a light pixel surrounded by light changed to dark. If you change the sample algorithm to enhancement = "#" and enhancement = "." you would see

#############
#############
#############
###.##.######
####..#.#####
#####.#..####
#######..####
###.#..##.###
#######..####
#####.#.#.###
#############
#############
#############

.............
.............
.............
.......#.....
..###........
...#..###....
........#....
...#..###.#..
..#..#####...
.....#....#..
....#.....#..
.............
.............

You need to find a way to cope with that.

2. 
Crespyl
This is pretty much the root of the puzzle. I think every input enhancement string starts with a "#" character. Without getting too far into spoilers: the edge case that's catching you out is when...

This is pretty much the root of the puzzle. I think every input enhancement string starts with a "#" character.

Without getting too far into spoilers: the edge case that's catching you out is when nine "."s become a "#", but what happens in the infinite expanse of "#"s on the next step?

1. wycy
(edited )
Thanks, I did just figure it out. Phew. Wasn't ready to spend a lot of time on this one after the last 2 days. You're right that this was the root of the puzzle--given that, there were effectively...

Thanks, I did just figure it out. Phew. Wasn't ready to spend a lot of time on this one after the last 2 days.

You're right that this was the root of the puzzle--given that, there were effectively no samples for this puzzle.

1 vote
2. Crespyl
This was refreshingly easy after that last one! Part 1 Ruby The only tricky thing here is to keep a close eye on your puzzle input, especially the "enhancement string". if your test case passes,...

This was refreshingly easy after that last one!

Part 1 Ruby

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

if your test case passes, but doesn't work on the real inputPay attention to what's happening in the infinite expanse outside the main area, what happens to a pixel when every value is a `1`, and what happens when every value is a `0`?
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 }.min
max_x = map.keys.map { |k| k }.max
min_y = map.keys.map { |k| k }.min
max_y = map.keys.map { |k| k }.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 }.min
max_x = map.keys.map { |k| k }.max
min_y = map.keys.map { |k| k }.min
max_y = map.keys.map { |k| k }.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

Part 2 Ruby

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

3. bhrgunatha
Data Structure 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)...
Data Structure

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 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"))

Part 1

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)
(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))

Part 2

CSI levels of enhancement.

(define (part-02 input)