adventofcode17: Advent of Code 2017

#' Day 10: Knot Hash
#'
#' [Knot Hash](http://adventofcode.com/2017/day/10)
#'
#' @name day10
#' @rdname day10
#' @details
#'
#' **Part One**
#'
#' You come across some programs that are trying to implement a software
#' emulation of a hash based on knot-tying. The hash these programs are
#' implementing isn't very strong, but you decide to help them anyway. You
#' make a mental note to remind the Elves later not to invent their own
#' cryptographic functions.
#'
#' This hash function simulates tying a knot in a circle of string with 256
#' marks on it. Based on the input to be hashed, the function repeatedly
#' selects a span of string, brings the ends together, and gives the span a
#' half-twist to reverse the order of the marks within it. After doing this
#' many times, the order of the marks is used to build the resulting hash.
#'
#'       4--5   pinch   4  5           4   1
#'      /    \  5,0,1  / \/ \  twist  / \ / \
#'     3      0  -->  3      0  -->  3   X   0
#'      \    /         \ /\ /         \ / \ /
#'       2--1           2  1           2   5
#'
#' To achieve this, begin with a *list* of numbers from `0` to `255`, a
#' *current position* which begins at `0` (the first element in the list),
#' a *skip size* (which starts at `0`), and a sequence of *lengths* (your
#' puzzle input). Then, for each length:
#'
#' -   *Reverse* the order of that *length* of elements in the *list*,
#'     starting with the element at the *current position*.
#' -   *Move* the *current position* forward by that *length* plus the
#'     *skip size*.
#' -   *Increase* the *skip size* by one.
#'
#' The *list* is circular; if the *current position* and the *length* try
#' to reverse elements beyond the end of the list, the operation reverses
#' using as many extra elements as it needs from the front of the list. If
#' the *current position* moves past the end of the list, it wraps around
#' to the front. *Lengths* larger than the size of the *list* are invalid.
#'
#' Here's an example using a smaller list:
#'
#' Suppose we instead only had a circular list containing five elements,
#' `0, 1, 2, 3, 4`, and were given input lengths of `3, 4, 1, 5`.
#'
#' -   The list begins as `[0] 1 2 3 4` (where square brackets indicate the
#'     *current position*).
#' -   The first length, `3`, selects `([0] 1 2) 3 4` (where parentheses
#'     indicate the sublist to be reversed).
#' -   After reversing that section (`0 1 2` into `2 1 0`), we get
#'     `([2] 1 0) 3 4`.
#' -   Then, the *current position* moves forward by the *length*, `3`,
#'     plus the *skip size*, 0: `2 1 0 [3] 4`. Finally, the *skip size*
#'     increases to `1`.
#' -   The second length, `4`, selects a section which wraps:
#'     `2 1) 0 ([3] 4`.
#' -   The sublist `3 4 2 1` is reversed to form `1 2 4 3`:
#'     `4 3) 0 ([1] 2`.
#' -   The *current position* moves forward by the *length* plus the *skip
#'     size*, a total of `5`, causing it not to move because it wraps
#'     around: `4 3 0 [1] 2`. The *skip size* increases to `2`.
#' -   The third length, `1`, selects a sublist of a single element, and so
#'     reversing it has no effect.
#' -   The *current position* moves forward by the *length* (`1`) plus the
#'     *skip size* (`2`): `4 [3] 0 1 2`. The *skip size* increases to `3`.
#' -   The fourth length, `5`, selects every element starting with the
#'     second: `4) ([3] 0 1 2`. Reversing this sublist (`3 0 1 2 4` into
#'     `4 2 1 0 3`) produces: `3) ([4] 2 1 0`.
#' -   Finally, the *current position* moves forward by `8`: `3 4 2 1 [0]`.
#'     The *skip size* increases to `4`.
#'
#' In this example, the first two numbers in the list end up being `3` and
#' `4`; to check the process, you can multiply them together to produce
#' `12`.
#'
#' However, you should instead use the standard list size of `256` (with
#' values `0` to `255`) and the sequence of *lengths* in your puzzle input.
#' Once this process is complete, *what is the result of multiplying the
#' first two numbers in the list*?
#'
#' **Part Two**
#'
#' The logic you've constructed forms a single *round* of the *Knot Hash*
#' algorithm; running the full thing requires many of these rounds. Some
#' input and output processing is also required.
#'
#' First, from now on, your input should be taken not as a list of numbers,
#' but as a string of bytes instead. Unless otherwise specified, convert
#' characters to bytes using their [ASCII
#' codes](https://en.wikipedia.org/wiki/ASCII#Printable_characters). This
#' will allow you to handle arbitrary ASCII strings, and it also ensures
#' that your input lengths are never larger than `255`. For example, if you
#' are given `1,2,3`, you should convert it to the ASCII codes for each
#' character: `49,44,50,44,51`.
#'
#' Once you have determined the sequence of lengths to use, add the
#' following lengths to the end of the sequence: `17, 31, 73, 47, 23`. For
#' example, if you are given `1,2,3`, your final sequence of lengths should
#' be `49,44,50,44,51,17,31,73,47,23` (the ASCII codes from the input
#' string combined with the standard length suffix values).
#'
#' Second, instead of merely running one *round* like you did above, run a
#' total of `64` rounds, using the same *length* sequence in each round.
#' The *current position* and *skip size* should be preserved between
#' rounds. For example, if the previous example was your first round, you
#' would start your second round with the same *length* sequence
#' (`3, 4, 1, 5, 17, 31, 73, 47, 23`, now assuming they came from ASCII
#' codes and include the suffix), but start with the previous round's
#' *current position* (`4`) and *skip size* (`4`).
#'
#' Once the rounds are complete, you will be left with the numbers from `0`
#' to `255` in some order, called the *sparse hash*. Your next task is to
#' reduce these to a list of only `16` numbers called the *dense hash*. To
#' do this, use numeric bitwise
#' [XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) to combine
#' each consecutive block of `16` numbers in the sparse hash (there are
#' `16` such blocks in a list of `256` numbers). So, the first element in
#' the dense hash is the first sixteen elements of the sparse hash XOR'd
#' together, the second element in the dense hash is the second sixteen
#' elements of the sparse hash XOR'd together, etc.
#'
#' For example, if the first sixteen elements of your sparse hash are as
#' shown below, and the XOR operator is `^`, you would calculate the first
#' output number like this:
#'
#'     65 ^ 27 ^ 9 ^ 1 ^ 4 ^ 3 ^ 40 ^ 50 ^ 91 ^ 7 ^ 6 ^ 0 ^ 2 ^ 5 ^ 68 ^ 22 = 64
#'
#' Perform this operation on each of the sixteen blocks of sixteen numbers
#' in your sparse hash to determine the sixteen numbers in your dense hash.
#'
#' Finally, the standard way to represent a Knot Hash is as a single
#' [hexadecimal](https://en.wikipedia.org/wiki/Hexadecimal) string; the
#' final output is the dense hash in hexadecimal notation. Because each
#' number in your dense hash will be between `0` and `255` (inclusive),
#' always represent each number as two hexadecimal digits (including a
#' leading zero as necessary). So, if your first three numbers are
#' `64, 7, 255`, they correspond to the hexadecimal numbers `40, 07, ff`,
#' and so the first six characters of the hash would be `4007ff`. Because
#' every Knot Hash is sixteen such numbers, the hexadecimal representation
#' is always `32` hexadecimal digits (`0`-`f`) long.
#'
#' Here are some example hashes:
#'
#' -   The empty string becomes `a2582a3a0e66e6e86e3812dcb672a272`.
#' -   `AoC 2017` becomes `33efeb34ea91902bb2f59c9920caa6cd`.
#' -   `1,2,3` becomes `3efbe78a8d82f29979031a4aa0b16a9d`.
#' -   `1,2,4` becomes `63960835bcdc130f0b66d7ff4f6a5a8e`.
#'
#' Treating your puzzle input as a string of ASCII characters, *what is the
#' Knot Hash of your puzzle input?* Ignore any leading or trailing
#' whitespace you might encounter.
#'
#' @export
#' @param args a list of arguments to control the twisting
#' @param seed a value to hash
#' @examples
#' args <- list(
#'   items = 0:4,
#'   step = 0,
#'   current_position = 1,
#'   lengths = c(3, 4, 1, 5))
#' twist_knot(args)
#' knot_hash("test")
twist_knot <- function(args) {
  while (length(args$lengths) > 0) {
    args <- do_call_twist_a_knot(args)
  }
  args
}

