今年もその季節です!昨年同様、Advent of Code パズルの解法を投稿します.今年は Julia のパズルを解きます.ソリューションとコードを GitHub にも投稿します.昨年は、最初は R で、次に Rust を学習するための一連の演習として AoC を大いに楽しんだので、今年のパズルがもたらすものを見るのが本当に楽しみです. AoC を試したことがない場合は、私と一緒に試してみることをお勧めします.

17日目 - トリックショット

問題の説明 HERE を見つけます.

入力 - 目標を達成する

今日のパズル入力は、「ターゲット領域: x=.., y=-..」の形式のテキスト ファイル内の 1 つの文で、「」の値は実数です.このために、各数値のキャプチャ グループで正規表現を使用し、それらのキャプチャされた数値を整数に解析し、それらを TargetRange という名前のタプルに詰め込みます.最後の部分は、適切な型エイリアスを与えて、後続のコードを読みやすくするだけです.

# Helper Functions -------------------------------------------------------------

const TargetRange = @NamedTuple begin
    x_min::Int64
    x_max::Int64
    y_min::Int64
    y_max::Int64
end

function targetrange(vals::Vector{Int64})::TargetRange
    (x_min, x_max, y_min, y_max) = vals
    return (x_min=x_min, x_max=x_max, y_min=y_min, y_max=y_max)
end

# Ingest the Data -------------------------------------------------------------

function ingest(path)
    re = r"x=(-?\d+)\.\.(-?\d+), y=(-?\d+)\.\.(-?\d+)"
    m = match(re, readchomp(path))
    return targetrange([parse(Int, i) for i in m.captures])
end

Julia について不満があるとすれば、名前付きタプルを使用すると、これらのパズルのいくつかで通常の構造体よりもパフォーマンスの高いコードが得られることが証明されていますが、型エイリアスと同じ名前でコンストラクターを作成することはできません.ちょっとした不満ですが、これらは構造体と非常によく似た動作をするため、構造体と同じ方法で作成できるはずだと直感的に思えます.私が言ったように、マイナーな不満ですが、上記の TargetRange() の代わりに targetrange() を使用したいです.それで全部です.

パート 1 - 見せびらかす

待って、待って、待って.持続する.昨日、16 進値を 1 ビットずつデコードしたところ、エルフが「ハイ」と言いました!?そして、私たちはそれを通り越して移動するつもりですか?今日、私たちが調査を開始する気分になっているのも不思議ではありません!私たちの目標は、プロセスで甘いハング (フロート?) 時間を取得しながら、プローブをターゲットゾーンに着陸させる発射速度 (水平方向と垂直方向の両方) を特定することです.これは数学のように聞こえます...

# Some Useful Data Structures --------------------------------------------------

# I find it helpful to name my Types according to their use. 
const Velocity = @NamedTuple{x::Int64, y::Int64}
const Position = @NamedTuple{x::Int64, y::Int64}
const VelocityRange = @NamedTuple{x::UnitRange{Int64}, y::StepRange{Int64,Int64}}

# Helper Functions -------------------------------------------------------------

# These little functions do a lot of work. 
# - `triangle()` returns the `nth` triangle number (or Gaussian sum), the sum of
# the sequence of numbers up to and including `n`.
# - `distanceat()` calculates the distance traveled for a given velocity of `V`
# at time `T`. Because the puzzle description indicates that velocity degrades
# at a constant rate over time, the general formula for distance is
# `position at time T = (initial velocity x T) - loss in velocity`, where the
# loss in velocity at any given time is the sum of all the prior losses.
# - `peak()` returns the maximum distance traveled for initial velocity `V₀`.
# This corresponds to the distance when the time matches the initial velocity,
# after which the accumulated velocity loss is larger than `V₀ × T`.
triangle(n) = (n^2 + n) ÷ 2
distanceat(V₀, T) = (V₀ * T) - triangle(T - 1)
peak(V₀) = distanceat(V₀, V₀)

# Given an initial velocity and a time, calculate the position of the launched
# probe at `time`. In the x-direction, this is either the distance at `time`, or
# the peak distance if `time` is greater than the initial velocity (the probe
# will not travel backwards once it reaches peak distance).
function positionat(initial::Velocity, time::Int64)::Position
    (v_x0, v_y0) = initial
    p_yt = distanceat(v_y0, time)
    p_xt = time >= v_x0 ? peak(v_x0) : distanceat(v_x0, time)
    return (x=p_xt, y=p_yt)
