Voice of the DBA

Tag: AdventofCode

Advent of Code–Day 2
I’ve continued working along, and while I found Day 2 to be straightforward in Python and PowerShell, I thought it was tricky in SQL I decided this one was worth a post, since I had to futz around a few times to solve it, and I managed a slightly different way than some others.

If you haven’t solved it, then try. Come back here later and compare solutions, but give it a try first.

Solution coming below, so don’t scroll if you don’t need the solution.

But first,

Missteps

I had a misstep in this one. I loaded the entire list of packages as separate lines into separate rows into a single column table. My challenge to myself was not to use ETL work to break this apart, or updates. I wanted a simple solution, thinking I didn’t want to take up extra space in the database.

As a result, I wanted a single query from a single string column that had the package size stored as one column, ‘2x3x4’ as an example.

My first attempt used the Moden Splitter function, which seemed to work well. I got three rows for each package. I then used a WIndow function to grab that data, order by the sizes, and then start performing calculations. When I didn’t get the right result, I started digging in.

One of the first things I saw was that I had multple packages with the same sizes. So I had two 22x3x1 packages, and when I used a partition based on the dimensions, I had calculation problems. That’s because the window partition doesn’t know that three rows are one package and three are another.

I could have fixed this with some other value to capture the package, maybe a row_number even, but I decided not to go down this route.

My Solution

I decided to break this down, and I used a series of CTEs to do this. I haven’t gone back to optimize things, or combine CTEs, which is possible, but instead left the CTEs as I wrote them to solve parts of the puzzle. Multiple CTEs are east, and they help examine the problem in pieces.

My first step was to parse the string. I don’t love this solution as it is limited to a three dimension package, but it does seem to be the easiest way to break down the dimensions of the package. My query looks to find the string positions for:
- end of the first dimension
- start of the second dimension
- start of the third dimension.
This gives me the simple query:

with cteSplit (d, el, sw, sh)
as
(
select
   dimensions
, endlength = charindex(‘x’, dimensions) – 1
, startwidth = charindex(‘x’, substring(dimensions, charindex(‘x’, dimensions),20)) + charindex(‘x’, dimensions)
, startheight = len(dimensions) – charindex(‘x’, reverse(dimensions)) + 2
from day2_wrappingpresents d
)

Once I had these values, a little math gives me the length, width, and height.

, cteDimensions
as
(select
   d
   , l = cast(substring(d, 1, el) as int)
   , w = cast(substring(d, sw, sh-sw-1) as int)
   , h = cast(substring(d, sh, len(d)) as int)
from cteSplit d
)

Now I’m in business. These two queries were fairly simple, despite all the nested functions. I’ve got integers with the dimensions of each package.

Now the tricky part. I want these ordered. They’re columns, not rows, and I can’t put an ORDER BY in the CTE, so I need to use some comparisons.

, cteOrder
as
( select
   d
, small = case
            when l <= w and l <= h then l
            when w <= l and w <= h then w
            when h <= l and h <= w then h
        end
, middle = case
            when (l >= w and l <= h) or (l <= w and l >= h) then l
            when (w >= l and w <= h) or (w <= l and w >= h) then w
            when (h >= l and h <= w) or (h <= l and h >= w) then h
        end
, large = case
            when l >= w and l >= h then l
            when w >= l and w >= h then w
            when h >= l and h >= w then h
        end
from cteDimensions
)

Not the prettiest code, and perhaps there are better ways to determine this, but this passed all my tests, and seemed to work.

I could have put the next part in the final query, but I decided to make this a separate CTE to easily read the math. I know some people don’t like lots of CTEs, but in this case, I think they make the query very readable. I should look back at this in six months and see what I think.

, cteFinal
as
(
select
d
, area = (2 * small * middle) +
           (2 * small * large) +
           (2 * middle * large)
, slack = (small * middle)
from cteOrder
)

Now I use a final outer query to sum things up.

select
sum(area + slack)
from cteFinal

The other thing I noticed here is that when I needed to solve the second part, I only had to change the math in the cteFinal to get the new values. It took longer to re-read the second part than to change the code and solve it.

I looked over how Wayne Sheffield and Andy Warren solved this in T-SQL, and I thought their approaches were interesting. I didn’t want to PIVOT or UNPIVOT anywhere, nor did I look at performance here. This runs so quickly, I’m not sure it matters, though I wonder if we were calculating across 1mm rows, would one be better?

