방학(과 프로그래밍)의 정신에 따라 저는 여기서 Advent of Code 2020 수수께끼 해결 방안을 발표할 것입니다. 적어도 발표 후 하루는 (파괴자가 없습니다!)나는 R에서 이러한 해결 방안을 실현할 것이다. 왜냐하면 나는 이렇게 하는 것을 좋아하기 때문이다.나는 어떤 실제 답안도 발표하지 않을 것이다. 단지 배후의 이유만 발표할 뿐이다.
그 밖에 일반적으로 퍼즐에 다운로드할 수 있는 입력이 있을 때마다 나는 그것을 input.txt라는 파일에 저장한다.

8일째 - 휴대용 주차

문제 설명 찾기HERE.

1부. - 레임보이.

아마도 나와 나는 고등학교 컴퓨터 수업에 대한 모호한 기억일 것이다. 그러나 나는 이 수수께끼에서 강렬한 기본적인 느낌을 받았다.여기에서, 우리는 휴대용 게임 장치 안내 서열의 '지령' 목록을 얻었는데, 유일한 목적은 게이머들이 그들의 게임에 접근할 수 있도록 하기 전에 조금 건너뛰는 것 같다.아이에게 만족감을 늦추는 것 같은 것을 가르칠 수도 있다.어쨌든 우리 빨리 지령을 분석합시다!

시뮬레이션 방법

우리가 사용할 첫 번째 방법은 명령을 순서대로 실행하는 것을 모의하고 결과를 분석해서 무슨 일이 일어났는지 보는 것이다.

library(stringr) # For `str_extract()`
library(purrr) # For `map()`, `map2()`

test_input <- c(
  "nop +0",
  "acc +1",
  "jmp +4",
  "acc +3",
  "jmp -3",
  "acc -99",
  "acc +1",
  "jmp -4",
  "acc +6"
)
real_input <- readLines('input.txt')

# Helpful structure, a list containing one function per instruction type
# assigned by name
funs <- list(
  nop = function(accumulator, pointer, arg) {
    list(accumulator = accumulator, pointer = pointer + 1)
  },
  acc = function(accumulator, pointer, arg) {
    list(accumulator = accumulator + arg, pointer = pointer + 1)
  },
  jmp = function(accumulator, pointer, arg) {
    list(accumulator = accumulator, pointer = pointer + arg)
  }
)

# Helper function, given a vector of lines from the input (format 'acc +6'), 
# returns # a nested list object where each list item represents a single 
# instruction and each sublist item contains a [['fun']], which is the name of 
# the instruction and an [['arg']], which is the argument for that line, 
# ex. list(list(fun = 'acc', arg = 6), list(fun = 'nop', arg = -5))
parse_instructions <- function(funs, input) {
  fun <- str_extract(input, 'nop|acc|jmp')
  arg <- as.integer(str_extract(input, '[+-]\\d+'))

  result <- map2(fun, arg, list)
  result <- map(result, setNames, c('fun', 'arg'))
  result
}

# Main function, given a set of instructions (produced by 
# `parse_instructions()`), runs the 'code' described and returns the result
# as a list containing the current `accumulator` value, the `pointer` to the
# current line in the instructions, a list of instruction line numbers in the
# order they ran as `run_lines`, and a flag for whether the instruction set
# was terminated by running all the instructions as `successfully_completed`.
profile_instructions <- function(instructions) {
  # These values are all in a list to make it easier to return the entire
  # package at the end
  profile <- list(
    accumulator = 0,
    pointer = 1,
    run_lines = numeric(0),
    successfully_completed = FALSE
  )

  # For each instruction in the list, follow that instruction and move
  # to the next instruction as appropriate
  while(profile$pointer <= length(instructions)) {
    current_line <- profile$pointer
    result <- with(
      instructions[[profile$pointer]], 
      funs[[fun]](profile$accumulator, profile$pointer, arg)
    )

    # If we encounter a loop, return early with the profile
    if (profile$pointer %in% profile$run_lines) { return(profile) }

    # Update the profile
    profile$run_lines <- c(profile$run_lines, current_line)
    profile$accumulator <- result$accumulator
    profile$pointer <- result$pointer
  }

  # If the instructions run to completion, mark the profile as 
  # `successfully_completed`
  profile$successfully_completed <- TRUE
  profile
}

instructions <- parse_instructions(funs, test_input)
final_profile <- profile_instructions(instructions)
answer <- final_profile$accumulator

