Advent of Code 2021 - Day 17

bjorng · December 17, 2021, 6:42am

This topic is about Day 17 of the Advent of Code 2021.

We have a private leaderboard (shared with users of Erlang Forums):

https://adventofcode.com/2021/leaderboard/private/view/370884

The entry code is:
370884-a6a71927

bjorng · December 17, 2021, 6:46am

I used a brute-force solution, testing many more initial velocities than necessary. It does the job in less than 3 seconds on my computer.

github.com

bjorng/advent-of-code-2021/blob/4e2c966e8eee059c6d220597406f1b8ccdb8119f/day17/lib/day17.ex

# Both parts are solved with brute force. y limits are tailored to my
# input data (with a wide margin). Finishes in less than 3 seconds
# on my computer.

defmodule Day17 do
  def part1(input) do
    {xrange, _yrange} = ranges = parse(input)

    Enum.reduce(1..xrange.last+1, 0, fn x, best ->
      Enum.reduce(1..500, best, fn y, best ->
        case max_height({x, y}, ranges) do
          nil ->
            best
          height ->
            max(best, height)
        end
      end)
    end)
  end

This file has been truncated. show original

ruslandoga · December 17, 2021, 6:56am

I think for part1, to find the best initial y velocity we can use something like y = abs(target_area.y.min) - 1 so that the max(y) is as big as possible and the probe doesn’t overshoot the target area when falling.

I got this idea after drawing the example with initial velocity of 6,9:

.....................#.........
.....................#.........
...............................
.....................#.........
...............................
...............................
.....................#.........
...............................
...............................
...............................
....................##.........
...............................
...............................
...............................
...............................
..................#..#.........
...............................
...............................
...............................
...............................
...............................
...............#.....#.........
...............................
...............................
...............................
...............................
...............................
...............................
...........#.........#.........
...............................
...............................
...............................
...............................
...............................
...............................
...............................
......#..............#.........
...............................
...............................
...............................
...............................
...............................
...............................
...............................
...............................
S....................#.........
...............................
...............................
...............................
...............................
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................TTTTTTTTTTT
....................T#TTTTTTTTT

bjorng · December 17, 2021, 7:11am

Yes, your formula for y works for part 1 with my input. My input is:

target area: x=185..221, y=-122..-74

and the best initial velocity is {19, 121}.

princemaple · December 17, 2021, 7:45am

github.com

princemaple/aoc/blob/main/2021/day17.exs

# Title: Day17

# ── Untitled ──

data =
  "input"
  |> IO.getn(1_000_000)
  |> String.trim()
  |> String.trim_leading("target area: ")
  |> String.split(", ")
  |> then(fn ["x=" <> x_range, "y=" <> y_range] ->
    {x_range, []} = Code.eval_string(x_range)
    {y_range, []} = Code.eval_string(y_range)
    {x_range, y_range}
  end)

defmodule D17 do
  def calc({xmin..xmax = xr, ymin..ymax = yr}) do
    dxmin = 1..xmin |> Enum.find(&(Enum.sum(1..&1) >= xmin))

This file has been truncated. show original

dallagi · December 17, 2021, 8:55am

Here’s my solution.
I’m not sure if this is the best approach, but using streams to determine the trajectory turned out pretty nice imho.
Runs in 2.5s for both parts on my machine.

github.com

dallagi/aoc2021/blob/main/lib/aoc2021/day17.ex

defmodule Aoc2021.Day17 do
  def part1(input) do
    target = parse(input)
    {initial_xs, initial_ys} = initial_starting_velocities(target)

    highest_ys =
      for x_vel <- initial_xs, y_vel <- initial_ys do
        initial_velocity = {x_vel, y_vel}
        highest_y_if_hits(initial_velocity, target)
      end

    highest_ys
    |> Enum.reject(&(&1 == nil))
    |> Enum.max()
  end

  def part2(input) do
    target = parse(input)
    {initial_xs, initial_ys} = initial_starting_velocities(target)

This file has been truncated. show original

qhwa · December 17, 2021, 10:43am

Part 1 can be solved with a simple approach.

target_y_range = -85..-56
max_vy = -1 - target_y_range.first
div(max_vy * (max_vy + 1), 2)

My full solution for day 17.

wasi0013 · December 17, 2021, 10:50am

I did the same thing for part 1

def solve_part1([_x1, _x2, y1, _y2]), do: div(y1 * (y1 + 1), 2)

y2021/day_17.ex

zevv · December 17, 2021, 3:27pm

A bit of brute force shooting, the only mathy thing happening is that the max height is calculated from the initial vertical velocity. For shits & giggles I also made a version that shoots every projectile on its own thread. I was shocked to find that was not even faster!

github.com

