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

20日目 - トレンチマップ

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

入力 - 2 つの入力の物語

20 日目は、基本的に 1 つのファイルに 2 つの異なる入力があったという点で興味深いものでした.確かに、以前に入力の「チャンク」を含むファイルを見たことがありますが、私の記憶が間違っているか (完全にもっともらしい)、まったく異なる 2 つの入力を見たのはこれが初めてです.結局のところ、これはそれほど問題ではありません.最初の入力は最初の行から取得されます.これは、各文字が 2 つの可能な状態のいずれかであるかどうかを知るだけでよいため、BitVector として扱います. 2 番目の入力では、Dict を使用します.ここで、キーは文字グリッド内の文字の行/列の座標であり、値はその文字が「#」(オン) か「.」かを示す Bool です. (オフ).

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

const Point = NTuple{2,Int64}
const Image = Dict{Point,Bool}

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

function ingest(path)
    return open(path) do f
        # Parse the first line into a BitVector, with '#' => 1, '.' => 0
        algostr = readuntil(f, "\n\n")
        algo = collect(algostr) .== '#'

        # Parse the rest of the lines into a Dict of (row, col) => true/false, 
        # where the value is true if the corresponding row/col of the input
        # is a '#'
        image = Dict{Point,Bool}()
        imagestr = readchomp(f)
        for (row, line) in enumerate(split(imagestr))
            for (col, char) in enumerate(collect(line))
                image[(row,col)] = char == '#'
            end
        end

        (algo, image)
    end
end

問題ステートメントの「無限」というキーワードは、Matrix または BitMatrix を使用することがこのパズルの間違った呼び出しになることを示しています.

パート 1 - 光の海の下 (ピクセル)

今日のパズルは (ありがたいことに) とても簡単です.低解像度の画像が与えられた場合、それが有用なものに解決されるまで、それを強化し続けます.テレビで見られるように!これがうまくいかないわけがありません.さらに、問題を解決した後は、本当にクールな方法でサングラスを着用できるようになるかもしれません.ええええええええええええええええええええええええええええええええええええええええええええええええええええええええええええええええええええええええええ特定のピクセルの周囲の 3x3 グリッドの値を取得して、その新しい値を決定します.唯一の本当にトリッキーなビット (「ビット」、わかりますか?) は、アクティブに保持していないピクセルに使用する値を知ることです.トラックの.これらすべてに対して「false」または「0」になると思うかもしれませんが、それは難しい部分です!

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

# Used to get the coordinates of the nine pixels surrounding any given
# pixel in the image
const OFFSETS = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,0), (0,1), (1,-1), (1,0), (1,1)]

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

# Get a list of the coordinates of the pixels surrounding a given point
offsets(p::Point) = [p .+ offset for offset in OFFSETS]

# Convert binary value to decimal
todecimal(x) = sum(D*2^(P-1) for (D, P) in zip(x, length(x):-1:1))

# Given a point in the image, calculate the value of the point from the
# 3x3 area centered on that point
function valueat(image::Image, point::Point, default=false)
    value = [get(image, p, default) for p in offsets(point)]
    return todecimal(value)
end

# Enhance the image! Creates a new image (expanded by one in all directions) 
# where each pixel is flipped according to its calculated value.
function enhance(image::Image, algo::BitVector, default=false)
    newimage = Dict{Point,Bool}()

    # Need to expand the enhancement area by 1 in all directions each pass
    (minpoint, maxpoint) = extrema(keys(image))
    rng = (minpoint[1]-1):(maxpoint[2]+1)

    # For each possible point in the new image, determine its value
    for point in Iterators.product(rng, rng)
        pointvalue = valueat(image, point, default)
        pixel = algo[pointvalue + 1]
        newimage[point] = pixel
    end

    return newimage
end

# Solve ------------------------------------------------------------------------

function solve(input, rounds; test = false)
    (algo, image) = input
    for round in 1:rounds
        # The 'real' algorithm (not the test) has a '#' in the first position 
        # and a '.' in the last position, which means that the 'empty' pixels
        # surrounding the image all flip from '.' to '#' on odd numbered rounds.
        # The 'test' input does not have this 'feature'.
        default = !test && round % 2 == 0
        image = enhance(image, algo, default)
    end
    return sum(values(image))
end

どうやら Eric Wastl 、Advent of Code の作成者でありデザイナーである彼は、この 2 日間はおそらく簡単すぎたのではないかと考えたようで、彼は私たちを緊張させておく必要があったと考えました...よくやった!実際の入力 (テスト入力ではない) の「強化アルゴリズム」には、ラウンドごとに、追跡されていないピクセルの無限の広がりにあるすべてのピクセルをオフからオンに「反転」し、再び元に戻すという面白い機能がありました.これについては、「光に敏感な視聴者」の警告の1つがあったはずだと思います.しかし、それを知っていれば、1 回おきにデフォルト値を変更して、最終的な答えを得ることができます.

パート 2 - デ ナダ

パート 1 と同じですが、あと 1 回だけです.この種のエスカレーションは以前にも見たことがあり、パート 1 の rounds 関数で既に solve() 引数を取得しているため、ここで答えを得るには、50 引数として 2 ではなく rounds を渡すだけで済みます.新しいコードはありません!

要約

20日目が必要でした.18日目と19日目は本当に私を引き延ばしました.18日目は満足のいく結果が得られなかった道をたどり、19日目は数学の勉強を強いられました.ソリューションと毎日のブログ投稿.休日が近づいてきたので、20 日目の非常に単純な実装で、物事にスパイスを加えるために 1 つの奇妙なトリックが投入されました. Julia でここまでたどり着いたことで、この比較的簡単なパズルでも、コードが指からスムーズに出てきて、Julia でうまく考えることができたことを嬉しく思います.こちらもジャストインタイム!

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