Welcome to day 4 of Chapel’s Advent of Code 2022 series! For more context, check out our introductory Advent of Code 2022: Twelve Days of Chapel blog article for context or instructions on compiling this code.
The Task at Hand and My Approach
In brief, the challenge for
today is to read in a series of
range pairs representing work assignments and determine how many of those assignments
are subsets of one another for part 1 and how many overlap at all for part 2.
An example range pair is 2442,3042
. The first elf in the pair
is assigned to clean up the range of sections 2442
in camp, and the second
elf is assigned the range of sections 3042
. The second range is a subset of
the first range, so would be counted for both part 1 and part 2 of this challenge.
Here is the recommended, parallelized approach that we get to at the end of this blog.
aoc2022day04ranges.chpl


Chapel’s formatted IO made the code to read in the data for this challenge very succinct. In this post, I discuss how Chapel’s formatted IO works, especially within the context of the day 4 challenge. I also talk about some general problemsolving strategies and how they can be applied to this AoC challenge, including examples that show how the Chapel range feature is an excellent conceptual fit to solve this problem. I wrap up showing how to parallelize a Chapel solution to day 4.
First Solution: Handcoded Interval Arithmetic
Here is a succinct solution for both parts in Chapel.
use IO;
var sumSubset = 0;
var sumOverlap = 0;
var s1, e1, s2, e2: int;
while readf("%i%i,%i%i", s1, e1, s2, e2) {
// Check if the second section assignment is a subset
// of the first or vice versa.
if (s1<=s2 && e2<=e1)  (s2<=s1 && e1<=e2) {
sumSubset+= 1;
}
// Partial overlap: if both starts are less than
// the other end, then we have overlap
if s1<=e2 && s2<=e1 {
sumOverlap += 1;
}
}
writeln("sumSubset = ", sumSubset);
writeln("sumOverlap = ", sumOverlap);
Formatted IO is what makes reading/parsing the input so easy. The call to
readf("%i%i,%i%i", s1, e1, s2, e2)
does all of the work! See the blog post for day
1 for more information about the use IO;
statement that enables us to use the readf
procedure. The procedure readf
will try to read the given formatted string (e.g., "%i%i,%i%i"
) from
standard input into the provided variables, much like scanf
works in the C
programming language. The %i
s indicate integer values of any number of
digits. The 
and ,
are the dash and comma characters respectively and will
be matched directly. Whitespace is just ignored between calls to readf
.
Since readf
returns false when it can’t match the format or when it sees an
endoffile (EOF), we can use readf
in a while
loop to gather all of our
input.
(More examples of using Chapel’s formatted IO for AOC 2022…)
For the day 1 challenge of calorie counting, readf
could have been used to
read in the integers. However, this approach wouldn’t have been that helpful for the
challenge, because the empty line between groups of integers would just be ignored.
use IO;
var num : int;
while readf("%i", num) {
writeln("num = ", num);
}
Here is how readf
was used to read in the “character space character”
format used for the rock, paper, and scissors
challenge from day 2.
use IO;
var abc, xyz : string;
while readf("%s %s", abc, xyz) {
writeln("abc = ", abc, ", xyz = ", xyz);
}
The %s
format character will read characters into the given variable
until a whitespace character is reached.
The readf
procedure can also be used for the day 3 input, but it isn’t as exciting
or necessary since iterating over the strings provided by stdin.lines()
or readLine()
also
works.
use IO;
var line : string;
while readf("%s", line) {
writeln("line = ", line);
}
Once we are able to read in the problem input, we can work on solving the
problem. My goto approach for solving any programming problem is to think
about how the current problem is similar to problems I have seen in the past.
Yesterday’s advent of code problem involved
determining what item showed up in two different compartments of a rucksack.
Putting the items in the first compartment into a set and then checking if any
of the items in the second compartment are in that set was an approach that
worked well. We could do that approach here, but it would be inefficient
because today’s problem has more structure. Specifically, the set of sections
each elf has been assigned to clean is being specified with a range ab
,
where we know all of the integers between a
and b
, inclusive,
are in the set. Because of that, we can avoid putting all of
those integers explicitly into a set to check for subsetting and partial
overlap. Instead, we can rely on the mathematical properties of the range.
Finding out how to leverage existing structure in problems is an important problemsolving technique. You can start out considering the whole space of possible inputs and solutions to a problem, and then use the structure of the problem to prune that space. In other words, some of the possibilities are going to result in the same answer, so we don’t have to code the answer for all possibilities.
For today’s problems, we are comparing two ranges/intervals
for each pair of elves to determine if one range is a subet of another for part
1 and to determine if there is any overlap for part 2. The code above reads
the start and end of the ranges into variables so that [s1,e1] is the first
range and [s2,e2] is the second range. The [s1,e1] notation indicates a
set with the numbers s1 through e1 including s1 and e1. There are 48
possibilities for the relationships between the s1
, e1
, s2
, and e2
values, assuming that s1<=e1 and s2<=e2 (e.g., s1<e1<s2<e2, s1==e1<s2<e2,
…). To solve part 1, we can check if the second range is a subset of the
first with (s1<=s2 && e2<=e1)
, or if the first range is a subset of the second
with (s2<=s1 && e1<=e2)
. To solve part 2, we can just check if the start of
the first range is less than or equal to the end of the second range and the
second range start is less than or equal to the first range end, s1<=e2 && s2<=e1
. Deriving this condition takes some reasoning about all possible 48
input conditions and which groups of them end up with the same answer.
Second Solution: Rangebased Approach
This solution uses Chapel ranges to reason about whether there are subsets or overlap.
There are lots of applications that involve reasoning about overlapping ranges/intervals (i.e., interval arithmetic). In Chapel, there is a builtin abstraction called a ‘range’ that makes computing on ranges/intervals even easier. Chapel ranges were developed with High Performance Computing (HPC) applications in mind, like Adaptive Mesh Refinement (AMR), where it is important to determine the intersections/overlaps of grids that model physical phenomena.
The code below shows the creation of a range representing each elf’s cleanup
assignment. Then we can use the contains()
method to determine if one range
is a superset of another one, and the range slicing operator to determine if
there is any overlap. Determining whether one range contains a specific
index—or an entire range of indices as is done here—is a common operation to want
to do in interval computations. The range’s builtin contains
method supports
such queries out of the box. Then the expression r1[r2]
slices the r1
range with the r2
range. This is equivalent to range intersection and is
discussed in
more depth in the
Chapel range documentation.
use IO;
var sumSubset = 0;
var sumOverlap = 0;
var s1, e1, s2, e2: int;
sumSubset = 0;
sumOverlap = 0;
while readf("%i%i,%i%i", s1, e1, s2, e2) {
// Initialize a Chapel range for each elf
var r1 = s1..e1;
var r2 = s2..e2;
// Check if the second section assignment is a subset
// of the first or vice versa.
if r1.contains(r2)  r2.contains(r1) {
sumSubset += 1;
}
// Partial overlap occurs if the intersection of the ranges is nonempty
const intersection = r1[r2];
if intersection.size>0 {
sumOverlap += 1;
}
}
writeln("sumSubset = ", sumSubset);
writeln("sumOverlap = ", sumOverlap);
Third Solution: Parallel Approach
Now let’s look at creating a parallel solution. This means that distinct portions of the computation will be computed simultaneously to reduce overall execution time. Parallelization is important because today’s computing processors all have multiple cores, perhaps even dozens or hundreds, so without parallel computations, a large amount of a system’s processing power may go unutilized. The Chapel programming language was designed from the ground up to express parallelism (and locality, which is critical for high performance).
The example problem has quite a bit of inherent parallelism: we could potentially read the lines of input in parallel, and determining if each pair is a subset or overlaps can both be done in parallel. In the provided solutions, reading the input file in parallel is out of scope for this blog article. With Chapel, it is easy to expose the parallelism available for determining the subsets and overlaps. To do this, we create an array using an iterator (see the day 2 blog post where it talks about iterators). This is a superpowerful way to create an array without having to compute how many entries will be in the array ahead of time.


