Day 17: Trick Shot

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python with any of the "short names" listed in this page of supported languages):

<details>
<summary>Part 1</summary>

```python
```

</details>

1. 
bhrgunatha
Not my insight but: Part 1 If velocity ym gives the maximum height, then that height is 1+2+...+ym. The y velocity range is bounded ymin <= vy <= -ymin maximum height is therefore ymin (ymin+1)/2....

Not my insight but:

Part 1

For the y-coordinate, the lower bound is like the x-coordinate upper bound; anything lower than the bottom edge of the target area will immediately fall past it

• If velocity ym gives the maximum height, then that height is 1+2+...+ym.
• The y velocity range is bounded ymin <= vy <= -ymin
• maximum height is therefore ymin (ymin+1)/2.
• x and y velocity act independently so if there is any answer it is always this.
1. 
Crespyl
Aha, I figured there should be a closed form solution for part one, but brute-force was fast enough that I didn't bother pursuing it further. Good catch!

Aha, I figured there should be a closed form solution for part one, but brute-force was fast enough that I didn't bother pursuing it further.

Good catch!

1 vote
1. bhrgunatha
Yes sorry it was meant as a reply to your comment. It's nice to have something to compete with all those Rust developers that post sub millisecond runtimes.

It's nice to have something to compete with all those Rust developers that post sub millisecond runtimes.

1 vote
2. bhrgunatha
(edited )
Part 1 Brute force over the possible velocity. The velocity range for x must be from 1 up to the target. For y it from the target's minimum depth to its absolute value. (define (part-01 input)...
Part 1

Brute force over the possible velocity. The velocity range for x must be from 1 up to the target. For y it from the target's minimum depth to its absolute value.