zevv/aoc2021/blob/master/lib/day17.ex

defmodule Day17 do

  def pewpew({x, y}, iv, {dx, dy}, {x1, y1, x2, y2}) do
    cond do
      x >= x1 and x <= x2 and y >= y1 and y <= y2 ->
        iv
      y < y1 and y < y2 ->
        false
      true ->
        pewpew({x+dx, y+dy}, iv, {max(0, dx-1), dy-1}, {x1, y1, x2, y2})
    end
  end

  def run do
    [_, x1, x2, _, y1, y2] = File.read!("data/17.txt")
                             |> String.trim()
                             |> String.split(["=", ".", ","], trim: true)
    target = [x1, y1, x2, y2]
           |> Enum.map(&String.to_integer/1)
           |> List.to_tuple

This file has been truncated. show original

ramuuns · December 17, 2021, 9:39pm

Right, so I somehow absolutely did not want to brute force, so instead I implemented a thing where

I get the list of x velocity candidates (which contains a tuple of {x, min_steps, stays_in_target_area?, max_steps}
get a similar list of y velocity candidates ({y, min_steps, max_steps})
effectively double that list of y velocity candidates because I only went for y < 0 (and all the positive ones are can be calculated from these)

and then for part one sort the ys, and get the first one for which we can find an x with corresponding steps

now for part two I ended up doing two approaches (which at least on this input data end up being equivalent performance wise)

for each y velocity find all x velocities, that reach the target in same amount of steps
make a map of %{nr_of_steps => %{ x: [list, of, x, velocities, in, this, amount, of, steps], y: [list, of, y, velocities, ...] }, ...}, and then do a Cartesian product of all the xes and ys

Anyhow, here’s the code for the curious: aoc/day-17.ex at 3bf7bf357a7431f427c0a0647dc163aeba73fc38 · ramuuns/aoc · GitHub

tommyokeefe · December 18, 2021, 1:34am

My approach is kinda brute force but it still runs in under 1 second on my laptop. The way I wrote part 1 I had all the target hits already, so part two was just swapping a count in for where I was getting the max.

github.com

tommyokeefe/advent-of-code-2021/blob/main/lib/advent_of_code_2021/day_17.ex

defmodule AdventOfCode.Day17 do
  def part1(args) do
    input = parse(args)
    velocity_y = elem(input, 1)
    find_velocities(input, {0, velocity_y}, velocity_y)
    |> get_max()
  end

  def part2(args) do
    input = parse(args)
    velocity_y = elem(input, 1)
    find_velocities(input, {0, velocity_y}, velocity_y)
    |> Enum.count()
  end

  def find_velocities(input, velocity, current_y, hits \\ %{})

  def find_velocities({target, too_short, too_wide, max_velocity}, {x, y}, current_y, hits) do
    x = x + 1
    result = launch_probe(target, too_short, too_wide, max_velocity, {x, y})

This file has been truncated. show original

tommyokeefe · December 18, 2021, 1:39am

Random question - Is there a cleaner/better way to do a ternary for assignment than this?

highest_peak = if y > highest_peak, do: y, else: highest_peak

Coming from a JavaScript/TypeScript background I’m used to doing something like:

highestPeak = y > highestPeak ? y : highestPeak

I’m just wondering if there is a terse syntax like this I can use in Elixir.

code-shoily · December 18, 2021, 1:47am

y > highestPeak && y || highestPeak

tommyokeefe · December 18, 2021, 1:48am

Thank you! I knew there had to be a way.

qhwa · December 18, 2021, 2:26am

You may also use Kernel.max/2 for the same purpose:

highest_peak = max(highest_peak, y)

APB9785 · December 18, 2021, 5:03pm

def part_2 do
  target = parse_input()

  vels =
    for x <- 0..target.x_range.last,
        y <- target.y_range.first..-target.y_range.first do
      {x, y}
    end

  Enum.count(vels, &valid?(&1, target))
end

Runs in 52ms. Full solution here

stevensonmt · December 19, 2021, 4:28am

Definitely feels like I’m missing something, but brute force worked well enough on my input:

github.com

stevensonmt/advent_of_code/blob/44036521e0c917f9f2b7a99c5096ac566380ff58/2021/day17/lib/day17.ex

defmodule Day17 do
  @moduledoc """
  Solution for AoC `Day17`.
  """

  def apogee(y_vel) do
    div(y_vel * y_vel + y_vel, 2)
  end

  def step({x, y}, {dx, dy}, apogee, target_x, target_y) do
    case in_target({x, y}, target_x, target_y) do
      :nailedit ->
        {:ok, apogee}

      :undershot ->
        new_dx =
          if dx == 0 do
            0
          else
            dx - 1

This file has been truncated. show original