🏡 2021/day15.nim

Day 15: Chiton

Today is about path search on a grid. I tend to struggle with these since I never properly studied the theory.

Part 1

We need to go from top left to bottom right minimizing sum of risk. My strategy will be to create from given grid a new grid that at every "node" (it usually pays to think of these problems in terms of graphs), will tell me the direction I should come from in order to minimize the risk and get there. The final path will be found by following directions from bottom right.

Here are the inputs:

let
  testInput = """
1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581"""
  puzzleInput = readFile("2021/input15.txt")

I will be using grid code from my Day09 (no blogpost published), copying and pasting here the useful bits (I will need to think of an ergonomic way to import from a notebook). I am also fine with having a sentinel value for stuff outside the grid that is a high value.

type
  Coord = tuple[x, y: int]
  Grid[T] = object
    data: seq[T]
    yLen, xLen: int
    sentinel: T  # value for outside the grid
  GridInt = Grid[int]
  Dir = enum
    right, down, left, up

func isOutside[T](c: Coord, g: Grid[T]): bool =
  c.x < 0 or c.x >= g.xLen or c.y < 0 or c.y >= g.yLen

func toIndex[T](g: Grid[T], c: Coord): int =
  if c.isOutside(g):
    -1
  else:
    c.y*g.xLen + c.x

func `[]`[T](g: Grid[T], c: Coord): T =
  let i = g.toIndex(c)
  if i < 0:
    g.sentinel
  else:
    g.data[i]

# added today
func `[]=`[T](g: var Grid[T], c: Coord, value: T) =
  let i = g.toIndex(c)
  if i >= 0:
    g.data[i] = value

func parseInt(c: char): int =
  result = ord(c) - ord('0')
  assert result >= 0 and result <= 9

func parse(text: string): GridInt =
  # result.data = newSeqOfCap(text.len)
  for line in text.strip.splitLines:
    result.data.add line.toSeq.map(parseInt)
    inc result.yLen
    if result.xLen == 0:
      result.xLen = line.len
    else:
      assert line.len == result.xLen
  result.sentinel = int.high

iterator coords[T](g: Grid[T]): Coord =
  for y in 0 ..< g.yLen:
    for x in 0 ..< g.xLen:
      yield (x, y)

func `+`(c: Coord, dir: Dir): Coord =
  case dir
  of right:
    (c.x + 1, c.y)
  of down:
    (c.x, c.y + 1)
  of left:
    (c.x - 1, c.y)
  of up:
    (c.x, c.y - 1)

Let's use it to parse inputs:

let
  testGrid = parse testInput
  puzzleGrid = parse puzzleInput
dump (testGrid.xlen, testGrid.ylen)
dump (puzzleGrid.xlen, puzzleGrid.ylen)
dump testGrid.sentinel
(testGrid.xlen, testGrid.ylen) = (10, 10)
(puzzleGrid.xlen, puzzleGrid.ylen) = (100, 100)
testGrid.sentinel = 9223372036854775807

I am not using a GridDiff (I did not copy related code), I will be using a GridRisk which will tell me minimal total risk up to here and best direction I should come from.

I will also use show functions to debug.

type
  Risk = tuple[risk: int, dir: Dir]
  GridRisk = Grid[Risk]

func show(g: GridInt): string =
  for c in g.coords:
    result.add $g[c]
    if c.x == g.xLen - 1:
      result.add '\n'

func show(g: GridRisk, paddingCount=4): string =
  for c in g.coords:
    if g[c].risk < g.sentinel.risk:
      result.add align($(g[c].risk), paddingCount)
    else:
      result.add align("*", paddingCount)
    if c.x == g.xLen - 1:
      result.add '\n'

echo show testGrid
1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581

Here is the heart of the problem. Key for this is realizing how to compute incrementally compute the risk.

func computeRisk(g: GridInt, gr: GridRisk, c: Coord): Risk =
  ## Computes Risk at Coord assuming Risk has been computed
  ## for cells on the left and above
  let
    riskUp = gr[c + up].risk + g[c]
    riskLeft = gr[c + left].risk + g[c]
  #debugEcho "computeRisk for c: ", c
  #debugEcho "  riskUp: ", riskUp
  #debugEcho "  riskLeft: ", riskLeft
  if riskUp <= riskLeft:
    (riskUp, up)
  else:
    (riskLeft, left)

