20: Infinite Elves and Infinite Houses

library(mistlecode)

To install `mistlecode` yourself, run `devtools::install_github('guslipkin/mistlecode')`.

 Also loading:  cipheR data.table dplyr purrr slider stringr tidyverse glue

library(Rcpp)
library(RcppArmadillo)

Part 1

There’s something I can do with prime factorization, I just can’t figure it out. Ugh. Took me a fat minute but I was able to work with my idea about how if you divide a number x by 1:x then round down, you get the total number of times each elf would have stopped at a house before x. Just had to get that set up right and we’re good to go. Not the fastest, but it works. Maybe another chance for Rcpp if I’m up for it later.

Spoiler alert. I wasn’t happy with the plain R version and re-wrote it in Rcpp. At this point I’ve been through so many versions, I think my working R solution is lost…

Double spoiler… I did it again, but way better this time.

R (Best)

target <- 36e6
i <- 0
repeat {
  i <- i + 1
  n <- sum(RcppBigIntAlgos::divisorsBig(i))
  if (n >= target / 10) break
}
i

[1] 831600

Rcpp

cppFunction('
IntegerVector part1(int target, int total_l) {
  IntegerVector m_vec, sum_vec(total_l, 0.0), v;
  IntegerMatrix m_mat;
  int idx = 0;
  while (idx <= total_l) {
    idx++;
    if (idx % 1000 == 0) { std::cout << "\\r" << idx; }
    v = rep_len(IntegerVector::create(idx), total_l / idx);
    m_mat = IntegerMatrix(idx, v.size());
    m_mat(idx - 1, _) = v * 10;
    m_vec = IntegerVector(m_mat);
    m_vec.attr("dim") = R_NilValue;
    m_vec = rep_len(m_vec, total_l);
    sum_vec = sum_vec + m_vec;
    for (int i = 0; i < sum_vec.size(); i++) {
      if (i <= idx & sum_vec[i] >= target) {
        if (idx > 1000) { std::cout.clear(); }
        return IntegerVector::create(i) + 1;
      }
    }
  }
  if (idx > 1000) { std::cout.clear(); }
  return sum_vec;
}
')
part1(36e6, 1e6)

R

target <- 36e6 / 10
idx <- 1
s <- 0
d <- seq_len(target)
denominator <- d
repeat {
  denominator <- d[seq_len(idx)]
  s <- sum(denominator[idx %% denominator == 0])
  if (s < target) idx <- idx + 1 else break
}
idx

Part 2

Finally. Remembering the logic for the last fifty divisors took longer than it should’ve. At least it’s over now…

target <- 36e6
i <- 0
repeat {
  i <- i + 1
  d <- 
    i |>
    RcppBigIntAlgos::divisorsBig() |>
    as.integer()
  n <- sum(d[i %/% d <= 50] * 11)
  if (n >= target) break
}
i

[1] 884520