Chapel Language Blog

Here we are on day 8 of Advent of Code 2022, two-thirds of the way through our ‘Twelve Days of Chapel AoC’ series! If you’re new to the series, check out the introductory article for more context.

The Task at Hand and My Approach

In part one of today’s puzzle, we’re given a 2-dimensional (2D) grid of integers, representing the heights of trees in a very dense, regular forest. Our goal is to determine how many trees are visible from outside the forest by looking for lines of sight to each tree along the rows or columns of trees. Essentially, starting from a given tree, if you can walk directly to the edge of the forest encountering only trees that are shorter, your starting tree is visible.

To accomplish this, I’m going to use a 2D array to represent the forest, which will be the first higher-dimensional Chapel array we’ve seen in this series. I’ll also be introducing the concept of the domain, which is Chapel’s way of representing sets of indices that can be used for declaring arrays or describing iteration spaces. I’ll also make use of slicing, reductions, and promotion, which we’ve seen in earlier articles.

For those who looked in their parents’ closets for presents before holidays, here’s my full solution for today:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

const Lines = readLines();

iter readLines() {
  use IO;

  var line: string;
  while readLine(line, stripNewline=true) do
    yield line;
}

const numRows = Lines.size,
      numCols = Lines.first.size;

const ForestSpace = {0..<numRows, 0..<numCols};

var Forest = [(r,c) in ForestSpace] Lines[r][c]:int;

proc visible((r, c): 2*int, height: int) {

  return && reduce (Forest[..<r, c] < height) ||
         && reduce (Forest[r+1.., c] < height) ||
         && reduce (Forest[r, ..<c] < height) ||
         && reduce (Forest[r, c+1..] < height);
}

writeln(+ reduce visible(ForestSpace, Forest));

The code for this one’s going to be short and sweet, so let’s get into it.

Reading the Forest Input

Here, I’m going to take the approach we’ve used in a lot of these articles, of writing an iterator that reads and yields lines, storing them as an inferred-size array named Lines:

1
2
3
4
5
6
7
8
9

const Lines = readLines();

iter readLines() {
  use IO;

  var line: string;
  while readLine(line, stripNewline=true) do
    yield line;
}

If you’ve been following this series, you might notice a few differences between this code and my last such routine on day 5. Specifically:

• I moved my use IO; statement into the iterator itself. The use statement only makes its module’s contents available to the scope that contains it, and this is the only scope in which I need to access symbols from ‘IO’. So I move it from the file’s module scope to this local scope in order to not pollute the namespace of the whole program with symbols that won’t be needed.

• I’ve also used the optional stripNewline argument provided by the readLine() routine, which tells it to remove the terminating newline character (\n) before storing a line of input into line. Note that identifying the argument name, as I’ve done here with stripNewline=, is not necessary; however, it makes the call more self-documenting than if I’d simply written readLine(line, true).

After executing these statements, Lines will be a 1-dimensional (1D) 0-based array of strings, with each string value representing one line from the file (or, a row of trees in our forest).

Storing the Forest in a 2D Array

Up until this point in the series, we have used arrays frequently, but only 1D arrays. Because Chapel was designed for scientific computing, where modeling the physical world often involves multidimensional data sets, it also supports n-dimensional arrays, as in NumPy or Fortran. Such arrays are notably absent from C, C++, Java, and the like, which support arrays-of-arrays, yet don’t have a language-supported way to represent a dynamically-sized, n-dimensional array using a contiguous block of memory. Doing so enables elements to be traversed along any dimension by walking a pointer through memory using a fixed stride. This can be important for efficiency in applications using nD arrays.

For this program, a 2D array is a very natural representation of the forest data, since it will permit us to focus on data along rows or columns, as desired. Of course, we could do the computation directly on the input array of strings; but as we will see, using the 2D array permits us to make use of slicing in interesting ways.

First, I declare a pair of integer constants representing the number of rows and columns in the forest:

11
12

const numRows = Lines.size,
      numCols = Lines.first.size;

I compute the number of rows (numRows) by querying the size of my array of lines that I read in—effectively, the number of lines in the file. Then I take the size of the first line from the file (the number of characters or codepoints it is storing), which serves as the number of columns (numCols). Note that I’m assuming that all lines have the same length. I can safely make this assumption since it is true of the AoC input sets. Because of this, I could have equivalently checked the size of Lines.last or Lines[i] for any value of i in 0..<numRows instead.

