Day 15: Chiton

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[0].keys()))-1)

bounds_x = len(list(grid.keys()))
bounds_y = len(list(grid[0].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[0] + direction[0]
        nearby_y = checking[1] + direction[1]
        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])

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[0].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[0].keys()))-1)

bounds_x = len(list(supergrid.keys()))
bounds_y = len(list(supergrid[0].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[0] + direction[0]
        nearby_y = checking[1] + direction[1]
        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.

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.

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[0].len();

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

        Ok((input, grid))
    }
}

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;
}

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));
}

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) {
            let already_explored = explored.contains(&n);

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

                explored.insert(n);
            }
        }
    }

    unreachable!()
}

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])
    (for/vector ([c (in-string l)])
      (string->number (string c)))))

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)
  (define R (read-risks 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)))

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

(define (part-02 input)
  (risks (extend (read-risks 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
your clients completely change their minds, but to that I'd ask:
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.

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)]
                      [else (add-closed! C state)
                            (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.

use std::env;
use std::io::{self, prelude::*, BufReader};
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) {

            // Check already visited
            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<()> {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);

    // 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[1];
    solve(&filename).unwrap();
}

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[0])
    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

        visited.add(current_vertex)

        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[0])

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

Added time:

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

#!/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[1]
		y = xy[2]

		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]
}

#!/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[1]
		y = xy[2]

		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[1]
		y = xy[2]

		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]
}

defmodule AdventOfCode.Solution.Year2021.Day15 do
  alias AdventOfCode.CharGrid
  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()
    |> Graph.add_edges(
      Stream.flat_map(grid.grid, fn {coords, _} ->
        grid
        |> CharGrid.adjacent_cells(coords, :cardinal)
        |> 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

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:
      convertedLine.add(parseInt("" & character))
    result.add(convertedLine)

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[0][0] - baseGrid[0][0]

  # 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[0][0] - bigGrid[0][0]


when is_main_module:
  main(paramStr(1))