# Solve Advent of Code 2017 Day 1 with XQuery and BaseX

I solved the Advent of Code 2017 Day 1 puzzle with XQuery, an XML query language, and BaseX, an XML database engine and XQuery processor. This post details my approach to solving both parts of Advent of Code 2017 Day 1 using a ‘circular list’, XQuery, and BaseX.

Something I enjoy about Advent of Code puzzles and coding in general is that there are numerous ways to conceptualize and approach these problems, and we can compare our approaches within and across languages. The XQuery code I reference within this post is available in my GitHub repository aoc-xquery. Word of warning: Advent of Code 2017 Day 1 spoilers ahead.

## Advent of Code 2017 Day 1

Advent of Code 2017 Day 1 is an inverse CAPTCHA puzzle. We generally interact with a CAPTCHA to prove we are human, yet this challenge is to prove we’re not human by solving a complex problem in two parts:

### Part one

The captcha requires you to review a sequence of digits (your puzzle input) and find the sum of all digits that match the next digit in the list. The list is circular, so the digit after the last digit is the first digit in the list.

### Part two

Now, instead of considering the next digit, it wants you to consider the digit halfway around the circular list. That is, if your list contains `10` items, only include a digit in your sum if the digit `10/2 = 5` steps forward matches it. Fortunately, your list has an even number of elements.

To solve Advent of Code 2017 Day 1, I thought it’d be fun to turn the sequence of digits into an actual ‘circular list’ in order to find matching digits. First, however, we need to have a sequence of digits. Advent of Code provides unique ‘puzzle input’ to each user, and my sequence of digits is the following string of numbers:

``````77736991856689225253142335214746294932318813454849177823468674346512426482777696993348135287531487622845155339235443718798255411492778415157351753377959586612882455464736285648473397681163729345143319577258292849619491486748832944425643737899293811819448271546283914592546989275992844383947572926628695617661344293284789225493932487897149244685921644561896799491668147588536732985476538413354195246785378443492137893161362862587297219368699689318441563683292683855151652394244688119527728613756153348584975372656877565662527436152551476175644428333449297581939357656843784849965764796365272113837436618857363585783813291999774718355479485961244782148994281845717611589612672436243788252212252489833952785291284935439662751339273847424621193587955284885915987692812313251556836958571335334281322495251889724281863765636441971178795365413267178792118544937392522893132283573129821178591214594778712292228515169348771198167462495988252456944269678515277886142827218825358561772588377998394984947946121983115158951297156321289231481348126998584455974277123213413359859659339792627742476688827577318285573236187838749444212666293172899385531383551142896847178342163129883523694183388123567744916752899386265368245342587281521723872555392212596227684414269667696229995976182762587281829533181925696289733325513618571116199419759821597197636415243789757789129824537812428338192536462468554399548893532588928486825398895911533744671691387494516395641555683144968644717265849634943691721391779987198764147667349266877149238695714118982841721323853294642175381514347345237721288281254828745122878268792661867994785585131534136646954347165597315643658739688567246339618795777125767432162928257331951255792438831957359141651634491912746875748363394329848227391812251812842263277229514125426682179711184717737714178235995431465217547759282779499842892993556918977773236196185348965713241211365895519697294982523166196268941976859987925578945185217127344619169353395993198368185217391883839449331638641744279836858188235296951745922667612379649453277174224722894599153367373494255388826855322712652812127873536473277
``````

We can start by assigning the above input to the variable `\$puzzle-input` as a string in order to use it as the first argument for the XQuery function I wrote to solve the puzzle: `inverse-captcha()`. The second argument of `inverse-captcha()` represents the part of the puzzle we intend to solve, and should be an integer value of `1` or `2`. Next, let’s examine how `inverse-captcha()` works.

## `inverse-captcha()` explained

The XQuery function `inverse-captcha()` solves Advent of Code 2017 Day 1 by piping `\$puzzle-input` through three lambda expressions`\$get-digits()`, `\$create-circular-list()`, and `\$find-matches()`—and the XQuery function `fn:sum()` to return an integer solution for either part one or part two of the puzzle.

### `\$get-digits()` explained

We begin by passing `\$puzzle-input` as an argument to the lambda expression `\$get-digits()`, which breaks the string into a sequence of integers:

