Day 15: Chiton

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. 
PapaNachos
(edited )
Oh god, a shortest path algorithm. It's been a minute since I've done one of these. I don't know if I'll finish tonight. We'll see how it goes Edit: Wow, this one is just kinda dickish on multiple...

Oh god, a shortest path algorithm. It's been a minute since I've done one of these. I don't know if I'll finish tonight. We'll see how it goes

Edit: Wow, this one is just kinda dickish on multiple levels

Edit 2: This felt like a bad tech interview sort of gotcha question. Did anyone enjoy this? Or am I the only one mad about it.

Day 15 Part A - Python

I had to look up how Djikstra's algorithm works since it's been a while since I've written a shortest path algorithm. IMO they're pretty tedious and rarely useful to know

import re
from collections import defaultdict

#data = test_data
data = real_data
data = data.split('\n')

grid = defaultdict(lambda: defaultdict(int))

for index2, row in enumerate(data):
for index, val in enumerate(list(row)):
grid[index2][index] = int(val)

start = (0,0)
end = (len(list(grid.keys()))-1, len(list(grid.keys()))-1)

bounds_x = len(list(grid.keys()))
bounds_y = len(list(grid.keys()))

directions = [(1,0), (-1,0), (0,1), (0,-1)]

def display_grid(grid):
for row in grid.keys():
this_row = ""
for col in grid[row].keys():
this_row = this_row + str(grid[row][col])
print(this_row)

#display_grid(grid)
paths = {start:None}
checked = []
to_check = [start]
options = {start:0}
checking = start
while checking != end:
checked.append(checking)
to_check.remove(checking)
#rint('Checking: ', checking)
weight = options[checking]
for direction in directions:
nearby_x = checking + direction
nearby_y = checking + direction
if nearby_x >= 0 and nearby_x < bounds_x and nearby_y >= 0 and nearby_y < bounds_y:
nearby_location = (nearby_x, nearby_y)
distance = weight+grid[nearby_x][nearby_y]
if nearby_location in options.keys():
if distance < options[nearby_location]:
options[nearby_location] = distance
paths[nearby_location] = checking
to_check.append(nearby_location)
else:
options[nearby_location] = distance
paths[nearby_location] = checking
to_check.append(nearby_location)
next_to_check = None
next_distance = 10000000
for key in to_check:
if options[key] < next_distance and key not in checked:
next_to_check = key
next_distance = options[key]
checking = next_to_check
#print(paths)
print(options[end])

Day 15 Part B - Python

Wow. Really? Wow. Just fuck you. I did not enjoy this problem. After running into an actually pretty funny bug that required me to rewrite my display program, I just made a bigger grid and ran it. It took like 30-60 minutes to run, and I'm pretty sure that most of the time was from how I was handling my memory and I really didn't want to get into that sort of optimization.

I'm well aware my implementation is janky, but I don't think this one had a different way to think about it like some of the other optimization problems did. It's just 'be better at algorithms' or 'use a library'

import re
from collections import defaultdict

#data = test_data
data = real_data
data = data.split('\n')

grid = defaultdict(lambda: defaultdict(int))

for index2, row in enumerate(data):
for index, val in enumerate(list(row)):
grid[index2][index] = int(val)

bounds_x = len(list(grid.keys()))
bounds_y = len(list(grid.keys()))

supergrid = defaultdict(lambda: defaultdict(int))
for row in grid.keys():
for col in grid[row].keys():
#print('-----------')
for index1 in range(0,5):
for index2 in range(0,5):
new_raw_val = grid[row][col] + index1 + index2
new_actual_val = ((new_raw_val - 1) % 9) + 1
new_row = row + (index1 * bounds_y)
new_col = col + (index2 * bounds_x)
#print(new_row, new_col, new_raw_val, new_actual_val)
supergrid[new_row][new_col] = new_actual_val

start = (0,0)
end = (len(list(supergrid.keys()))-1, len(list(supergrid.keys()))-1)

bounds_x = len(list(supergrid.keys()))
bounds_y = len(list(supergrid.keys()))

directions = [(1,0), (-1,0), (0,1), (0,-1)]

def display_grid(display_grid):
rows = list(display_grid.keys())
rows.sort()
for row in rows:
this_row = ""
cols = list(display_grid[row].keys())
cols.sort()
for col in cols:
this_row = this_row + str(display_grid[row][col])
print(this_row)