I may look, but for now, I’ll leave that to someone else.
January 20, 2016
Hash Tables in PowerShell–Advent of Code Day 3

I continue to work on solving the Advent of Code puzzles in both PowerShell and T-SQL after completing them in Python.

When I hit day 3 in PowerShell, it was a few new tricks to learn, one of which was reading a large string from a file. However the interseting thing for me was learning to work with hash tables.

The Day 3 puzzle looks at moving Santa around on a grid. We don’t know the size or shape of the grid, just that we get directions in 1 of 4 ways (^<>V) and then must move to a new house. The first puzzle asks how many houses get one present.

This is interesting, and naturally to me the first thing that occurs is a dictionary. I used one in Python, adding new elements as I received new coordinates. I wasn’t sure how to do this in PowerShell, and ended up searching a bit about two dimensional arrays, thinking I could perform a count there, adding indexes as needed. However I ran into hash tables while searching, and this was a better solution for me.

The short part of working with hash tables is that you declare them with a simple command. In my case, since I had a delivery at coordinates (0,0), I wrote this:

$houses = @{“0,0” = 1}

This uses the @{} syntax to set up a key value pair. Essentially a dictionary. From here, I computed new “keys” from the directions, and could add new values like this:

$houses.Add(“1,1”, 1)

Of course, I had to check for existing values, and if there were existing values, I had to increment them.

$houses.Set_Item(“1,1”, $houses[“1,1”] + 1)

With that code, I could easily solve the puzzle. However I was struck by the various ways I work with the hash tables. I use braces, {}, to declare the table. I use brackets, [], to access elements and then parenthesis, (), when calling methods. All of that makes programming sense, but it’s something to keep in mind, especially as those three marks mean different things in Python.

I also learned how to search with ContainsKey and ContainsValue, as well as how to Set_Item and Get_Item, which didn’t appear to work with the ISE Intellisense.

All in all, it was interesting working with a hash table and good to learn PowerShell supports them. They are very handy constructs when building up a set of data that you’ll need to work with, and you need more than the simple buckets an array provides.

January 11, 2016
Advent of Code Day 1, Puzzle B
As I continue through the Advent of Code, albeit slowly, I’m solving each puzzle 3 days. I worked through 6 of them in Python before moving on to other languages, and this is my chance to catch up with both PowerShell and T-SQL. I likely won’t post all solutions, but I was having fun rewriting code, so here are the ways I looked at things.

Note: You should try this on your own. I logged into the AventofCode with GitHub and things worked great for me.

Go on, give it a try.

I’ll wait.

Solutions coming.

Python

I started here, using iterations, which are very powerful in Python. In this case, I took advantage of the multiple variable assignment in Python to enumerate the array and get each value and index. I think use a comparison to determine if I add or subtract one. Finally, an IF returns the current index if I hit –1. I should probably have a break in there for efficiency as well.
```
def calculate_negative(directions):
    start = 0
    for i, c in enumerate(directions):
        if c == '(':
            start += 1
        else:
            start -= 1
        if start == -1:
            print(i)
```
PowerShell

This was a bit trickier for me. I wasn’t sure how to work with a string and pull out values. I did some searching and ran across the .ToCharArray function. That doesn’t feel like the best way to do this, but I decided to use it.

The rest of the function is similar and gave me the correct answer, so there you go.
```
$count = 0
$floor = 0
foreach ($c in $input.ToCharArray())
  { 
   if ($c -eq '(') {$floor += 1} 
   elseif ($c -eq ')') {$floor -= 1 }
   $count += 1
   if ($floor -eq -1)
     {
     $count
     break
     }
  }
```
T-SQL

A more complex situation here, given that we need to work through a string, calculating a running total. I broke the input up using a tally table and a splitter with substring. This was fairly easy, and not complex as I was just getting individual charaters.

Then it was a simple running total of the CTE to get me the totals at each point in time. This worked well, but I needed the first –1 total.