func computeGridRisk(g: GridInt): GridRisk =
  result.xLen = g.xLen
  result.yLen = g.ylen
  result.sentinel = (g.sentinel - 10, up) # forgot this line on first try
  # need to do - 10 to avoid overflow
  result.data = @[(0, up)]  # risk for initial position does not count
  for c in g.coords:
    if c == (0, 0): continue
    result.data.add g.computeRisk(result, c)

func part1(gr: GridRisk): int =
  gr[(gr.xLen - 1, gr.yLen - 1)].risk

let
  testGridRisk = computeGridRisk testGrid
  puzzleGridRisk = computeGridRisk puzzleGrid

echo show testGridRisk

dump part1 testGridRisk
dump part1 puzzleGridRisk # 719 wrong, too high!
   0   1   7  10  17  22  23  30  34  36
   1   4  12  11  14  21  24  30  37  38
   3   4   7  13  18  19  20  23  25  33
   6  10  16  17  26  22  21  26  31  40
  13  14  20  20  24  23  28  27  28  29
  14  17  18  27  25  25  33  28  31  36
  15  18  23  32  34  26  28  32  33  34
  18  19  21  26  30  28  29  35  36  43
  19  21  30  29  30  31  37  40  38  39
  21  24  25  26  35  35  39  44  46  40

part1 testGridRisk = 40
part1 puzzleGridRisk = 719

I am stuck at the moment with a correct test result and an incorrect puzzle result. Not really sure how to debug.

... after looking at our discord aoc I got a useful hint (thanks @Michal58!), the example only gives a path where the solution only goes down and to the right and this was also my (wrong) assumption! It is indeed possible for a minimal solution to wiggle around all directions but my algorithm for sure is not going to find it.

So I really need to implement Dijkstra or A* algorithm!

But first let me give a minimal example that makes it clear why I need the better approach:

let
  hintInput = "19999\n19111\n11191"
  hintGrid = parse hintInput
  hintGridRisk = computeGridRisk hintGrid

echo show hintGrid, "\n", show hintGridRisk
19999
19111
11191

   0   9  18  27  36
   1  10  11  12  13
   2   3   4  13  14

... (a few hours later) back to writing the blogpost and writing my solution.

This morning I shared the hint on advent of code subreddit and it has been quite popular! The irony is that I have not yet taken advantage of the hint and finalized my solution 😁, so let's get to it.

I will implement Dijkstra's algorithm because it is simpler than A* (although in general less powerful) and also because of its compelling history (did you open last link on a chromium based browser? did you know what text-fragments are? I didn't but having seen some weird highlighted stuff after google results I got curious...).

I will still be using my GridRisk type although it seems not completely appropriate... The risk value will be the distance, I will try also to set the correct distance.

In the following implementation comments not in parenthesis are taken verbatim from wikipedia's description of the algorithm. An important change I make is to make sure I use a priority queue. Among the many Dijkstra implementations that have been written today, I dare say this must rank among the worst... "

import std / heapqueue  # (not among my standard aoc imports)

type
  Node = tuple[coord: Coord, risk: int]

proc `<`(a, b: Node): bool = a.risk < b.risk

iterator neighbours[T](g: Grid[T], c: Coord): (Coord, Dir) =
  for dir in Dir:
    if not (c + dir).isOutside(g):
     yield (c + dir, dir)

