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

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)

# 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

# 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)