Finally, I used the outer query to get the min value out of the code and use that, which gave me the lowest value where the –1 occurred.
```
WITH tally (n)
AS
( SELECT ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
   FROM (VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)) a(n)        -- 10
   CROSS JOIN (VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)) b(n)  -- x 10 = 100
   CROSS JOIN (VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)) c(n)  -- x 10 = 1000
   CROSS JOIN (VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)) d(n)  -- x 10 = 10000
)
, direction (n, d)
AS
(
SELECT tally.n
   , d = CASE WHEN SUBSTRING(@input, n, 1) = '(' THEN 1 ELSE -1 end
 FROM tally
), currfloor 
as
(SELECT 
   d.n
   , 'currentfloor' = SUM(d.d) OVER (ORDER BY d.n ROWS UNBOUNDED PRECEDING)
FROM direction d
)
SELECT MIN(currfloor.n)
 FROM currfloor
WHERE currentfloor = -1
```
January 8, 2016
Advent of Code Day 1, Puzzle A
I have been working my way through the Advent of Code series across the last few weeks. This is a side project, allowing me to use some Python skills to solve the various puzzles. I also started to use PowerShell to solve the puzzles, mostly becauase this means I practice new skills.

Note: I urge you to try to work on this yourself, withough reading my solutions. It’s fun and worth some practice. Once you’ve done that, feel free to read on.

Go ahead

Write your own.

Here’s the input:

DECLARE @input VARCHAR(MAX) = ‘()(((()))(()()()((((()(((())(()(()((((((()(()(((())))((()(((()))((())(()((()()()()(((())(((((((())))()()(()(()(())(((((()()()((())(((((()()))))()(())(((())(())((((((())())))(()())))()))))()())()())((()()((()()()()(()((((((((()()())((()()(((((()(((())((())(()))()((((()((((((((())()((()())(())((()))())((((()())(((((((((((()()(((((()(()))())(((()(()))())((()(()())())())(()(((())(())())()()(()(()((()))((()))))((((()(((()))))((((()(()(()())())()(((()((((())((((()(((()()(())()()()())((()((((((()((()()))()((()))()(()()((())))(((()(((()))((()((()(()))(((()()(()(()()()))))()()(((()(((())())))))((()(((())()(()(())((()())))((((())))(()(()(()())()((()())))(((()((()(())()()((()((())(()()((())(())()))()))((()(())()))())(((((((()(()()(()(())())))))))(()((((((())((((())((())())(()()))))()(())(()())()())((())(()))))(()))(()((()))()(()((((((()()()()((((((((()(()(())((()()(()()))(())()())()((())))()))()())(((()))(())()(())()))()((()((()(()()())(())()()()((())())))((()()(()()((()(())()()())(((()(()()))))(())))(()(()())()))()()))))))()))))((((((())))())))(()(())())(()())))))(()))()))))))()((()))))()))))(()(()((()())())(()()))))(((())()))())())())(((()(()()))(())()(())(())((((((()()))))((()(()))))))(()))())(((()()(()))()())()()()())))))))))))))(())(()))(()))((()(())(()())(())())(()())(())()()(()())))()()()))(())())()))())())(())((())))))))(())))(())))))()))))((())(()(((()))))(()))()((()(())))(()())(((((()))()())()()))))()))))()))())(()(()()()))()))))))((()))))))))))()((()))((()(())((())()()(()()))()(()))))()()(()))()))(((())))(())()((())(())(()())()())())))))))())))()((())))()))(()))()()))(((((((()))())(()()))(()()(()))()(()((()())()))))))(((()()()())))(())()))()())(()()))()()))))))))(())))()))()()))))))()))()())))()(())(())))))()(())()()(()()))))())((()))))()))))(()(((((()))))))))())))())()(())()()))))(())))())()()())()()())()(()))))()))()))))))))())))((()))()))()))())))()())()()())))())))(()((())()((()))())))))())()(())((())))))))))))())()())(())())())(()))(()))()))())(()(())())()())()()(()))))(()(())))))))(())))())(())))))))())()()(())())())))(())))))()))()(()())()(()))())())))))()()(()))()))))())))))))))()))))()))))))())()())()()))))()())))())))))))))))()()))))()()(((()))()()(())()))))((()))))(()))(())())))(())()))))))(()))()))))(())())))))()))(()())))))))))))))())))))))))()((()())(()())))))))((()))))(())(())))()(()())())))())())(()()()())))()))))))())))))())()()())))))))))))()()(()))))()())()))((()())(()))))()(()))))))))))()())())(((())(()))))())()))()))()))))))()))))))(()))))()))))()(())))(())))(()))())()()(()()))()))(()()))))))))()))(()))())(()()(()(()())()()))()))))))))(())))))((()()(()))())())))))()))())(()())()()))())))()(()()()()))((())())))())()(()()))()))))))))(()))(())))()))))(()(()())(()))))()())())()))()()))())))))))))))())()))))))()))))))))())))))()))))())(()())))(())()))())())))))()()(()()())(()())))()()))(((()))(()()()))))()))))()))))((())))()((((((()()))))))())))))))))))(((()))))))))))))(())())))))())(()))))))(()))((()))())))()(()((()))()))()))))))))))())()))()(()()))))())))())(())()(()))()))())(()))()))))(()()))()()(())))))()))(())(()(()()))(()()())))))(((()))))))()))))))))))))(())(()))))()())())()()((()()))())))))(()))))())))))))()()()))))))))())))()(((()()))(())))))(((())())))))((()))()(()))(()))))(()())))(()))())))))()))))(())(())))()((()))(())())))()()))()))))))))()))(()()()(()()()(()))())(())()())(((()))(())))))))))(((()())))()()))))))))()(())(()))()((((())(())(()())))()))(((())()()()))((()))(()))())())))())))(()))())()())())(()(())())()()()(())))())(())))(())))(())()))()))(()((()))))))))())(()))))))())(()()))()()))()(()(()())))()()(()((()((((((()))(())))()()()))())()))((()()(()))())((()(()(()))(()()))))()())))()))()())))))))()()((()())(())))()))(()))(())(()))())(()(())))()()))))))(((()(((()()))()(()(())())((()()))()))()))()))()(()()()(()))((()())()(())))()()))(((())()()())(())()((()()()()(()(())(()()))()(((((()())))((())))))(()()()))))(((()(())))()))((()((()(())()(()((())))((()())()(()))(((()())()()(()))(())(((()((()())()((())()())(((()()))((()((())(()))(()())(()()()))((()))(())(()((()()())((()))(())))(())(())(())))(()())))(((((()(()(((((()())((((()(()())(())(()()(((())((()(((()()(((()()((((((())))())(()((((((()(()))()))()()((()((()))))()(()()(()((()()))))))(((((()(((((())()()()(())())))))))()))((()()(())))(())(()()()())))))(()((((())))))))()()(((()(()(()(()(()())()()()(((((((((()()())()(()))((()()()()()(((((((()())()((())()))((((((()(()(()(()())(((()(((((((()(((())(((((((((())(())())()))((()(()))(((()()())(())(()(()()(((()(())()))())))(())((((((())(()()())()()(((()(((())(()(((())(((((((()(((((((((()))(())(()(()(()))))((()))()(())())())((()(()((()()))((()()((()(())(())(()((())(((())(((()()()((((((()()(())((((())()))))(())((()(()((())))(((((()(()()())())((())())))((())((()((()()((((((())(((()()(()())())(()(()))(()(()))())())()(((((((()(((()(())()()((())((()(()()((()(()()(((((((((((())((())((((((())((()((((()(()((((()(((((((())()((()))))())()((()((((()(()(((()((()())))(())())(((()(((())((((((()(((((((((()()(())))(()(((((()((((()())))((()((()((()(()()(((())((((((((((((()(((())(()(((((()))(()()(()()()()()()((())(((((((())(((((())))))())()(()()(()(()(((()()(((((())(()((()((()(((()()((()((((())()))()((((())(())))()())(((())(())(()()((()(((()()((((((((((()()(()())())(((((((((())((((()))()()((((())(()((((()(((())())(((((((((((()((((())))(())(()(((()(((()((())(((((()((()()(()(()()((((((()((((()((()(()((()(()((((((()))))()()(((((()((()(()(())()))(())(((((((()((((()())(()((()((()(()))())))(())((()))))(((((((()()()())(()))(()()((()())()((()((()()()(()(()()))(()())(())(((((()(((((((((((()((()(((()(((((((()()((((((()(((((()(()((()(((((())((((((()))((((())((()()((())(((())()(((((()()(((((()((()(()(((((((()(((((()((()((()((())(())((())(()))()()))(()()(()(()()(((((((()(((()(((())()(((((()((((((()())((((())()((()((()(()()())(()))((((()()((((((()((()(()(()((((()((()((())((((((()(()(())((((((()((((((((((()((())()))()(()(()(((((()()()))((())))()(()((((((((((((((()(((()((((()((())((()((()(((()()(()(((()((())(()()())))()(()(()(((((()()(()(()((((()(((((())()(()(()))(((((()()(((()()(())((((((((((((((())((())(((((((((((())()()()(())()(()(()(((((((((())(((()))(()()())(()((((()(())(((((()())(())((((((((())()((((()((((((())(()((()(())(((()((((()))(((((((((()()))((((()(())()()()(())(()((())((()()))()(((())(((((())((((((()()))(((((((((()((((((())))(((((((()((()(()(())))())(()(()))()(((((()())(()))()(()(())(((()))))())()())))(((((()))())()((()(()))))((()()()((((((()))()()((((((((())((()(()(((()(()((())((()())(()((((())(()(((()()()(()(()()))())())((((((((((())())((()))()((())(())(())))())()(()()(())))())(()))(((()(()()(((()(((())))()(((()(())()((((((())()))()))()((((((()(()(((((()())))()))))())()()(((()(((((())((()()(()((()((()(()(()(())))(()()()()((()(())(((()((()))((((()))())(())))())(()))()()()())()))(((()()())()((())))(())(()()()()(()())((()(()()((((())))((()((()(())((()(()((())()(()()(((()())()()())((()))((())(((()()(())))()()))(((()((())()(((((()())(())((())()())())((((((()(()(((((()))(()(‘;

Now solve it.

Your turn.

Here come my solutions, so don’t scroll down until you’re ready.

Python

I’ve been trying to learn Python, so this was a good chance to practice. Day 1 is fairy simple in Python, since I can do a .count of a string. In my case, I made a function that takes the input and does a count of a particular string.
```
def calculate_floor(directions):
    print(str(directions.count('(') - directions.count(')')))
```
This function takes the input and counts the number of open parenthesis, an up, and then subtracts the count of the close parenthesis, the down. I print that, and with the input given on the site, this gives me the correct answer.

PowerShell

I have been trying to improve my PowerShell skills, and this doesn’t really help with lots of the types of things I do in PoSh, but it does help me learn a bit more about the language and practice some code.

In this case, I take a similar approach, which may not be the best. I start by converting the input to an array and then using Where-Object to look for the open parenthesis. I do the same for the close, and then subtract. I don’t know if I could do this in one statement, and didn’t research much. What I found wasn’t helpful, but I was able to solve the puzzle. Perhaps someone will tell me if I can assign two variables at once with different counts.

I did try RegEx, but coulnd’t get it to work, so I moved on. Perhaps I’ll go back to that. Input abbreviated.

$input = ‘()(((()))(()()()((((()(((())(()(()((((((()(()(((()’

$up = ($input.ToCharArray() | Where-Object {$_ -eq ‘(‘} ).Count
$down = ($input.ToCharArray() | Where-Object {$_ -eq ‘)’} ).Count

Write-Host(“Up:” + $up)
Write-Host(“Down:” + $up)
Write-Host(“Final:” + ($up-$down))

T-SQL

This was interesting to me since some of the puzzles I did in Python (I was 6 ahead when I tried new languages), required some parsing. In this case, I decided that I’d do some replacement. I thought that I wanted to count all open parens. How could I do this?

The easy way is to pull out the opens, or remove the closes. REPLACE() does this, so my up was a CTE

WITH UpFloors (UpCount)
AS
( SELECT LEN(REPLACE(@input, ‘)’, ”)) ‘UpFloors’)

Then I did the same for the closes.

WITH UpFloors (DownCount)
AS
( SELECT LEN(REPLACE(@input, ‘(‘, ”)) ‘DownFloors’)

Now I can put them together.

WITH UpFloors (UpCount)
AS
( SELECT LEN(REPLACE(@input, ‘)’, ”)) ‘UpFloors’)
,
DownFloors (DownCount)
AS
( SELECT LEN(REPLACE(@input, ‘(‘, ”)) ‘DownFloors’)
SELECT UpFloors.UpCount – DownFloors.DownCount
FROM UpFloors, DownFloors
January 7, 2016