#display_grid(grid)
paths = {start:None}
checked = []
to_check = [start]
options = {start:0}
checking = start
while checking != end:
checked.append(checking)
to_check.remove(checking)
#rint('Checking: ', checking)
weight = options[checking]
for direction in directions:
nearby_x = checking + direction
nearby_y = checking + direction
if nearby_x >= 0 and nearby_x < bounds_x and nearby_y >= 0 and nearby_y < bounds_y:
nearby_location = (nearby_x, nearby_y)
distance = weight+supergrid[nearby_x][nearby_y]
if nearby_location in options.keys():
if distance < options[nearby_location]:
options[nearby_location] = distance
paths[nearby_location] = checking
to_check.append(nearby_location)
else:
options[nearby_location] = distance
paths[nearby_location] = checking
to_check.append(nearby_location)
next_to_check = None
next_distance = 10000000
for key in to_check:
if options[key] < next_distance and key not in checked:
next_to_check = key
next_distance = options[key]
checking = next_to_check
#print(paths)
print(options[end])
#display_grid(supergrid)

• Ugh, fuck this problem, there are a LOT of ways to make it take an extremely long time to solve. It felt like a substantial jump in difficulty

• For the first part at least I highly recommend looking up some shortest path algorithms such as Djikstra's Algorithm. It's the sort of problem where you're extremely unlikely to be able to have a spark of insight unless you've studied that sort of problem

• Even with a decent algorithm part B might take a while. My code wasn't great but it still took somewhere between 30-60 minutes to run while being able to handle part A in <1 second.

• An out of the box pathfinding solution will probably have good memory management Deep Magic that will substantially speed up the problem, but also that doesn't feel like really engaging with the problem. I don't know.

1. 
wycy
(edited )
I enjoyed today's problem. I came up with a working solution relatively quickly (though my part 2 solution took over a minute to run even with a Rust --release build). Then, wanting to optimize...

I enjoyed today's problem. I came up with a working solution relatively quickly (though my part 2 solution took over a minute to run even with a Rust --release build). Then, wanting to optimize and come up with a fast solution, I ultimately learned about binary heaps/priority queues. So I not only got the satisfaction of being able to solve it myself (slowly), I also then later got the satisfaction of learning something new.

I did struggle to generate the expanded map today. I kept making silly errors with that.

1. PapaNachos
I'm glad you enjoyed it and had a chance to learn from it. For some reason this one just made me really grumpy

I'm glad you enjoyed it and had a chance to learn from it. For some reason this one just made me really grumpy

2. 
DataWraith
(edited )
Day 15 (Rust) After yesterday's twisted path of debugging, today was very straightforward and fun. Imports use pathfinding::prelude::dijkstra; use aoc2021::grid::Grid; use...

Day 15 (Rust)

After yesterday's twisted path of debugging, today was very straightforward and fun.

Imports
use pathfinding::prelude::dijkstra;

use aoc2021::grid::Grid;
use aoc2021::position::Pos2D;

This uses the pathfinding crate and two structs I've extracted from previous problems, a (x, y)-Position and a Grid (a simple wrapper around ndarray).

You could consider using the crate for pathfinding cheating, but if a library exists, why not use it? I've written plenty of pathfinders in my life, so I don't feel bad about skipping this one.

Interestingly, it turns out that Dijkstra works faster here than A* or Fringe search, both of which use a heuristic to guide the search and should in theory be faster.

Parsing

Again, re-used from day 9.

mod parse {
use nom::{
character::complete::{digit1, line_ending},
combinator::eof,
multi::many1,
IResult,
};

use super::Grid;

fn row(input: &str) -> IResult<&str, Vec<u8>> {
let (input, row) = digit1(input)?;
let (input, _) = line_ending(input)?;

let row = row.chars().map(|c| c as u8 - b'0').collect();

Ok((input, row))
}

pub fn grid(input: &str) -> IResult<&str, Grid<u8>> {
let (input, rows) = many1(row)(input)?;
let (input, _) = eof(input)?;

let height = rows.len();
let width = rows.len();

let grid = Grid::new(width, height, rows);

Ok((input, grid))
}
}

Helper functions
fn find_path(g: &Grid<u8>, start: Pos2D, end: Pos2D) -> Option<(Vec<Pos2D>, usize)> {
// returns neighbors and their cost
let successors = |pos: &Pos2D| {
pos.von_neumann_neighborhood()
.iter()
.filter(|&p| g.in_bounds(*p))
.map(|p| (*p, g[*p] as usize))
.collect::<Vec<(Pos2D, usize)>>()
};

let goal = |pos: &Pos2D| *pos == end;

dijkstra(&start, successors, goal)
}

fn enlarge_grid(g: &Grid<u8>) -> Grid<u8> {
let inc_val = |x: u8, inc: u8| {
let increased = x + inc;

if increased > 9 {
increased - 9
} else {
increased
}
};

let mut result = Grid::new(
g.width() * 5,
g.height() * 5,
vec![vec![0u8; g.width() * 5]; g.height() * 5],
);

for y in 0..g.height() {
for x in 0..g.width() {
let orig = Pos2D { x, y };
let level = g[orig];

for oy in 0..5 {
for ox in 0..5 {
let p = Pos2D {
x: x + ox * g.width(),
y: y + oy * g.height(),
};

let inc = ox + oy;
result[p] = inc_val(level, inc as u8);
}
}
}
}

return result;
}