``````let \$get-digits := (
function (
\$digit-list as xs:string
) as xs:integer+
{
\$digit-list
=> fn:string-to-codepoints()
=> fn:for-each(fn:codepoints-to-string#1)
=> fn:for-each(xs:integer#1)
}
)
``````

The XQuery code above takes an argument of type `xs:string` and binds it to the variable `\$digit-list` before piping it through a series of functions to return a sequence of `xs:integer` items. We first pipe `\$digit-list` to `fn:string-to-codepoints()`, which returns a sequence containing each individual character’s codepoint. For example, the head character of the string, `7`, is returned as the head of the output sequence in its Unicode decimal form: `55`. Next, we pipe our newly formed sequence of codepoints to `fn:for-each()`. Because `fn:for-each()` takes a function as its argument it’s termed a higher-order function, and in this case we use it to apply `fn:codepoints-to-string()` to each item in our sequence—using some syntactic sugar, `#1`, to represent our sequence. At this point, we’ve broken `\$digit-list` into a sequence of type `xs:string` and our last step is to convert each item to type `xs:integer` using `fn:for-each()` and `xs:integer()` in order to return our data as an `xs:integer+` sequence.

Overall, `\$get-digits()` is an efficient expression for converting a string of digits into a sequence of integers. From this point forward, we’ll require items of type `xs:integer` for mathematical operations and creating a ‘circular list’.

### `\$create-circular-list()` explained

Upon reading the description of Advent of Code 2017 Day 1, I was inspired to solve this puzzle by creating a ‘circular list’ rather than by looping through a sequence, which for some reason I imagine as more of a line beginning and ending with a ‘Portal-style’ wormhole rather than a circular loop. So, what is a ‘circular list’? Technically, I’ve used an XQuery map to associate angles with our output from `\$get-digits()` as key-value pairs. My idea is that if we think of the length of our `xs:integer+` sequence as the circumference of a circle, we can create a circle and label points on its circumference with the digits from our `xs:integer+` sequence. This method also solves my ‘Portal problem’ since `0` and `2π` are the same point on the circle’s circumference and we can begin and end there. The XQuery code to create a ‘circular list’ follows:

``````let \$create-circular-list := (
function (
\$digits as xs:integer+
) as map(*)
{
let \$circumference := (
fn:count(\$digits)
)
\$circumference div (2 * math:pi())
)
let \$theta := (
2 * math:pi() div \$circumference
)
let \$circular-list := (
map:merge((
for \$point in (1 to \$circumference)
let \$angle := (
\$theta * \$point
)
let \$digit := (
\$digits[\$point]
)
return (
map:entry(\$angle, \$digit)
),
map:entry(0, \$digits[\$circumference]),
map:entry("theta", \$theta)
))
)
return (
\$circular-list
)
}
)
``````

The lambda expression `\$create-circular-list()` takes our `xs:integer+` sequence output from `\$get-digits()` and returns a `map(*)` item representing a ‘circular list’ and some metadata. The value of the variable `\$digits` is the `xs:integer+` sequence argument of `\$create-circular-list()`. To create our circle, we first use `fn:count()` to determine the length of `\$digits` and bind the result to the variable `\$circumference`. Next, we use a mathematical formula to derive the radius of our ‘circular list’ and bind its result to the variable `\$radius`. To do so, we use the `div` operator to divide `\$circumference` by `2π`, which in XQuery requires an expression containing the integer `2`, the operator `*`, and the function `math:pi()`. The last step we’ll take before creating a ‘circular list’ is determining the smallest angle between two points on the circle’s circumference. Here, we bind the result of dividing `2π` by `\$circumference` to the variable `\$theta`.

We use XQuery’s `for` clause within the function `map:merge()` to iterate through each point along our circle’s circumference and create a ‘circular list’. Specifically, we use XQuery’s `for` clause and declare the variable `\$point`, whose initial value is `1` and final value is the length of our `xs:integer+` sequence: `\$circumference`. Therefore, for each `\$point` we bind the result of `\$theta * \$point` to the variable `\$angle` and the value of `\$digits[\$point]` to the variable `\$digit` before returning `\$angle` and `\$digit` as a key-value pair with the function `map:entry()`. For example, the first point on our circle’s circumference is stored in our `map(*)` item with our circle’s smallest angle, `\$theta`, representing the point’s key and the head of our `xs:integer+` sequence, `7`, representing the point’s label (i.e., its value). After the `for` clause, we use `map:entry()` to add three additional entries: the final item within `\$digits` with the integer key `0`, ensuring `0` and `2π` are the same point; `\$radius` with the string key `radius`; and, `\$theta` with the string key `theta`. The addition of these entries completes our ‘circular list’ with the necessary metadata to solve Advent of Code 2017 Day 1 by finding matching digits within our ‘circular list’.

### `\$find-matches()` explained

The instructions for finding matches within are slightly differ for part one and part two of Advent of Code 2017 Day 1. Where necessary, we’ll use conditional expressions to return output appropriate for each part of the puzzle—either the next digit or the digit halfway around our ‘circular list’. Essentially, `\$find-matches()` compares points along our circle’s circumference and returns the points with matching labels as an `xs:integer+` sequence:

``````let \$find-matches := (
function (
\$circular-list as map(*)
) as xs:integer+
{
\$circular-list
)
let \$theta := (
\$circular-list
=> map:get("theta")
)
let \$arc-length := (
if (
\$part = 1
)
then (
)
else if (
\$part = 2
)
then (
)
else ()
)
let \$points := (
\$circular-list
=> map:size() - 3 - \$arc-length
=> xs:integer()
)
let \$matches := (
for \$point in (0 to \$points)
let \$angle-A := (
\$theta * \$point
)
let \$angle-B := (
\$theta * (\$point + \$arc-length)
)
let \$digit-A := (
\$circular-list
=> map:get(\$angle-A)
)
let \$digit-B := (
\$circular-list
=> map:get(\$angle-B)
)
where (
\$digit-A = \$digit-B
)
return (
\$digit-A
)
)
return (
if (
\$part = 1
)
then (
\$matches
)
else if (
\$part = 2
)
then (
\$matches,
\$matches
)
else ()
)
=> fn:unordered()
}
)
``````