투명하게 보기 위해서 이것은 내가 두 번째 부분을 읽은 후에 얻은 profile_instructions() 함수이다.첫 번째 부분의 문제를 해결할 때, 나는 함수를 만났는데, 함수는 퇴출 전의 마지막 값accumulator만 되돌려 주었다.그러나 이것은 내가 시작해야 할 방식이다. profile 목록은 확실히 유용한 정보를 제공했고, 이것은 우리가 이 불쌍한 소년의 문제를 해결하는 데 필요한 모든 것을 제공했기 때문이다. (무슨 일이 발생하든지 간에 우리는 두 번째 부분에서 반드시 해야 한다.)

도표법

두 번째 부분의 결과(코드 방면)에 대해 약간 불만족스러우니, 나는 반드시 이 수수께끼의 답을 찾을 수 있는 더 깨끗한 방법이 있어야 한다고 생각한다.그래.또 다른 방법이 있지만, 나는 네가 그것이 깨끗한지 아닌지를 판단하도록 할 것이다.도면을 사용하여 명령 세트의 전체 경로를 나타낼 수 있습니다.한 걸음 한 걸음 누적기에 추가된 양을 그림의 가장자리에 분배함으로써 프로그램 순환점에 도달하기 전에 이 값을 검사할 수 있습니다.

library(igraph) # For all the graph-related functions 
library(magrittr) # For the %>% operator

instructions_to_graph <- function(instructions) {
  origins <- seq(length(instructions)) # Current instruction index
  names <- map_chr(instructions, ~ .x$name) # Instruction name
  vals <- map_int(instructions, ~ .x$arg) # Instruction value
  shifts <- ifelse(names == 'jmp', vals, 1) # Amount to move by after instruction
  acc <- ifelse(names == 'acc', vals, 0) # Amount to add to accumulator

  # Build a matrix where one column is the origins and the second column is the
  # represents the index of the next instruction in the sequence, determined
  # by the type and amount of the current instruction
  edge_matrix <- matrix(c(origins, origins + shifts), ncol = 2)

  # Make a graph! Converts the `edge_matrix` to a graph; assigns the 'name'
  # of the instruction to each vertex with a special name ('end') for the 
  # vertex representing the space after the last instruction, assigns
  # the 'shift' of each instruction to each vertex as a `$shift` attribute,
  # assigns the amount added to the accumulator for each instruction to 
  # each vertex as the '$acc' attribute
  graph_from_edgelist(edge_matrix) %>%
    set_vertex_attr('name', value = c(names, 'end')) %>% 
    set_vertex_attr('shift', value = c(shifts, 0)) %>% 
    set_vertex_attr('acc', value = c(acc, 0))
}

instructions <- parse_instructions(real_input)
instr_graph <- instructions_to_graph(instructions)
operation_path_vertices <- subcomponent(instr_graph, 1, mode = 'out')
answer <- sum(operation_path_vertices$acc)

subcomponent() 함수는 그림 하나, 시작 정점 1 하나와 mode를 취한다.'out'는 기본적으로 주어진 정점부터 바깥으로 이동하는 것을 가리킨다.이 매개변수를 사용하면 시작 정점에서 액세스할 수 있는 정점 목록을 반환합니다.그리고 우리는 이 경로 여행에서 수집한 $acc 값을 얻기 위해 되돌아오는 각 정점accumulator 분량의 값을 합친다.

두 번째 부분. - 저희가 해결할 수 있을까요?(네, 할 수 있어요!)

시뮬레이션 방법

우리는 우리가 여기서 끝날 것을 안다.왠지 모르게, 우리는 지령 하나만 파괴되었다는 것을 깨달았다.두 개의 손상된 지령을 복구하는 것이 훨씬 어려울 것 같아서 다행이다.시뮬레이션 방법에 대해 우리는 지령집의 운행 상황(제1부분의 상황처럼)을 분석하고 집행과 상반된 순서에 따라 집행하는 규칙을 반복하여 지령을'nop'에서'jmp'로 뒤집었다.매번 우리가 지령을 뒤집을 때마다, 우리는 이 지령들을 다시 분석하여, 이것이 문제를 해결했는지 아닌지를 볼 것이다.

# Main function, iterates backwards through the `run_lines` of the 
# input profile, flipping 'nop's and 'jmp's when we come to them, checking
# the result by profiling again. If the program runs successfully, return
# the winning profile list early.
adjust_instructions <- function(fail_profile, instructions) {
  for (line in rev(fail_profile$run_lines)) {
    test_instructions <- instructions # Copy the instructions before modifying
    current_fun <- instructions[[line]]$fun # Get the instruction type

    # Flip 'jmp's to 'nop's, and vice versa
    if (current_fun == 'jmp') {
      test_instructions[[line]]$fun <- 'nop'
    } 
    if (current_fun == 'nop') {
      test_instructions[[line]]$fun <- 'jmp'
    }

    new_profile <- profile_instructions(test_instructions) # Test the change
    if (new_profile$successfully_completed) { 
      print(paste0('It was ', line, '!')) # Yells about the line that was fixed
      return(new_profile) 
    }
  }

  new_profile
}

