source: //www.myphillyalive.com/wp-content/uploads/2013/11/A-Elves-having-fun-Photo-by-Mark-Garvin.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 20. In this challenge, it seems that Santa’s elves have too much time on their hands. To keep them busy, he is having them deliver presents. By hand. Door to door.
Santa sends the elves down a street. But this isn’t an ordinary street… this street is infinitely long. The houses on this street are sequentially numbered, starting with one. The elves (which is seems there is also an infinite supply of) are also numbered, starting with one. Each elf goes to every x house of the same number as the elf. In other words, elf #1 stops at every house. Elf #2 stops at every even numbered house. Elf #3 stops at every third house. And so on. At each stop, the elf leaves 10 times his number of presents. So elf 1 leave 10 presents, elf 2 leaves 20 presents, and so on.
For Part 1 of this puzzle, what is the lowest numbered house to receive at least a certain number of gifts? For me, I need to find out the lowest numbered house with 36 million gifts (and I’m left wondering just how long it would take to unwrap all of those presents).
To solve this problem, we need to determine what elves would be stopping at a particular house. We then need to sum up the elvf # times 10 for all of those elves, and see if it is at least the specified number. To determine if an elf would be stopping at a house, the elf’s number needs to divide evenly into the house number. In other words, we are looking for all of the factors of a number. In SQL Server, we can determine whether a number can be evenly divided into another with the modulo operator. This function returns the remainder, so we just need to look for results where the remainder is zero.
My first attempt to solve this is to use a set-based approach. In this approach, I use a virtual tally table, which is then cross-joined to itself (once for the sequential house numbers, and once for the elf numbers). The code checks that the elf number would go to the house number with the modulo operator, and it reduces the work by ensuring the elf number is less than or equal to the house number.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
WITH Tens (N) AS (SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1), Hundreds(N) AS (SELECT 1 FROM Tens t1, Tens t2), Millions(N) AS (SELECT 1 FROM Hundreds t1, Hundreds t2, Hundreds t3), Tally (N) AS (SELECT ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM Millions) ,cte AS ( SELECT Houses.N AS HouseN, Elves.N AS ElfN FROM Tally Houses CROSS JOIN Tally Elves WHERE Houses.N % Elves.N = 0 AND Elves.N <= Houses.N ) SELECT TOP (1) HouseN, SUM(ElfN * 10) AS Presents FROM cte GROUP BY HouseN HAVING SUM(ElfN * 10) >= 36000000 ORDER BY HouseN; |
I did mention that this was my first attempt. This would be because this code locked up my laptop overnight for over 12 hours, and still didn’t complete (once I was able to determine the actual number, I came back to this and in running the code for just 1000 houses that included the correct house, this still took almost 90 seconds). Obviously, this is not a desired solution. So let’s look into an alternative.
In testing out this code, I found that this runs fine for an individual house. So I next decided to iterate through the houses, and to perform the determination of which elves go to that house in a set-based manner. The resulting code is:
|
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 |
DECLARE @HouseNbr INTEGER = 800000, @Presents INTEGER; WHILE @HouseNbr <= 1000000 -- limit of the tally table BEGIN IF @HouseNbr % 1000 = 0 RAISERROR('House Number: %i', 10, 1, @HouseNbr) WITH NOWAIT; WITH Tens (N) AS (SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1), Hundreds(N) AS (SELECT 1 FROM Tens t1, Tens t2), Millions(N) AS (SELECT 1 FROM Hundreds t1, Hundreds t2, Hundreds t3), Tally (N) AS (SELECT ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM Millions) SELECT @Presents = SUM(N*10) FROM Tally WHERE @HouseNbr % N = 0 AND N <= @HouseNbr ; IF @Presents >= 36000000 BEGIN SELECT @HouseNbr 'House Number', @Presents 'Presents'; BREAK; END; SET @HouseNbr += 1; END; |
In this newer incarnation of the code, the @HouseNbr variable is used to iterate through the house numbers. To keep track of the progress, I print out messages (with the RAISERROR function). At this point, patience is a virtue as you need to wait for the iteration to find the first house number that receives the specified number of presents. But at least while you wait, the laptop isn’t locked up and you can continue other work while waiting. And once the code returns the answer, you can enter it and move on to Part 2.
In Part 2, the elves will only stop at 50 houses each; however they will leave 11 presents at each house. With this new criteria, what is the new house number with this minimum number of presents?
Well, this is pretty straightforward change. Since each elf is now dropping of 11 presents instead of 10, change the 10 to 11 in line 13. And since each elf is only going to 50 houses, just add a new predicate where the Elf # * 50 is greater than or equal to the house number. Replace likes 13-16 of the above code with these 5 lines of code:
|
13 14 15 16 17 |
SELECT @Presents = SUM(N*11) FROM Tally WHERE @HouseNbr % N = 0 AND N <= @HouseNbr AND N * 50 >= @HouseNbr -- elf only delivers to 50 houses |
And there is my solution for day 20. I would love to find a better way to solve this – if you know of a way, please share it in the remarks.
