Ok. I nearly didn't start this one. I took a look at the puzzle, and thought "I can work out how to simulate the probe but I've got no idea how to work out the best start value". This feels like I should be able to solve with maths somehow, like reason about the graph, solve for the intercept and there is it. Except that my maths isn't strong enough to do that.
But I then started dreaming about it, and thinking about it idly, and an idea came to me, an idea that I want to try out.
Todays solution is going to be far more functional than previous weeks.
My idea was to write a simple function that can take the initial variables and calculate each successive step each time its called. For any given start values, we can then generate an infinite stream of coordinates. We're going to then filter that stream for anything that goes outside our bounds, that's the edge of the target box, or above an arbitrary height or behind the sub. Finally we'll search that stream for the maximum y coordinate. That will give us a mapping of start settings to maximum y.
We'll then have some settings that we can play with. We're going to need to explore the solution space for those settings, but we won't know whats possible. At a gut feel, based on the numbers, anything that has an x-increment of more than half the total x bound is pointless, as we wont have more than 1 point in the stream. On the y coordinate test, I don't really know what a sensible number is, so lets try around -1000 to 1000 and see if that works
Finally, there's a thought. I don't actually ever think I want an infinite range, stuff with infinite loops makes me nervous, so I'm going to hardcode a global MAX_ITERATIONS of around 1000. That should be plenty
## Import ipytest and get it setup for use in Python Notebook
import pytest
import ipytest
ipytest.autoconfig()
import itertools
from collections import namedtuple
Coord = namedtuple('Coord', ['x', 'y'])
Vector = namedtuple('Vector', ['dx', 'dy'])
Area = namedtuple('Area', ['start', 'end'])
MAX_ITERATIONS = 1000
def steps(vec):
dx=0
c = Coord(0,0)
for _ in range(MAX_ITERATIONS):
c = Coord(c.x+vec.dx, c.y+vec.dy)
yield c
if vec.dx > 0:
dx=-1
elif vec.dx < 0:
dx=1
vec = Vector(vec.dx+dx, vec.dy-1)
assert [Coord(7,2), Coord(13,3), Coord(18,3), Coord(22,2), Coord(25,0), Coord(27,-3), Coord(28,-7)] == list(itertools.islice(steps(Vector(7,2)),7))
Ok, we have a generator that can create the path for any probe, now we need to find it either going out of bounds or hitting the target.
We can filter out anything that goes out of bounds first
def boundsFilter(bounds):
def filter(coord):
return coord.x >= min(bounds.start.x,bounds.end.x) and coord.y >= min(bounds.start.y, bounds.end.y) and coord.x <= max(bounds.start.x, bounds.end.x) and coord.y <= max(bounds.start.y, bounds.end.y)
return filter
testarea = Area(Coord(0,-10), Coord(30,100))
expected = [Coord(7,2), Coord(13,3), Coord(18,3), Coord(22,2), Coord(25,0)]
assert expected == list(itertools.islice(filter(boundsFilter(testarea), steps(Vector(7,2))),5))
Now we need something to tell us if the entire stream hits the goal or not. This is the same as the bounds filter, just for a smaller bounds
targetarea = Area(Coord(20,-5), Coord(30,-10))
expected = [Coord(28,-7)]
assert expected == list(filter(boundsFilter(targetarea), steps(Vector(7,2))))
Ok, we can finda target that hits a goal.
But I've had a thought, instead of using the bounds filter, we might want a generator that stops at the bounds as well, that means that we don't have to generate a thousand items for a poor shot. It also means we can drop the islice calls
def stepsInBounds(vec, bounds):
dx=0
c = Coord(0,0)
for _ in range(MAX_ITERATIONS):
c = Coord(c.x+vec.dx, c.y+vec.dy)
if c.x < min(bounds.start.x,bounds.end.x) or c.y < min(bounds.start.y, bounds.end.y) or c.x > max(bounds.start.x, bounds.end.x) or c.y > max(bounds.start.y, bounds.end.y):
return
yield c
if vec.dx > 0:
dx=-1
elif vec.dx < 0:
dx=1
vec = Vector(vec.dx+dx, vec.dy-1)
expected = [Coord(7,2), Coord(13,3), Coord(18,3), Coord(22,2), Coord(25,0), Coord(27,-3), Coord(28,-7)]
assert expected == list(stepsInBounds(Vector(7,2), testarea))
assert [Coord(28,-7)] == list(filter(boundsFilter(targetarea), stepsInBounds(Vector(7,2), testarea)))
assert [Coord(20,-9)] == list(filter(boundsFilter(targetarea), stepsInBounds(Vector(6,3), testarea)))
assert [Coord(30,-6)] == list(filter(boundsFilter(targetarea), stepsInBounds(Vector(9,0), testarea)))
assert [] == list(filter(boundsFilter(targetarea), stepsInBounds(Vector(17,-4), testarea)))
Ok, we can now generate steps, filter for those which hit a goal.
We can try to different numbers and see how they work. We're going to have to try a range of numbers. The x probably needs to go from 1 to 1/2 the start of the target area. The y needs to go from 0 to ... at a guess about the same bound.
Let's give that a try for a search, which should give us a couple of hundred combinations. We can then filter those for only those sequences that contain at least 1 goal hitting step, and then we can search that list for the one with the highest y
from more_itertools import take, first
def generateTestSet(targetarea):
return [Vector(x,y) for y in range(targetarea.end.x//2) for x in range(targetarea.end.x//2)]
def findValidFiringSolutions(possibleset, targetarea, testarea):
return [stepsInBounds(test, testarea) for test in possibleset if first(filter(boundsFilter(targetarea), stepsInBounds(test, testarea)), False)]
def mapSolutionToYs(solution):
return
def findSolutionWithHighestY(solutions):
return max([max(solution, key=lambda c: c.y) for solution in solutions], key=lambda c: c.y)
testset = generateTestSet(targetarea)
solutions = findValidFiringSolutions(testset, targetarea, testarea)
highestYCoord = findSolutionWithHighestY(solutions)
assert Coord(20,45) == highestYCoord
Ok, We can find the highest Y, but we need to parse the original file, and we need to work out if we're guessing the right numbers.
We'll start with parsing, but for the numbers, we're going to have to rely on asking it to find an answer and then seeing if the adventofcode website finds it.
import re
def parseline(line):
nums = [int(m) for m in re.findall(r"-?\d+", line)]
return Area(Coord(min(nums[0],nums[1]), min(nums[2], nums[3])), Coord(max(nums[0],nums[1]), max(nums[2], nums[3])))
assert Area(Coord(20,-10), Coord(30,-5)) == parseline("target area: x=20..30, y=-10..-5")
assert Area(Coord(20,-10), Coord(30,-5)) == parseline("target area: x=20..30, y=-5..-10")
assert Area(Coord(20,-10), Coord(30,5)) == parseline("target area: x=20..30, y=5..-10")
def testAreaFromTarget(targetarea):
start = Coord(0, min(targetarea.start.y, targetarea.end.y))
end = Coord(targetarea.end.x,1000)
return Area(start, end)
assert Area(Coord(0,-10), Coord(30,1000)) == testAreaFromTarget(parseline("target area: x=20..30, y=-10..-5"))
assert Area(Coord(0,-50), Coord(90,1000)) == testAreaFromTarget(parseline("target area: x=70..90, y=15..-50"))
line = "target area: x=20..30, y=-10..-5"
targetarea = parseline(line)
testarea = testAreaFromTarget(targetarea)
testset = generateTestSet(targetarea)
solutions = findValidFiringSolutions(testset, targetarea, testarea)
highestYCoord = findSolutionWithHighestY(solutions)
assert Coord(20,45) == highestYCoord
Ok, lets try that production data
line = open("day17.txt").read()
targetarea = parseline(line)
testarea = testAreaFromTarget(targetarea)
testset = generateTestSet(targetarea)
solutions = findValidFiringSolutions(testset, targetarea, testarea)
highestYCoord = findSolutionWithHighestY(solutions)
print(highestYCoord)
Coord(x=252, y=861)
That's not right, but at 861 y, I think we're way too small with a maximum y of 1000, so lets increase that by 10x
def testAreaFromTarget(targetarea):
start = Coord(0, min(targetarea.start.y, targetarea.end.y))
end = Coord(targetarea.end.x,10000)
return Area(start, end)
assert Area(Coord(0,-10), Coord(30,10000)) == testAreaFromTarget(parseline("target area: x=20..30, y=-10..-5"))
assert Area(Coord(0,-50), Coord(90,10000)) == testAreaFromTarget(parseline("target area: x=70..90, y=15..-50"))
line = open("day17.txt").read()
targetarea = parseline(line)
testarea = testAreaFromTarget(targetarea)
testset = generateTestSet(targetarea)
solutions = findValidFiringSolutions(testset, targetarea, testarea)
highestYCoord = findSolutionWithHighestY(solutions)
print(highestYCoord)
Coord(x=252, y=3570)
We found it!
Ok, our next part requires us to simply list all the initial velocities that result in a valid firing solution, luckily, we already wrote that with findValidFiringSolutions, so we should just be able to run that and see if it works.
Let's try that on our test set and see what works
line = "target area: x=20..30, y=-10..-5"
targetarea = parseline(line)
testarea = testAreaFromTarget(targetarea)
testset = generateTestSet(targetarea)
solutions = findValidFiringSolutions(testset, targetarea, testarea)
assert 112 == len(solutions)
--------------------------------------------------------------------------- AssertionError Traceback (most recent call last) /var/folders/wv/w00k3xk15fn7b3nyyn0_rwtw0000gn/T/ipykernel_76973/2884118959.py in <module> 4 testset = generateTestSet(targetarea) 5 solutions = findValidFiringSolutions(testset, targetarea, testarea) ----> 6 assert 112 == len(solutions) AssertionError: assert 112 == 23 + where 23 = len([<generator object stepsInBounds at 0x1132e22e0>, <generator object stepsInBounds at 0x1132e2350>, <generator object s...at 0x1132e2430>, <generator object stepsInBounds at 0x1132e24a0>, <generator object stepsInBounds at 0x1132e2510>, ...])
Hmm, we don't have enough solutions. Let's take a look at the examples and see what we've done.
Oh, I see a problem. I always assumed that we were looking for paths that went up and down, hence the x//2, but in fact, we obviously can also use every single location within the target area as the first step as well.
Let's change our initial bounds to cover the entire target area as well as see if that helps
def generateTestSet(targetarea):
return [Vector(x,y) for y in range(-1000,1000) for x in range(targetarea.end.x+1)]
line = "target area: x=20..30, y=-10..-5"
targetarea = parseline(line)
testarea = testAreaFromTarget(targetarea)
testset = generateTestSet(targetarea)
solutions = findValidFiringSolutions(testset, targetarea, testarea)
expected = [ Coord(23,-10), Coord(25,-9), Coord(27,-5), Coord(29,-6), Coord(22,-6), Coord(21,-7), Coord(9,0), Coord( 27,-7), Coord(24,-5),
Coord(25,-7), Coord(26,-6), Coord(25,-5), Coord(6,8), Coord( 11,-2), Coord(20,-5), Coord(29,-10), Coord( 6,3), Coord( 28,-7),
Coord(8,0), Coord( 30,-6), Coord(29,-8), Coord(20,-10), Coord( 6,7), Coord( 6,4), Coord( 6,1), Coord( 14,-4), Coord(21,-6),
Coord(26,-10), Coord(7,-1), Coord( 7,7), Coord( 8,-1), Coord( 21,-9), Coord(6,2), Coord( 20,-7), Coord(30,-10), Coord( 14,-3),
Coord(20,-8), Coord(13,-2), Coord(7,3), Coord( 28,-8), Coord(29,-9), Coord(15,-3), Coord(22,-5), Coord(26,-8), Coord(25,-8),
Coord(25,-6), Coord(15,-4), Coord(9,-2), Coord( 15,-2), Coord(12,-2), Coord(28,-9), Coord(12,-3), Coord(24,-6), Coord(23,-7),
Coord(25,-10), Coord(7,8), Coord( 11,-3), Coord(26,-7), Coord(7,1), Coord( 23,-9), Coord(6,0), Coord( 22,-10), Coord( 27,-6),
Coord(8,1), Coord( 22,-8), Coord(13,-4), Coord(7,6), Coord( 28,-6), Coord(11,-4), Coord(12,-4), Coord(26,-9), Coord(7,4),
Coord(24,-10), Coord(23,-8), Coord(30,-8), Coord(7,0), Coord( 9,-1), Coord( 10,-1), Coord(26,-5), Coord(22,-9), Coord(6,5),
Coord(7,5), Coord( 23,-6), Coord(28,-10), Coord( 10,-2), Coord(11,-1), Coord(20,-9), Coord(14,-2), Coord(29,-7), Coord(13,-3),
Coord(23,-5), Coord(24,-8), Coord(27,-9), Coord(30,-7), Coord(28,-5), Coord(21,-10), Coord( 7,9), Coord( 6,6), Coord( 21,-5),
Coord(27,-10), Coord(7,2), Coord( 30,-9), Coord(21,-8), Coord(22,-7), Coord(24,-9), Coord(20,-6), Coord(6,9), Coord( 29,-5),
Coord(8,-2), Coord( 27,-8), Coord(30,-5), Coord(24,-7)]
actual =[first(s) for s in solutions]
assert 112 == len(actual)
assert sorted(expected) == sorted(actual)
Well that was a pain to find. The Y coordinate is still a nightmare, I can't work out how to come up with sensible guesses.
We know that the highest that the Y coordinate ever gets is around 3500, so lets hope that a maximum of 1000 is enough.
line = open("day17.txt").read()
targetarea = parseline(line)
testarea = testAreaFromTarget(targetarea)
testset = generateTestSet(targetarea)
solutions = findValidFiringSolutions(testset, targetarea, testarea)
print(len(solutions))
1919
Overall, I'm really unhappy with this one. A 6 second runtime makes me think that I'm missing something clever, but this was decidedly horrible.