func dijkstra(g: GridInt): GridRisk =
  # (0. initialize result)
  result.xLen = g.xLen
  result.yLen = g.ylen
  result.sentinel = (g.sentinel, up)

  # 1. Mark all nodes unvisited. Create a set of all the unvisited nodes called the unvisited set.
  # (I will instead create a visited set)
  # (I will also create a priority queue for unvisited nodes, but I will start populating later)
  var
    visited = initHashSet[Coord]()
    unvisited = initHeapQueue[Node]()

  # 2. Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
  result.data = @[(0, up)]  # risk for initial position does not count
  for c in g.coords:
    if c == (0, 0): continue
    result.data.add @[result.sentinel]
  
  # 3. For the current node, consider all of its unvisited neighbors
  # and calculate their tentative distances through the current node.
  # Compare the newly calculated tentative distance to the current assigned value
  # and assign the smaller one
  var
    current = (0, 0)
    destination = (g.xLen - 1, g.yLen - 1)
    risk: int
  # 5. If the destination node has been marked visited then stop. The algorithm has finished.
  while destination not_in visited:
    for neighbour, dir in g.neighbours(current):
      if neighbour in visited:
        continue
      risk = result[current].risk + g[neighbour]
      if risk < result[neighbour].risk:
        result[neighbour] = (risk, dir)
        unvisited.push (neighbour, risk) # (push to queue)
    # 4. When we are done considering all of the unvisited neighbors of the current node,
    # mark the current node as visited and remove it from the unvisited set
    visited.incl current
    if current == destination: break # seems I need this (for puzzle input)

    # 6. Otherwise, select the unvisited node that is marked with the smallest tentative distance,
    # set it as the new current node, and go back to step 3.
    while current in visited: # (I think it may happen that I pull from queue stuff already visited)
      if len(unvisited) == 0:
        debugEcho "current: ", current
        raise ValueError.newException "whaaaat?"
      current = unvisited.pop().coord # (pull from queue)

echo show dijkstra(hintGrid)
echo "\n", show dijkstra(testGrid)
   0   9  14  15  16
   1  10   5   6   7
   2   3   4  13   8


   0   1   7  10  17  22  23  30  34  36
   1   4  12  11  14  21  23  29  32  34
   3   4   7  13  18  19  20  23  25  33
   6  10  16  17  26  22  21  26  31  38
  13  14  20  20  24  23  28  27  28  29
  14  17  18  27  25  25  33  28  31  36
  15  18  23  32  34  26  28  32  33  34
  18  19  21  26  30  28  29  35  36  43
  19  21  30  29  30  31  37  40  38  39
  21  24  25  26  35  35  39  44  46  40

results look good!

let puzzleGridDijkstra = dijkstra(puzzleGrid)
echo puzzleGridDijkstra.data[^1]
(risk: 717, dir: down)

That's the right answer! You are one gold star closer to saving your vacation.

Part 2

Now the map is bigger, and from what I hear around, the implementation with the priority queue might be key to have a working solution now.

Let's create the bigger maps and solve part 2:

func biggerMap(g: GridInt): GridInt =
  result.xLen = g.xLen*5
  result.yLen = g.yLen*5
  result.sentinel = g.sentinel
  result.data = newSeqWith(len=g.data.len*25): 0
  for coord in result.coords:
    let
      smallCoord = (coord.x mod g.xLen, coord.y mod g.yLen)
      oneUps = (coord.x div g.xLen) + (coord.y div g.yLen)
    result[coord] = (g[smallCoord] + oneUps - 1) mod 9 + 1

let
  testGridBigger = testGrid.biggerMap
  puzzleGridBigger = puzzleGrid.biggerMap
echo show testGridBigger
11637517422274862853338597396444961841755517295286
13813736722492484783351359589446246169155735727126
21365113283247622439435873354154698446526571955763
36949315694715142671582625378269373648937148475914
74634171118574528222968563933317967414442817852555
13191281372421239248353234135946434524615754563572
13599124212461123532357223464346833457545794456865
31254216394236532741534764385264587549637569865174
12931385212314249632342535174345364628545647573965
23119445813422155692453326671356443778246755488935
22748628533385973964449618417555172952866628316397
24924847833513595894462461691557357271266846838237
32476224394358733541546984465265719557637682166874
47151426715826253782693736489371484759148259586125
85745282229685639333179674144428178525553928963666
24212392483532341359464345246157545635726865674683
24611235323572234643468334575457944568656815567976
42365327415347643852645875496375698651748671976285
23142496323425351743453646285456475739656758684176
34221556924533266713564437782467554889357866599146
33859739644496184175551729528666283163977739427418
35135958944624616915573572712668468382377957949348
43587335415469844652657195576376821668748793277985
58262537826937364893714847591482595861259361697236
96856393331796741444281785255539289636664139174777
35323413594643452461575456357268656746837976785794
35722346434683345754579445686568155679767926678187
53476438526458754963756986517486719762859782187396
34253517434536462854564757396567586841767869795287
45332667135644377824675548893578665991468977611257
44961841755517295286662831639777394274188841538529
46246169155735727126684683823779579493488168151459
54698446526571955763768216687487932779859814388196
69373648937148475914825958612593616972361472718347
17967414442817852555392896366641391747775241285888
46434524615754563572686567468379767857948187896815
46833457545794456865681556797679266781878137789298
64587549637569865174867197628597821873961893298417
45364628545647573965675868417678697952878971816398
56443778246755488935786659914689776112579188722368
55172952866628316397773942741888415385299952649631
57357271266846838237795794934881681514599279262561
65719557637682166874879327798598143881961925499217
71484759148259586125936169723614727183472583829458
28178525553928963666413917477752412858886352396999
57545635726865674683797678579481878968159298917926
57944568656815567976792667818781377892989248891319
75698651748671976285978218739618932984172914319528
56475739656758684176786979528789718163989182927419
67554889357866599146897761125791887223681299833479