(define (part-01 input)
(define target (map string->number (regexp-match* #px"[+-]?\\d+" input)))
(match-define (list _ xmax ymin _) target)
(for*/fold ([max-height 0])
([vx (in-inclusive-range 1 xmax)]
[vy (in-inclusive-range (add1 ymin) (abs ymin))]
[hit? (in-value (fire vx vy (in-bounds? target) (overshot? target)))])
(if hit? (max max-height hit?) max-height)))

(define (in-bounds? target)
(match-define (list xmin xmax ymin ymax) target)
(λ (pos)
(and (<= xmin (first pos) xmax)
(<= ymin (second pos) ymax))))

(define (overshot? target)
(match-define (list xmin xmax ymin ymax) target)
(λ (pos)
(or (> (first pos) xmax)
(< (second pos) ymin))))

(define (to-zero v)
(cond [(> v 0) (sub1 v)]
[else 0]))

(define (fire vx vy hit? over?)
(for/fold ([x 0] [y 0] [vx vx] [vy vy] [ymax 0]
#:result (and (hit? (list x y)) ymax))
([step (in-naturals 1)]
#:break (or (hit? (list x y))
(over? (list x y))))
(values (+ x vx)
(+ y vy)
(to-zero vx)
(sub1 vy)
(max ymax (+ y vy)))))

Part 2

Same as part 1 except instead of checking for the maximum height reached we just keep a count of when the target is hit.

(define (part-02 input)
(define target (map string->number (regexp-match* #px"[+-]?\\d+" input)))
(match-define (list _ xmax ymin _) target)
(for*/fold ([hit-count 0])
([vx (in-inclusive-range 1 xmax)]
[vy (in-inclusive-range (add1 ymin) (abs ymin))]
[hit? (in-value (fire vx vy (in-bounds? target) (overshot? target)))])

3. Crespyl
Part 1 Ruby A simple brute-force approach works just fine here. def compute_p1(input) matches = input.chomp.match(/target area: x=(-?\d+)..(-?\d+), y=(-?\d+)..(-?\d+)/) x_min, x_max, y_min, y_max...
Part 1 Ruby A simple brute-force approach works just fine here.
def compute_p1(input)
matches = input.chomp.match(/target area: x=(-?\d+)..(-?\d+), y=(-?\d+)..(-?\d+)/)
x_min, x_max, y_min, y_max = matches[1..].map(&:to_i)

x_range = x_min..x_max
y_range = y_min..y_max

best_x = 0
best_y = 0
best_max_y = 0

x_range.max.times do |x|
x_range.max.times do |y|
hit, max_y = test_probe(x,y, x_range, y_range)
if hit && max_y > best_max_y
best_x = x
best_y = y
best_max_y = max_y
end
end
end

return best_max_y
end

def test_probe(vx, vy, x_range, y_range)
x,y = 0,0
max_y = 0
loop do
return [true, max_y] if x_range.include?(x) && y_range.include?(y)
return [false, max_y] if x > x_range.max || y < y_range.min || (! x_range.include?(x) && vx == 0)

x += vx
y += vy

max_y = y if y > max_y

vx = (vx - (vx <=> 0)) # we use ruby's `<=>` all-in-one comparison operator, which returns one of -1, 0, or +1 depending on whether the left value is less, equal, or greater than the right value
vy -= 1
end
end

Part 2 Ruby My initial solution here was also just straight-forward brute force, which took about ~3min on my machine. While that was running I took a closer look at the problem and tried to work out how to narrow down the search space a bit.

For the x-coordinate, we know that the upper bound can't be any higher than the right (/highest) side of the target box since the first step would put the probe beyond it. Next, we know that the x-velocity will eventually reach 0, and we need to make sure that it reaches the left (/lowest) side of the target area before that happens. Since the velocity decreases by one each step, we can work out the distance covered with the same series sum from an earlier puzzle (n * (n+1) / 2).

At first, I just used this directly as a filter ( (0..x_max).filter { (_1 * (_1 + 1) / 2) >= x_min } ), but it turns out that sqrt(2n) actually gives us a quick approximation of the lower bound of that series anyway, so instead we can just search the range (Math.sqrt(x_min*2).floor..x_max).

For the y-coordinate, the lower bound is like the x-coordinate upper bound; anything lower than the bottom edge of the target area will immediately fall past it. The upper bound turns out to be closely related, any positive velocity will reach 0 after n steps, and then by the time the probe returns to y=0, the y-velocity will be -n, and suddenly the situation looks the same as it does for the lower bound.

All together, we have (Math.sqrt(x_min).floor >= x < x_max) and (y_min >= y < y_min.abs), which lets us narrow down the search enough to complete in under a second.

def compute_p2(input)
matches = input.chomp.match(/target area: x=(-?\d+)..(-?\d+), y=(-?\d+)..(-?\d+)/)
x_min, x_max, y_min, y_max = matches[1..].map(&:to_i)

((Math.sqrt(x_min*2).floor)..x_max).to_a
.product((y_min..(y_min.abs-1)).to_a)
.reduce(0) do |sum, coords|
hit, _max_y = test_probe(coords, coords, x_min..x_max, y_min..y_max)
hit ? sum + 1 : sum
end
end

4. tomf
It feels like its been a while since I got one. Google Sheets, again. Part 1 =ABS(REGEXEXTRACT(A2,"y=(-?\d+)"))* (ABS(REGEXEXTRACT(A2,"y=(-?\d+)"))-1)/2

It feels like its been a while since I got one.

Part 1
=ABS(REGEXEXTRACT(A2,"y=(-?\d+)"))*
(ABS(REGEXEXTRACT(A2,"y=(-?\d+)"))-1)/2

5. PapaNachos
I'm sure there's an elegant, mathy solution to this problem. I couldn't find it, so I went with some jank. Day 17 Part A - Python After giving up on finding an elegant solution, I looked for all...

I'm sure there's an elegant, mathy solution to this problem. I couldn't find it, so I went with some jank.

Day 17 Part A - Python

After giving up on finding an elegant solution, I looked for all valid y trajectories between 0 and 1000. I only needed to care about positive ones, because we're aiming up. For each one I checked it's max height and if it ever landed in the target zone. I recorded the max height and however many turns it was inside the target zone. Once I had the turn number I was looking for, I searched for an x-velocity that would land in the target within that many turns. Fingers crossed that the best result would have an accompanying x velocity that worked, but I felt good about it because eventually x movement will stabilize and all future turns will be valid.

import re
from collections import defaultdict

#data = test_data
data = real_data

pattern = re.compile(r'target area: x=(-?\d+)..(-?\d+), y=(-?\d+)..(-?\d+)')

bounds = pattern.search(data)

x_min = int(bounds)
x_max = int(bounds)
y_min = int(bounds)
y_max = int(bounds)

best_y_max_height = 0
best_y = 0
best_y_valid_turns = []
for init_y_vel in range(1000):
y_pos = 0
num_turns = 0
y_vel = init_y_vel
max_height = 0
valid_turns = []
while y_pos >= y_min:
#print(y_pos)
num_turns = num_turns + 1
y_pos = y_pos + y_vel
y_vel = y_vel - 1
max_height = max(max_height, y_pos)
if y_pos <= y_max and y_pos >= y_min:
valid_turns.append(num_turns)
if max_height > best_y_max_height and len(valid_turns) > 0:
best_y = init_y_vel
best_y_valid_turns = valid_turns
best_y_max_height = max_height
valid_x = None
for init_x_vel in range(1000):
x_pos = 0
x_vel = init_x_vel
for i in range(max(best_y_valid_turns)+1):
x_pos = x_pos + x_vel
#print(i, x_pos, x_vel)
if x_vel > 0:
x_vel = x_vel - 1
elif x_vel < 0:
x_vel = x_vel + 1
if i in best_y_valid_turns and x_pos > x_min and x_pos < x_max:
valid_x = init_x_vel
print(best_y_max_height)
print(best_y)
print(valid_x)

Day 17 Part B - Python

I modified my code to instead look for all x and y values that would eventually fall within the target zone. And recorded what turns they were within the zone. Then I took the lists and compared them against each other and recorded any matches were a given x velocity and y velocity had overlapping turns in the target area. The answer was how many unique entries were in that list.

import re
from collections import defaultdict

#data = test_data
data = real_data

pattern = re.compile(r'target area: x=(-?\d+)..(-?\d+), y=(-?\d+)..(-?\d+)')

bounds = pattern.search(data)

x_min = int(bounds)
x_max = int(bounds)
y_min = int(bounds)
y_max = int(bounds)

valid_ys = defaultdict(list)
valid_y_turns = []
for init_y_vel in range(-100, 100):
y_pos = 0
num_turns = 0
y_vel = init_y_vel
while y_pos >= y_min:
#print(y_pos)
num_turns = num_turns + 1
y_pos = y_pos + y_vel
y_vel = y_vel - 1
if y_pos <= y_max and y_pos >= y_min:
valid_ys[init_y_vel].append(num_turns)
valid_y_turns.append(num_turns)
valid_y_turns = list(set(valid_y_turns))

valid_xs = defaultdict(list)
valid_x_turns = []

for init_x_vel in range(305):
x_pos = 0
x_vel = init_x_vel
for i in range(1,max(valid_y_turns)+1):
x_pos = x_pos + x_vel
#print(i, x_pos, x_vel)
if x_vel > 0:
x_vel = x_vel - 1
elif x_vel < 0:
x_vel = x_vel + 1
if x_pos >= x_min and x_pos <= x_max:
valid_xs[init_x_vel].append(i)
valid_x_turns.append(i)

valid_x_turns = list(set(valid_x_turns))

valid_combos = []
for x_key in valid_xs.keys():
for y_key in valid_ys.keys():
for turn_y in valid_ys[y_key]:
if turn_y in valid_xs[x_key]:
valid_combos.append((x_key, y_key))

valid_combos = list(set(valid_combos))
#print(valid_combos)

#print(valid_x_turns)
#print(valid_y_turns)

print(len(valid_combos))

Tips
• X movement and Y movement don't affect each other, you can break them out and handle them individually

• A given trajectory may have multiple turns where it's within the target area, especially if you're looking at x and y separately

• Eventually x slows down and stabilizes

• I found thinking about it in terms of turns was very helpful

6. Crestwave
(edited )
I'm so glad I didn't complete* yesterday's decoder /s I appreciate that today's challenge can be easily brute forced. I'm probably going to try to optimize this later, but it always feels great...

You finally decode the Elves' message. HI, the message says.

I'm so glad I didn't complete* yesterday's decoder /s

I appreciate that today's challenge can be easily brute forced. I'm probably going to try to optimize this later, but it always feels great when you get it done and the optimization is optional.

Part 1
#!/usr/bin/awk -f
{
sub(/.*x=/, "")
sub(/, y=/, " ")

split(\$1, xx, ".")
split(\$2, yy, ".")

for (y = yy; y <= yy; ++y) {
for (x = xx; x <= xx; ++x) {
grid[x, y] = "T"
}
}

for (_y = 200; _y >= -200; --_y) {
for (_x = 500; _x >= 0; --_x) {
split("0,0", pos, ",")
x = _x
y = _y

while (pos < xx && pos > yy) {
pos += x
pos += y

if (grid[pos, pos] == "T") {
print (_y * (_y + 1) / 2)
exit
}

if (x > 0) {
x -= 1
} else if (x < 0) {
x += 1
}

y -= 1
}
}
}
}

Part 2
#!/usr/bin/awk -f
{
sub(/.*x=/, "")
sub(/, y=/, " ")

split(\$1, xx, ".")
split(\$2, yy, ".")

for (y = yy; y <= yy; ++y) {
for (x = xx; x <= xx; ++x) {
grid[x, y] = "T"
}
}

for (_y = 200; _y >= -200; --_y) {
for (_x = 500; _x >= 0; --_x) {
split("0,0", pos, ",")
x = _x
y = _y

while (pos <= xx && pos >= yy) {
pos += x
pos += y

if (grid[pos, pos] == "T") {
total += 1
break
}

if (x > 0) {
x -= 1
} else if (x < 0) {
x += 1
}

y -= 1
}
}
}

print total
}

*

I got most of the way there, but my decoder had a pretty severe bug specifically with two of the examples that didn't have step-by-step walk-throughs, and I just didn't feel like debugging a bunch of 1's and 0's.

7. DataWraith
(edited )
Day 17 (Rust) I spent a bit of time trying to come up with a formula, but all I found was a way to calculate the x coordinate at the point where drag reduces the velocity to zero; this isn't very...

Day 17 (Rust)

I spent a bit of time trying to come up with a formula, but all I found was a way to calculate the x coordinate at the point where drag reduces the velocity to zero; this isn't very significant in practice though, the whole thing still takes about 1 second to run.

Edit: D'oh! I had a dbg!-statement still in there. Turns out, writing to the console is slow... actual runtime is more like 8ms.

Data structures
#[derive(Debug)]
pub struct TargetArea {
x_start: i64,
x_end: i64,
y_start: i64,
y_end: i64,
}

#[derive(Clone, Copy, Debug)]
pub struct Probe {
x: i64,
y: i64,
dx: i64,
dy: i64,
}

impl Probe {
pub fn new(dx: i64, dy: i64) -> Probe {
Probe { x: 0, y: 0, dx, dy }
}
}

Parsing
mod parse {
use super::TargetArea;

use nom::{bytes::complete::tag, character::complete::i64, combinator::eof, IResult};

fn puzzle(input: &str) -> IResult<&str, TargetArea> {
let (input, _) = tag("target area: x=")(input)?;
let (input, x_start) = i64(input)?;
let (input, _) = tag("..")(input)?;
let (input, x_end) = i64(input)?;
let (input, _) = tag(", y=")(input)?;
let (input, y_start) = i64(input)?;
let (input, _) = tag("..")(input)?;
let (input, y_end) = i64(input)?;
let (input, _) = eof(input)?;

Ok((
input,
TargetArea {
x_start,
x_end: x_end + 1,
y_start,
y_end: y_end + 1,
},
))
}

pub fn parse(input: &str) -> TargetArea {
puzzle(input).unwrap().1
}
}

Helper functions
fn is_within_target(probe: &Probe, target: &TargetArea) -> bool {
(target.x_start..target.x_end).contains(&probe.x)
&& (target.y_start..target.y_end).contains(&probe.y)
}

fn is_lost(probe: &Probe, target: &TargetArea) -> bool {
probe.x > target.x_end
|| probe.dx == 0 && !(target.x_start..target.x_end).contains(&probe.x)
|| probe.y < target.y_start
}

fn step(probe: &Probe) -> Probe {
Probe {
x: probe.x + probe.dx,
y: probe.y + probe.dy,
dx: probe.dx - probe.dx.signum(),
dy: probe.dy - 1,
}
}

fn trajectory(p: &Probe, t: &TargetArea) -> Option<Vec<Probe>> {
let mut result = vec![p.clone()];
let mut next = *p;

loop {
next = step(&next);

result.push(next);

if is_within_target(&next, &t) {
return Some(result);
}

if is_lost(&next, &t) {
return None;
}
}
}

Solving
fn part1(target: &TargetArea) -> i64 {
let mut best_y = i64::MIN;

for dx in 0..=target.x_end {
// x coordinate we reach when drag has eaten up all our velocity.
let final_x = dx * (dx + 1) / 2;

// This falls short of the target area, so start next attempt
if final_x < target.x_start {
continue;
}

// Assuming the target is directly below us, we can't use a velocity that is larger than
// y_start or we'll overshoot. This is the worst case. I just mirrored the shot velocity
// towards the positive as well, but just because that happened to work, not because it's
// mathematically rigorous.
for dy in target.y_start..=(-target.y_start) {
if let Some(trajectory) = trajectory(&Probe::new(dx, dy), &target) {
let highest = trajectory.iter().map(|probe| probe.y).max().unwrap();
best_y = std::cmp::max(best_y, highest);
}
}
}

best_y
}

fn part2(target: &TargetArea) -> i64 {
let mut count = 0;

for dx in 0..=target.x_end {
let final_x = dx * (dx + 1) / 2;

if final_x < target.x_start {
continue;
}

for dy in target.y_start..=(-target.y_start) {
if let Some(trajectory) = trajectory(&Probe::new(dx, dy), &target) {
count += 1;
}
}
}

count
}

fn main() {
let input = include_str!("../../input-17.txt").trim();
let target = parse::parse(input);

println!("Part I:  {}", part1(&target));
println!("Part II: {}", part2(&target));
}

8. jzimbel
(edited )
Elixir Catching up after a little break! This one wasn't too hard. It looked like part 1 could be solved with basic math since we only really care about the y position, but I went ahead and set up...

Elixir

Catching up after a little break! This one wasn't too hard. It looked like part 1 could be solved with basic math since we only really care about the y position, but I went ahead and set up code to simulate shots assuming we would need to do more than the bare minimum for part 2. That worked out well for me.

Side note: the Elixir syntax highlighter used here doesn't distinguish used from unused match variables—any variable starting with a _ is unused and is only included so that the pattern on the left matches the expression on the right. These variables are normally grayed out in most editors.

Both parts

simulate_shot/2 returns a stream that emits the position at each step until (and excluding) the first position past the target region.

The rest of the problem boils down to simulating a bunch of shots and querying the results for the first one that matches a condition (goes from a position at or above y=0 to a position inside the y-bounds of the target in one step), or counting up all of the results that match a condition (hits the target).

def part1(input) do
{_x_target, ymin..ymax} = target = parse_input(input)

-ymin..-ymax//-1
|> Stream.map(&simulate_shot({0, &1}, target))
|> Enum.find(&first_step_hit?(&1, target))
|> Stream.map(fn {_x, y} -> y end)
|> Enum.max()
end

def part2(input) do
{_xmin..xmax, ymin.._ymax} = target = parse_input(input)

for(vx <- 0..xmax, vy <- ymin..-ymin, do: {vx, vy})
|> Stream.map(&simulate_shot(&1, target))
|> Enum.count(&hits_target?(&1, target))
end

defp simulate_shot(v, target) do
{v, {0, 0}}
|> Stream.iterate(&step/1)
|> Stream.map(&elem(&1, 1))
|> Stream.take_while(&in_simulation_bounds?(&1, target))
end

defp step({{vx, vy}, {x, y}}) do
{{vx - unit(vx), vy - 1}, {x + vx, y + vy}}
end

defp in_simulation_bounds?({x, y}, {xmin..xmax, ymin.._ymax}) do
x in min(0, xmin)..max(0, xmax) and y >= ymin
end

# Detects shots where the probe hits the target's y bounds on its first step below y=0
defp first_step_hit?(shot, {_x_target, y_target}) do
shot
|> Enum.any?(fn [{_x1, y1}, {_x2, y2}] -> y1 >= 0 and y2 in y_target end)
end

defp hits_target?(shot, target) do
Enum.any?(shot, &on_target?(&1, target))
end

defp on_target?({x, y}, {x_target, y_target}) do
x in x_target and y in y_target
end

defp parse_input(input) do
~r/(-?\d+)\.\.(-?\d+)/
|> Regex.scan(input, capture: :all_but_first)
|> List.flatten()
|> Enum.map(&String.to_integer/1)
|> then(fn [xmin, xmax, ymin, ymax] ->
{xmin..xmax, ymin..ymax}
end)
end

defp unit(0), do: 0
defp unit(n) when n > 0, do: 1
defp unit(_n), do: -1
end

1 vote