연휴(및 프로그래밍) 정신으로 Advent of Code 2020 퍼즐에 대한 솔루션을 여기에 게시할 예정입니다. 게시된 후 적어도 하루 후에 여기에 게시할 예정입니다(스포일러 없음!). R로 솔루션을 구현할 것입니다. 왜냐하면 그게 제가 좋아하는 것이기 때문입니다! 내가 하지 않을 일은 실제 답변을 게시하는 것입니다.

또한 일반적으로 퍼즐에 다운로드 가능한 입력이 있을 때마다 input.txt라는 파일에 저장합니다.

15일 - 광란의 암송

문제 설명을 찾습니다HERE.

1부 - 순록 엘프 게임

1부에서는 기억력 게임을 하는 엘프가 있습니다. 숫자 목록이 주어지면 엘프들은 각 숫자를 차례로 말합니다. 목록의 끝에 도달하면 이전 차례에 말한 숫자가 이전 차례 이전에 말한 이후의 라운드 수를 말하기 시작합니다. 따라서 목록 0, 3, 6 의 경우 처음 9턴 동안 [0, 3, 6], 0, 3, 1, 0, 4, 0를 얻습니다. 진짜 질문은 2020년 턴에 말하는 숫자는 무엇입니까?

솔직히 말해서, 아래의 구현은 이것에 대한 나의 첫 크랙이 아니지만, 나중에 명확해질 이유 때문에(또는 이러한 퍼즐이 어떻게 구성되어 있는지에 대한 아이디어를 얻기 시작한다면 더 빨리), R에서 생각해낼 수 있는 가장 빠른 구현.

library(testthat) # For tests

# Given a starting sequence `start_vec` and a number `n`, returns the `n`th 
# number of the elve's counting game, according to the rules in the puzzle
# instructions. Note, the `rounds` vector below contains, at each index, the
# last round (prior to the most recent round) that the number (index - 1) was
# spoken. This is because R is 1-indexed, so the value for '0' is stored in
# index '1' and so on.
number_spoken <- function(start_vec, n) {
  rounds <- numeric(0) # Empty vector for the round a number was last spoken
  start_len <- length(start_vec) # Length of the `start_vec`
  last_number <- start_vec[start_len] # Last number spoken, starting value

  # Fill in the starting numbers into `rounds`
  for (i in 1:start_len) { rounds[[start_vec[i]+1]] <- i }

  # For each number after the starting veector...
  for (i in (start_len+1):n) {
    index <- last_number + 1 # Correction for 1-indexing

    # If the `index` either contains the number of the last round or an NA, 
    # then the last round was the first time `last_number` was spoken and the
    # `next_number` should be '0'. Otherwise, the `next_number` should be the
    # number of the last round (i-1) minus the number of the previous round
    # in which the number was spoken (rounds[last_number+1])
    next_number <- if (is.na(rounds[index]) || rounds[index] == i - 1) {
      0
    } else {
      (i - 1) - rounds[last_number+1]
    }

    rounds[last_number+1] <- i - 1 # Update the round number stored for this number
    last_number <- next_number # The new `last_number` is this `next_number`

    # Sanity Check
    if (i %% 10000 == 0) { cat('\r', paste('Simulating round:', i)) }
  }

  next_number # Return the `n`th number spoken
}

test_that("sample inputs return expected results", {
  expect_equal(number_spoken(c(0, 3, 6), 2020), 436)
  expect_equal(number_spoken(c(1, 3, 2), 2020), 1)
  expect_equal(number_spoken(c(1, 2, 3), 2020), 27)
  expect_equal(number_spoken(c(2, 3, 1), 2020), 78)
  expect_equal(number_spoken(c(3, 2, 1), 2020), 438)
  expect_equal(number_spoken(c(3, 1, 2), 2020), 1836)
})

answer1 <- number_spoken(c(2, 0, 1, 7, 4, 14, 18), 2020)

# Answer: 496

기억이 나지 않는 이유로 이 퍼즐에 테스트를 사용하도록 영감을 받았습니다. testthat 패키지와 기능을 통해 한 번에 모두 테스트할 수 있는 쉬운 방법을 제공하기 때문에 주어진 테스트 입력의 수와 관련이 있다고 생각합니다. 알려진 엣지 케이스를 놓치지 않고 구현을 조정할 수도 있습니다.

2부 - 더!

source('exercise_1.R')

# Yep, that's it.
answer2 <- number_spoken(c( 2, 0, 1, 7, 4, 14, 18), 30000000)

구현 속도가 중요한 이유입니다.

마무리

아, 컴파일된 언어를 사용하는 사람들이 부럽기도 합니다만, 제 일상 업무가 엄청나게 빠른 배열 조회보다 shiny 대시보드와 tidyverse의 데이터 분석을 훨씬 더 잘 활용한다는 것을 깨달았습니다. 그리고 나는 그것에서 스냅합니다. 즉, 이것은 R에서 신속하게 작업을 수행하는 방법에 대해 배울 수 있는 좋은 기회였습니다(지금까지 많은 시간을 할애하지 않은 것입니다). 간단한 요점은 벡터에 NA 가 많이 포함되어 있어도 벡터의 알려진 인덱스에서 값을 얻는 것은 매우 간단하다는 것입니다. 환경에서 키로 값을 찾는 것보다 확실히 빠르며 명명된 목록을 일종의 의사 사전으로 사용하는 것보다 훨씬 빠릅니다. 전반적으로 좋은 하루!

다른 솔루션을 찾았거나 내 솔루션 중 하나에서 실수를 발견한 경우 저에게 연락해 주세요!