looks good, let's go for the prize:

let
  testGridBiggerDijkstra = testGridBigger.dijkstra
  puzzleGridBiggerDijkstra = puzzleGridBigger.dijkstra
echo "part2(test): ", testGridBiggerDijkstra.data[^1]
echo "part2(puzzle): ", puzzleGridBiggerDijkstra.data[^1]
part2(test): (risk: 315, dir: right)
part2(puzzle): (risk: 2993, dir: down)

That's the right answer! You are one gold star closer to saving your vacation.

import animu, nimib

nbInit(theme=useAdventOfNim)
nbText: """## Day 15: [Chiton](https://adventofcode.com/2021/day/15)

Today is about path search on a grid. I tend to struggle with these
since I never properly studied the theory.

### Part 1

We need to go from top left to bottom right minimizing sum of risk.
My strategy will be to create from given grid a new grid that
at every "node" (it usually pays to think of these problems in terms of graphs),
will tell me the direction I should come from in order to minimize the risk and
get there. The final path will be found by following directions from bottom right.

Here are the inputs:
"""
nbCode:
  let
    testInput = """
1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581"""
    puzzleInput = readFile("2021/input15.txt")
nbText: """I will be using grid code from my Day09 (no blogpost published),
copying and pasting here the useful bits (I will need to think of an ergonomic
way to import from a notebook). I am also fine with having a sentinel value
for stuff outside the grid that is a high value.
"""
nbCode:
  type
    Coord = tuple[x, y: int]
    Grid[T] = object
      data: seq[T]
      yLen, xLen: int
      sentinel: T  # value for outside the grid
    GridInt = Grid[int]
    Dir = enum
      right, down, left, up

  func isOutside[T](c: Coord, g: Grid[T]): bool =
    c.x < 0 or c.x >= g.xLen or c.y < 0 or c.y >= g.yLen

  func toIndex[T](g: Grid[T], c: Coord): int =
    if c.isOutside(g):
      -1
    else:
      c.y*g.xLen + c.x

  func `[]`[T](g: Grid[T], c: Coord): T =
    let i = g.toIndex(c)
    if i < 0:
      g.sentinel
    else:
      g.data[i]

  # added today
  func `[]=`[T](g: var Grid[T], c: Coord, value: T) =
    let i = g.toIndex(c)
    if i >= 0:
      g.data[i] = value

  func parseInt(c: char): int =
    result = ord(c) - ord('0')
    assert result >= 0 and result <= 9

  func parse(text: string): GridInt =
    # result.data = newSeqOfCap(text.len)
    for line in text.strip.splitLines:
      result.data.add line.toSeq.map(parseInt)
      inc result.yLen
      if result.xLen == 0:
        result.xLen = line.len
      else:
        assert line.len == result.xLen
    result.sentinel = int.high

  iterator coords[T](g: Grid[T]): Coord =
    for y in 0 ..< g.yLen:
      for x in 0 ..< g.xLen:
        yield (x, y)

  func `+`(c: Coord, dir: Dir): Coord =
    case dir
    of right:
      (c.x + 1, c.y)
    of down:
      (c.x, c.y + 1)
    of left:
      (c.x - 1, c.y)
    of up:
      (c.x, c.y - 1)
