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
10items, only include a digit in your sum if the digit10/2 = 5steps 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)
)
let $radius := (
$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("radius", $radius),
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+
{
let $radius := (
$circular-list
=> map:get("radius")
)
let $theta := (
$circular-list
=> map:get("theta")
)
let $arc-length := (
if (
$part = 1
)
then (
$radius * $theta
)
else if (
$part = 2
)
then (
math:pi() * $radius
)
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:
With the $part argument 2, BaseX returns a different number of matches:
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
- solve an inverse CAPTCHA
- 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(), andxs:integer()
Thank you for reading, and have fun coding.