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

19日目 - ビーコンスキャナー

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

入力 - 一見シンプル

入力の解析は、今日のパズルの難しい部分ではありませんでした.ここでは、入力の各「チャンク」を Dict のキーと値のペアに変換しているだけです.ここで、各キーはスキャナーの ID 番号であり、その値はビーコン座標の Set です.

# Data Structures --------------------------------------------------------------

# We'll store each `Beacon` as a Tuple of (x, y, z) coordinates, each `Scanner`
# as a Set of `Beacon`s, and maintain a collection of `Scanner`s as a Dict where
# each key is the scanner ID and value is the set of beacons associated with
# that scanner.
const Beacon = NTuple{3,Int}
const Scanner = Set{Beacon}
const Scanners = Dict{Int,Scanner}

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

# Functions to help parse a chunk of the input into an (<ID>, `Scanner`) pair

# Parse a line starting a scanner chunk into the scanner ID
scannerid(s) = parse(Int, match(r"--- scanner (\d+) ---", s)[1])

# Parse a line containing beacon coordinates into a `Beacon`
parsebeacon(s) = NTuple{3,Int}(parse(Int,n) for n in split(s, ","))

# Parse a "scanner chunk" (from the "--- scanner ## ---" line to the next blank
# line) into an (<ID>, `Scanner`) pair, for conversion into a Dict entry.
function parsescanner(f)
    id = readline(f) |> scannerid
    beacons = Set(parsebeacon(s) for s in split(readuntil(f, "\n\n")))
    return (id, beacons)
end

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

# Parse scanner chunks until the file is empty!
function ingest(path)
    return open(path) do f
        entries = []
        while !eof(f); push!(entries, parsescanner(f)); end
        Scanners(entries)
    end
end

汗かいていない.ここでも、Julia の Base パッケージに組み込まれているストリームおよびデータ解析関数により、これがかなり簡単になります.

パート 1 - 私たちはどこにいますか?

パズルの入力によると、巧妙に打ち上げられたプローブは、現在の位置をマッピングするために使用できるスキャナーとビーコンでエリアをシードしました.残念ながら、スキャナーはお互いのことや自分の向きを知る方法がありません.どういうわけか、3 つの軸のうちの 1 つに正確に位置合わせすることができますが、これは少し疑わしいですが、コーディングがいくらか簡単になる (そして潜在的なランタイムが大幅に削減される) ため、それを無視しましょう.今日のパズルには、(私が知る限り)かなり力ずくのアプローチが必要です.各スキャナーが持っているビーコンの数に関係なく、スキャナーのペアごとに最大 24 の変換を適用します…

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

# The cosines for each 90° rotation: 0° => 1, 90° => 0, 180° => -1, 270° => 0
const COS = Dict{Int,Int}([(0,1), (90,0), (180,-1), (270, 0)])

# The sines for each 90° rotation: 0° => 0, 90° => 1, 180° => 0, 270° => -1
const SIN = Dict{Int,Int}([(0,0), (90,1), (180, 0), (270,-1)])

# These are all the rotations that can place a scanner into any of the 24
# orientations described in the puzzle input, starting with no rotation.
const ROTATIONS = [
    (0, 0, 0), (90, 0, 0), (180, 0, 0), (270, 0, 0),
    (0, 90, 0), (90, 90, 0), (180, 90, 0), (270, 90, 0),
    (0, 180, 0), (90, 180, 0), (180, 180, 0), (270, 180, 0),
    (0, 270, 0), (90, 270, 0), (180, 270, 0), (270, 270, 0),
    (0, 0, 90), (90, 0, 90), (180, 0, 90), (270, 0, 90),
    (0, 0, 270), (90, 0, 270), (180, 0, 270), (270, 0, 270)
]

# Describes the unit vector for a 3D system
const Basis = NTuple{3, NTuple{3,Int}}

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

# The formula to rotate a vector about the x axis in 3 dimensions:
# - x′ = x
# - y′ = y × cos(θ) - z × sin(θ)
# - z′ = y × sin(θ) + z × cos(θ)
rotabout_x(x, y, z, θ) = (x, y*COS[θ] - z*SIN[θ], y*SIN[θ] + z*COS[θ])

# The formula to rotate a vector about the y axis in 3 dimensions:
# - x′ = x × cos(θ) + z × sin(θ)
# - y′ = y
# - z′ = z × cos(θ) - x × sin(θ)
rotabout_y(x, y, z, θ) = (x*COS[θ] + z*SIN[θ], y, z*COS[θ] - x*SIN[θ])

# The formula to rotate a vector about the z axis in 3 dimensions:
# - x′ = x × cos(θ) - y × sin(θ)
# - y′ = x × sin(θ) + y × cos(θ)
# - z′ = z
rotabout_z(x, y, z, θ) = (x*COS[θ] - y*SIN[θ], x*SIN[θ] + y*COS[θ], z)

# Rotate a vector about the x, y, and z axes in sequence
function rotabout_xyz(x, y, z, xθ, yθ, zθ)
    (x, y, z) = rotabout_x(x, y, z, xθ)
    (x, y, z) = rotabout_y(x, y, z, yθ)
    return rotabout_z(x, y, z, zθ)
end

# Pre-calculate the rotation matrices for each of the 24 possible Scanner
# facings. The unit vector for 'no rotation' is `standard` below. Each rotation
# matrix can be used to translate points from one scanner facing to another
# scanner facing.
const BASES = begin
    standard = ((1,0,0), (0,1,0), (0,0,1))
    (sx, sy, sz) = standard
    unitvectors = []

    for rotation in ROTATIONS
        unitvector = (
            rotabout_xyz(sx..., rotation...),
            rotabout_xyz(sy..., rotation...),
            rotabout_xyz(sz..., rotation...),
        )
        push!(unitvectors, unitvector)
    end
    unitvectors
