祝日(そしてプログラミング)の精神で、私は私の解決策を投稿しますAdvent of Code 2020 パズルは、ここでは、少なくとも1日後に掲示されています.私はRのソリューションを実装しているので、まあ、それは私が好きです!私がしないことは、実際の答えのいずれかを掲示しているだけで、その背後にある推論.
また、一般的な慣例として、パズルが入力をダウンロードしたときはいつでも、私はそれをファイルに保存していますinput.txt .

日9 -符号化エラー

問題記述HERE .

パート1 -それはちょうど追加しません

非標準のポート、私は正しいか.ああまあ、我々はとにかく接続し、今我々は現在のフライトをハックする準備が整いました.待って、我々が本当にやっていることですか?そうです.ああ、何が間違って行くことができる?この部分のために、私たちは、どの番号(1 K番号のリストの中で)が前の25の数字の2つの合計として誘導されることができないか特定する必要があります.これは、1日、パート1、ちょうど一度の束を繰り返してかなり似ています.私は私のアプローチを合理化して、このリストの2つの数字を見つけます.合計から可能な補数のベクトルを差し引くことによって新しいベクトルを作成して、それから、その新しいベクトルの交差点と付属品の元のベクトルをとることは、両方のベクトルに現れる一連の数をもたらすでしょう.このセットで少なくとも2つの数字があるならば、あなたは合計に合計するその元のベクトルで少なくとも2つの数があるということを知っています.セットの1つの数だけがあるならば、それはあなたの合計の半分がAddedの原型のベクトルにあったことを意味するが、合計に合計2つの数があるというわけではありません.

test_input <- c(
   "35", "20", "15", "25", "47", 
   "40", "62", "55", "65", "95",
  "102", "117", "150", "182", "127",
  "219", "299", "277", "309", "576"
)

real_input <- readLines('input.txt')

# Helper function, checks a element of numeric vector `vec` at index `i` to
# determine whether the preceding `len` elements contain at least two items
# that sum to `vec[i]`
check_index <- function(i, vec, len) {
  # Some paranoid input validation
  if (i <= len) { stop('`i` must be greater than `len`') }
  if (length(vec) < i) { stop('`vec` must contain at least `i` items') }

  n <- vec[i] # Current number to check
  n_vec <- vec[(i-len):(i-1)] # Preceding `len` elements

  # Do at least two numbers appear in both the set of numbers you get when all
  # `n_vec` elements are subtracted from `n` and the original `n_vec` numbers?
  length(intersect(n - n_vec, n_vec)) >= 2
}

# Main function, iterates through numeric vector `vec` and checks each element
# in `vec` at index > `len` to determine whether any two of the `len` elements
# prior to `vec[i]` sums to `vec[i]`. Returns the first `i` where this is not
# true.
first_false <- function(vec, len) {
  check_range <- (len+1):length(vec) # Only check `vec` items after the `len`th

  for (i in check_range) {
    if (!check_index(i, input_as_num, check_n)) { return(i) }
  }

  return(NA)
}

input_as_num <- as.numeric(real_input)
check_n <- 25 # Number of previous items to check, 5 for tests, 25 for real data

answer1 <- input_as_num[first_false(input_as_num, check_n)]

answer1 2番目の部分で使用されますので、数値の識別子で保存します.正直にmy first two approaches この問題は複雑すぎた.私は、数字がそれほど大きくなかったならば、それが働いたかもしれないテーブル化アプローチで最初にそれを解決しようとしました.残念なことに、私の(かなりbeefy)ラップトップは、実入力で最も大きい数のいくつかのために十分に長いベクトルを割り当てることができませんでした.memoizationは動作しますが、私の実装は、単にintersect() 上記の通り.

パート2 -あなたは強く感じ、私の友人？

本当にこの弱点を暴露するXMAS 暗号化は、パート1からの回答に合計する入力ベクトルの連続セクションを見つける必要があります.入力が注文されていない(そして、それらを分類することは失敗を保証するでしょう)ので、私はちょうどその範囲を捜すどんなより良い方法も思い付くことができませんでした.入力より大きな数字の一般的なパターンに気づいて、私はより速い結果を望んでいる終わりから検索を始めました.ちょうどチェックするために、私も正面から捜してみました.方法は遅くなります.手にその範囲で、我々は答えを得るために必要なすべてを持っています.

# Helper function, given an index `i`, a number `total`, and a numeric vector `vec`,
# attempts to find a contiguous range in `vec` starting with index `i` that 
# sums to `total`
check_index <- function(i, total, vec) {
  next_i <- i + 1 # The current end of the range in `vec` to check

  while (next_i <= length(vec)) {
    current_sum <- sum(vec[i:next_i]) # Current contiguous sum
    if (current_sum == total) { return(i:next_i) } # Success!
    if (current_sum > total) { return(NULL) } # No need to check further
    next_i <- next_i + 1 # Try the next `next_i`
  }
}

# Main function, given a number `total` and a numeric vector `vec`, finds the
# first contiguous segment of `vec` that sums to `total`, working backwards
# from the end of `vec`
contiguous_range_sum <- function(total, vec) {
  for (p in seq(length(vec)-1, 1)) { # Work backwards from the end
    sum_range <- check_index(p, total, vec)
    if (!is.null(sum_range)) { return(sum_range) } # NULL if no range is found
  }
  NA_integer_
}

input_as_num <- as.numeric(real_input)
sum_range <- contiguous_range_sum(answer1, input_as_num)
contiguous_nums <- input_as_num[sum_range]
answer2 <- min(contiguous_nums) + max(contiguous_nums)

私も、このコードの不必要に複雑な順列のカップルを経験しました、しかし、2、3の再要因の後、私は結果にとても満足しています.

包む

このパズルは、全体的にかなり簡単だった.パート2で後方への反復のように、実行が少し難しくなったので、私にはすぐにはっきりしないカップルがいました.私はなんとかパート1で良い方法で私自身の方法で得ることができました、しかし、全体的にこれは以前からのより難しい問題のいくらかからの良い報酬です.
別の解決策(または私の1つのミスを発見)を見つけた場合は、私にラインをドロップしてください!