Domains: First-class Index Sets

All arrays in Chapel are defined over a concept known as a domain. A Chapel domain is a language feature representing a set of indices. These indices can be used for a variety of purposes, such as defining the indices of an array or an array slice, or serving as the iterand for a loop.

Up until now, the 1D arrays we’ve declared have had their indices defined using a range. For instance, we’ve seen declarations like:

var A: [1..1000] int;

Though ranges are not domains themselves, they are used to build rectangular domains of 1 or more dimensions. As a convenience, they can be used to create domains when used in array declarations like this. Specifically, for this declaration of A, the compiler will introduce an anonymous domain representing the indices 1..1000. Domain literals in Chapel are represented by specifying the indices within curly brackets, and if we were to type out the domain’s value, it would look like {1..1000}. Like ranges, domains can be named, so we could write:

const D = {1..1000};

This declares a 1D domain named D, representing the indices 1 through 1000, inclusive. A named domain can also be used to specify an array’s indices, like so:

var B: [D] string;

which would give us an array of 1000 strings, indexed using 1..1000.

Multidimensional rectangular domains are defined using a list of ranges. For example, here is a 3D domain whose size in each dimension is defined by the variables m, n, and o respectively:

var D3 = {1..m, 1..n, 1..o};

If we wanted to declare an array over this set of indices, we could do it in any of the following ways:

var A: [D3] int;
var B: [{1..m, 1..n, 1..o}] int;
var C: [1..m, 1..n, 1..o] int;

Note that these three forms are equivalent, and that the curly brackets used in B’s declaration are unnecessary. In practice, we typically omit them for brevity, as in our 1D array declarations up to this point. One motivation for naming domains is that it permits them to be reused within the code rather than typing the raw indices over and over again, reducing the chances of mistakes. For example, we can write a parallel loop over the indices of these arrays as follows:

forall (i,j,k) in D3 do
  A[i,j,k] = B[i,j,k] * C[i,j,k];

Since D3 is a 3-dimensional domain, loops over it will yield 3-tuple indices. Here, I am de-tupling them into their respective integer components, naming them i, j, and k. We can then index into our arrays using the three integers, separated by commas in the normal square brackets used for indexing.

Chapel’s arrays can also be accessed using tuple indices. So if we were to store the indices yielded by D3 using a single loop index variable, we could write:

forall idx in D3 do
  A[idx] = B[idx] * C[idx];

Note that idx is a 3-tuple of ints in this loop.

A = B * C;

forall (a, b, c) in zip(A, B, C) do
  a = b * c;

Representing our Forest Using a Domain and Array

We now have everything we need to create our domain and array. I start by declaring a 2D array in terms of the number of rows and columns we got from the input file:

14

const ForestSpace = {0..<numRows, 0..<numCols};

I declare this as a constant because I have no intention of changing the domain’s indices after it is initialized. In practice, this provides useful semantic information to the compiler that can enable important optimizations.

I named this domain because I want to loop over it in order to convert my 1D Lines input array into a 2D array. By giving it a name, I avoid the need to repeat these range expressions again when I write that loop. And by giving it a (somewhat) meaningful name, I potentially improve my code’s readability compared to just using literal range and domain expressions.

I chose to use 0-based indexing for this domain because that’s what my Lines array and its string values will use. That said, I don’t end up using the numerical values of my indices at all after the next statement, so could nearly as easily have used 1-based indexing or any other indexing scheme that felt natural.

At this point, I could declare my array as follows:

var Forest: [ForestSpace] int;

However, since the first thing I want to do with the array is store my input data into it, I took a different approach:

16

var Forest = [(r,c) in ForestSpace] Lines[r][c]:int;

As described in our day 6 article, [idx in expr] is a Chapel loop expression that is equivalent to for[all] idx in expr. It will be parallel if expr supports parallel iteration and serial otherwise. Like most built-in Chapel types, domains do support parallel iteration, so this declaration is equivalent to:

var Forest = forall (r,c) in ForestSpace do Lines[r][c]:int;

which in turn is very similar to:

var Forest: [ForestSpace] int;
forall (r, c) in ForestSpace do
  Forest[r, c] = Lines[r][c]:int;