Once we have an array, Chapel has built in ways to do a parallel forall
loop over that array.
When parallelizing computations, we do have to ask the question “Is this loop
actually parallel?”. The below forall
loop isn’t fully parallel. Fully
parallel is when all of the iterations of the loop can be executed at the same
time and you will get the same answer. But the loop does have a common pattern
called a reduction. We can’t overlap (aside: parallel computing requires
reasoning about intervals/ranges as well!!) the increments to the sum variables
because if one iteration reads between the read and write of another then we
have problems. However, addition is associative and commutative. Associative
means the expressions being added up can all be evaluated in parallel, but then
the summation of the results needs to happen in order. Commutative means we
can do the additions in any order. Chapel can leverage reduction parallelism
for associative and commutative operators such as addition.
The second phrase of the forall
loop
with (+ reduce sumSubset, + reduce sumOverlap)
indicates that summations are being done on the sumSubset
and sumOverlap
variables.


A challenge to parallelizing AoC codes, particularly during these
early days, is that the computations are simple enough that the
running time tends to be dominated by the overheads of reading the
input from, and writing the results to, the console. In addition, if
the problem size is not big enough, the overheads of creating
parallelism and computing the reduction can also weigh down a parallel
execution. In contrast, in the realworld HPC problems for which
Chapel was designed, the computational intensity and data set sizes
tend to require parallelism to be accomplished in any
reasonable time at all. All that said, with a big enough dataset, and
compiling the code using the Chapel compiler’s fast
flag, today’s
parallel solution can be shown to outperform the serial rangebased
approach on my laptop. Parallelism for the win!
Summary
That wraps up this fourth day of introducing Chapel through AoC 2022. The full code for these solutions can be browsed and downloaded from https://github.com/mstrout/adventOfCode2022. Thank you for reading this blog post, and feel free to make comments or ask questions by creating a thread in the Chapel Blog Discourse Category.