end

# Identify the possible initial x and y velocities for a given `target`.
function velocityrange(target::TargetRange)::VelocityRange
    # The smallest possible x velocity that will reach the target is the
    # velocity where `triangle(v_x)` is at least equal to the minimum
    # range of x in the target. Any lower velocity that this will not reach
    # the distance of `target.x_min`. The maximum x velocity is just the
    # maximum range of x in the target, since the probe could theoretically
    # be shot straight at that point.
    v_xmin = 0
    while triangle(v_xmin) < target.x_min; v_xmin += 1; end
    v_xrange = v_xmin:target.x_max

    # The largest possible y velocity is the one that, when reaching the point
    # of y == 0, will not overshoot the target on the next step. This works out
    # to be the absolute value of `target.y_min`. This range is given backwards,
    # since it is assumed that the maximum height will be found at larger values
    # for y velocity.
    v_ymax = abs(target.y_min)
    v_yrange = v_ymax:-1:target.y_min

    return (x=v_xrange, y = v_yrange)
end

# Given the initial velocity of a probe, determine whether that probe will land
# in the target zone. 
function willhit(initial::Velocity, target::TargetRange)::Bool
    # Starting at the initial position of 0, 0 and time 0
    (x_t, y_t) = (0, 0)
    time = 0

    # Check the position of the probe at subsequent times until it reaches a
    # position either to the right or below the target area. If, during this
    # search, the probe position is found to be within the target area, return
    # true. Otherwise, return false.
    while x_t <= target.x_max && y_t >= target.y_min
        x_t >= target.x_min && y_t <= target.y_max && return true
        (x_t, y_t) = positionat(initial, time)
        time += 1
    end
    return false
end

# Solve Part One ---------------------------------------------------------------

# Starting with the range of possible velocities, check each combination of 
# x and y velocities until an x/y velocity is found that lands in the target
# area. Since we're counting down from the maximum possible y velocity, the
# first probe we find that lands in the target will reach the maximum 
# height, so just return the peak of that y velocity.
function part1(input)
    v_range = velocityrange(input)

    for (v_x, v_y) in Iterators.product(v_range...)
        initial = (x=v_x, y=v_y)
        willhit(initial, input) && return peak(v_y)
    end
    error("Could not find maximum Y for $input")
end

数学でした!まあ、少なくともいくつか.反復やコードなしでこの部分を解決するための数学があると確信しています.私はそれに取り組み、少し考えましたが、解読できませんでした.それが私がコードを書く理由だと思います!

パート 2 - 最も孤独なプローブ

あ、プローブは 1 つしかありませんね.インターネットでこれらのトリックショットのビデオを見たことがありますが、最初に計算を行ったとしても、最初の試行でそれらを着陸させることは (ほとんど) ないことを確信しています.最も安全なショットを選択する必要があると思いますが、それを行う唯一の方法は (明らかに)、ターゲット エリアに着陸するすべての発射速度を特定することです.実際、それはそれほど悪くはありません.

# Solve Part Two ---------------------------------------------------------------

# This time, just search through the whole range of possible x/y combinations
# and increment the counter for each launch velocity that lands the probe in
# the target area.
function part2(input)
    v_range = velocityrange(input)
    found = 0

    for (v_x, v_y) in Iterators.product(v_range...)
        initial = (x=v_x, y=v_y)
        if willhit(initial, input)
            found += 1
        end
    end

    return found
end

ここでは大きな変更はありません.発射ベクトルの可能な範囲全体をループし、ターゲット ゾーンに着陸するすべてのベクトルのカウントをインクリメントします.

要約

今日は数式を並べるのに気が散ってしまいました!私は、私が探していた答えに似たものを何も与えてくれなかった二次式になりました.代数を練習する機会にイライラしているのか、感謝しているのかはわかりません.それがうまくいかなかったので、おそらくイライラしました.とはいえ、私はジュリアでますます快適になっているので、それは勝利です.プロセスは確実に機能しています.

別の解決策を見つけた場合 (または私の解決策の間違いを見つけた場合) は、私に連絡してください!