# Takes a list
do_call_twist_a_knot <- function(args) {
  do.call(twist_a_knot, args)
}

# Takes several arguments
twist_a_knot <- function(items, lengths, current_position, step, ...) {
  current_length <- lengths[1]

  rev_items <- function(xs, position, length) {
    positions <- seq(from = position, length = length) %>%
      wrap_around(length(xs))
    xs[positions] <- rev(xs[positions])
    xs
  }

  items <- rev_items(items, current_position, current_length)

  current_position <- wrap_around(
    current_position + step + current_length,
    length(items))

  list(
    items = items,
    lengths = lengths[-1],
    current_position = current_position,
    step = step + 1,
    pos_change = step + current_length
  )
}

#' @rdname day10
#' @export
knot_hash <- function(seed) {
  lengths <- create_day10_lengths(seed)
  args <- list(
    items = 0:255,
    lengths = lengths,
    current_position = 1,
    step = 0)

  i <- 0
  while (i < 64) {
    args <- twist_knot(args)
    args$lengths <- lengths
    i <- i + 1
  }

  args$items %>%
    split(rep(1:16, 16) %>% sort()) %>%
    lapply(., reduce_bitwise_xor) %>%
    unlist() %>%
    sprintf("%.02x", .) %>%
    paste0(collapse = "")
}

reduce_bitwise_xor <- function(xs) {
  Reduce(bitwXor, xs)
}

create_day10_lengths <- function(string) {
  add_noise <- function(x) {
    c(x, 17, 31, 73, 47, 23)
  }
  string %>% charToRaw() %>% as.integer() %>% add_noise()
}