12 votes

Day 15: Chiton

Today's problem description: https://adventofcode.com/2021/day/15

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
Your code here.
```

</details>

16 comments

  1. [3]
    PapaNachos
    (edited )
    Link
    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[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])
    
    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[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)
    
    Tips/Comments
    • 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.

    6 votes
    1. [2]
      wycy
      (edited )
      Link Parent
      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.

      3 votes
      1. PapaNachos
        Link Parent
        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

        3 votes
  2. [2]
    DataWraith
    (edited )
    Link
    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[0].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));
    }
    
    [Edit] 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) {
                let already_explored = explored.contains(&n);
    
                if !already_explored {
                    frontier.push(Node {
                        pos: n,
                        cost: cur.cost + nc,
                    });
    
                    explored.insert(n);
                }
            }
        }
    
        unreachable!()
    }
    
    3 votes
    1. kari
      Link Parent
      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 votes
  3. [5]
    bhrgunatha
    (edited )
    Link
    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.)

    (define (read-risks input)
      (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)
      (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)))
    
    Part 2

    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.

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

    3 votes
    1. [4]
      DataWraith
      Link Parent
      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.

      2 votes
      1. [3]
        bhrgunatha
        Link Parent
        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.

        2 votes
        1. [2]
          DataWraith
          Link Parent
          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.

          4 votes
          1. bhrgunatha
            Link Parent
            Now I feel stupid. But thanks for explaining what I failed see.

            Now I feel stupid.

            But thanks for explaining what I failed see.

            2 votes
  4. Bauke
    Link
    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)
    }
    
    3 votes
  5. wycy
    (edited )
    Link
    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::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();
    }
    
    2 votes
  6. asterisk
    (edited )
    Link
    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[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
    
    2 votes
  7. Crestwave
    (edited )
    Link
    $ 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[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]
    }
    
    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[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]
    }
    
    2 votes
  8. jzimbel
    Link
    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
    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
    
    1 vote
  9. Gyrfalcon
    Link
    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:
          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))
    
    1 vote