Day 20 spoiler
Similar to Kem’s method.
First, traverse the grid to generate the running step count (aka picoseconds) for each point on the path, and store them in an array.
Then, for the part 1 solution, because the cheat move was only two steps, I simply looked at each internal wall element and took the difference in path length values on opposite sides of each of these wall elements. This was quick to code and ran quite fast, but wouldn’t work for part 2 where the cheat distance was a range of 2…20.
So for part two, I generated an array of all possible x,y offsets for distances 2…20. (It’s general enough that by setting variable nCheatMax to either 2 or 20, it solves both parts 1 and 2.)
'Generate list of all possible relative final positions for the cheat moves
var cListR() As Integer
var cListC() As Integer
for a as Integer = 0 to nCheatMax 'number of steps in one direction
for b as Integer = 1 to nCheatMax 'number of steps in orthogonal direction
if a=1 and b=1 then Continue 'skip the single diagonal jump; it accomplishes nothing
if a+b>1 and a+b<=nCheatMax then 'move is in the range of 2..nCheatMax
cListR.Add a
cListC.Add b
cListR.Add -a
cListC.Add -b
cListR.Add b
cListC.Add -a
cListR.Add -b
cListC.Add a
end if
next b
next a
This generates all final offsets without duplicates. For part 2 there are 832 of them.
Then for each point on the path, try each of the offsets, and calculate the running distance difference for each one.
'For each position on the path, try each cheat jump
var chtTotal As Integer = 0
var testPt As new Point2D(0,0,gRows,gCols)
var sPt As new Point2D(0,0,gRows,gCols)
for pPos as Integer = 0 to pathListR.LastIndex 'loop for path position
sPt.SetRC(pathListR(pPos),pathListC(pPos))
var baseScore As Integer = score(pathListR(pPos),pathListC(pPos))
for ic as Integer = 0 to cListR.LastIndex 'loop for cheat offfset
testPt.SetRC(pathListR(pPos)+cListR(ic),pathListC(pPos)+cListC(ic))
if testPt.iGridDataN(grid,0,0,-1) = path then
var jmpSize As Integer = abs(cListR(ic)) + abs(cListC(ic))
var chSavings As Integer = score(testPt.R,testPt.C) - baseScore - jmpSize
if chSavings > 99 then 'Saves 100 picosecs or more, so add to the count
chtTotal = chtTotal+1
end if
end if
next ic
next pPos
Again, I used my increasingly useful Point2D class which handles bounds checking automatically, so that I don’t have to worry whether the jump offset puts the test position out of bounds.
Part 2 runs in 2.5 seconds on my 2015 MacBook.