Day 7: Some Assembly Required

This solution is strongly inspired from here.

library(tidyverse)

input <- read_lines(file = "inputs/2015/07.txt")

Bitwise Conversion

To convent a number into binary we can use the function base::intToBits().

Example

map(0:4, intToBits)
## [[1]]
##  [1] 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
## [26] 00 00 00 00 00 00 00
## 
## [[2]]
##  [1] 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
## [26] 00 00 00 00 00 00 00
## 
## [[3]]
##  [1] 00 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
## [26] 00 00 00 00 00 00 00
## 
## [[4]]
##  [1] 01 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
## [26] 00 00 00 00 00 00 00
## 
## [[5]]
##  [1] 00 00 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
## [26] 00 00 00 00 00 00 00

Since we are considering a 16-bit signal (a number from 0 to 65535), we can consider just the first 16 elements of the output vector of the output.

int_to_bit16_01 <- function(x) {
    intToBits(x)[1:16]
}

Example

map(0:4, int_to_bit16_01)
## [[1]]
##  [1] 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
## 
## [[2]]
##  [1] 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
## 
## [[3]]
##  [1] 00 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00
## 
## [[4]]
##  [1] 01 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00
## 
## [[5]]
##  [1] 00 00 01 00 00 00 00 00 00 00 00 00 00 00 00 00

Since we are going to perform bitwise operations, it is convenient to convert the output to logical type.

int_to_bit16 <- function(x) {
    intToBits(x)[1:16] |> 
        as.logical()
}

Example

map(0:4, int_to_bit16)
## [[1]]
##  [1] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
## [13] FALSE FALSE FALSE FALSE
## 
## [[2]]
##  [1]  TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
## [13] FALSE FALSE FALSE FALSE
## 
## [[3]]
##  [1] FALSE  TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
## [13] FALSE FALSE FALSE FALSE
## 
## [[4]]
##  [1]  TRUE  TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
## [13] FALSE FALSE FALSE FALSE
## 
## [[5]]
##  [1] FALSE FALSE  TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
## [13] FALSE FALSE FALSE FALSE

Finally the inverse function is defined.

bit16_to_int <- function(x) {
    sum(2^(0:15) * x)
}

Example

example <- map(0:4, int_to_bit16)

map(example, bit16_to_int)
## [[1]]
## [1] 0
## 
## [[2]]
## [1] 1
## 
## [[3]]
## [1] 2
## 
## [[4]]
## [1] 3
## 
## [[5]]
## [1] 4

Bitwise Operations

Custom R Binary Operations

In R a binary operation can be defined using % at the start and the end of its name. For example:

`%XOR%` <- function(x, y) (x & !y) | (!x & y)

FALSE %XOR% FALSE
## [1] FALSE
FALSE %XOR% TRUE
## [1] TRUE
TRUE %XOR% FALSE
## [1] TRUE
TRUE %XOR% TRUE
## [1] FALSE

map2(.x = c(FALSE, FALSE, TRUE, TRUE),
     .y = c(FALSE, TRUE, FALSE, TRUE), 
     .f = `%XOR%`)
## [[1]]
## [1] FALSE
## 
## [[2]]
## [1] TRUE
## 
## [[3]]
## [1] TRUE
## 
## [[4]]
## [1] FALSE

(all_zeros <- int_to_bit16(0))
##  [1] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
## [13] FALSE FALSE FALSE FALSE
(one <- int_to_bit16(1))
##  [1]  TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
## [13] FALSE FALSE FALSE FALSE
(zero_one <- int_to_bit16(43690))
##  [1] FALSE  TRUE FALSE  TRUE FALSE  TRUE FALSE  TRUE FALSE  TRUE FALSE  TRUE
## [13] FALSE  TRUE FALSE  TRUE
(one_zero <- int_to_bit16(21845))
##  [1]  TRUE FALSE  TRUE FALSE  TRUE FALSE  TRUE FALSE  TRUE FALSE  TRUE FALSE
## [13]  TRUE FALSE  TRUE FALSE
(all_ones <- int_to_bit16(65535))
##  [1] TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE TRUE
## [16] TRUE

`%AND%` <- function(x, y) {
    bit16_result <- int_to_bit16(x) & int_to_bit16(y)
    bit16_to_int(bit16_result)
}

Example

zero_one %AND% one_zero
## [1] 0

`%OR%` <- function(x, y) {
    bit16_result <- int_to_bit16(x) | int_to_bit16(y)
    bit16_to_int(bit16_result)
}

Example

zero_one %OR% one_zero
## [1] 1

`%NOT%` <- function(dummy, x) {
    bit16_result <- !int_to_bit16(x)
    bit16_to_int(bit16_result)
}

Example

zero_one %NOT% zero_one
## [1] 65535
zero_one %NOT% one_zero
## [1] 65534