Solving
fn part1(parsed: &Grid<u8>) -> usize {
let path = find_path(
&parsed,
Pos2D { x: 0, y: 0 },
Pos2D {
x: parsed.width() - 1,
y: parsed.height() - 1,
},
);

path.unwrap().1
}

fn part2(parsed: &Grid<u8>) -> usize {
let enlarged = enlarge_grid(parsed);

let path = find_path(
&enlarged,
Pos2D { x: 0, y: 0 },
Pos2D {
x: enlarged.width() - 1,
y: enlarged.height() - 1,
},
);

path.unwrap().1
}

fn main() {
let input = include_str!("../../input-15.txt");

let parsed = parse::grid(input).unwrap().1;

println!("Part I:  {}", part1(&parsed));
println!("Part II: {}", part2(&parsed));
}

 Bonus

Made my own Dijkstra-Algorithm after all. The only problem I had was that BinaryHeap is a max-heap, not a min-heap, so that caused some head scratching.
It takes 30ms more than the one from the pathfinding crate, for a total of 100ms.

#[derive(Eq, PartialEq, Debug)]
struct Node {
pos: Pos2D,
cost: usize,
}

impl PartialOrd for Node {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
other.cost.partial_cmp(&self.cost)
}
}

impl Ord for Node {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
other.cost.cmp(&self.cost)
}
}

fn dijkstra_cost(start: &Pos2D, goal: &Pos2D, g: &Grid<u8>) -> usize {
let successors = |pos: &Pos2D| {
pos.von_neumann_neighborhood()
.iter()
.filter(|&p| g.in_bounds(*p))
.map(|p| (*p, g[*p] as usize))
.collect::<Vec<(Pos2D, usize)>>()
};

let mut explored: HashSet<Pos2D> = HashSet::new();
let mut frontier = BinaryHeap::new();

explored.insert(*start);

frontier.push(Node {
pos: start.clone(),
cost: 0,
});

while let Some(cur) = frontier.pop() {
if cur.pos == *goal {
return cur.cost;
}

for (n, nc) in successors(&cur.pos) {

frontier.push(Node {
pos: n,
cost: cur.cost + nc,
});

explored.insert(n);
}
}
}

unreachable!()
}

1. kari
Another thing you can do to make a min-heap in Rust is make it of type BinaryHeap<Reverse<your dat>> and then push like heap.push(Reverse(data)) and do the same when popping. With something like...

Another thing you can do to make a min-heap in Rust is make it of type BinaryHeap<Reverse<your dat>> and then push like heap.push(Reverse(data)) and do the same when popping. With something like this where you have to implement Ord on your own anyways it's definitely easier to just do that backwards like you did

