Day 01

Discussion

To pair the smallest number in the left list with the smallest number in the right, sort the two lists, keeping duplicates.

Then, to find the total distances between pairs, simply subtract one from another and get absolute value (in case negative), then sum.

How in XSLT. Oh, geez.

Given the lists are in the same file, side-by-side, let's do this:

1. Create two node variables, each by:
   1. Reading in the file, line-by-line, grabbing whichever side this variable represents.
   2. Perhaps do it in an XPATH 3 way, sorting and assigning to a single sequence as we go. We'll see.
2. Now that we have two sorted lists of nodes of the same length, to keep a running total, we need to do that recursive business. Call a recursive template that takes sum as param, and the base case is to print the sum. Each recursive calls itself on the following-sibling::*[1] with the $sum + $calculated-distance.

I think that'll do it, let's go!

Solution

Let's see how far I need to deviate from my initial plan to get this thing working.

<xsl:template xmlns:xsl="http://www.w3.org/1999/XSL/Transform" name="solution-part-1">
                  <xsl:param name="dataset-name" select="'test'"/>
                  <xsl:variable name="data-doc"
                                select="unparsed-text('file:///'||$srcdir||'/data/'||$day||'/'||$dataset-name||'.txt')"/>
                  <xsl:variable name="answer"
                                select="     let $left-list := sort(for $x in tokenize($data-doc, '\n') return tokenize($x, '   ')[1]),         $right-list := sort(for $x in tokenize($data-doc, '\n') return tokenize($x, '   ')[2])     return         sum(for $pos in 1 to count($left-list) return abs(number($left-list[$pos]) - number($right-list[$pos])))     "/>
                  <p>
                     <b>Solution to the <xsl:value-of xmlns:xsl="http://www.w3.org/1999/XSL/Transform" select="$dataset-name"/> data set</b>
                  </p>
                  <codeblock>
                     <xsl:value-of xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
                                   select="format-number($answer, '#')"/>
                  </codeblock>
               </xsl:template>

Solution to the test data set

11

Solution to the actual data set

1834060

Wow, that was pretty easy with sequences and XPATH 3.1. No recursing through nodes and carrying the running total necessary. Not at all what I expected.

Discussion

Okay, this part is weird. I don't know what it actually solves, but I'm to take every number in the left list, count how often it appears in the right list, and multiply the number by how often it's in the right list, Then move onto the next left list number, adding all the products together.

I know what it's testing, how to make the right list a hash lookup table rather than running through it every time. Hmm. I think this time, I'll build a node-tree of the right-list and use that as the lookup. Not sure how under the covers XSLT optimizes the lookup of matching nodes, but ....

Solution

<xsl:template xmlns:xsl="http://www.w3.org/1999/XSL/Transform" name="solution-part-2">
                  <xsl:param name="dataset-name" select="'test'"/>
                  <xsl:variable name="data-doc"
                                select="unparsed-text('file:///'||$srcdir||'/data/'||$day||'/'||$dataset-name||'.txt')"/>
                  <xsl:variable name="right-list">
                     <xsl:for-each select="tokenize($data-doc, '\n')">
                        <location>
                           <xsl:value-of xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
                                         select="tokenize(., '   ')[2]"/>
                        </location>
                     </xsl:for-each>
                  </xsl:variable>
                  <xsl:variable name="answer"
                                select="     let $left-list := for $x in tokenize($data-doc, '\n') return tokenize($x, '   ')[1],      $products := sum(for $location in $left-list return number($location) * count($right-list/location[text() = $location]))     return         format-number($products, '#')     "/>
                  <p>
                     <b>Solution to the <xsl:value-of xmlns:xsl="http://www.w3.org/1999/XSL/Transform" select="$dataset-name"/> data set</b>
                  </p>
                  <codeblock>
                     <xsl:value-of xmlns:xsl="http://www.w3.org/1999/XSL/Transform" select="$answer"/>
                  </codeblock>
               </xsl:template>

Solution to the test data set

31

Solution to the actual data set

21607792

Still no real hoops to jump through, but I'm curious if using a node-tree as a lookup is most efficient.