`%RSHIFT%` <- function(x, y) {
    bit16_result <- c(int_to_bit16(x)[seq(y + 1, 16)], rep(FALSE, y))
    bit16_to_int(bit16_result)
}

Example

int_to_bit16(65300)
##  [1] FALSE FALSE  TRUE FALSE  TRUE FALSE FALSE FALSE  TRUE  TRUE  TRUE  TRUE
## [13]  TRUE  TRUE  TRUE  TRUE
65300 %RSHIFT% 2
## [1] 16325
int_to_bit16(16325)
##  [1]  TRUE FALSE  TRUE FALSE FALSE FALSE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE
## [13]  TRUE  TRUE FALSE FALSE

`%LSHIFT%` <- function(x, y) {
    bit16_result <- c(rep(FALSE, y), int_to_bit16(x)[seq(1, 16 - y)])
    bit16_to_int(bit16_result)
}

Example

int_to_bit16(65300)
##  [1] FALSE FALSE  TRUE FALSE  TRUE FALSE FALSE FALSE  TRUE  TRUE  TRUE  TRUE
## [13]  TRUE  TRUE  TRUE  TRUE
65300 %LSHIFT% 2
## [1] 64592
int_to_bit16(64592)
##  [1] FALSE FALSE FALSE FALSE  TRUE FALSE  TRUE FALSE FALSE FALSE  TRUE  TRUE
## [13]  TRUE  TRUE  TRUE  TRUE

Part One

# input <- c(
#     "123 -> x",
#     "456 -> y",
#     "x AND y -> d",
#     "x OR y -> e",
#     "x LSHIFT 2 -> f",
#     "y RSHIFT 2 -> g",
#     "NOT x -> h",
#     "NOT y -> i"
# )

instructions <- tibble(original = input) |> 
    separate_wider_delim(cols = original,
                         delim = " -> ",
                         names = c("lhs", "rhs"),
                         cols_remove = FALSE) |> 
    mutate(
        lhs = str_replace_all(lhs, c(
            "AND"    = "%AND%",
            "OR"     = "%OR%",
            "NOT"    = "1 %NOT%",
            "RSHIFT" = "%RSHIFT%",
            "LSHIFT" = "%LSHIFT%"
        )),
    )

lhs <- instructions |> pull(lhs)
rhs <- instructions |> pull(rhs)

repeat{
    # find where we have JUST numbers
    numbers_ind <- which(str_detect(lhs, "^[0-9]*$"))
    
    if (length(numbers_ind) == length(lhs)) break
    
    # create named vector (of regex) for replacement
    # everyname must have (?<=^| ) before so either the name
    # is a the beginning of the string or is following a space,
    # and (?=$| ) at the end so either the name is at the end
    # of the string or is followed by a space
    #
    # this is because some names are made or more than one letter
    # and we don't want to "partially" replace a name 
    replacement <- str_extract(lhs[numbers_ind], "[0-9]+")
    names(replacement) <- paste0("(?<=^| )", rhs[numbers_ind], "(?=$| )")
    
    # replace values
    lhs <- lhs %>%
        str_replace_all(replacement)
    
    # evaluate instructions that can be evaluated
    # these can be found where there are no lower case letters
    # (operators use UPPERCASE LETTERS on purpose!)
    lhs[!str_detect(lhs, "[a-z]+")] <-
        map_chr(lhs[!str_detect(lhs, "[a-z]+")],
                ~as.character(eval(parse(text = .))))
}

a <- lhs[rhs == "a"]
cat(a)
## 956

Part Two

# take the signal you got on wire a, override wire b to that signal
instructions <- instructions |> 
    mutate(lhs = if_else(rhs == "b", a, lhs))

lhs <- instructions |> pull(lhs)
rhs <- instructions |> pull(rhs)

repeat{
    # find where we have JUST numbers
    numbers_ind <- which(str_detect(lhs, "^[0-9]*$"))
    
    if (length(numbers_ind) == length(lhs)) break
    
    # create named vector (of regex) for replacement
    # everyname must have (?<=^| ) before so either the name
    # is a the beginning of the string or is following a space,
    # and (?=$| ) at the end so either the name is at the end
    # of the string or is followed by a space
    #
    # this is because some names are made or more than one letter
    # and we don't want to "partially" replace a name 
    replacement <- str_extract(lhs[numbers_ind], "[0-9]+")
    names(replacement) <- paste0("(?<=^| )", rhs[numbers_ind], "(?=$| )")
    
    # replace values
    lhs <- lhs %>%
        str_replace_all(replacement)
    
    # evaluate instructions that can be evaluated
    # these can be found where there are no lower case letters
    # (operators use UPPERCASE LETTERS on purpose!)
    lhs[!str_detect(lhs, "[a-z]+")] <-
        map_chr(lhs[!str_detect(lhs, "[a-z]+")],
                ~as.character(eval(parse(text = .))))
}

a <- lhs[rhs == "a"]
cat(a)
## 40149