# Day 15: Chiton

By @anatoliykmetyuk

## Puzzle description

https://adventofcode.com/2021/day/15

## Problem

The problem in its essence is that of finding the least-costly path through a graph. This problem is solved by Dijkstra's algorithm, nicely explained in this Computerphile video.

## Domain Model

The two domain entities we are working with are the game map and an individual cell of that map. In presence of the game map, a cell is fully described by a pair of its coordinates.

`type Coord = (Int, Int)`

The game map contains all the cells from the challenge input. It also defines the neighbours of a given cell, which we need to know for Dijkstra's algorithm. Finally, it defines a function to get the cost of entering a given cell.

`class GameMap(cells: IndexedSeq[IndexedSeq[Int]]):`

val maxRow = cells.length - 1

val maxCol = cells.head.length - 1

def neighboursOf(c: Coord): List[Coord] =

val (row, col) = c

val lb = mutable.ListBuffer.empty[Coord]

if row < maxRow then lb.append((row+1, col))

if row > 0 then lb.append((row-1, col))

if col < maxCol then lb.append((row, col+1))

if col > 0 then lb.append((row, col-1))

lb.toList

def costOf(c: Coord): Int = c match

case (row, col) => cells(row)(col)

end GameMap

`IndexedSeq`

in the `cells`

type is important for this algorithm since we are doing a lot of index-based accesses, so we need to use a data structure optimized for that.

## Algorithm – Part 1

We start the solution by defining three data structures for the algorithm:

`val visited = mutable.Set.empty[Coord]`

val dist = mutable.Map[Coord, Int]((0, 0) -> 0)

val queue = java.util.PriorityQueue[Coord](Ordering.by(dist))

queue.add((0, 0))

The first one is a `Set`

of all visited nodes – the ones the algorithm will not look at again. The second one is a `Map`

of distances containing the smallest currently known distance from the top-left corner of the map to the given cell. Finally, the third one is a `java.util.PriorityQueue`

that defines in which order to examine cells. We are using Java's `PriorityQueue`

, not the Scala's one since the Java `PriorityQueue`

implementation defines the `remove`

operation on the queue which is necessary for efficient implementation and which the Scala queue lacks.

We also initialize the queue with the first node we are going to examine – the top-left corner of the map.

Once we have the data structures, there's a loop which runs Dijkstra's algorithm on those structures:

`while queue.peek() != null do`

val c = queue.poll()

visited += c

val newNodes: List[Coord] = gameMap.neighboursOf(c).filterNot(visited)

val cDist = dist(c)

for n <- newNodes do

val newDist = cDist + gameMap.costOf(n)

if !dist.contains(n) || dist(n) > newDist then

dist(n) = newDist

queue.remove(n)

queue.add(n)

dist((gameMap.maxRow, gameMap.maxCol))

We use `queue.remove(n)`

followed by `queue.add(n)`

here – this is to recompute the position of `n`

in the queue following the change in the ordering of the queue (that is, the mutation of `dist`

). Ideally, you would need a decreaseKey operation on the priority queue for the best performance – but that would require writing a dedicated data structure, which is out of scope for this solution.

## Part 2

Part 2 is like Part 1 but 25 times larger. The Part 1 algorithm is capable of dealing with scale, and so the only challenge is to construct the game map for part 2.

We generate the Part 2 game map from the Part 1 map using three nested loops:

`val seedTile = readInput()`

val gameMap = GameMap(

(0 until 5).flatMap { tileIdVertical =>

for row <- seedTile yield

for

tileIdHorizontal <- 0 until 5

cell <- row

yield (cell + tileIdHorizontal + tileIdVertical - 1) % 9 + 1

}

)

The innermost loop generates individual cells according to the challenge spec. The second-level loop pads the 100x100 tiles of the map horizontally, starting from the `seedTile`

(the one used in Part 1). Finally, the outermost loop pads the tiles vertically.

## Solutions from the community

Share your solution to the Scala community by editing this page.