Day 17: Trick Shot

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.

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)]
        [(< v 0) (add1 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)))))

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)))])
    (if hit? (add1 hit-count) hit-count)))

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

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[0], coords[1], x_min..x_max, y_min..y_max)
    hit ? sum + 1 : sum
  end
end

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

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[1])
x_max = int(bounds[2])
y_min = int(bounds[3])
y_max = int(bounds[4])


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)

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[1])
x_max = int(bounds[2])
y_min = int(bounds[3])
y_max = int(bounds[4])


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))

• 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

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

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

	for (y = yy[1]; y <= yy[3]; ++y) {
		for (x = xx[1]; x <= xx[3]; ++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[1] < xx[3] && pos[2] > yy[1]) {
				pos[1] += x
				pos[2] += y

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

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

				y -= 1
			}
		}
	}
}

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

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

	for (y = yy[1]; y <= yy[3]; ++y) {
		for (x = xx[1]; x <= xx[3]; ++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[1] <= xx[3] && pos[2] >= yy[1]) {
				pos[1] += x
				pos[2] += y

				if (grid[pos[1], pos[2]] == "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.

#[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 }
    }
}

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
    }
}

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;
        }
    }
}

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));
}

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).

defmodule AdventOfCode.Solution.Year2021.Day17 do
  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
    |> Stream.chunk_every(2, 1, :discard)
    |> 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