nbText: """
Let's use it to parse inputs:
"""
nbCode:
  let
    testGrid = parse testInput
    puzzleGrid = parse puzzleInput
  dump (testGrid.xlen, testGrid.ylen)
  dump (puzzleGrid.xlen, puzzleGrid.ylen)
  dump testGrid.sentinel
nbText: """
I am not using a `GridDiff` (I did not copy related code),
I will be using a `GridRisk` which will tell
me minimal total risk up to here and best direction I should come from.

I will also use show functions to debug.
"""
nbCode:
  type
    Risk = tuple[risk: int, dir: Dir]
    GridRisk = Grid[Risk]

  func show(g: GridInt): string =
    for c in g.coords:
      result.add $g[c]
      if c.x == g.xLen - 1:
        result.add '\n'

  func show(g: GridRisk, paddingCount=4): string =
    for c in g.coords:
      if g[c].risk < g.sentinel.risk:
        result.add align($(g[c].risk), paddingCount)
      else:
        result.add align("*", paddingCount)
      if c.x == g.xLen - 1:
        result.add '\n'

  echo show testGrid
nbText: """
Here is the heart of the problem. Key for this is realizing
how to compute incrementally compute the risk.
"""
nbCode:
  func computeRisk(g: GridInt, gr: GridRisk, c: Coord): Risk =
    ## Computes Risk at Coord assuming Risk has been computed
    ## for cells on the left and above
    let
      riskUp = gr[c + up].risk + g[c]
      riskLeft = gr[c + left].risk + g[c]
    #debugEcho "computeRisk for c: ", c
    #debugEcho "  riskUp: ", riskUp
    #debugEcho "  riskLeft: ", riskLeft
    if riskUp <= riskLeft:
      (riskUp, up)
    else:
      (riskLeft, left)

  func computeGridRisk(g: GridInt): GridRisk =
    result.xLen = g.xLen
    result.yLen = g.ylen
    result.sentinel = (g.sentinel - 10, up) # forgot this line on first try
    # need to do - 10 to avoid overflow
    result.data = @[(0, up)]  # risk for initial position does not count
    for c in g.coords:
      if c == (0, 0): continue
      result.data.add g.computeRisk(result, c)

  func part1(gr: GridRisk): int =
    gr[(gr.xLen - 1, gr.yLen - 1)].risk
  
  let
    testGridRisk = computeGridRisk testGrid
    puzzleGridRisk = computeGridRisk puzzleGrid

  echo show testGridRisk

  dump part1 testGridRisk
  dump part1 puzzleGridRisk # 719 wrong, too high!
nbText: """
I am stuck at the moment with _a correct test result and an incorrect
puzzle result_. Not really sure how to debug.

... after looking at our discord aoc I got a useful hint (thanks @Michal58!),
the example only gives a path where the solution only goes down and to the right
and this was also my (wrong) assumption! It is indeed possible
for a minimal solution to wiggle around all directions but
my algorithm for sure is not going to find it.

So I really need to implement [Dijkstra](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)
or [A*](https://en.wikipedia.org/wiki/A*_search_algorithm) algorithm!

But first let me give a minimal example that makes it clear why I need
the better approach:
"""
nbCode:
  let
    hintInput = "19999\n19111\n11191"
    hintGrid = parse hintInput
    hintGridRisk = computeGridRisk hintGrid
  
  echo show hintGrid, "\n", show hintGridRisk