In any of these forms, the loop’s body is simply an indexing expression into my Lines array, first to pick out line r and then to pick out the cth character from that line’s string. I cast that character to an int in order to make the array store integer values that I can compare easily and cheaply.

Note that Chapel distinguishes very strictly between 2D arrays and 1D arrays of 1D arrays (or in this case, 1D arrays of indexable, array-like types, such as strings). For this reason, we could not write Lines[r,c] because Lines is not a 2D array or data structure. Only Lines[r] or Lines[r][c] would be legal, returning a full-line string or a single-character string from a line, respectively..

We store the result of this [...]-loop expression into the new inferred-type variable Forest. When a variable is initialized with a [...]-loop like this, its domain is determined by the index set of the loop. In this case, since ForestSpace defines that index set, it also serves as the domain for Forest. Thus, this statement could have been written out more verbosely as:

var Forest: [ForestSpace] int = [(r,c) in ForestSpace] Lines[r][c]:int;

At this point, we have our 2D array, Forest, of tree heights and are ready to compute on it.

A Procedure for Computing a Tree’s Visibility

Next, let’s look at my procedure for computing the visibility of a tree. Here is its argument list:

18

proc visible((r, c): 2*int, height: int) {

I declare this routine to take a 2-tuple of ints, (r, c), which will serve as the row and column coordinates of the tree in question—essentially, an index from TreeSpace. It also takes height, an int indicating the corresponding tree’s height, for use in determining whether it’s larger than its neighbors along any of the row- or column-based sight lines.

Those who have been following this series may note that I’ve departed from my typical style of omitting the types for my procedures’ formal arguments by declaring them here. If you’re curious, I’ll explain why I did this a bit later.

Using Slices to Refer to Subsets of the Forest

First, let’s focus on the body of the procedure. We’ve introduced examples of slicing in previous articles in this series, in which a range of indices is used to access a subset of elements in a bytes value, string, or array. We’ll be using slicing today to refer to subsets of the forest. For example, the slice Forest[0..r, 0..c] would represent the sub-array of trees that are in the quadrant northwest of (r,c), inclusive.

For this computation, we will be looking at trees in the same row or column. For example, the slice Forest[0..<numRows, c] would represent all trees in my column and Forest[r, 0..<numCols] would represent all those in my row. These two slice expressions can be written in a more concise form, though, which is Forest[r, ..] and Forest[.., c], respectively. When an unbounded range is used in an array slicing expression, it uses the array’s bounds in place of any missing range bounds. Thus, rather than remembering whether Forest is 0-based or 1-based, or how many elements it has, I can use an unbounded range as a more mnemonic way to refer to sub-arrays of values. This also often reduces the chances of errors.

Of course, in this computation, we don’t want the entire row or column of the forest, just the subset directly to the north, west, south, and east of the current tree. These could be expressed using the slices:

ref north = Forest[ ..<r, c    ],  // all rows before mine in my column
    south = Forest[r+1.., c    ],  // all rows after mine in my column
    west  = Forest[    r, ..<c ],  // all columns before mine in my row
    east  = Forest[    r, c+1..];  // all columns after mine in my row

(where the spacing here is not necessary or meaningful, but just used to align the dimensions).

As before, I’m using unbounded ranges, but leaving only one of the two bounds unspecified. As a result, missing low bounds will use 0, the array’s low bound in each dimension; and missing high bounds will use numRows or numCols, respectively. These four slice expressions describe the neighbors we must analyze.

Using Promotions and Reductions to Compute Visibility

Here’s how I wrote the body of visible() itself:

20
21
22
23
24

  return && reduce (Forest[..<r, c] < height) ||
         && reduce (Forest[r+1.., c] < height) ||
         && reduce (Forest[r, ..<c] < height) ||
         && reduce (Forest[r, c+1..] < height);
}

Note that I wrote the slice expressions directly rather than naming them and using those names here. Either approach is fine, but I found I preferred seeing the slice expressions directly in the computation for some reason.

I use the < operator to compare each of the four sight-line slices to my tree’s height, height. This is another instance of operator promotion as described in the sidebar above. Specifically, the < operator takes two int arguments, yet I am passing it an array slice and an int. As a result, an expression like:

Forest[..<r, c] < height