instructions <- parse_instructions(funs, real_input)
fail_profile <- profile_instructions(instructions)
new_profile <- adjust_instructions(fail_profile, instructions)
answer <- new_profile$accumulator

print() 명령은 전혀 필요하지 않지만, 어떤 명령이 이 모든 문제를 초래했는지 알고 싶습니다.

도표법

두 번째 부분의 도형 방법은 훨씬 복잡할 것 같지만 이것은 문제의 복잡성이 아니라 igraph에 대한 나의 익숙하지 않은 것과 관련이 있을 수 있다.실제로 개념의 측면에서 볼 때 최종 논리는 상당히 간단하다.시뮬레이션 방법과 달리 우리는 실제적으로'jmp'지령을'뒤집기'를'nop'지령으로 하지 않았고 반대로도 마찬가지이다.반대로, 우리는 단지 'jmp' 와 'nop' 정점에 하나의 변을 추가하여, 그것들이 동시에 'jmp' 와 'nop' 정점을 충당하도록 할 뿐이다.잘 됐다!만약 우리가 정말로 기존의 가장자리를 삭제하고 싶다면, 우리는 삭제할 수 있지만, 이런 상황에서는 필요없다.

# Helper function, adds edges from 'jmp' vertices as if they were 'nop'
# vertices and adds edges to 'nop' vertices as if they were 'jmp' vertices
flip_instruction <- function(i, instr_graph) {
  v <- V(instr_graph)[[i]]
  if (v$name == 'jmp') {  
    # Add an edge connecting to the next vertex in sequence
    mod_graph <- add_edges(instr_graph, c(i, i+1))
  }
  if (v$name == 'nop') {
    # Add an edge connection to the next vertex based on `shift` value
    mod_graph <- add_edges(instr_graph, c(i, i + v$shift))
  }
  mod_graph
}

get_path_to_end <- function(instr_graph) {
  # Get the vertex indices for the longest path starting at index 1,
  # AKA the indexes for all the vertices that can be reached from the
  # starting point
  steps <- subcomponent(instr_graph, 1, mode = 'out') # Reachable vertices

  for (i in rev(steps)) { # Stepping backwards
    if (instructions[[i]]$name %in% c('jmp', 'nop')) {
      # Flip the instruction at index `i` then check to see if there is a
      # `path` from the first vertex to the 'end' vertex. If there is, 
      # return the list of vertices in that path.
      test_graph <- flip_instruction(i, instr_graph)
      path <- all_simple_paths(test_graph, 1, 'end', mode = 'out')
      if (length(path) > 0) { return(path[[1]]) }
    }
  }
}

instructions <- parse_instructions(real_input)
instr_graph <- instructions_to_graph(instructions)
path_to_end <- get_path_to_end(instr_graph)
answer2 <- sum(path_to_end$acc)

기본적으로 all_simple_paths()는 두 벡터 사이의 모든 가능한 직접 경로를 되돌려줍니다. 그러나 검사 사이의 한 변만 바꾸기 때문에 여러 경로를 얻지 말아야 합니다.그리고 문제는 우리에게 이것이 가능하다는 것을 알려주기 때문에...

마무리

옛일을 회상하기 위해서, 이 수수께끼는 다른 것이 없다면, 매우 재미있다.그리고 도표!시뮬레이션 방법을 끝낸 후에 나는 결코 완전히 만족하지 않았고, 반드시 더욱 우아한 방법으로 이 문제를 해결해야 한다고 느꼈다.나는 도형 방법 자체가 더 우아한지 모르겠지만, 이것은 매우 재미있다.그리고 많이 배웠어요igraph.이기다주: 두 번째 부분의 도형 방법은 모든'jmp'와'nop'정점을'뒤집기'하고 모든 경로를 계산한 다음에 가장 짧은 경로를 선택할 수 있습니다.가능하다, ~할 수 있다,...그것은 테스트 입력에 확실히 효과가 있지만, 진정한 입력으로 시도하는 것은 나의 노트북 컴퓨터에 있어서 너무 처리하기 어렵다.너의 이정은 다를 수 있다.
만약 당신이 다른 해결 방안을 발견하거나 (또는 나의 잘못을 발견한다면) 나에게 편지를 쓰세요!