end

# Translate the location of a given beacon using another basis vector. This is
# basically just a matrix right multiply:
# https://cseweb.ucsd.edu/classes/wi18/cse167-a/lec3.pdf
function translate(beacon::Beacon, basis::Basis)
    (bx1, by1, bz1) = basis[1]
    (bx2, by2, bz2) = basis[2]
    (bx3, by3, bz3) = basis[3]
    (x, y, z) = beacon

    newx = x*bx1 + y*by1 + z*bz1
    newy = x*bx2 + y*by2 + z*bz2
    newz = x*bx3 + y*by3 + z*bz3

    return (newx, newy, newz)
end

# Translate all the beacon locations for one scanner to what their locations
# would be if the scanner had a different facing.
function translate(scanner::Scanner, basis::Basis) 
    return Set(translate(beacon, basis) for beacon in scanner)
end

# Identify the beacons detected in common between two scanners. This is a pretty
# intensive process:
# - For each possible scanner facing...
# - Translate all the `Beacon`s for Scanner `b` to the given facing
# - For each combination of a `Beacon` detected by Scanner `a` and a `Beacon`
# detected by Scanner `b`...
# - Calculate the distance between the `Beacon` from `a` and the `Beacon`
# from `b`, called `offset`
# - Add the `offset` to all the `Beacon` locations from Scanner `b`
# - Check how many of the offset Beacons from Scanner `b` are matched by a 
# Beacon detected by Scanner `a`
# - If 12 or more beacon locations match, then we have determined the
# relative location of Scanner `b` from Scanner `a`
function incommon(a::Scanner, b::Scanner)
    for basis in BASES
        translated_b = translate(b, basis)
        for (a_beacon, b_beacon) in Iterators.product(a, translated_b)
            offset = a_beacon .- b_beacon
            shifted_b = Set(beacon .+ offset for beacon in translated_b)
            length(a ∩ shifted_b) >= 12 && return (shifted_b, offset)
        end
    end
    return Iterators.repeated(nothing)
end

# To map all the Scanners, we check each Scanner against every other Scanner, 
# adding scanners to `mapped` when we identify (and apply) the appropriate
# offset of between the two scanners.
function mapscanners(scanners)
    mapped = Dict(0 => scanners[0])
    offsets = [(0,0,0)]
    searched = Set()

    while length(setdiff(keys(scanners), keys(mapped))) > 0
        for id1 in keys(scanners)
            (id1 ∈ searched || id1 ∉ keys(mapped)) && continue

            for (id2, scanner2) in scanners
                (id2 ∈ keys(mapped) || id1 == id2) && continue
                (common, offset) = incommon(mapped[id1], scanner2)

                if !isnothing(common)
                    mapped[id2] = common
                    push!(offsets, offset)
                end
            end

            push!(searched, id1)
        end
    end
    return (mapped, offsets)
end

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

# Given the mapping of scanners from `mapscanners()`, count the total number of
# beacons. Since they've all been translated and offset relative to the initial
# scanner, this just means union-reducing the sets of beacons.
function part1(mapped)
    allbeacons = reduce(∪, values(mapped))
    return length(allbeacons)
end

ああ、また数学だった.これが幾何学なのか線形代数なのかよくわからないということは、おそらく、これを行うのに十分な数学を知らないということです.まあ、それは動作します.もちろん、これはおそらく、このパズルを解くためのより優れた、より数学的な方法もあるということでもあります…

パート 2 - 結局のところ、イッツ ア スモール ワールド

各スキャナーが他のスキャナーと比較してどこに位置するかがわかったので、次はこれらのスキャナーがどれだけ広く普及しているかを調べます.パート 2 では、任意の 2 つのスキャナー間の最大距離 (マンハッタン スタイル) を特定します.以前の offset を保持していてよかったですね.

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

# Calculate the manhattan distance between two beacons
distance(a::Beacon, b::Beacon) = mapreduce(abs, +, a .- b)

# Given the offsets from `mapbeacons()`, calculate the manhattan distance between
# all pairs of offsets and return the largest value.
function part2(offsets)
    maxdistance = 0
    for (offset1, offset2) in Iterators.product(offsets, offsets)
        distance = mapreduce(abs, +, offset1 .- offset2)
        maxdistance = max(maxdistance, distance)
    end
    return maxdistance
end

これらはすべて相対距離であるため、すべてのペア間の距離を計算し、最大のものを取るだけです.汗かいていない!

要約

これは、私にとってもう 1 つの非常に時間のかかる日でした.その理由の 1 つは、すべてのビーコンを他のすべてのビーコンに対してチェックすることなく (複数回、おそらく複数回)、スキャナーが相互に相対的にどこにあるかを特定するための巧妙な方法が必要であることを知っていたからです. ).このソリューションの実行時に表示されます.mapscanners() 関数を実行すると、入力に約 15 秒かかります.次に、24 の異なる面の回転を計算し、24 のスキャナ面のそれぞれのビーコン位置を変換する方法を調査するという小さな問題がありました.私にとって非常に幸運なことに、単位ベクトルについて言及したビデオを見て、ポイントを別の単位ベクトルに変換することについて少し話したのはそれほど前のことではありません.大変な一日でしたが、達成できてうれしいです.

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