nbText: """
... _(a few hours later) back to writing the blogpost and writing my solution_.

This morning I shared the hint on [advent of code subreddit](https://www.reddit.com/r/adventofcode/comments/rgszh7/2021_day_15_part_1_hint_if_you_get_correct_answer/)
and it has been quite popular! The irony is that I have not yet taken advantage of the hint and finalized my solution 😁, so let's get to it.

I will implement Dijkstra's algorithm because it is simpler than A* (although in general less powerful) and also because of its
[compelling history](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#History#:~:text=it%20was%20a%20twenty,pencil%20and%20paper)
(did you open last link on a chromium based browser? did you know what [text-fragments](https://web.dev/text-fragments/) are?
I didn't but having seen some weird highlighted stuff after google results I got curious...).

I will still be using my `GridRisk` type although it seems not completely appropriate...
The `risk` value will be the distance, I will try also to set the correct distance.

In the following implementation comments not in parenthesis are taken verbatim
from wikipedia's description of the algorithm. An important change I make
is to make sure I use a priority queue. Among the many Dijkstra implementations
that have been written today, I dare say this must rank among the worst...
""""
nbCode:
  import std / heapqueue  # (not among my standard aoc imports)

  type
    Node = tuple[coord: Coord, risk: int]

  proc `<`(a, b: Node): bool = a.risk < b.risk

  iterator neighbours[T](g: Grid[T], c: Coord): (Coord, Dir) =
    for dir in Dir:
      if not (c + dir).isOutside(g):
       yield (c + dir, dir)

  func dijkstra(g: GridInt): GridRisk =
    # (0. initialize result)
    result.xLen = g.xLen
    result.yLen = g.ylen
    result.sentinel = (g.sentinel, up)

    # 1. Mark all nodes unvisited. Create a set of all the unvisited nodes called the unvisited set.
    # (I will instead create a visited set)
    # (I will also create a priority queue for unvisited nodes, but I will start populating later)
    var
      visited = initHashSet[Coord]()
      unvisited = initHeapQueue[Node]()

    # 2. Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
    result.data = @[(0, up)]  # risk for initial position does not count
    for c in g.coords:
      if c == (0, 0): continue
      result.data.add @[result.sentinel]
    
    # 3. For the current node, consider all of its unvisited neighbors
    # and calculate their tentative distances through the current node.
    # Compare the newly calculated tentative distance to the current assigned value
    # and assign the smaller one
    var
      current = (0, 0)
      destination = (g.xLen - 1, g.yLen - 1)
      risk: int
    # 5. If the destination node has been marked visited then stop. The algorithm has finished.
    while destination not_in visited:
      for neighbour, dir in g.neighbours(current):
        if neighbour in visited:
          continue
        risk = result[current].risk + g[neighbour]
        if risk < result[neighbour].risk:
          result[neighbour] = (risk, dir)
          unvisited.push (neighbour, risk) # (push to queue)
      # 4. When we are done considering all of the unvisited neighbors of the current node,
      # mark the current node as visited and remove it from the unvisited set
      visited.incl current
      if current == destination: break # seems I need this (for puzzle input)

      # 6. Otherwise, select the unvisited node that is marked with the smallest tentative distance,
      # set it as the new current node, and go back to step 3.
      while current in visited: # (I think it may happen that I pull from queue stuff already visited)
        if len(unvisited) == 0:
          debugEcho "current: ", current
          raise ValueError.newException "whaaaat?"
        current = unvisited.pop().coord # (pull from queue)

  echo show dijkstra(hintGrid)
  echo "\n", show dijkstra(testGrid)
nbText: "results look good!"
nbCode:
  let puzzleGridDijkstra = dijkstra(puzzleGrid)
  echo puzzleGridDijkstra.data[^1]
gotTheStar
nbText: """
### Part 2

Now the map is bigger, and from what I hear around, the implementation
with the priority queue might be key to have a working solution now.

Let's create the bigger maps and solve part 2:
"""
nbCode:
  func biggerMap(g: GridInt): GridInt =
    result.xLen = g.xLen*5
    result.yLen = g.yLen*5
    result.sentinel = g.sentinel
    result.data = newSeqWith(len=g.data.len*25): 0
    for coord in result.coords:
      let
        smallCoord = (coord.x mod g.xLen, coord.y mod g.yLen)
        oneUps = (coord.x div g.xLen) + (coord.y div g.yLen)
      result[coord] = (g[smallCoord] + oneUps - 1) mod 9 + 1
  
  let
    testGridBigger = testGrid.biggerMap
    puzzleGridBigger = puzzleGrid.biggerMap
  echo show testGridBigger
nbText: "looks good, let's go for the prize:"
nbCode:
  let
    testGridBiggerDijkstra = testGridBigger.dijkstra
    puzzleGridBiggerDijkstra = puzzleGridBigger.dijkstra
  echo "part2(test): ", testGridBiggerDijkstra.data[^1]
  echo "part2(puzzle): ", puzzleGridBiggerDijkstra.data[^1]
gotTheStar
nbSave