Advent of Code: Day 3

Reading Time: 4 minutes

It’s day 3 of the Advent of Code, so day 3 of my set-based approach to solving the challenges.

The Challenge

The challenge today was the Spiral Memory challenge.

The first challenge was, given a number, to determine the number of steps from the centre of the grid to that number. It’s pretty clear that this problem is not really suited to a set-based approach, but I did try to use it anyway.

The Solution (download)

The first thing I noticed was that the diagonal starting in the middle of the grid, and going down and right, was the squares of the odd numbers (1…9…25…). I decided to use this fact to determine which “spiral” my puzzle input could be found in. In my case, the answer was 515. This meant that my square would extend 257 steps in each direction from the starting block. I decided to work with the co-ordinates of each square, starting at (0,0).

declare @puzzleinput bigint = 265149

declare @gridsize int,
 @startvalue int

select top 1 @gridsize = Number, 
             @startvalue = POWER(LAG(Number,1,0) over (order by Number) ,2)
from Utility.dbo.TallyTable
where Number % 2 = 1
and Number - 1 < SQRT(@puzzleinput)
order by Number desc

declare @extreme int = (@gridsize - 1) / 2

I created a table to store the co-ordinates of the number in the square. I then built only the outside spiral, by using my tally table again (see Day 1 for more info). The right hand side of the grid had a y-coordinate of 257, and starts with an x-coordinate of 257 and moves to -257. The other sides all follow a similar pattern, having one static coordinate, and one which moves. By starting with the square of the previous odd number (513), I could easily work out what position my puzzle input was found at. Calculating the distance to (0,0) was the pretty simple, it was just the absolute value of my x-coordinate plus the absolute value of the y-coordinate.

declare @coordtable table (x int, y int, sqno int identity(1,1) )

-- insert the right hand side of the block

insert into @coordtable
select Number - @extreme - 1, @extreme 
from Utility.dbo.TallyTable
where Number between 1 and @gridsize - 1
order by Number desc

-- insert the top of the block

insert into @coordtable
select -1 * @extreme , Number - @extreme - 1
from Utility.dbo.TallyTable
where Number between 1 and @gridsize - 1
order by Number desc

-- insert the left hand side of block

insert into @coordtable
select Number - @extreme, -1 * @extreme
from Utility.dbo.TallyTable
where Number between 1 and @gridsize - 1
order by Number asc

-- insert the bottom of block

insert into @coordtable
select @extreme, Number - @extreme
from Utility.dbo.TallyTable
where Number between 1 and @gridsize - 1
order by Number asc

SELECT abs(x) + abs(y) as Answer1
FROM @coordtable
where sqno + @startvalue = @puzzleinput

So that worked pretty well, and it unlocked part 2 of the question.

And… the question needed a totally different solution. Where the previous part only required 1 value, this part needed to know all the cells around it. So I would have to change my method entirely.

declare @answer2 int

declare @x int = 0, 
 @y int = 0,
 @dir char(1) = 'E'

declare @move table
(
 dir char(1),
 x int,
 y int
)

set @extreme = 1

insert into @move
values
('N',0,-1),
('W',-1,0),
('S',0,1),
('E',1,0)

I used a similar idea, but I couldn’t insert entire rows at once, I had to load each value individually so I could calculate the value of the cells around it. The only benefit that set-based thinking was that it was super easy to calculate the value of the blocks that were already “filled”.

while @puzzleinpupt > (select max(val) from @coordtable2) 
begin

if @x = @extreme and @y = @extreme set @extreme += 1
 if @dir = 'E' and @x = @extreme set @dir = 'N'
 if @dir = 'N' and @y = -1 * @extreme set @dir = 'W'
 if @dir = 'W' and @x = -1 * @extreme set @dir = 'S'
 if @dir = 'S' and @y = @extreme set @dir = 'E'

select @x = @x + x,
 @y = @y + y
 from @move
 where dir = @dir

insert into @coordtable2
 select @x, @y, sum(val)
 from @coordtable2
 where x between @x - 1 and @x + 1
 and y between @y - 1 and @y + 1

end

select max(val) as Answer2
from @coordtable2

I haven’t thought of a better method to solve the problem, but this still feels very clunky. If you have a better solution, please feel free to point it out to me in the comments.

Hopefully tomorrow is better suited to set based thinking. (Spoiler – it is)

One comment

Leave a Reply

Your email address will not be published. Required fields are marked *