This guy by the name of Eric Wastl (t) created this neat neat web site called “Advent of Code“. It’s a… well, let’s let Eric describe it:

Advent of Code is a series of small programming puzzles for a variety of skill levels. They are self-contained and are just as appropriate for an expert who wants to stay sharp as they are for a beginner who is just learning to code. Each puzzle calls upon different skills and has two parts that build on a theme.

These puzzles are nicely arranged in the format of a Christmas tree. Each level in the tree is a different programming challenge, and it has two parts (the second part is shown to you after you complete the first part). So I’ve decided to work through these, and to post a T-SQL solution for each of them.

For Day 1, the puzzle is to evaluate a string consisting of “(” and “)” characters, in random order. A “(” means to go up a floor, and a “)” means to go down a floor (you’re in a building that has infinite floors – both above and below ground). The part 1 exercise is to determine what floor Santa ends up on if he starts on the ground floor.

This is a relatively simple exercise… just count how many times you go up, and subtract from that how many times you go down. But.. here is the input string given to work with:

Yuck! Were you able to count those? Yeah, I thought not. So, let’s go with another approach… let’s replace all of the “)” with an empty string, and check the length. The length will be the number of “(” left, or the number of times that Santa went up a floor. Then replace all of the “(” with an empty string, and check the length (this will be the number of times that Santa went down a floor). The delta between these is the ending result.

Well, that was certainly pretty easy, and part 1 is wrapped up. Once you get that answer, part 2 wants to know at what position in the string did Santa first go into the basement? To determine this, I’m going to use a virtual / dynamic tally table to break apart this string character by character. If the character is a “(“, then the offset is +1; if the character is a “)”, then the offset is a -1. Then just perform a running total against this offset, and find the first row where the position is -1. Before I show the code, let me explain what these concepts are.

  1. Tally table: A tally table is a table that consists of sequential numbers. Because of the nature of this table, many people will call this a numbers table. Using a tally table allows for the creation of set-based solutions to problems that otherwise would require a more iterative approach. Typically, using a tally table solution will perform many orders of magnitude faster than an iterative solution. Please read http://www.sqlservercentral.com/articles/T-SQL/62867/ for a more detailed explanation
  2. A dynamic / virtual tally table is one that is built and created without storing the values on disk. The creation of a dynamic tally table allows you to utilize a tally table in places where you may not be able (or allowed) to create a permanent tally table. This method works so well that frequently I will use a dynamic tally table and not bother creating a physical tally table. You can read more about a dynamic tally table at http://www.sqlservercentral.com/articles/T-SQL/67899/. My virtual tally table uses four common table expressions (CTEs). The first CTE just creates 10 rows, all consisting of the value 1. The second CTE performs a cross join between the first CTE two times, which creates 100 rows. Again, this CTE is simply returning the value 1 – 100 times. The third CTE performs additional cross joins between the second CTE – this will generate one million rows (again, all with the value 1). The fourth CTE utilizes the ROW_NUMBER() function to generate a sequential number across all of the one million rows.
  3. Running total: a running total is a total that is built upon previous rows. An easy to understand example is your checkbook. The balance is based upon the total from the previous row (transaction), and the current row (transaction) is applied to the previous rows’ total to produce the new total for the current row.

Now that these concepts are explained, the code to perform this turns out to be eazy-peazy:

Creating the virtual tally table was most of this code (thank goodness for having SQL Prompt – this is a custom snippet that I use frequently). Since we now have where Santa is after each move, we can go back and do Part 1 in a slightly different manner. Just replace the last line with:

And we can even combine both of these by replacing that line with:

So here we have Advent of Code, Day 1, Parts 1 and 2 solved (with Part 1 solved in two different ways).

Come back tomorrow for my solution for Day 2.