The argument of `\$find-matches()` is the `map(*)` item returned by `\$get-digits()`, and we assign it to the variable `\$circular-list`. Before finding matches, we declare the variables `\$radius` and `\$theta` and use the function `map:get()` to retrieve the metadata values we stored within our ‘circular list’. Next, we declare the variable `\$arc-length`, which represents the length of the arc between two points along our circle’s circumference. A conditional expression determines the value of `\$arc-length` by either multiplying `\$radius` by `\$theta` or by `π` in order to match either the next digit or the digit halfway around our ‘circular list’ respectively.

The number of points required to check for matches is dependent on the value of `\$arc-length`. In other words, while part one checks whether each digit matches the next digit on our ‘circular list’ and requires we travel 2π radians around our circle’s circumference, part two checks the digit halfway around and requires we travel only π radians. Therefore, we assign the variable `\$points` a value of `map:size()` minus `3`—our three additional entries—and minus `\$arc-length`. From here, we use a `for` clause to iterate the value of `\$point` along our circle’s circumference from `0` to `\$points`. At each `\$point`, we declare two angles: `\$angle-A`—for the current point—and `\$angle-B`—for the comparison point. We pass these angles to `map:get()` in order to retrieve two values (i.e., digits) from our ‘circular list’: `\$digit-A` and `\$digit-B`. Next, we use XQuery’s `where` clause to filter only digits with a match through to our `return` clause. Finally, `\$find-matches()` returns an `xs:integer+` sequence of digits with matches, using `fn:unordered()` for a performance boost because we have no compelling reason to maintain the order of our output sequence before passing it to `fn:sum()`. Note that we return `\$matches` twice for part two since we travelled only π radians around our ‘circular list’ and these matches are reciprocal.

### Solution

Ultimately, we solve Advent of Code 2017 Day 1 by piping `\$puzzle-input` through our lambda expressions and `fn:sum()`:

``````let \$solution := (
\$puzzle-input
=> \$get-digits()
=> \$create-circular-list()
=> \$find-matches()
=> fn:sum()
)
``````

Running `inverse-captcha()` in BaseX with my `\$puzzle-input` and the `\$part` argument `1` returns the following result:

1223

With the `\$part` argument `2`, BaseX returns a different number of matches:

1284

I’m making a note here: HUGE SUCCESS. I’ve completed both parts of Advent of Code 2017 Day 1 using XQuery and a ‘circular list’, and have received two gold stars.

## Notes

My thanks to Clifford Anderson for introducing me to Advent of Code. I’d also like to thank the Vanderbilt University XQuery Working Group and the Nashville Functional Programmers for allowing me to present this XQuery code in person in addition to elevating my understanding of XQuery and functional programming.

## What we learned

Thanks to Advent of Code 2017 Day 1, we can now:

• write and use lambda expressions
• convert a string a digits to a sequence of integers
• create a ‘circular list’
• perform mathematical operations in XQuery
• use the following XQuery functions: `fn:codepoints-to-string()`, `fn:count()`, `fn:for-each()`, `fn:string-to-codepoints()`, `fn:sum()`, `fn:unordered()`, `map:entry()`, `map:get()`, `map:merge()`, `map:size()`, `math:pi()`, and `xs:integer()`