R/solutions.R

In mrkaye97/euleR: Tidy solutions to Euler problems

#' Problem 1
#'
#' If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
#' Find the sum of all the multiples of 3 or 5 below 1000.
#' @return the sum
#' @export
problem_1 <- function() {
  multiples_sum(numbers = c(3,5), max_value = 1000)
}

#' Problem 2
#'
#' Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
#' 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
#' By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
#'
#' @return the sum
#' @importFrom purrr map discard
#' @export
problem_2 <- function() {
  1:50 %>%
    map(fibs, 1, 2) %>%
    discard(function(x) x > 4 * 10 ** 6) %>%
    discard(function(x) x %% 2 != 0) %>%
    as.numeric() %>%
    sum()
}

#' Problem 3
#'
#' The prime factors of 13195 are 5, 7, 13 and 29.
#' What is the largest prime factor of the number 600851475143 ?
#' @return the largest prime factor
#' @importFrom numbers primeFactors
#' @importFrom purrr pluck
#' @export
problem_3 <- function() {
  primeFactors(600851475143) %>%
    pluck(max)
}

#' Problem 22
#'
#' Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.
#' For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714.
#' What is the total of all the name scores in the file?
#' @return the total name score
#' @importFrom readr read_lines
#' @importFrom magrittr %>%
#' @importFrom purrr flatten map imap_dbl pluck
#' @importFrom stringr str_extract_all str_split
#' @export
problem_22 <- function() {
  all_names <- (
    read_lines('https://projecteuler.net/project/resources/p022_names.txt') %>%
      str_split(',')
  ) %>%
    pluck(1) %>%
    sort()

  all_names %>%
    map(str_extract_all, "[A-Z]") %>%
    flatten() %>%
    map(get_word_values) %>%
    imap_dbl(~ .y * .x) %>%
    sum()
}

#' Problem 28
#'
#' Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:
#'
#' 21 22 23 24 25
#' 20  7  8  9 10
#' 19  6  1  2  3
#' 18  5  4  3 12
#' 17 16 15 14 13

#' It can be verified that the sum of the numbers on the diagonals is 101.
#' What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed the same way?
#' @return the sum of the numbers on the diagonals
#' @importFrom purrr discard map_dbl
#' @importFrom magrittr %>%
#' @export
problem_28 <- function() {
  N <- 1001
  (N * (N * (4 * N + 3) + 8) - 9) / 6
}

#' Problem 35
#'
#' The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.
#' There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
#' How many circular primes are there below one million?
#' @return the number of circular primes
#' @param workers the number of workers to use for parallel computing
#' @importFrom purrr map_lgl
#' @importFrom numbers Primes
#' @importFrom future plan multisession
#' @importFrom furrr future_map_lgl
#' @export
problem_35 <- function(workers = 8) {
  primes_below_1m <- Primes(1000000)

  plan(multisession, workers = workers)
  results <- future_map_lgl(
    primes_below_1m,
    function(x) x %>%
      get_all_circular_permutations() %>%
      map_lgl(isPrime) %>%
      all()
    )

  results %>%
    sum()
}

#' Problem 42
#'
#' The nth term of the sequence of triangle numbers is given by, tn = ½n(n+1); so the first ten triangle numbers are:
#' 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
#' By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value is a triangle number then we shall call the word a triangle word.
#'
#' Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?
#'
#' @importFrom readr read_lines
#' @importFrom purrr map flatten detect_index
#' @importFrom stringr str_split str_extract_all
#' @return the number of triangle words
#' @export
problem_42 <- function() {
  words <- read_lines('https://projecteuler.net/project/resources/p042_words.txt') %>%
    str_split(',') %>%
    map(str_extract_all, "[A-Z]") %>%
    flatten() %>%
    map(get_word_values) %>%
    unlist()

  max_triangle_to_test <- max(words)
  max_triangle_to_consider <- 1:1000 %>%
    detect_index(triangle_greater_than_max, max_triangle_to_test)

  triangles <- get_triangle_numbers(max_triangle_to_consider)

  words %in% triangles %>%
    sum()
}

#' Problem 84
#'
#' @importFrom tibble enframe
#' @param num_sims The number of simulations to run
#' @param num_die_sides the number of sides of the monopoly dice
#' @return the requested string
#' @export
problem_84 <- function(num_sims = 10000, num_die_sides = 4) {
  state <- list()
  chance <- init_chance()
  cc <- init_community_chest()

  state[[1]] <- list(
    current_square = 0,
    chance_deck = chance,
    cc_deck = cc
  )

  for (turn in 2:num_sims) {
    state[[turn]] <- play_turn(
      current_square = state[[turn - 1]]$current_square,
      chance_deck = state[[turn - 1]]$chance_deck,
      cc_deck = state[[turn - 1]]$cc_deck,
      num_die_sides = num_die_sides
    )
  }

  state %>%
    map(
      pluck, "current_square"
    ) %>%
    unlist() %>%
    table() %>%
    prop.table() %>%
    enframe(
      name = "square",
      value = "prop"
    ) %>%
    slice_max(.data$prop, n = 3) %>%
    pull(.data$square) %>%
    paste(collapse = "")
}

#' A solution to 84 by approximating the transition matrix and directly solving from it
#'
#' @importFrom MASS ginv
#' @importFrom purrr map rerun
#' @importFrom tidyr pivot_wider replace_na
#' @return the three most common squares
#' @export
problem_84_roughly_exact <- function() {

  sorted_colnames <- as.character(0:39)

  P <- 0:39 %>%
    map(
      ~ rerun(
        500,
        play_turn(
          .x,
          cc_deck = init_community_chest(),
          chance_deck = init_chance()
        )
      ) %>%
        map(
         ~ .x %>%
           pluck("current_square")
        )
    ) %>%
    map(
      ~ .x %>%
        unlist() %>%
        table() %>%
        prop.table() %>%
        enframe() %>%
        pivot_wider(
          names_from = name,
          values_from = value
        )
    ) %>%
    bind_rows() %>%
    mutate(
      across(everything(), ~ .x %>% as.numeric() %>% replace_na(0))
    ) %>%
    mutate(
      `30` = 0
    ) %>%
    select(all_of(sorted_colnames)) %>%
    as.matrix()

  eigs <- eigen(P)

  right_eig_vecs <- eigs$vectors
  left_eig_vecs <- ginv(right_eig_vecs)

  pi_eig <- Re(left_eig_vecs[1,] / sum(left_eig_vecs[1,]))

  tibble(
    square = 0:39,
    prob = pi_eig
  ) %>%
    slice_max(.data$prob, n = 3) %>%
    pull(.data$square) %>%
    paste(collapse = "")
}