# Day 9: Smoke Basin

by @VincenzoBaz

## Puzzle description

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

# Solution of Part 1

Part 1 requires us to find all low points of the grid, where a low point is a cell in the grid which contains a value smaller than the four adjacent values (up, down, left, right).

I model the two dimensional grid containing height values using a case class
called `Heightmap`

. I provide it with a utility method which returns the list of
coordinates and height values of the cells adjacent to a given cell. The list
can have size 2, 3 or 4 depending whether the cell is on the edge of the grid or
not:

`type Height = Int`

case class Position(x: Int, y: Int)

case class Heightmap(width: Int, height: Int, data: Vector[Vector[Height]]):

def apply(pos: Position): Height = data(pos.y)(pos.x)

def neighborsOf(pos: Position): List[(Position, Height)] =

val Position(x, y) = pos

List(

Option.when(x > 0)(Position(x - 1, y)),

Option.when(x < width - 1)(Position(x + 1, y)),

Option.when(y > 0)(Position(x, y - 1)),

Option.when(y < height - 1)(Position(x, y + 1))

).flatMap(List.from)

.map(pos => pos -> apply(pos))

Using this method I implement the `lowPointsPositions`

method which iterates over
all the cells in the grid and for each of them, it checks if the value in it is
smaller than the values of adjacent cells:

` def lowPointsPositions: LazyList[Position] =`

LazyList.range(0, height).flatMap { y =>

LazyList.range(0, width).map { x =>

val pos = Position(x, y)

(

apply(pos),

pos,

this.neighborsOf(pos).map(_._2)

)

}

}

.collect {

case (value, pos, neighbors) if neighbors.forall(value < _) =>

pos

}

The method `forall`

on collections returns true only if the predicate it is
provided with holds true for all elements of the collection. It is similar to
the `exists`

methods which returns true if at least one element in the
collection satisfies the provided predicate.
Finally, `collect`

allows us to simplify chains of `map`

and `filter`

.

You can find more information about these methods in the documentation

We now have all the tools to solve part 1:

`def part1(input: String): Int =`

val heightMap = Heightmap.fromString(input)

heightMap.lowPointsPositions.map(heightMap(_) + 1).sum

end part1

## Solution of Part 2

In part 2 we have to create, for each low point, a basin: a group of grid cells that the smoke traverses while flowing downward towards the low point.

This is how we can solve part 2 after implementing the basin creation for a single low point:

` val lowPoints = heightMap.lowPointsPositions`

val basins = lowPoints.map(basin(_, heightMap))

basins

.to(LazyList)

.map(_.size)

.sorted(Ordering[Int].reverse)

.take(3)

.product

To build a basin from a low point I use a data structure provided in
the standard library:
`Queue`

which implements a first-in-first-out
(FIFO) data
structure.

Starting from the low point, I retrieve the neighbors of a cell and check if
they should be part of the basin, in other words whether they contain the
digit `9`

. I also remember the coordinates of the cells I visited using a `Set`

which provides constant time `contains`

checks. As the basin grows, the cells
that form it are stored in the `basinAcc`

accumulator. As I continue to
retrieve neighbors of neighbors, I add the cells that still need to be processed
in the queue.
The algorithm stops when there are no more cells to visit:

`def basin(lowPoint: Position, heightMap: Heightmap): Set[Position] =`

@scala.annotation.tailrec

def iter(visited: Set[Position], toVisit: Queue[Position], basinAcc: Set[Position]): Set[Position] =

// No cells to visit, we are done

if toVisit.isEmpty then basinAcc

else

// Select next cell to visit

val (currentPos, remaining) = toVisit.dequeue

// Collect the neighboring cells that should be part of the basin

val newNodes = heightMap.neighborsOf(currentPos).toList.collect {

case (pos, height) if !visited(currentPos) && height != 9 => pos

}

// Continue to next neighbor

iter(visited + currentPos, remaining ++ newNodes, basinAcc ++ newNodes)

iter(Set.empty, Queue(lowPoint), Set(lowPoint))

## Run it locally

You can get this solution locally by cloning the scalacenter/scala-advent-of-code repository.

`$ git clone https://github.com/scalacenter/scala-advent-of-code`

$ cd scala-advent-of-code

You can run it with scala-cli.

`$ scala-cli 2021 -M day9.part1`

The solution is 448

$ scala-cli 2021 -M day9.part2

The solution is 1417248

You can replace the content of the `input/day9`

file with your own input from adventofcode.com to get your own solution.

## Solutions from the community

- Solution of @FlorianCassayre.
- Solution of @tOverney.
- Solution of Jan Boerman.

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