source: //www.brockpress.com/wp-content/uploads/2014/11/RudolphandSanta.jpg
In my previous post, I introduced you to the Advent of Code programming challenge, and explained how I’m going through the days, solving both parts of each puzzle. Continuing on, today we have day 19. In this challenge, Rudolph is sick and needs some medicine. Since Rudolph’s biology is different from other reindeer, he needs some specialized medicine. Therefore, Santa has ensured that the North Pole has a specialized Red-Nosed Reindeer nuclear fusion/fission plant, which is capable of constructing any Red-Nosed Reindeer molecule that you might need. This plant works by starting with an input molecule and then doing a series of replacements, one per step, until it has the right molecule.
Prior to using the machine, it needs to be calibrated. This involves determining the number of molecules that can be generated in one step from a given starting point. For instance, assume that the machine can make the following replacements:
H => HO
H => OH
O => HH
If you are starting with the molecule HOH, then the following replacements can be made:
- Replace the first H with HO to get HOOH.
- Replace the second H with HO to get HOHO.
- Replace the first H with OH to get OHOH.
- Replace the second H with OH to get HOOH.
- Replace the O with HH to get HHHH.
Today’s puzzle has an input file that lists all of the replacements that the machine can make, followed by the medicine molecule used to calibrate the machine. For Part 1, we need to determine how many unique molecule combinations can be made by doing just one replacement of all of the combinations. In the above example, there are 5 replacement molecules, but there are only 4 distinct molecules created (HOOH can be created two different ways).
The first challenge we run into when loading this file is that the input file has both the replacements and the medicine molecule. These need to be separated. After splitting the line on the carriage returns, the code then looks to see if the line has the “=>” string within the line. If so, then this line is a replacement line; otherwise it is the medicine molecule that we need. Since we will need to be extracting out from the replacement lines the string to be replaced, and the string to be replaced with, the code gets the position of the “=>” for further use. This information will be stored into a temporary table. Finally, get the line without the “=>” for the medicine molecule:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
IF OBJECT_ID('tempdb.dbo.#temp') IS NOT NULL DROP TABLE #temp; CREATE TABLE #temp ( ItemNumber INTEGER , Item VARCHAR(8000) , Pos TINYINT ); DECLARE @MedicineMolecule VARCHAR(8000); INSERT INTO #temp SELECT ds.ItemNumber, ds.Item, ca1.Pos FROM OPENROWSET(BULK 'D:\AdventOfCode\Day19.txt', SINGLE_CLOB) InputFile(FileText) CROSS APPLY Sandbox.dbo.DelimitedSplit8K(REPLACE(InputFile.FileText, CHAR(10), ''), CHAR(13)) ds CROSS APPLY (VALUES (CHARINDEX('=>', ds.Item))) ca1(Pos) WHERE ds.Item > ''; SELECT @MedicineMolecule = Item FROM #temp WHERE Pos = 0; |
In the next step, we need to step through each replacement line, and replace just one occurrence of the characters to be replaced with the replacement characters. If I were to use the REPLACE function, then all occurrences of the characters to be replaced would be replaced in that line. Since we need to do just one at a time, the code needs to walk through the medicine molecule string to find the characters to be replaced, and then use the STUFF function to replace those characters with the replacement characters. I’ll be using the CHARINDEX function to find the next occurrence of the characters to be replaced, using the optional third parameter to specify the starting position within the string in order to find the next occurrence. Additionally, this is a case-sensitive string search, so I need to use the COLLATE option to specify that the medicine molecule string is of a collation that is case sensitive. After each replacement, the new medicine molecule string is stored into a table, and when all of the replacements have been performed, the code then will get the distinct count of all of these medicine molecules, using the DISTINCT keyword in the COUNT function. Since we need to work on each input line one at a time, and then to do the replacements one at a time upon the medicine molecule, I will be using a cursor to go line by line, and a nested WHILE loop to go through the medicine molecule. The cursor shreds the line into the Characters To Be Replaced and the Replacement Characters:
|
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
DECLARE @Molecules TABLE ( Molecule VARCHAR(MAX), -- remaining columns are for testing / debug purposes CharsToReplace VARCHAR(100), ReplacementChars VARCHAR(100), Pos INTEGER ); /* declare cursor variables */ DECLARE @CharsToReplace VARCHAR(50), @ReplacementChars VARCHAR(50), @Pos INTEGER; DECLARE cur CURSOR FAST_FORWARD READ_ONLY FOR SELECT CharsToReplace, ReplacementChars FROM #temp CROSS APPLY (VALUES (LEFT(Item, Pos-2), SUBSTRING(Item, Pos + 3, 8000))) ca2(CharsToReplace, ReplacementChars) WHERE Pos > 0; OPEN cur FETCH NEXT FROM cur INTO @CharsToReplace, @ReplacementChars; WHILE @@FETCH_STATUS = 0 BEGIN SET @Pos = CHARINDEX(@CharsToReplace, @MedicineMolecule COLLATE Latin1_General_CS_AS); WHILE @Pos > 0 BEGIN INSERT INTO @Molecules (Molecule, CharsToReplace, ReplacementChars, Pos) VALUES (STUFF(@MedicineMolecule, @Pos, LEN(@CharsToReplace), @ReplacementChars), @CharsToReplace, @ReplacementChars, @Pos); SET @Pos = CHARINDEX(@CharsToReplace, @MedicineMolecule COLLATE Latin1_General_CS_AS, @Pos+1); END; FETCH NEXT FROM cur INTO @CharsToReplace, @ReplacementChars; END; CLOSE cur; DEALLOCATE cur; SELECT COUNT(DISTINCT Molecule) FROM @Molecules; |
Part 1 has solved the issue for the calibration of the machine. For Part 2, we need to build the molecule. To build the molecule, we start with “e”, and run through the steps until the desired molecule has been created. For Part 2, starting with “e”, what is the minimum number of steps required to build the supplied medicine molecule using the same replacement list? At this point, I haven’t figured out how to solve this part, but I intend to come back to it and finish this up when time permits.
Well, I did get Part 1 finished. Come back tomorrow for the solutions for Day 20, and I’ll update this post when Part 2 is finished.
