I used a recursive method to perform each operator on the subsequent values, which, now that I type it, is harder to describe than to show.
Private Shared Function TestValues(values() As Integer, index As Integer, incoming As Integer, testValue As Integer) As Boolean
if index > values.LastIndex then
return incoming = testValue
end if
return TestValues( values, index + 1, incoming + values( index ), testValue ) or _
TestValues( values, index + 1, incoming * values( index ), testValue )
End Function
I call this as:
if TestValues( values, 1, values( 0 ), testValue ) then ...
Part 2 spoiler
This is essentially the same thing but has to consider the possibility of concatenation.
Private Shared Function TestValues2(values() As Integer, index As Integer, incoming As Integer, testValue As Integer) As Boolean
if index > values.LastIndex then
return incoming = testValue
end if
var thisValue as integer = values( index )
if TestValues2( values, index + 1, incoming + thisValue, testValue ) or _
TestValues2( values, index + 1, incoming * thisValue, testValue ) then
return true
end if
var exp as integer = log( thisValue ) / log( 10 ) + 1
var mult as integer = 10^exp
var shiftedIncoming as integer = incoming * mult
var sendToNext as integer = shiftedIncoming + thisValue
return TestValues2( values, index + 1, sendToNext, testValue )
End Function
I didn’t use recursion. I just generated every permutation of the operations in a loop. I love a puzzle where both parts can be solved by changing a single variable (nOps).
Part 2 took about 9 seconds on my ancient MacBookPro.
Public Sub main()
LoadData
var inpData() As String = Split(pzlData,EndOfLine)
var lg10 As Double = log(10)
for pzlPart as Integer = 1 to 2
var validCount As Integer = 0
for i as Integer = 0 to inpData.LastIndex
var tempS() As String = inpData(i).Split(":")
var result As Integer = tempS(0).ToInteger
var operandStr() As String = tempS(1).trim.Split(" ")
var operand() As Integer
var nOps As Integer = pzlPart+1 '(2 or 3 for pt1 & pt2 respectively)
for j as Integer = 0 to operandStr.LastIndex
operand.Add operandStr(j).ToInteger
next j
var comboCount As Integer = nOps^(operand.LastIndex)-1
for iCombo as Integer = 0 to comboCount
var acc As Integer = operand(0)
for op as Integer = 1 to operand.LastIndex
var q As Integer = (iCombo\(nops^(op-1))) mod nOps
Select case q
case 0 'multiply
acc = acc * operand(op)
case 1 'add
acc = acc + operand(op)
case 2 'concat
var ndigits As Integer = (Log(operand(op))/lg10)+1
acc = acc*10^ndigits+operand(op)
End Select
if acc>result then exit for op 'acc already bigger than result, so abort
next op
if result = acc then 'success
validCount = validCount+result
exit for iCombo
end if
next iCombo
next i
PrintLine "Part "+pzlPart.ToString+" solution: "+str(validCount)
next pzlPart
End Sub
So I was stumped with day 7 for a while… then finally realized my compiler settings was on 32-bit instead of 64-bit.
What was strange though is that I used UInt64 everywhere, but the two output modes gives difference answers. I would have expected them to give the same answers when using UInt64 types.
Your recursive solution is very elegant Kem. Couldn’t you just have changed it as follow for part 2 though?
Spoiler Day 7 - Part 2
Public Function TestValues(values() As UInt64, index As Integer, incoming As UInt64, testValue As Integer) As Boolean
if index > values.LastIndex then
return incoming = testValue
end if
return TestValues( values, index + 1, incoming + values( index ), testValue ) or _
TestValues( values, index + 1, incoming * values( index ), testValue ) or _
TestValues( values, index + 1, Val(Str(incoming) + Str(values( index ))), testValue )
End Function
What kind of speeds did you guys get for Day 7 part 2?
Because of the way I did mine in a loop, it meant recalculating each combination from the beginning. I could have modified it not to do that, but didn’t seem worth the effort.
Work down your grid. When you find an antenna, locate each antenna of the same frequency further down the grid, then calculate its difference of row and column. On a separate grid, place a marker at origRow - rowDiff and another at origCol - colDiff, as long as those are within bounds. Then put another marker at foundRow + rowDiff and foundCol + colDiff
As for part 2…
Part 2 spoiler
It’s basically the same idea except once you get rowDiff and colDiff, work backwards as far as you can from the original point, then put a marker at each point from there moving forward until you are out of bounds.
I didn’t have any problem understanding what they were looking for. The example was clear enough to me.
Day 8 Spoiler
I didn’t use a grid array for this one. I scanned the input and saved the coordinates in a dictionary. A single dictionary entry for each transmitter ID with all of the transmitter coordinates in that entry.
My Point2D class has come in handy a couple of times now for checking whether a point is out of bounds. Also my combination generator was useful.
Uses a dictionary to organize transmitter locations:
'Process input data
LoadData
var inpData() As String = Split(pzlData,EndOfLine)
var d As new Dictionary
var rows As Integer = inpData.LastIndex
var cols As Integer = inpData(0).Length-1
var node As new Point2D(0,0,rows,cols)
var ndCount As Integer = 0
'Add all transmitter coordinates to dictionary
for r as Integer = 0 to rows
var rData() As String = inpData(r).Split("")
for c as Integer = 0 to cols
if rData(c)<>"." then
var ks As byte = rData(c).AscByte
var v As d8 'd8 contains two integer array properties r() and c()
if d.HasKey(ks) then
v = d.Lookup(ks,nil)
Else
v = new d8
d.Value(ks)=v
end if
v.r.Add r
v.c.Add c
end if
next c
next r
Parts 1 & 2 use a second dictionary to avoid duplicate nodes. This is the code for part 2 only (part 1 is similar but simpler)
var xType() As Variant = d.Keys
var xLocn() As Variant = d.Values
var nTypes As Integer = xType.LastIndex
var dNodes As new Dictionary
for t as Integer = 0 to nTypes
var xloc As d8 = xLocn(t) 'd8 contains 2 integer array properties r() & c() for xmtr coords
var combo() As Integer 'holds nCr type combinations
for i as Integer = 0 to xloc.r.LastIndex
combo.add i
next i
Do 'for each combination of transmitter pairs
var r0 as Integer = xloc.r(combo(0)) 'Get coords of the xmtr pair
var c0 as Integer = xloc.c(combo(0))
var r1 As Integer = xloc.r(combo(1))
var c1 As Integer = xloc.c(combo(1))
var deltaR As Integer = r1-r0 'calculate coords of the two nodes
var deltaC As Integer = c1-c0
node.R = r1 'first node
node.C = c1
while node.inBounds
dNodes.Value(node.r*cols*2+node.c)=nil
node.R = node.R+deltaR
node.C = node.C+deltaC
wend
node.R = r0 'second node
node.C = c0
while node.inBounds
dNodes.Value(node.r*cols*2+node.c)=nil
node.R = node.R-deltaR
node.C = node.C-deltaC
wend
Loop Until NextCombination(xloc.r.LastIndex,1,combo)=False
next t
ndCount = dNodes.KeyCount 'Solution value
I’ve finally got my run times into the microsecond range.
Impressive to get it into the microsecond range Robert!
Day 8 Spoiler
I used fairly similar approach to the solutions given above, with some slight variants. On the first pass I built a lookup dictionary of all the frequencies that holds an array of all their positions on that map.
Then on the second pass I looped through the freq dictionary and their positions and calculated the antinodes, while using a second dictionary of keeping track of used locations.
I just realized that I’ve written no significant code for the past year. Not since AOC 2023. For the first few puzzles, I felt that I was just blundering through them. After the last couple of puzzles, I’m finally beginning to feel more like my old nerdy self.
I managed to make Day 9 far more difficult than it needed to be. Struggled with part 2 for ages and then decided to go to bed. Five minutes of staring into the blackness, the answer came to me. Back to the computer and got it done.
Ironically, I unknowingly solved Day 10 part 2 first, got the wrong answer (of course), refactored to get the right answer, then duplicated what I did originally to get the part 2 answer (again).
I nearly did the same thing. Before I had the part 1 code finished, I went back and re-read the puzzle and while it wasn’t completely clear, the code didn’t need to change much to work either way. So, once part 1 was complete, part 2 was only a few more seconds to do.
Day 10 Spoiler
Recursive routine to traverse the grid (given a zero elevation starting point):
Public Function Traverse(grid(, ) As integer, r As integer, c As integer, d As dictionary) As Integer
var startpt As new Point2D(r,c,grid.lastindex(1),grid.lastindex(2))
var trCount As Integer = 0
for dir as Integer = 0 to 6 step 2 'test adjacent pts in 90 degree increments
var tstPt As Point2D = startpt.cpyIB(dir) 'Inbounds copy of input point one position away
if tstPt<>nil and grid(tstPt.R,tstPt.C)=grid(r,c)+1 then
if grid(tstPt.R,tstPt.C)=9 then 'reached target trail end
d.Value(tstPt.R*(grid.lastindex(2)+1)+tstPt.C)=nil
trCount= trCount+1
Else
trCount = trCount + Traverse(grid,tstPt.r,tstPt.c,d)
end if
end if
next dir
Return trCount
End Function
The d.KeyCount is the part 1 solution.
The returned value of the function is the part 2 solution
Well, I figured we were due for an “infinite processing time” puzzle and it looks like Day 11 part 2 is it. I have a theory as to how to attack it but it’s going to have to wait until tomorrow. I have to be up bright and early tomorrow morning, so I have to get some sleep now.
