Advent of Code 2018 Day 5

As I explained ina recent post, I’m participating in this year’s Advent of Code challenge, with the twist of doing the challenges in T-SQL. In case you don’t know what “Advent of Code” is, Eric Wastl ( t ) created it for the purpose of, as Eric describes 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.

The full explanation of “Advent of Code” is at https://adventofcode.com/2018/about . You can see my other posts in the “Advent of Code” category.

We started off with someone going back in time and altering Santa’s past. You went back in time to correct it, but the device to fix the problems hadn’t been calibrated before sending you on your way. You calibrated the device on Day 1. On Day 2, we located the boxes in the warehouse where the new (500 years ago) Santa suit material is. We figured out the best time to sneak into the Santa suit lab on Day 4.

Day 5 Part 1

In Day 5 , we find ourselves working with the polymers of the new Santa suit. A polymer (the input file), consists of units, represented by upper and lower case letters. Adjacent units of the same letter, but of different polarity (case), cancel each other out. This may lead to other units that can then cancel each other out. The goal is to reduce the polymer to as small as possible, and report back the reduced size.

Perform a case-sensitive search/replace for each letter of the alphabet. The search is for a pair of the same letter, where one is upper case, and the other is lower case. Recursively perform this operation until the string can no longer be reduced.

In my opinion, the key part to this is that the operation needs to be performed recursively. I can think of only two ways to recursively perform an operation in SQL Server:

A recursive common table expression (cte). Using a WHILE loop.

I don’t like using either of these mechanisms in SQL Server they both perform operations in a “Row-By-Agonizing-Row” method, instead of a more set-based approach. However, set-based recursion usually performs extremely poorly. So, I’m going to use a while loop.

Day 5 Part 1 Recursive replaces

The code for this operation is relatively short. As you may have noticed from previous days, I like to do the code is small pieces where they can be explained. Today, I’ll break from that and show all of the code, and then explain it.

DECLARE @dataVARCHAR(MAX), @Letters CHAR(26)= 'ABCDEFGHIJKLMNOPQRSTUVWXYZ', @SizeINTEGER, @NewSize INTEGER = 0, @LoopINTEGER = 0; SELECT@data = FileData FROM OPENROWSET(BULK 'D:\AdventOfCode\2018\Input\Day05.txt', SINGLE_CLOB) dt(FileData); SET @Size = LEN(@data); RAISERROR('Loop %d; Size %d', 10, 1, @Loop, @Size) WITH NOWAIT; WHILE @Size <> @NewSize BEGIN SET @NewSize = @Size; SELECT@data = REPLACE(@data COLLATE SQL_Latin1_General_CP1_CS_AS, ca.UpperLtr + ca.LowerLtr, '') FROM (VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11),(12),(13),(14),(15),(16),(17),(18),(19),(20),(21),(22),(23),(24),(25),(26)) dt(N) CROSS APPLY (VALUES (UPPER(SUBSTRING(@Letters, dt.N, 1)), LOWER(SUBSTRING(@Letters, dt.N, 1)))) ca(UpperLtr, LowerLtr) SELECT@data = REPLACE(@data COLLATE SQL_Latin1_General_CP1_CS_AS, ca.LowerLtr + ca.UpperLtr, '') FROM (VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11),(12),(13),(14),(15),(16),(17),(18),(19),(20),(21),(22),(23),(24),(25),(26)) dt(N) CROSS APPLY (VALUES (UPPER(SUBSTRING(@Letters, dt.N, 1)), LOWER(SUBSTRING(@Letters, dt.N, 1)))) ca(UpperLtr, LowerLtr) SET @Size = LEN(@data); SET @Loop += 1; RAISERROR('Loop %d; Size %d', 10, 1, @Loop, @Size) WITH NOWAIT; END SELECT @Loop AS Loops, @Size AS Size;

After declaring and initializing some variables, load the file into a variable. Since this example doesn’t have rows of data, I don’t need to split the data into rows. Store the size of the data so that we can break out of the WHILE loop.

Entering the WHILE loop, we do two case-sensitive replaces. By default, SQL Server is case-insensitive. To do a case-sensitive replace, we specify a case-sensitive collation to work with. In the collation used (“SQL_Latin1_General_CP1_CS_AS”), the “_CS_” identifies that this is a case-sensitive collation.

In the SELECT statements that do the replace, I’m using a table value constructor to create a set of numbers. I know that I’ll only be working with 26 letters, so I create a table with those 26 numbers. Next, the CROSS APPLY converts the numbers into upper-case and lower-case letters. Then the REPLACE function searches for these characters. The first replace looks for Upper\Lower, and the second looks for Lower\Upper.

After performing the replaces, we get the new size of the string. If it’s the same size as what we started the loop with, then the WHILE loop ends. Finally, we return the ending size of the string. When working with recursion, you MUST have a break, or it will run forever.

Day 5 Part 2

In part 2, we need to identify which unit type could be removed from the polymer to reduce the polymer to the lowest size. This entails removing all occurrences of a unit (upper and lower case) from the polymer, and then running the process to see which unit produces the smallest polymer.

I added another WHILE loop to cycle through each letter. The new WHILE loop goes through each letter, removing all occurrences of it, before starting the recursive replace. At the end of the new loop, store the polymer size. After processing all letters, we see which letter (when removed) produces the smallest polymer.

DECLARE @dataVARCHAR(MAX), @Letters CHAR(26)= 'ABCDEFGHIJKLMNOPQRSTUVWXYZ', @SizeINTEGER, @NewSize INTEGER = 0, @LoopINTEGER = 0, @LetterCHAR(1) = 'A', @data2 VARCHAR(MAX); SELECT@data2 = FileData FROM OPENROWSET(BULK 'D:\AdventOfCode\2018\Input\Day05.txt', SINGLE_CLOB) dt(FileData); DECLARE @Results TABLE (Letter CHAR(1) PRIMARY KEY, Size INTEGER); WHILE ASCII(@Letter) <= ASCII('Z') BEGIN SET @data = REPLACE(@data2, @Letter, ''); SET @NewSize = 0 SET @Size = LEN(@data); SET @Loop = 0; RAISERROR('Letter: %s; Loop %d; Size %d', 10, 1, @Letter, @Loop, @Size) WITH NOWAIT; WHILE @Size <> @NewSize BEGIN SET @NewSize = @Size; SELECT@data = REPLACE(@data COLLATE SQL_Latin1_General_CP1_CS_AS, ca.UpperLtr + ca.LowerLtr, '') FROM (VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11),(12),(13),(14),(15),(16),(17),(18),(19),(20),(21),(22),(23),(24),(25),(26)) dt(N) CROSS APPLY (VALUES (UPPER(SUBSTRING(@Letters, dt.N, 1)), LOWER(SUBSTRING(@Letters, dt.N, 1)))) ca(UpperLtr, LowerLtr) SELECT@data = REPLACE(@data COLLATE SQL_Latin1_General_CP1_CS_AS, ca.LowerLtr + ca.UpperLtr, '') FROM (VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11),(12),(13),(14),(15),(16),(17),(18),(19),(20),(21),(22),(23),(24),(25),(26)) dt(N) CROSS APPLY (VALUES (UPPER(SUBSTRING(@Letters, dt.N, 1)), L

• ### 人工智能之生命3.0：欧米茄与普罗米修斯（2）成为全世界最大的媒体帝国

1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责；
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性，不作出任何保证或承若；
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。