Walking Through Advent of Code Day 8 Part 2

With Day 8 part 1 being all about traversing tables, I’m sure our little friends the elves will find a new way to make this harder for us.

First, we find out that we’re now starting with multiple positions – anything that ends with an A – and finishing anywhere that ends in a Z.

To make this happen, we’re going to want to create another table that will have all of our positions that end with the letter A.

CREATE TABLE #AllThatEndWithA
( Position char(3) NOT NULL,
  Loops bigint NOT NULL)
;

INSERT INTO #AllThatEndWithA
SELECT Starter, 0
FROM #ThePath
WHERE Starter LIKE '%A';

Now that we have all of our starting positions we need to make 2 additional changes:

1. Change our WHILE loop to check for “RIGHT(@CurrPos, 1) != ‘Z'” — This gives us an easy out since we don’t know for sure which of the paths that end with Z will we hit first.
2. We have to create a loop around the entire WHILE loop mentioned above so that we can find the number of paths traversed for each of the positions. Yes, that’s the reason for the Loop column in the #AllThatEndWithA table. At the end of each loop, we’ll UPDATE the row with the value from @CurrStep.

Once we have those answers, we’ll need to find the Lowest Common Multiple (LCM) of the answers we found in the #AllThatEndWithA table. (And you thought you’d never use the LCM function outside of math class!)

To find the Least Common Multiple in SQL Server, we need to create 2 user defined functions – neither of which are in SQL Server natively.

IF OBJECT_ID (N'GreatestCommonDivisor') IS NOT NULL
   DROP FUNCTION dbo.GreatestCommonDivisor
GO

CREATE FUNCTION dbo.GreatestCommonDivisor (@a bigint, @b bigint)
RETURNS bigint
WITH EXECUTE AS CALLER
AS
BEGIN
    DECLARE     @c INT
 
    IF @a IS NULL OR @b IS NULL OR (@a = 0 AND @b = 0) 
           RETURN NULL
 
    IF @a = 0 OR @b = 0
           RETURN ABS(@a) + ABS(@b)
 
    IF ABS(@a) < ABS(@b)
           SELECT  @c = ABS(@a),
                   @a = ABS(@b),
                   @b = @c
    ELSE
           SELECT  @a = ABS(@a),
                   @b = ABS(@b)
 
    SET @c = @a % @b
 
    WHILE @c > 0
          SELECT  @a = @b,
                  @b = @c,
                  @c = @a % @b
 
    RETURN      @b
END
GO

IF OBJECT_ID (N'LeastCommonMultiple') IS NOT NULL
   DROP FUNCTION LeastCommonMultiple
GO

CREATE FUNCTION dbo.LeastCommonMultiple (@a bigint, @b bigint)
RETURNS bigint
WITH EXECUTE AS CALLER
AS
BEGIN
	DECLARE @C bigint
	SELECT @C = dbo.GreatestCommonDivisor(@A, @b)
	
	RETURN (@A * @B) / @C;
END
GO

Yes, for those of you who reviewed the two user defined functions, we’re creating the LeastCommonMultiple function – which is what we’re looking for – and the GreatestCommonDivisor function. I will not bore you with the Euclidean geometry that it took to get to these functions, but it was definitely a fun challenge.

Now, to get through our results, we simply loop through the answers in our temp table.

DECLARE @A bigint, 
	@B bigint, 
	@BPosition char(3),
	@Answer bigint

SELECT @A = Loops FROM #AllThatEndWithA WHERE Position = 'AAA'
SELECT TOP 1 @B = Loops, @BPosition = Position FROM #AllThatEndWithA WHERE Position != 'AAA'
SET @Answer = dbo.LeastCommonMultiple(@A, @B)

DELETE FROM #AllThatEndWithA WHERE Position IN ('AAA', @BPosition)

WHILE EXISTS (SELECT 1 FROM #AllThatEndWithA)
BEGIN
	SELECT TOP 1 @B = Loops, @BPosition = Position FROM #AllThatEndWithA
	SET @Answer = dbo.LeastCommonMultiple(@Answer, @B)
	DELETE FROM #AllThatEndWithA WHERE Position = @BPosition
END
SELECT @Answer

First, we found the Least Common Multiple of AAA and some other position. We then took that answer and found the Least Common Multiple of that and the next value. We loop through the table until we’re done.

And that, my friends, is enough math for the day.