can be thought of as equivalent to:

forall f in Forest[..<r, c] do (f < height)

which in turn is equivalent to:

forall i in Forest.domain.low..<r do (Forest[i, c] < height)

This computation could have been written in any of these equivalent ways if preferred.

Because we are interested in whether all of the trees in these slices are shorter than ours, we use a logical and (&&) reduction, which applies a boolean short-circuiting ‘and’ operation to the arguments. This causes it to quit early if a single false is found, since there is no way for the result to become true at that point. Then, because only one of the four directions is required to get visibility, we use the short-circuiting ‘or’ operation (||) to combine the results. This means that if the tree is visible from any of the four directions, we don’t need to check the other three.

In this way, I’ve computed whether the tree at (r, c) is visible in a very succinct manner. It may seem surprising that I didn’t do any special handling of trees at the edge of the forest. Let’s look at why that is.

The first thing to note is that for a tree on the border, like (r=3, c=0), the slice that governs its west neighbors is Forest[r, ..<c] or Forest[3, ..<0] or Forest[3, 0..<0]. However, 0..<0 is a degenerate, or empty, range since there are no integers between 0 and 0 excluding 0. As a result, this slice is empty.

That leads to the question “What do reductions do if they are applied to an empty collection of values?” The answer is that they generate the identity element of their reduction operator, which is true for the && operator. Thus, our border trees are automatically visible, which matches the AoC definition as well. For this reason, no special handling for them is required!

Computing Visibility in Parallel via Promotion

Now all we have to do is call our visible() routine for all trees in the forest, passing in their coordinates and heights. We could do this using:

forall rc in ForestSpace do
  visible(rc, Forest[rc]);

However, this is another chance for us to apply promotion. We’ve already seen that we can promote an integer argument, like height above, with an array in order to promote the function. However, we can also use a domain to promote arguments, so long as the formal arguments are the same as the domain’s index type—in this case, a 2-tuple of ints. As a result, our forall-loop above can be written as:

visible(ForestSpace, Forest);

which is equivalent to the loop:

forall ((r, c), height) in zip(ForestSpace, Forest) do visible((r, c), height);

(yet, in a far more succinct manner).

proc visible((r, c), height) {

forall (r, c) in ForestSpace do
  visible((r, c), Forest);

proc visible((r, c): 2*int, height: [ForestSpace] int) {
  return && reduce (Forest[..<r, c] < height) ||
  // etc..
}

Finally, since the AoC problem asks us to find the number of visible trees in the forest, we can use our old friends, the + reduction and writeln() routine to do so:

26

writeln(+ reduce visible(ForestSpace, Forest));

And there you have it. Hopefully you did not have any trouble seeing the forest for the trees! [rim shot].

Before wrapping up, here are some optional, and slightly technical, notes on parallelism and performance in the code above:

return && reduce (for f in Forest[..<r, c] do f < height) ||
       && reduce (for f in Forest[r+1.., c] do f < height) ||
       && reduce (for f in Forest[r, ..<c] do f < height) ||
       && reduce (for f in Forest[r, c+1..] do f < height);

ref Slice1 = [..<r, c];

ref Slice2 = [..<r, c..c];

return && reduce (for f in Forest[..<r, c..c] do f < height) ||
       && reduce (for f in Forest[r+1.., c..c] do f < height) ||
       && reduce (for f in Forest[r..r, ..<c] do f < height) ||
       && reduce (for f in Forest[r..r, c+1..] do f < height);

return && reduce for rc in {0..<r, c..c} do Forest[rc] < height) ||
       // etc.

Summary

That concludes today’s article and a brief introduction to Chapel’s domains and multidimensional arrays, as well as their relationship to forall loops, promotion, slicing, and reductions. You can browse or download my code from the top of this article or GitHub if you want to try it yourself or make modifications to it.

Part two of today’s exercise is not too much harder (though I had a hard time with it due to not reading the instructions carefully). You should already have all the Chapel features you need to solve it. Essentially, you can create another procedure like visible() that implements different logic to compute a tree’s score and invoke it in the same promoted manner. Just be sure to read the description of how the score is computed more carefully than I did!

Thanks for reading this blog post and series, and please feel free to ask any questions or post any comments you have in the new Blog Category of Chapel’s Discourse Page.