3. 
bhrgunatha
(edited )
Data Structure I chose a 2d matrix since the problem has fixed dimensions that are small (500 x 500 for part 2.) (define (read-risks input) (max-ord (length input)) (for/vector ([l input])...
Data Structure

I chose a 2d matrix since the problem has fixed dimensions that are small (500 x 500 for part 2.)

(max-ord (length input))
(for/vector ([l input])
(for/vector ([c (in-string l)])
(string->number (string c)))))

Part 1

Is it cheating that I wrote my own little library of graph search algorithms in 2016?
I always regret reaching for it because it's slooooooooooooow, it eats memory and I always make
mistakes writing the functions needed to use it.
Still it has classic A* and I used a manhattan distance heuristic - not great, not terrible.

To use it I have a struct problem that holds:

• The start state - in this case just the starting co-ordinate.
• A procedure from current state -> list of successor items. Each item returned has:
• A valid next state.
• The action need to get from current state to next state.
• The cost to get from current state to next state.
• A procedure from current state -> boolean which is true when you reach the goal.

bfs, dfs, dijkstra and A* all use this struct to do their thing.
They all return a list of 3 items:

• The total cost
• The list of states visited
• The path taken

To avoid having to pass round the risks and it's dimension/s I abuse
Racket's parameters.
They provide dynamic (runtime) binding.
(define v (make-parameter "This string could be <ANY OBJECT>"))
creates a parameter v which is a procedure that returns the value.

(v) - returns "This string could be <ANY OBJECT>"

You can reset the value by calling it with an argument
(v 7)
Further calls to (v) thereafter return this new value.
(v) - returns 7.

(define max-dim (make-parameter #f))
(define risks (make-parameter #f))

(define (part-01 input)
(risks R)
(define end (list 0 0))
(define start (list (sub1 (max-dim))
(sub1 (max-dim))))
(define P (problem start neighbours (final-cave? end)))
(first (A* P manhattan)))

(define (neighbours P)
(define ds '(((1 0) R) ((-1 0) L) ((0 1) D) ((0 -1) U)))
(define R (risks))
(for*/list ([d (in-list ds)]
[P+ (in-value (point+ (first d) P))]
#:when (in-bounds? P+))
(define cost+ (risk-ref R P+))
(list P+ (second d) cost+)))

(define ((final-cave? target) S)
(equal? S target))

I need a few small procedures to help

(define (manhattan S)
(+ (first S) (second S)))

(define (in-bounds? P)
(define limit (max-dim))
(and (< -1 (first P) limit)
(< -1 (second P) limit)))

(define (point+ p1 p2)
(list (+ (first p1) (first p2))
(+ (second p1) (second p2))))

(define (risk-ref R P)
(vector-ref (vector-ref R (second P))
(first P)))

Part 2

I need to extend the risks with the extra tiles and then basically do the same.

(define (part-02 input)
(define end (list (sub1 (max-dim))
(sub1 (max-dim))))
(define start (list 0 0))
(define P (problem start neighbours (final-cave? end)))
(first (A* P manhattan)))

(define (extend C)
(define m (max-dim))
(define m+ (* 5 m))
(max-dim m+)
(for/vector ([y (in-range m+)])
(for/vector ([x (in-range m+)])
(define delta (+ (quotient x m)
(quotient y m)))
(define v (+ delta
(risk-ref C (list (remainder x m)
(remainder y m)))))
(if (> v 9) (- v 9) v))))

I little fed-up of these problems try and trip you up and trick you e.g.
by switching the start and end of the path searched between parts 1 and 2.

You could argue that it represents real world problem solving, like when
What does that achieve in terms of making an enjoyable puzzle?

For me the answer is: Literaly nothing.

You've already forced us to do the fussy work of replicating the cave with a rule
to change the values.

I also get a bit fed-up with all the intricate little gotchas. Like:

• ... after revealing the sum, the code that produced it is reversed, unless the elfs's sleigh number is
divisilbe by the fifth prime greater than the highest common factor of the 2 previous results
that included a capital letter missing from it's position in the palidrome of the next day's
secret offset by the index of the previous capital letter.

Still it's a small gripe considering the amount of effort that goes into creating and hosting this every year. I feel a mean and petty mentioning them but I think it's better to get it off your chest than let it fester.

The horror of search

All the different search procedures are wrappers for this brutish beast

(define (graph-search P open-set)
(match-define (fringe items push! pop! empty?) open-set)
(match-define (problem start successors goal?) P)
(define C (make-closed))
(push! items (search-node 0 0 start 'START null))
(let scan-fringe ()
(cond [(empty? items) null]
[else (define current (pop! items))
(match-define (search-node _ total-cost state a _) current)
(cond [(goal? state) (make-path current)]
[(in-closed? C state) (scan-fringe)]
(for ([next (in-list (successors state))]
#:unless (in-closed? C (first next)))
(match-define (list state action cost) next)
(define next-cost (+ total-cost cost))
(push! items (search-node next-cost next-cost state action current)))
(scan-fringe)])])))

Internal data structures.

; fringe holds a collection of search-node s to explore
; Operations:
; push!  : items -> (void)
; pop!   : items -> search-node
; empty? : items -> boolean
(struct fringe ((items #:mutable) push! pop! empty?))

; search-node holds:
; estimate : for use in dijkstra and A*
; cost     : total cost of the path to this node from the start state
; state    : user-defined
; action   : how you got from the previous node
; previous : search node that led to this node
(struct search-node ((estimate #:mutable) cost state action previous) #:transparent)

Yeah it eats memory and takes a long time and while it was fun writing I'm a bit embarrassed by its sluggish, bloated behaviour.

1. 
DataWraith
Interesting. I was wondering why you switched start and end around in your code when reading through it. With all the negative sentiment here, it feels like I did a completely different puzzle --...

I little fed-up of these problems try and trip you up and trick you e.g.
by switching the start and end of the path searched between parts 1 and 2.

Interesting. I was wondering why you switched start and end around in your code when reading through it. With all the negative sentiment here, it feels like I did a completely different puzzle -- my puzzle description emphasizes for both paths that they start at the top left and go to the bottom-right, for example. I suppose the odds for that are 1:4 if they randomize it.

1. 
bhrgunatha
Well now I'm, confused. It states top-left to bottom-right for BOTH parts. No idea why I thought part 1 was bottom-right to top-left. When I was solving part 2, I got a different answers for the...

Well now I'm, confused. It states top-left to bottom-right for BOTH parts. No idea why I thought part 1 was bottom-right to top-left.

When I was solving part 2, I got a different answers for the test input. I swapped start and end got the right answer. At the time I wondered how it cold possibly be different but shrugged it off. I mean it can't be different, so I must have had some other bug in there.

1. 
DataWraith
Potential spoiler The start location matters because it is not counted towards the total path cost. In the example input, both top-left and bottom-right are '1', so it doesn't actually matter for...

I mean it can't be different

Potential spoiler

The start location matters because it is not counted towards the total path cost. In the example input, both top-left and bottom-right are '1', so it doesn't actually matter for part 1. Part two has '1' and '9' in the example input, so there it matters where you start.

1. bhrgunatha
Now I feel stupid. But thanks for explaining what I failed see.

Now I feel stupid.

But thanks for explaining what I failed see.

4. Bauke
I decided to use the pathfinding crate because I didn't want to figure all that out myself, so today's puzzle for me was mostly figuring out how I need to set everything up to use the A*...

I decided to use the pathfinding crate because I didn't want to figure all that out myself, so today's puzzle for me was mostly figuring out how I need to set everything up to use the A* implementation. Thankfully they have excellent documentation.

Runtime
Day 15 Part 1: 386
Day 15 Part 2: 2806
- Runtime: 157.77425ms

Imports and setup
use std::collections::HashMap;

use color_eyre::{eyre::eyre, Result};
use pathfinding::prelude::{absdiff, astar};

pub fn solve() -> Result<()> {
let input_data = include_str!("../../data/day_15.txt").trim();
println!("Day 15 Part 1: {}", part_1(input_data)?);
println!("Day 15 Part 2: {}", part_2(input_data)?);
Ok(())
}

Setting up the grid and pathfinding

This code is almost verbatim the example from the documentation.

type Grid = HashMap<Coordinate, isize>;

#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
struct Coordinate(isize, isize);

impl Coordinate {
fn distance(&self, target: &Coordinate) -> isize {
absdiff(self.0, target.0) + absdiff(self.1, target.1)
}

fn successors(&self, grid: &Grid) -> Vec<(Coordinate, isize)> {
let &Coordinate(x, y) = self;
let mut successors = vec![];

for coordinate in [
Coordinate(x, y - 1), // Up
Coordinate(x - 1, y), // Left
Coordinate(x, y + 1), // Down
Coordinate(x + 1, y), // Right
] {
if let Some(value) = grid.get(&coordinate) {
successors.push((coordinate, *value));
}
}

successors
}
}

Parsing the grid
fn parse(input: &str) -> Result<(Grid, Coordinate)> {
let mut grid = Grid::new();
let mut end = Coordinate(0, 0);

for (y, line) in input.lines().enumerate() {
let y = (y + 1).try_into()?;

for (x, character) in line.char_indices() {
let x = (x + 1).try_into()?;
grid.insert(Coordinate(x, y), character.to_string().parse()?);

if end.0 < x && end.1 < y {
end = Coordinate(x, y);
}
}
}

Ok((grid, end))
}

fn enlarge_grid(grid: Grid, end: Coordinate) -> (Grid, Coordinate) {
let Coordinate(width, height) = end;
let mut larger_grid = grid.clone();

for (Coordinate(x, y), risk) in grid {
for step_x in 0..5 {
for step_y in 0..5 {
let risk = match (risk + step_x + step_y) % 9 {
0 => 9,
n => n,
};
let x = x + (width * step_x);
let y = y + (height * step_y);
larger_grid.insert(Coordinate(x, y), risk);
}
}
}

(larger_grid, Coordinate(width * 5, height * 5))
}

Solving both parts
fn run(grid: Grid, end: Coordinate) -> Result<isize> {
Ok(
astar(
&Coordinate(1, 1),
|p| p.successors(&grid),
|p| p.distance(&end),
|p| p == &end,
)
.ok_or_else(|| eyre!("No path found"))?
.1,
)
}

fn part_1(input: &str) -> Result<isize> {
let (grid, end) = parse(input)?;
run(grid, end)
}

fn part_2(input: &str) -> Result<isize> {
let (grid, end) = parse(input)?;
let (grid, end) = enlarge_grid(grid, end);
run(grid, end)
}

5. wycy
(edited )
Rust Later I think I need to switch this to a priority_queue. This takes a whole minute for part 2 with a regular VecDeque. Edit: Switched to a BinaryHeap, now it's fast Rust use std::env; use...

Rust

Later I think I need to switch this to a priority_queue. This takes a whole minute for part 2 with a regular VecDeque.

Edit: Switched to a BinaryHeap, now it's fast

Rust
use std::env;
use std::fs::File;
use std::collections::{HashMap,HashSet};

use std::collections::BinaryHeap;
use std::cmp::Ordering;

use point2d::point2d::Point2D;

const MAP_MULTIPLIER: i64 = 5;

#[derive(PartialEq,Eq)]
struct Path {
pt: Point2D,
cost: i64,
}
impl Ord for Path {
fn cmp(&self, other: &Self) -> Ordering {
other.cost.cmp(&self.cost)
}
}
impl PartialOrd for Path {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(other.cost.cmp(&self.cost))
}
}

fn neighbor_addresses(pt: &Point2D) -> Vec<Point2D> {
vec![Point2D { x: pt.x  , y: pt.y-1 },  // up
Point2D { x: pt.x+1, y: pt.y   },  // right
Point2D { x: pt.x  , y: pt.y+1 },  // down
Point2D { x: pt.x-1, y: pt.y   }] // left
}

fn map_extents(map: &HashMap<Point2D,i64>) -> (i64,i64,i64,i64) {
let xmin = &map.keys().map(|&pt| pt.x).min().unwrap();
let ymin = &map.keys().map(|&pt| pt.y).min().unwrap();
let xmax = &map.keys().map(|&pt| pt.x).max().unwrap();
let ymax = &map.keys().map(|&pt| pt.y).max().unwrap();
(*xmin,*ymin,*xmax,*ymax)
}

fn least_risky(map: &HashMap<Point2D,i64>) -> i64 {
// Prepare
let (xmin,ymin,xmax,ymax) = map_extents(&map);
let mut visited: HashSet<Point2D> = HashSet::new();

// Explore
let mut heap: BinaryHeap<Path> = BinaryHeap::new();
let start = Point2D { x: xmin, y: ymin };
let end = Point2D { x: xmax, y: ymax };
heap.push(Path{pt: start, cost: 0});
while heap.len() > 0 {

let path = heap.pop().unwrap();
let (now,current_risk) = (path.pt, path.cost);

'n_loop: for neighbor in neighbor_addresses(&now) {

match visited.get(&neighbor) {
Some(_) => { continue 'n_loop; },
None => {},
}
visited.insert(neighbor);

// Determine risk level
let new_risk = match map.get(&neighbor) {
Some(this_risk) => current_risk+this_risk,
None => { continue 'n_loop; }, // off the map
};

// Found the end
if neighbor == end {
return new_risk;
}
heap.push(Path{pt: neighbor, cost: new_risk});
}
}
i64::MAX
}

fn solve(input: &str) -> io::Result<()> {

// Input
let input: Vec<String> = match reader.lines().collect() {
Err(err) => panic!("Unknown error reading input: {}", err),
Ok(result) => result,
};

// Build map (part 1)
let mut risk_map: HashMap<Point2D,i64> = HashMap::new();
for (y,line) in input.iter().enumerate() {
for (x,risk) in line.chars().enumerate() {
let pt = Point2D { x: x as i64, y: y as i64 };
risk_map.insert(pt, risk.to_digit(10).unwrap().try_into().unwrap());
}
}

// Build map (part 2)
let mut risk_map2 = risk_map.clone();
let (xmin,ymin,xmax,ymax) = map_extents(&risk_map2);
for y in ymin..(ymax+1)*MAP_MULTIPLIER {
for x in xmin..(xmax+1)*MAP_MULTIPLIER {
let pt = &Point2D{x: x, y: y};
match risk_map2.get(pt) {
Some(_) => {}, // Already populated
None => {
// New point
let ref_pt = if y <= ymax {
Point2D { x: x-xmax-1, y: y }  // Reference left
} else {
Point2D { x: x , y: y-ymax-1 } // Reference up
};
let new_value = match risk_map2.get(&ref_pt) {
Some(z @ 1..=8) => z + 1,
Some(9) => 1,
Some(_) | None => unreachable!(),
};
risk_map2.insert(*pt,new_value);
},
}
}
}

let part1 = least_risky(&risk_map.clone());
println!("Part 1: {}", part1); // 537

let part2 = least_risky(&risk_map2.clone());
println!("Part 2: {}", part2); // 2881
Ok(())
}

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

6. asterisk
(edited )
Python from queue import PriorityQueue from collections import defaultdict def plus_form_sides(_y, _x, y_len, x_len): for side_y, side_x in ((1, 0), (-1, 0), (0, 1), (0, -1)): y, x = (_y + side_y,...
Python
from queue import PriorityQueue
from collections import defaultdict

def plus_form_sides(_y, _x, y_len, x_len):
for side_y, side_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):
y, x = (_y + side_y, _x + side_x)
if 0 <= y < y_len and 0 <= x < x_len:
yield (y, x)

# Updated from:
# https://stackabuse.com/dijkstras-algorithm-in-python
def dijkstra(graf: list) -> int:
y_len, x_len = len(graf), len(graf)
visited = set()

start_vertex = (0, 0)
stop_vertex = (y_len - 1, x_len - 1)

min_distances = defaultdict(lambda: float("inf"))
min_distances[start_vertex] = 0

pq = PriorityQueue()
pq.put((0, start_vertex))

while not pq.empty():
distance, current_vertex = pq.get()

if current_vertex == stop_vertex:
return distance

if current_vertex in visited:
continue

for y, x in plus_form_sides(*current_vertex, y_len, x_len):
if (y, x) in visited:
continue

new_distance = distance + graf[y][x]

if new_distance < min_distances[(y, x)]:
min_distances[(y, x)] = new_distance
pq.put((new_distance, (y, x)))

return float("inf")

cavern = [list(map(int, list(line))) for line in open("input.txt").read().splitlines()]

print("Part One:", dijkstra(cavern))

blocks = [[[v + s if v + s < 10 else v + s - 9 for v in row] for row in cavern] for s in range(9)]
y_len, x_len = len(blocks), len(blocks)

cavern = list()
larger = 5

for s in range(larger):
for x in range(x_len):
row = list()
for y in range(larger):
row.extend(blocks[y + s if y + s < y_len else y + s - y_len][x])
cavern.append(row)

print("Part Two:", dijkstra(cavern))

time python3 main.py
python3 main.py  6,05s user 0,14s system

7. Crestwave
(edited )
\$ time mawk -f b.awk input >ans2 real 371m55.120s user371m11.889s sys 0m0.150s Welp, this is the first problem I didn't like this year. It felt a bit bland how the problem is just a bog-standard...
\$ time mawk -f b.awk input >ans2

real 	371m55.120s
user	371m11.889s
sys  	0m0.150s

Welp, this is the first problem I didn't like this year. It felt a bit bland how the problem is just a bog-standard pathfinding problem solved by bog-standard Dijkstra's with no changes whatsoever. I did like part 2's extension, but the run-time to solve it was a bit annoying, to say the least.

Part 1
#!/usr/bin/awk -f
function walk(ox, oy) {
v = x + ox SUBSEP y + oy

if (! Q[v])
return

alt = dist[u] + grid[v]

if (alt < dist[v]) {
dist[v] = alt
prev[v] = u
}
}

BEGIN { FS = "" }

{
for (x = 1; x <= NF; ++x)
grid[x, NR] = \$x
}

END {
source = 1 SUBSEP 1
target = NF SUBSEP NR

for (v in grid) {
dist[v] = 999999
prev[v] = 0
Q[v] = ++p
}

dist[source] = 0

while (p > 0) {
min = 999999

for (v in Q) {
if (dist[v] < min && Q[v]) {
u = v
min = dist[v]
}
}

delete Q[u]
p -= 1

if (u == target)
break

split(u, xy, SUBSEP)
x = xy
y = xy

walk(-1, 0)
walk(1, 0)
walk(0, -1)
walk(0, 1)
}

u = target

if (prev[u] != "" || u == source) {
while (u != "") {
total += grid[u]
u = prev[u]
}
}

print total - grid[source]
}

Part 2
#!/usr/bin/awk -f
function walk(ox, oy) {
v = x + ox SUBSEP y + oy

if (! Q[v])
return

alt = dist[u] + grid[v]

if (alt < dist[v]) {
dist[v] = alt
prev[v] = u
}
}

BEGIN { FS = "" }

{
for (x = 1; x <= NF; ++x)
grid[x, NR] = \$x
}

END {
for (v in grid) {
split(v, xy, SUBSEP)
x = xy
y = xy

for (i = 1; i <= 4; ++i) {
for (j = 1; j <= 4; ++j) {
_x = x + (NF * i)
_y = y + (NR * j)

if ((grid[x, y] + i + j) > 9)
grid[_x, _y] = (grid[x, y] + i + j) % 9
else
grid[_x, _y] = (grid[x, y] + i + j)

if ((grid[x, y] + i) > 9)
grid[_x, y] = (grid[x, y] + i) % 9
else
grid[_x, y] = grid[x, y] + i

if ((grid[x, y] + j) > 9)
grid[x, _y] = (grid[x, y] + j) % 9
else
grid[x, _y] = grid[x, y] + j
}
}
}

NR *= 5
NF *= 5

source = 1 SUBSEP 1
target = NF SUBSEP NR

for (v in grid) {
dist[v] = 999999
prev[v] = 0
Q[v] = ++p
}

dist[source] = 0

while (p > 0) {
min = 999999

for (v in Q) {
if (dist[v] < min && Q[v]) {
u = v
min = dist[v]
}
}

delete Q[u]
p -= 1

if (u == target)
break

split(u, xy, SUBSEP)
x = xy
y = xy

walk(-1, 0)
walk(1, 0)
walk(0, -1)
walk(0, 1)
}

u = target

if (prev[u] != "" || u == source) {
while (u != "") {
total += grid[u]
u = prev[u]
}
}

print total - grid[source]
}

8. jzimbel
Elixir It terminates, it passes the provided test cases and gives the correct answer for part 1, but it apparently gives an incorrect (too low) answer for my real part 2 input. I'm stumped. I was...

Elixir

It terminates, it passes the provided test cases and gives the correct answer for part 1, but it apparently gives an incorrect (too low) answer for my real part 2 input. I'm stumped.

I was not interested in writing an efficient Dijkstra's algorithm implementation since I've already done that at least once in college, so I grabbed a libgraph library that does it for me. It's possible that the bug lies somewhere within that library, idk.

Really not a fan of this puzzle.

Part 1 and (buggy, I guess?) part 2
alias Graph

def part1(input) do
input
|> CharGrid.from_input()
|> make_numeric()
|> shortest_path_weight()
end

def part2(input) do
input
|> CharGrid.from_input()
|> make_numeric()
|> embiggen()
|> shortest_path_weight()
end

defp shortest_path_weight(grid) do
grid
|> build_graph()
|> Graph.dijkstra({0, 0}, {grid.width - 1, grid.height - 1})
|> Enum.drop(1)
|> Enum.map(&CharGrid.at(grid, &1))
|> Enum.sum()
end

defp build_graph(grid) do
Graph.new()
Stream.flat_map(grid.grid, fn {coords, _} ->
grid
|> Enum.map(fn {neighbor_coords, neighbor_value} ->
{coords, neighbor_coords, weight: neighbor_value}
end)
end)
)
end

defp embiggen(grid) do
grid
|> CharGrid.to_list()
|> Stream.flat_map(fn {{x, y}, value} ->
for x_offset <- 0..4,
y_offset <- 0..4 do
{
{x + grid.width * x_offset, y + grid.height * y_offset},
rem(value + x_offset + y_offset - 1, 9) + 1
}
end
end)
|> then(&%CharGrid{
grid: Enum.into(&1, %{}),
width: grid.width * 5,
height: grid.height * 5
})
end

defp make_numeric(grid) do
CharGrid.map(grid, fn {_, char_value} -> char_value - ?0 end)
end
end

1 vote
9. Gyrfalcon
I am in a similar boat to @jzimbel for my solution for this problem. No matter what I try, I get a too high result from part 2 with the actual input, even though it is dead on for the test input....

I am in a similar boat to @jzimbel for my solution for this problem. No matter what I try, I get a too high result from part 2 with the actual input, even though it is dead on for the test input. I went with an algorithm I remembered from the one time I was taught robotics, apparently called a wavefront expansion algorithm, though I implemented it completely without queues and just created a mirror map with the costs. Run time is fine, ~210 ms with a debug build, but I can see why it would need to be optimized for a bigger problem. I actually don't mind the path finding problem per se, but I really hate when part 2 (apparently) introduces a bug, but with no additional test data for sussing it out. If anyone has their input data I would be interested in trying it out.

Part 1 and buggy Part 2
import std/[strformat, strutils, sugar, os]

proc parseInput(inputFile: string): seq[seq[int]] =
var input = collect(newSeq):
for line in inputFile.lines: line

for line in input:
var convertedLine: seq[int]
for character in line:

func makeMap(grid: seq[seq[int]]): seq[seq[int]] =
result = newSeq[seq[int]](grid.len)
for idx in 0 ..< grid.len:
result[idx] = newSeq[int](grid[idx].len)

result[^1][^1] = grid[^1][^1]
for cornerIdx in countdown(grid.len - 2, 0, 1):
result[^1][cornerIdx] = result[^1][cornerIdx + 1] + grid[^1][cornerIdx]
result[cornerIdx][^1] = result[cornerIdx + 1][^1] + grid[cornerIdx][^1]

for vertIdx in countdown(grid.len - 2, cornerIdx + 1, 1):
result[vertIdx][cornerIdx] = grid[vertIdx][cornerIdx] +
min(result[vertIdx + 1][cornerIdx],
result[vertIdx][cornerIdx + 1])

for horizIdx in countdown(grid.len - 2, cornerIdx + 1, 1):
result[cornerIdx][horizIdx] = grid[cornerIdx][horizIdx] +
min(result[cornerIdx + 1][horizIdx],
result[cornerIdx][horizIdx + 1])

result[cornerIdx][cornerIdx] = grid[cornerIdx][cornerIdx] +
min(result[cornerIdx + 1][cornerIdx],
result[cornerIdx][cornerIdx + 1])

# Debugging
proc printGrid(grid: seq[seq[int]]) =
for row in grid:
var printRow: string
for num in row:
printRow = printRow & &"{num} "
echo printRow

func wrapAround(input, limit: int): int =
result = input
while result > limit:
result = result - limit

func enlargeMap(grid: seq[seq[int]]): seq[seq[int]] =
result = newSeq[seq[int]](grid.len * 5)
for idx in 0 ..< result.len:
result[idx] = newSeq[int](grid.len * 5)

for xQuad in 0 .. 4:
let xOffset = xQuad * grid.len
for yQuad in 0 .. 4:
let yOffset = yQuad * grid.len

for xdx in 0 ..< grid.len:
for ydx in 0 ..< grid.len:
result[ydx + yOffset][xdx + xOffset] = wrapAround(grid[ydx][xdx] + yQuad + xQuad, 9)

proc main(inputFile: string) =
let baseGrid = parseInput(inputFile)
let mapGrid = makeMap(baseGrid)
echo mapGrid - baseGrid

# This gives a too high result with my input,
# but not the example, can't figure out why
let bigGrid = enlargeMap(baseGrid)
let bigMap = makeMap(bigGrid)
echo bigMap - bigGrid

when is_main_module:
main(paramStr(1))

1 vote